پاورپوینت های علوم پایه

تركیبات و نظریه‌ های گرافدر این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای تركیبات و نظریه‌ی گراف بپردازیم كه در این دوران شاهد پیشرفت چشمگیر آنها می باشیم .   این دو مبحث بدلیل آنكه دارای كاربرد وسیعی در علم كامپیوتر و برنامه سازی های كامپیوتری می‌باشند حائز اهمیت فراوان می باشند . 1-تركیبات : شاید در نگاه اول تركیبات یك بخش معماگونه و سطحی از ریاضیات به نظر برسد كه دارای كاربرد چندانی نبوده و فقط مفهوم های انتزاعی را معرفی می كند ولی این شاخه…

تركیبات و نظریه‌ های گراف

سید محمد میرعالی بازدید : 55 دوشنبه 20 شهريور 1396 : 20:44 نظرات ()
تركیبات و نظریه‌ های گراف

تركیبات و نظریه‌ های گراف


در این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای تركیبات و نظریه‌ی گراف بپردازیم كه در این دوران شاهد پیشرفت چشمگیر آنها می باشیم . 

 


این دو مبحث بدلیل آنكه دارای كاربرد وسیعی در علم كامپیوتر و برنامه سازی های كامپیوتری می‌باشند حائز اهمیت فراوان می باشند . 
1-تركیبات : 
شاید در نگاه اول تركیبات یك بخش معماگونه و سطحی از ریاضیات به نظر برسد كه دارای كاربرد چندانی نبوده و فقط مفهوم های انتزاعی را معرفی می كند ولی این شاخه از ریاضیات دارای گستره‌ی وسیع بوده و دارای شاخه های زیادی نیز می باشد . 
ابتدا به مسأله ای زیبا از تركیبات برای آشنا شدن بیشتر با این مبحث ارائه می كنیم . 
سوال : یك اتاقی مشبك شده به طول 8 و عرض 8 داریم كه خانه‌ی بالا سمت چپ و خانه‌ی پایین سمت راست‌ آن حذف شده است (مانند شكل زیر) 

حال ما دو نوع موزاییك داریم . یكی 2*1 ( ) و دیگری 1×2 ( ) سوال این است كه آیا می توان این اتاق را با این دو نوع موزائیك فرش كرد . 
احتمالاً اگر شخص آشنایی با تركیبات نداشته باشد می گوید «آری» و سعی می كند با كوشش و 
خطا اتاق را فرش كند ولی این كار شدنی نیست ؟! و اثبات جالبی نیز دارد . 
اثبات : جدول را بصورت شطرنجی رنگ می كنیم مانند شكل زیر : 
حال با كمی دقت متوجه می شویم كه هر موزائیك یك خانه از خانه های سیاه و یك خانه از خانه‌های سفید را می پوشاند یعنی اگر قرار باشد كه بتوان با استفاده از این موزائیك ها جدول پوشانده شود باید تعداد خانه های سیاه با تعداد خانه های سفید برابر باشد ولی این گونه نیست زیرا تعداد خانه های سفید جدول برابر 32 و تعداد خانه های سیاه برابر 30 می باشد . در نتیجه این كار امكان امكان پذیر نیست . 

این مسأله مربوط به مسائل رنگ آمیزی در تركیبات بوده كه دارای دامنه‌ی وسیعی از مسائل دشوار و پیچیده می باشد در زیر چند نمونه از مسائل آسان و سخت را بیان می كنیم .
1-ثابت‌كنید هیچ جدولی را نمی توان به موزائیك هایی به شكل و پوشاند .
(راهنمایی: ثابت كنید حتی سطر اول جدول را هم نمی توان پوشاند) 
2-ثابت كنید یك مهره‌ی اسب نمی تواند از یك خانه‌ی دلخواه صفحه‌ی n*4 شروع به حركت كند و تمام خانه ها را طی كند . 
3-یك شبكه‌ی n*m از نقاط داریم یك مسیر فراگیر مسیری است كه از خانه‌ی بالا سمت چپ 
شروع به حركت كرده و از همه‌ی خانه هر كدام دقیقاً یك بار عبور كند و به خانه‌ی سمت راست پایین برود ثابت كنید شرط لازم و كافی برای وجود یك مسیر فراگیر در شبكه‌ی n*m آن است كه لااقل یكی از m یا n فرد باشد (مرحله‌ی دوم المپیاد كامپیوتر ایران) در شكل زیر یك مسیر فراگیر را برای جدول 5*4 می بینیم . 

