آشنایی با نظریه گراف ها

در مورد نظریه گراف ها  کتاب های خیلی خوبی نوشته شده:

به نظرم یکی از بهترین کتاب های موجود کتاب آشنایی با نظریه گراف ها اثر وست است. کتاب وست یک اثر جامع است که ویرایش دومش برای 2002 است.

برای دانلود کتاب وست روی این لینک کلیک کنید.

کتاب دیگری که قبلا مورد  استفاده بود کتاب باندی و مورتی است. که البته در 2008 ورژن جدیدش را ارائه کردند.

کتاب قدیمی تر از آن هم کتاب ویلسون است.

دومینو بازی

صفحه شطرنجی 100*99 به دومینوها افراز شده است. می دانیم برای هر افراز دیگر صفحه شطرنجی به دومینوها ،دومینویی وجود دارد که در هر دو افراز مشترک است .ثابت کنید در افراز اولیه دو ستون متوالی می توان یافت که همه خانه های آن به دومینوهای افقی افراز شده باشد.

مرتب سازی ادغامی و مرتب سازی سریع

روش مرتب سازی ادغامی از الگوریتم تقسیم و حل (divide-and-conquer) و همچنین ادغام برای مرتب کردن داده‌ها استفاده می‌کند. در این الگوریتم مساله به چند جزء کوچک‌تر تقسیم می‌شود. هر کدوم از این قسمت‌ها رو به طور مجزا حل کرده، و با ترکیب اونها به مساله اصلی می‌رسیم. و اما طرح کلی مرتب سازی ادغام:

در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شوند. و هر کدوم از این قسمت‌ها - به صورت بازگشتی - مرتب، و با ادغام آنها دادها بصورت کامل مرتب می‌شوند.اما توجه به این نکته ضروری است که اگر پس از یک بار تقسیم باز هم لیستهای ایجاد شده بزرگ باشند ، می توانیم برای هر زیر لیست مراحل بالا را دوباره انجام دهیم تا به زیر لیستهایی با تنها 1 عضو برسیم و واضح است که لیست تک عنصری خود مرتب است.

مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو مرتب می‌کنه. برای اینکار یکی از داده‌ها (مثلاً داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس محور طوری چینش می‌شن که همه داده‌های کوچک‌تر از محور سمت چپ و داده‌های بزرگ‌تر یا مساوی اون سمت راستش قرار می‌گیرن. با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچک‌تر هستن و بالعکس. 

منبع اصلی درس الگوریتم ها

کتاب آشنایی با الگوریتم ها که توسط چهار نفر (  CLRS ) نوشته شده:

ویرایش سوم کتاب

ویرایش دوم کتاب

جستجو ها و مرتب سازی های تدریس شده:

جستجوی خطی، جستجوی دودویی، مرتب سازی انتخابی، مرتب سازی درجی، مرتب سازی حبابی

جزوه

جدول مستطیلی

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

اعداد روی تخته

اگر n یک عدد فرد باشد و اعداد 1 تا 2n بر روی تخته نوشته شده باشد. در هر مرحله دو تا از اعداد را انتخاب کرده و تفاضل آن ها را به جای آن دو عدد بر روی تخته می نویسیم.

آیا در نهایت می توان به عدد صفر رسید؟

اکسترمال 4

جزوه اکسترمال از سایت المپیاد رشد که ترجمه فصل سوم کتاب استراتژی های حل مسئله است. به همراه اصل کتاب در زیر آمده است:

جزوه اکسترمال المپیاد رشد

کتاب استراتژی های حل مسئه

جاده های خاکی

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

راه حل: 

اکسترمال 3

مثال 5 : رخ هایی روی صفحه شطرنج  قرار دارند. واضح است که  رخ کمترین تعداد رخی می باشد که تمام خانه های شطرنج  را تهدید می نماید. اما درباره  چه می توان گفت که بتوانند خانه های شطرنج   را تهدید کند. 

مثال 6 : در چهاروجهی با سه یال همرس می توان یک مثلث ساخت. 

مثال 7 :   مجموعه نقاطی از صفحه است. هر نقطه وسط دو نقطه دیگر است. ثابت کنید مجموعه ای نامحدود است.   

مثال 8 : هفت کوتوله دور یک میز دایره ای نشسته اند.در برابر هر یک از آنها، فنجانی قرار دارد.در برخی از فنجان ها شیر هست،روی هم 3 لیتر. یکی از کوتوله ها شیرش رابه طور یکسان میان دیگر فنجان ها قسمت می کند.در فرآیندی پاد ساعتگرد،هر یک از کوتوله ها به نوبت همان کار را انجام می دهند. بعد از آن که کوتوله ی هفتم شیرش را قسمت کرد،محتویات آغازین هر فنجان بازگردانده می شود.میزان آغازین شیر را در هر یک از فنجان ها بیابید.

مثال 9 : در یک پنج ضلعی محدب می توان سه قطر انتخاب کرد که اضلاع یک مثلث باشند 

مثال 10 : عدد های طبیعی را از 1 تا 64 روی خانه های یک صفحه شطرنج به ترتیب نوشته ایم.  (از 1 تا 8 را از چپ به راست در سطر اول و به همین ترتیب تا سطر هشتم.) قبل از تعداد از عدد ها علامت بعلاوه و قبل از بعضی علامت منها را طوری نوشته ایم که در هر سطر و هر ستون 2 تا بعلاوه و 4 تا منها وجود دارد. ثابت کنید مجموع عددهای نوشته شده برابر صفر است.

مثال 11 :  ثابت کنید تعداد رشته های باینری n تایی به طوری که هر دوتا حداقل در سه مکان متفاوت باشند حداکثر (1+2ⁿ) / (n) است .

مثال 12 :  سه مدرسه مفروض است که در هر یک از سه مدرسه n دانش آموز وجود دارد . هر دانش آموز جمعن n+1 دوست از دو مدرسه دیگر دارد . ثابت کنید می توانیم یک نفر از هر مدرسه انتخاب کنیم به طوری که این سه نفر دو به دو با هم دوست باشند .

مثال 13 :  9 شکل مسطحه داریم که مساحت هر کدام 1 است. آنها را طوری در صفحه قرار داده ایم که مساحت شکل حاصل 5 شده است.ثابت کنید 2 شکل وجود دارد که اشتراک مساحتشان بزرگتر یا مساوی 1/2 است.

مثال 14 : ماشینی در مسیر دایره ای قرار دارد.مقداری بنزین به طور ناهمگن در مسیر ریخته شده است.(ممکن است در نقطه هایی از مسیر اصلا بنزینی وجود نداشته باشد.)باک ماشین در ابتدا خالی است.ماشین از هر نقطه ای از مسیر عبور کند تمام بنزین آن نقطه را در باک خود جمع می کند.اگر کل بنزین ها را جمع کنیم دقیقا به اندازه ی یک دور ماشین است.ثابت کنید نقطه ای در مسیر وجود دارد که اگر از آن نقطه شروع به حرکت کند می تواند دقیقا 1 دور مسیر را بپیماید.

مثال 15:  ثابت کنید برای اعداد صحیح مثبت معادله زیر جواب ندارد. 

موسیقی یا پیام جاسوسی

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

این شبکه می خواهد برای 9 نفر از مامورانش پیام بفرستد، ولی از آنجا که زیاد شدن طول پیام احتمال شناسایی و کشف آن را زیاد می کند سعی می کند طول کل پیام ارسالی تا حد ممکن کوتاه باشد. به این دلیل، در صورت امکان پیام های مورد نظر خود را با هم ترکیب و یک جا ارسال می کند. مثلا هر گام بخواهد پیام 0110 را به یکی از ماموران و پیام 1011 را مامور دیگر بفرستد، می تواند آن ها را به صورت 011011 ترکیب و یک جا ارسال کند. البته در این حالت باید قبل از ارسال این پیام ترکیبی، به مامور اول اطلاع دهد که از رقم اول شروع به خواندن کند و به مامور دوم بگوید که از رقم سوم شروع به خواندن کند. برای اطلاع دادن محل شروع پیام هر مامور (شماره رقم آن) هم از نت موسیقی خاصی برای آن مامور استفاده می شود.

1- این شبکه می خواهد پیام های 0000 ، 0011 ، 0100 ، 0110 ، 0111 ، 1011 ، 1100 ، 1101 و 1110را به مامورانش بفرستد. متخصصی کد گذاری شبکه موفق به یافتن دنباله ای به طول 15 بیت برای ترکیب این 9 پیام شده اند. آیا شما می توانید دنباله ای به طول 14 یا کمتر بیابید که شامل همه این 9 پیام باشد؟

2- فرض کنید تعداد ماموران این شبکه از 9 نفر به 14 نفر افزایش پیدا کرده است. آیا می توانید دنباله ای 19 بیتی پیدا کنید که شامل هر مجموعه 14 تایی دلخواه از پیام های 4 بیتی باشد؟

3- آیا می توان یک دنباله 18 بیتی که 14 دنباله 4 بیتی مشخص که از قبل به شما داده شده اند، زیر دنباله های آن باشند؟ (به تفاوت این سوال و سوال قبل دقت کنید. در سوال قبل دنباله 19 بیتی باید شامل هر مجموعه دلخواه از مجموعه 4 بیتی باشد، ولی در این سوال 14 دنباله داده شده است که دنباله 18 بیتی باید شامل هر یک از آن ها باشد. نشان دهید که بدون توجه به این که 14 دنباله انتخاب شده، چه دنباله هایی هستند؛ می توانید دنباله 18 بیتی مورد نظر را تشکیل دهید.)

4- نشان دهید مجموعه هایی از 14 دنباله 4 بیتی وجود دارند که هیچ دنباله ای به طول 18 بیت یا کمتر شامل همه آن ها نیست.

منبع: معماهای الگوریتمی، دکتر قدسی و یاشار گنجعلی، انتشارات فاطمی