ترکیبیات، الگوریتم و علوم کامپیوتر

علوم رایانه، علمی است پیرامون الگوریتم و در ارتباط زیاد با ریاضیات و مهندسی کامپیوتر می باشد

ترکیبیات، الگوریتم و علوم کامپیوتر

علوم رایانه، علمی است پیرامون الگوریتم و در ارتباط زیاد با ریاضیات و مهندسی کامپیوتر می باشد

این وبلاگ برای توزیع منابعی که سال هاست با آن ها در ارتباط هستم راه اندازی شده است تا همه بتونن از دنیای زیبای ترکیبیات و الگوریتم لذت ببرن.
ممکن است که مباحث مطرح شده در این وبلاگ در سطوح مختلفی باشد از مباحث در حد مبتدی تا سطوح پیشرفته فلذا؛ توصیه من برای دانش آموزان راهنمایی استفاده از برچست مبتدی، برای دانش آموزان دبیرستانی استفاده از برچسب متوسط و برای دانش جویان کارشناسی استفاده از برچسب پیشرفته و برای دانش جویان کارشناسی ارشد استفاده از برچسب تحقیقاتی را می باشد.
جای بجث و ارائه مرجع های مختلف باز است و بنده از نظرات و بحث های شما خوشحال خواهم شد.
انتشار مطالب این وبلاگ به هیچ عنوان مانعی ندارد.
والسلام علی من اتبع الهدی

۵ مطلب در فروردين ۱۳۹۲ ثبت شده است

معمای هوشی

۳۱
فروردين

در یک اتاق تاریک 3 (سه) کلاه قرمز و 2 (دو) کلاه آبی قرار داده ایم. 2 (دو) نفر بینا و 1 (یک) نفر نابینا وارد اتاق می شوند و هر کدام یک کلاه را بر سر می گذارند و از اتاق خارج می شوند. چون اتاق تاریک بوده است دو نفر بینا نیز مانند فرد نابینا قادر به تشخیص رنگ کلاه خود نیستند. بیرون از اتاق هر یک فقط به کلاه دیگران نگاه می کنند و درباره رنگ کلاه روی سر خودشان قضاوت می کنند ...

بینای اول: من نمی دانم که کلاهم چه رنگی است.

بینای دوم: من هم نمی دانم که کلاهم چه رنگی است.

نابینا: من می دانم که کلاهم چه رنگی است !!

سوال: چطور دو نفر بینا نتوانستند رنگ کلاه روی سر خود را تشخیص دهند ولی فرد نابینا متوجه رنگ کلاه خود شد؟!


جالب است که بدانید این سوال (با صورتی مشابه) در کتاب منطق شهید مطهری هم آمده است!


  • نوید ادهم

اصل اکسترمال 2

۲۸
فروردين

ریاضی دان ورزیده مجهز به یک سری اصول و فنون با دامنه کاربرد وسیع وساده می باشد که می تواند از آنها در حالت های مختلف استفاده نمایید. این اصول و فنون وابسته به موضوعی ویژه نبوده و در کلیه شاخه های ریاضی قابلیت استفاده را دارند. ریاضی دان به این اصول فکر نمی کند بلکه به طور ناخودآگاه از آن مطلع می باشد


 به اصل های زیر دقت کنید:


الف.هر زیر مجموعه محدود  از اعداد صحیح یا حقیقی دارای یک عنصر مینیمم و یک عنصر ماکسیمم است . (اصل اکسترمال)
ب.هر زیرمجموعه غیر تهی از اعداد صحیح مثبت دارای کوچک ترین عضو است. این را « اصل خوش ترتیبی» می نامند . (حالت کلی تر اصل اکسترمال)
ج.مجموعه نامحدود از اعداد حقیقی ضرورتاً دارای عضو ماکسیمال یا مینیمال نیست. اگر از بالا کران دار باشد، آنگاه دارای کوچک ترین کران بالاست که آن را سوپریمم می نامیم. اگر از پایین کران دار باشد دارای بزرگترین کران پایین است و آن را اینفیمم می نامیم. (کلی تر از اصل خوش ترتیبی)
و هم چنین  اگر SUPA \in A باشد آنگاه SUP(A) = max Aو اگر inf A\in A آنگاه inf(A) = min A.



