ریاضی-علوم کامپیوتر- المپیاد

ریاضیات _ علوم کامپیوتر _ المپیاد ریاضی و کامپیوتر

ریاضی-علوم کامپیوتر- المپیاد

ریاضیات _ علوم کامپیوتر _ المپیاد ریاضی و کامپیوتر

درباره ی من
دکتری ریاضی (ترکیبیات) - شهید بهشتی
ارشد علوم کامپیوتر - صنعتی شریف
hamid.kamely@yahoo.com
کانال تلگرام: @math-cs
Instagram: hamidkameli1366
61 10 739 0912
سوابق کاری من

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


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

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

 

تمام مسائل المپیاد ریاضی و کامپیوتر بدون استفاده از روش های احتمالاتی هم حل شده اند اما تعداد زیادی از این مسائل با استفاده از روش های احتمالاتی بسیار ساده تر حل می شوند.

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

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

 

کتاب روشهای احتمالاتی در المپیاد

 

 

اصلاحیه برای کتاب

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

نام کتاب: روشهای احتمالاتی در المپیاد

_ صفحه ی 4 ، تعریف دوم  خط 7  : به جای علامت  اشتراک باید اجتماع باشد.  

_ صفحه ی 17، در پایین صفحه بین 0 و ‏‎$‎{ n-1 \over n}‎$‎‏‎ باید علامت ضرب باشد نه جمع.

_ صفحه ی 20، مثال 7.4.1 اصلاحیه  دانلود  

_ صفحه ی 22، به جای قضیه ی کشی - شوارتز، قضیه ی کوشی- شوارتز درست است.

_ صفحه ی 33، مساله ی 39 به جای ‏‎$‎P_k(k)‎$‎‏‎ باید ‏‎$‎P_n(k)‎$‎‏‎ قرار بگیرد.

_ صفحه ی 33، مساله ی 40 به جای $n+1 \over d$، قرار دهید $n\over m+1$

_ صفحه ی 57 پاسخ سوال 6 : خط 5 ام :  به جای کسر 4/5 باید کسر 4/25  باشد.

 

با تشکر از دانش آموز خوبم، امیرمهدی حسین آبادی که تعدادی از اشتباهات ذکر شده را پیدا کردند.
--------------------------------------------------------------------------------------------------------------------------------------------

سوال جدید

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

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

تعدادی از مسائلی که شاید در کتاب نباشد را در این صفحه می توانید ببینید. لینک  

1) سوال 1 : دانلود  : حل شده توسط دو تا از دانش آموزانم : فرهود رستم خانی ، ماکان خدابنده

 

نظرات  (۱۹)

 

?Can we please have an English version of this

پاسخ:
you can use the  book "probabilistic method" from N. Alon , J, Spencer

سلام امکانش هست فصل اول کتاب رو لینکش رو درست کنید خرابه اگه میشه زودتر این اتفاق بیوغته چون نزذیک مرحله دو هستیم

پاسخ:
شرمنده. دیر دیدم
سلام استاد
شما ریاضی کاربردی خوندید یا محض؟
پاسخ:
گرایش من ترکیبیات بوده که شاخه ای کاربردی محسوب میشه.
۲۷ خرداد ۹۸ ، ۱۳:۲۴ طاها اکبری
سلام. این هم از سوالات نظریه:

1.نشان دهید چگالی اعدادی که می توان ان ها را به شکل مجموع دو عدد با عوامل اول کمتر یا مساوی 1394 نوشت در اعداد طبیعی برابر صفر است.(مرحله سوم ریاضی 1394)

2.نشان دهید اگر دنباله ای از اعداد طبیعی را بتوان توسط یه چند جمله ای از بالا کراندار کرد دنباله نامتناهی عامل اول داره.(تعمیم قضیه شور)

3.نشان دهید $n^2+1$  به ازای نامتناهی مقدار $n$ خالی از مربع است.(تی اس تی چین 2015).

4.تی اس تی امریکا 2005 سوال 3.

5.میان ترم مرحله سوم ایران نظریه 2017 سوال 2.

6.IMC 2013.(سوالش رو یادم نیست در مورد مجموعه نامتناهی بود و اعداد خالی از مربع.

7.تی اس تی امریکا 2014 سوال 3 یا 4.(راه حلش دو گونه شماری هست ولی همون طور که تو کتابتون انجام دادید میشه احتمالاتیش کرد.)



پاسخ:
دم شما گرم. 
۲۵ خرداد ۹۸ ، ۲۲:۰۵ طاها اکبری
سلام استاد.من هم چند تا سوال پیدا کردم که به اشتراک می زارم:

1.المپیاد بین المملی ریاضی 2012 سوال 3(سوال توی Alon  هم موجوده معادلش)

2.F را برابر مجموعه m عضوی از زیرمجموعه های مجموعه n  عضوی تعریف می کنیم که هر کدام لااقل سه عضو دارند.(3m >=n) در این صورت زیر مجموعه ای از مجمو عه ی n عضوی وجود دارد که لااقل $\frac{2n}{3} *\sqrt{\frac{n}{3m}}$ عضو دارد و شامل هیچ عضو F  نمی باشد.(حالت خاص این مسعله در ایران 1383 و اروپای مرکزی 2012 اومده)(سوال ایران رو تو کلاس با روش احتمالاتی حل کردم:)  )

3.شورتلیست 2012 C7(البته راه حل اصلیش روش احتمالاتی نیست راه حل احتمالیش رو اگه خواستید می فرستم البته پیدا کردنش سخت نیست.)

4.USAMO 2010/6

