اکسترمال

از shaazzz
پرش به ناوبری پرش به جستجو

در اکسترمال ما با انتخاب یکی از حالت های مساله که ویژگی خاصی، مانند کوچک ترین، چپ ترین، بهترین و ... ( که به آن یک ویژگی ترین می گوییم ) دارد را انتخاب کرده و با کمک آن مساله را حل می کنیم. اکسترمال طیف گسترده ای از مسائل را در بر می گیرد اما ممکن است در همه منابع همه کاربرد های آن را با نام اکسترمال معرفی نکنند.

اصول اکسترمال[ویرایش]

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

  • هر مجموعه محدودی که هر دو عضو آن قابل مقایسه باشند، ( مانند زیرمجموعه ای از اعداد حقیقی ) عضو ماکسیمم و عضو مینیمم دارد.
  • هر زیر مجموعه ای از اعداد طبیعی، عضو مینیمم دارد.
  • هر زیر مجموعه ای از اعداد حقیقی که کراندار باشد، لزوما دارای مینیمم یا ماکسیمم نیست، اما دارای بهترین کران است، به بهترین یا کمترین کران بالا مجموعه A، می گوییم sup(A) و به بهترین یا بیشترین کران پایین، inf(A) می گوییم. اگر بهترین کران عضو مجموعه باشد، آنگاه ماکسیمم یا مینمم است.

رابطه اکسترمال با استقرا[ویرایش]

اکسترمال و تناظر[ویرایش]

در این روش که برای شمارش به کار می رود، یک ترین را انتخاب می کنیم و بین چیزی که می خواهیم بشماریم و آن ویژگی، یک تناظر یک به یک برقرار می کنیم.

مثال[ویرایش]

شمردن تعداد ناحیه های ایجاد شده توسط n خط در صفحه و n خط در فضا. ( کامل شود)

فرض های مربوط به اکسترمال[ویرایش]

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

مثال[ویرایش]

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

تمرین[ویرایش]

پیدا کردن مطلوب مساله با انتخاب اکسترمالی[ویرایش]

در این مسائل مساله از ما شرایطی را می خواهد که در ظاهر پیچیده است و فراهم کردن آن مشکل است، اما اگر یک ویژگی مناسب را انتخاب کنیم و ترین آن را در نظر بگیریم، می توانیم شرایطی که مساله می خواهد را در آن بررسی کنیم و به این وسیله خروجی مطلوب را پیدا کنیم.

برهان خلف و اکسترمال[ویرایش]

در بسیاری از مسائل، می تواند با یک انتخاب اکسترمالی هوشمندانه از فرض خلف به تناقض برسیم.

اثبات نامحدود بودن یک چیز با اکسترمال[ویرایش]

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

مثال[ویرایش]

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

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

مسائل دیگر[ویرایش]

انتخاب های اکسترمالی[ویرایش]

در این قسمت به انتخاب های اکسترمالی پرکاربرد می پردازیم

در گراف[ویرایش]

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