اکسترمال 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:  ثابت کنید برای اعداد صحیح مثبت معادله زیر جواب ندارد. 

چالش بین P و NP

کسانی که با الگوریتم ها در گیر هستند می دانند که تحلیل یک الگوریتم (به لحاظ زمانی) در پیاده سازی و پیچیدگی آن الگوریتم اهمیت دارد در این رابطه مقاله زیر که به قلم دکتر رمضانیان (از اساتید دانشگاه شریف) است پیشنهاد می کنم.

مقاله

انشاالله در آینده در این مورد مطالب بیشتری را منتشر خواهم کرد.

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

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

این شبکه می خواهد برای 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 بیت یا کمتر شامل همه آن ها نیست.

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

معمای هوشی

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

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

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

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

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

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

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

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

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

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

و هم چنین  اگر  باشد آنگاه و اگر  آنگاه .

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

چند مسئله:

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

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

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

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

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

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

اصل اکسترمال

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

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

 

تمرین 1:

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

 

 

تمرین2 :

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

جزوه برنامه نویسی ++C

برای نمایش مطلب باید رمز عبور را وارد کنید

کوتاه ترین مسیر با دایسترای دوطرفه

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

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

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

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

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

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

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