5.حداکثر چند زیر مجموعه از مجموعه n عضوی X  می توان انتخاب کرد به طوری که اگر A  زیر مجموعه B  و در این مجموعه باشند تعداد اعضای A  لااقل سه تا کمتر از B باشد.(این هم روش احتمالاتیش رو ندیدم جایی گذاشته باشن خوبی روش احتمالاتیش اینه که در حالت کلی مسعله رو حل می کنه ولی استقرا همین حالت رو به زور حل می کنه.)(تی اس تی ایران 2015)

6.کوین دو به توان n منهای یک کلوچه دارد که هر کدام را با یک زیر مجموعه ناتهی از 1,2,3,...,n  علامت گذاری کرده ایم.هر بار کوین یک زیر مجموعه با احتمال یکسان انتخاب می کند و تمام کلوچه هایی که زیر مجموعه(نه لزوما محض) این مجموعه هستند را می خورد.امید ریاضی تعداد روز هایی که کلوچه ها تمام می شود چند است؟(OMO2013)

چند تا سوال نظریه هم هست که بعد از امتحانات می فرستم. 
پاسخ:
سلام. خیلی خیلی ممنونم. هر موقع فرصت کردی حتما بفرست. 
سلام. 
روش های احتمالی در فیزیک هم کاربرد داره؟
پاسخ:
بله. در کوانتوم ، فیزیک آماری و فکر می کنم کاربردهای دیگری هم داره که من مطلع نیستم. 
۱۴ مهر ۹۶ ، ۱۴:۵۲ real psychic readings
انتشار فوق العاده، بسیار آموزنده است. من تعجب می کنم که چرا متخصصین دیگر این بخش این را درک نمی کنند.
تو باید به نوشتنت ادامه بدهی. من مطمئن هستم، شما در حال حاضر یک پایگاه بزرگ خوانندگان!
۰۸ اسفند ۹۵ ، ۱۸:۱۴ طاها اکبری
ببخشید میشه به طور کلی بگید روش های احتمالی در ترکیبیات چی هست؟
پاسخ:
بخش اول کتاب 

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



روش های احتمالی چی هست
پاسخ:
یک تکنیک جدید برای حل مسائل. توضیح مفصل تری در همین صفحه داده شده اما برای اطلاعات بیشتر باید به مقدمه ی کتاب مراجعه کنید. فکر می کنم در سایت انتشارات خوشخوان مقدمه ی کتاب رو برای دانلود قرار داده اند. می تونید به کتاب The probabilistic method در مطلب ترکیبیات مراجعه کنید و فصل اول کتاب رو بخونید. البته برای یاد گرفتن روش های احتمالاتی باید مقدمات احتمال و هنچنین تا حد خوبی با شمارش آشنایی داشته باشید.
چه کتابی برای کسی که کلاس دوم دبیرستانه و تازه با المپیاد کامپیوتر اشنا شده خوبه؟
پاسخ:
کتاب هایی که در صفحه ی المپیاد معرفی شده رو ببین. مباحث بخش المپیاد کامپیوتر رو ببینی بهتر می تونه کمکت کنه.
اقا تو کتابه معلوم نیس چی نوشته اصن من تنها اونجاهاییش که جمع و تفریق داره رو می تونم حل کنم اگه می شه ی روش احتمالاتی برای هفتم ها هم درست کنید 
پاسخ:
بابا این کتاب به درد شما ها نمی خوره . قبل از اینکه بخری خوب پیشگفتارش رو یه نگاه بنداز. برای بچه هایی خوبه که می خوان مرحله دو و سه المپیاد بدن
سایت فوق العاده ای دارید ممنون از زحماتتان
۱۶ مرداد ۹۴ ، ۱۰:۵۶ ابوالفضل یوسفی
خواهش می کنم. فکر کنم در معما ها سوال خوبی به نظر برسه. البته خود شما استاد مایید هر جور که صلاح می دونید بهتره.
یا علی
پاسخ:
حتما در همون قسمت قرار خواهد گرفت. ممنون می شم از سوال های دیگه شما .
۱۳ مرداد ۹۴ ، ۱۵:۵۰ ابوالفضل یوسفی
سوالههای ارسال شده توسط من توسط دکتر علیشاهی مطرح شده اند. یاعلی
۱۳ مرداد ۹۴ ، ۱۵:۴۹ ابوالفضل یوسفی
سلام. یه سوال خوب:
در یک برنامه ی تلویزیونی مجری در حال اجرای مسابقه است و سه جعبه جلوی آن قرار دارد.

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

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

تشکر از مشارکت شما در طرح سوال . از سوال های دیگر شما نیز استقبال می کنم به خصوص اگر توسط دکتر علیشاهی طرح شده باشد. ما به ایشون خیلی ارادت داریم.
۰۵ دی ۹۳ ، ۱۴:۴۵ مجید گروسی
عه
مرسی!
خیلی نیاز داشتم بهش :د
لطفا برای دانلود بزارید اخه مگه چه اشکالی داره ؟؟؟
اگه مدال طلا گرفتم براتون دعا می کنم
پاسخ:
با انتشارات دچار مشکل می شم . شما اسکن کن بزار رو اینترنت من که مشکلی ندارم .
لطفا یک نسخه از کتاب را برای دانلود در این صفحه قرار دهید
با تشکر
کتاب سختیه من هیچی نمیفهمم
پاسخ:
پسر خوب . این کتاب که برای سن تو نیست . برای دبیرستانی هاست . برای اونهایی که مرحله یک قبول شدند .

ارسال نظر

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