در استفاده از اکسترمال سعی می کنیم وجود یک حالت را به اثبات برسانیم. اصل اکسترمال به ما می گوید که با انتخاب این حالت سعی کنید برخی حالت های ماکزیمم و مینیمم آن را بررسی کنید. حالت حاصل نشان دهنده تقریبی وضعیت خواسته شده است هر چند کاملاً با آن منطبق نمی نماید ولی با کمی تغییر روی توابع به حالت اصلی می توان رسید. اگر راه های مختلفی برای بهینه سازی وجود داشته باشد انتخاب یکی از آنها بسته به نظر ما می باشد. اصل اکسترمال بسیار خلاق است و می تواند الگوریتم روش ساختن آن حالت را به ما نشان دهد



چند مسئله:


مثال ۱ : ‏الف. خط حداکثر یک صفحه را به چند بخش تقسیم می کند؟ 

ب. با  صفحه در حالت کلی فضا به چند بخش تقسیم می گردد

مثال 2: ادامه بخش ب: فرض کنیم  نشان دهید در بین  بخش از فضا حداقل  چهاروجهی وجود دارد (). 


مثال 3 (مسئله سیلوستر) :  مجموعه محدود شامل نقاطی از صفحه‌است که هر خط گذرنده ازدو نقطه از نقطه ‏سومی می‌گذرد. ثابت کنید تمام نقاط روی یک خط واقع می‌باشند.‏


مثال 4 : ‏ در کشور اسکانیا هر شهری به شهر دیگر فقط بوسیله یک جاده یک طرفه وصل شده ‏است. ثابت کنید شهری وجود دارد که از هر شهری به آن مستقیم و یا حداکثر به ‏واسطه یک شهر دیگر می‌توان رسید. ‏



منبع: انگل، آرتور. استراتژی‌های حل مسئله، چاپ دوم . تهران: مبتکران ، ۱۳۸۴ 




  • نوید ادهم

اصل اکسترمال

۲۸
فروردين


اصل اکسترمال: هر مجموعه متناهی  یک ماکسیمم و مینیمم دارد .


البته این اصل بسیار ساده به نظر می رسد اما مثل اصل لانه کبوتری کاربرد های بسیاری دارد . معمولا در برهان خلف یکی از ماکسیمم یا مینیمم ها را انتخاب میکنند و ثابت میکنند اگر این طور باشد عددی کمتر از مینیمم یا بزرگتر ازماکسیمم وجود دارد .

 

تمرین 1:

جدولی نامتناهی به ما داده اند که از یک مجموعه متناهی از اعداد پر شده است و هر عدد میانگین 4 عدد مجاورش است ثابت کنید همه اعداد با هم برابر اند .

 

 

تمرین2 :

 نقطه در یک صفحه واقعند به طوری که هر سه تا از آن نقاط مثلثی با مساحت کمتر مساوی 1 تشکیل میدهند . ثابت کنید همه آنها را میتوان در مثلثی با مساحت 4 جا داد .




  • نوید ادهم
برای نمایش مطلب باید رمز عبور را وارد کنید
  • ۲۳ فروردين ۹۲ ، ۱۷:۲۵
  • ۴۳۶ نمایش
  • نوید ادهم

برای پیدا کردن کوتاه ترین مسیر بین دو راس مشخص در یک گراف می توان با دایسترای دوطرفه کار کرد که در عمل بسیار عالی است.

دایسترای دو طرفه در واقع با ساختن دو تا گراف از مبدا و مقصد (رو به جلو و رو به عقب) به دست می آید.

با به هم رسیدن این گراف ها الگوریتم پایان می یابد اما این لزوما به این معنی نیست که کوتاه ترین مسیر همان گرافی است که از برخورد این دو گراف به دست می آید. برای همین در دایسترا باید تغییراتی اعمال شود.

این تغییر عبارت است از چک کردن یال های بین مسیر اول و مسیر دوم.

فایل پاور پوینت زیر که توسط خودم درست شده این مطلب را نشان می دهد.


فایل پاورپوینت


فایل پی دی اف مقاله مربوطه

  • نوید ادهم