B
4-ثابت كنید شرط لازم كافی برای پوشش جدول n*m با موزائیك های 2*1 یا 1*2 آن است كه یا m یا n زوج باشند . 
حال می‌خواهیم یك مبحث مهم از تركیبات به نام استقراء را معرفی كنیم.
استقراء بعنی رسیدن ازجزء به كل و هم ارز است با اصل خوشترتیبی زیر مجموعه‌ها( اصل خوشتربینی بیان می‌كند كه هر مجموعه متناهی از اعداد عضوی به نام كوچكترین عضو دارد).
برای اثبات حكمی به كمك استقراء لازم است:
1) حكم را برای یك پایة دلخواه(كه معمولاً كوچك باشد) ثابت كنیم.
2) حكم را برای یك k دلخواه فرض می‌گیریم.
3) به كمك قسمت 2 حكم را برای ثابت می‌كنیم.
بسیاری از گزاره‌ها به كمك این استقراء كه در ظاهر ساده است ثابت می‌شود:
یك مثال ساده:
ثابت كنید: .
برای كه داریم و حكم برقرار است: 
فرض كنیم برای درست باشد حكم را برای ثابت می‌كنیم داریم:

كه این قسمت طبق فرض بردار می‌باشد
و برای نیز حكم مسأله برقرار است.
یك مثال سخت:
این سئوال در المپیاد كامپیوتر امسال مطرح شده و ما فقط یك قسمت آنرا بطور خلاصه بیان می‌كنیم.
سئوال: در روز A دارای تعداد مجموعه می‌باشد بطوریكه هیچ مجموعه‌‌ای زیرمجموعة دیگری نیست یعنی اكر )
حل شایان در روز B می‌آید از روی مجموعه‌های A تمام مجموعه‌هایی را نمی‌سازیم كه دارای دو شرط زیر می‌باشند:
1- هر مجموعه‌ای دلخواه در روز B با تمام مجموعه‌ها در روز A اشتراك دارد.
2-اگر از یك مجموعة دلخواه در روز B یك عضو را حذف كنیم آنگاه دیگر شرط 1 برقرار نباشد( كه به این شرط، شرط مینیمالی می‌گوئیم:
حال فراز در روز C از روی مجموعه‌های B تمام مجموعه‌هایی با دو شرط بالا را می‌سازد ثابت كنید ( یعنی تمام مجموعه‌های روز اول در روز سوم نیز تولید شده‌اند) 
اثبات: ابتدا لم زیر را ثابت می‌كنیم:
لم: به ازای هر مجموعة دلخواه در روز A مثل در روز B n تتا مجموعه وجود دارند بطوریكه هر كدام از آنها دقیقاً یكی از اعضای را دارند( ممكن است اعضای دیگری نیز داشته باشند ولی هر كدام دقیقاً یكی از را دارند.)
اثبات لم: با استقراء روی تعداد مجموعه‌های روز اول حكم را ثابت می‌كنیم. برای یك مجموعه در روز A وضعیت مجموعه‌ها در روزهای C,B,A مشخص شده‌اند:

قیمت فایل فقط 3,000 تومان

خرید


مراحل خرید:


1- پیش از خرید محصول توضیحات آن را به دقت مطالعه کنید زیرا محتوای فایل شامل تمام آن چیزی است که در توضیحات نوشته شده (نه کمتر و نه بیشتر)

2- پس از انتخاب فایل مورد نظر خود روی دکمه "دانلود" کلیک کنید
3- در مرحله بعد و در قسمت "تکمیل فرم خرید" مشخصات خواسته شده را به دقت وارد کنید و سپس روی دکمه "پرداخت و دانلود فایل" کلیک کنید.

(ایمیل را بدون www وارد کنید. نمونه صحیح ایمیل:  gsmyha@gmail.com)
3- در این مرحله به صفحه پرداخت وارد شده و با تمام کارت های عضو شتاب می توانید هزینه را واریز نمایید
4- پس از پرداخت موفق مجددا به سایت برگردانده می شوید و لینک دانلود برای شما نمایش داده می شود و علاوه بر آن یک نسخه از فایل به ایمیل شما هم ارسال می گردد تا با خیال راحت فایل خود را دانلود کنید.

(در صورتی که ایمیل فایل ناب به صندوق ورودی شما نرسیده ، باید پوشه اسپم را در ایمیل خود باز کنید و آنرا به صندوق ورودی انتقال دهید تا لینک دانلود فعال شود)


چند نکته مهم:

* پس از خرید فایل تا سه روز فرصت دارید تا فایل را بررسی کنید و در صورتی که فایل مطابق با توضیحات ارائه شده نبود از طریق بخش "تماس با ما" جزییات خرید را برای ما ارسال کنید تا پس از بررسی ، هزینه پرداختی شما را به حسابتان واریز کنیم.


* برای خرید محصولاتی که کمتر از 5000 تومان قیمت دارند نمی توانید از کارت بانک ملی استفاده کنید چون بانک ملی این اجازه را به دارندگان کارت بانک ملی نداده و به همین دلیل پیشنهاد می شود که برای خریدهای کمتر از 5000 تومان از کارت سایر بانکها استفاده نمایید.


* اگر صفحه لینک دانلود ظاهر نشود علت آن گزارش تخلف فایل و غیر فعال شدن فایل از طرف سایت می باشد. در این شرایط از طریق بخش "تماس با ما" جزییات خرید را برای ما ارسال کنید تا پس از بررسی ، هزینه پرداختی شما را به حسابتان واریز کنیم.

1  در هنگام خرید فایل به هیچ وجه از وی پی ان استفاده نکنید زیرا به احتمال زیاد خرید شما موفق نخواهد بود.


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

2 دانلود مرورگر گوگل کروم (نسخه 32 بیتی)

2 دانلود مرورگر گوگل کروم (نسخه 64 بیتی)

3 دانلود مرورگر فایرفاکس (نسخه 32 بیتی)

3 دانلود مرورگر فایرفاکس (نسخه 64 بیتی)


* برای حفظ کیفیت و همچنین دانلود آسانتر ، تمامی فایل ها فشرده شده و با فرمت rar یا zip آپلود شده اند. برای باز کردن فایل باید حتما نرم افزار win rar بر روی سیستم شما نصب شده باشد.

4 دانلود نرم افزار win rar (نسخه 32 بیتی)

4 دانلود نرم افزار win rar (نسخه 64 بیتی)


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

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

5 دانلود نرم افزار اینترنت دانلود منیجر

با آرزوی خریدی مطمئن برای شما

پاورپوینت های مرتبط
ارسال نظر برای این مطلب

نام
ایمیل (منتشر نمی‌شود)
وبسایت
:) :( ;) :D ;)) :X :? :P :* =(( :O @};- :B :S
کد امنیتی
رفرش
کد امنیتی
نظر خصوصی
مشخصات شما ذخیره شود ؟ [حذف مشخصات] [شکلک ها]
تبلیغات
محل تبلیغات شما
آرشیو
آمار سایت
  • کل پاورپوینت ها: 1988
  • کل نظرات : 1