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

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

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

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

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

اصل اکسترمال

چهارشنبه, ۲۸ فروردين ۱۳۹۲، ۰۵:۳۲ ب.ظ


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


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

 

تمرین 1:

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

 

 

تمرین2 :

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





حل تمرین 1:

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

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



حل تمرین 2 (از سینا موسوی):

سه تا نقطه ABC رو طوری انتخاب می کنیم که مساحت ماکزیموم رو بین مثلث ها داشته باشیم. با توجه به فرض مسئله S(ABC) <= 1. حالا میایم برای هر کدوم از اضلاع ABC به اندازه دو برابرش یک خط موازی با اون می کشیم. با این کار یه مثلث با مساحت 4 برابر ABC به دست میاد که بدیهیه کوچیک تر مساوی 4 هست. حالا ثابت می کنیم که تمامی نقاط در داخل این مثلث هستن. برای این کار از برهان خلف استفاده می کنیم. فرض می کنیم نقطه ای وجود داره که خارج این مثلثه. اسمش رو D می ذاریم. در این صورت یکی از مثلث های ABD، ACD یا BCD از یک بزرگتر هستن که با فرض مسئله در تناقضه.


راه حل دیگر (بسیار مشابه): img/daneshnameh_up/b/b3/com0039d.jpg


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

نظرات (۴)

حل تمرین 2 به نظرم این شکلی میشه:
سه تا نقطه ABC رو طوری انتخاب می کنیم که مساحت ماکزیموم رو بین مثلث ها داشته باشیم. با توجه به فرض مسئله S(ABC) <= 1. حالا میایم برای هر کدوم از اضلاع ABC به اندازه دو برابرش یک خط موازی با اون می کشیم. با این کار یه مثلث با مساحت 4 برابر ABC به دست میاد که بدیهیه کوچیک تر مساوی 4 هست. حالا ثابت می کنیم که تمامی نقاط در داخل این مثلث هستن. برای این کار از برهان خلف استفاده می کنیم. فرض می کنیم نقطه ای وجود داره که خارج این مثلثه. اسمش رو D می ذاریم. در این صورت یکی از مثلث های ABD، ACD یا BCD از یک بزرگتر هستن که با فرض مسئله در تناقضه.
سلام
درسته
با تشکر
پاسخ:
درسته اما باید قسمت آخرش رو بیشتر و بهتر توضیح بدهی
سلام آقا
یادتونه بهتون گفتم یه کتاب هست مال تیتو که اکسترمال هم داره
این لینک دانلودشه
http://bookos.org/book/1320669/a9f89c
اگه وقت کردید یه نیگا به فصل اکسترمالش بندازید ببینید چجوریه

راستی آقا چه جور دلتون اومد به من ۱۸ بدید؟؟؟؟؟
ممنون پسر
ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی