Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger
طبقه بندی موضوعی
مطالب آخیر
بایگانی
پیوندهای روزانه
پیوندها

آزمون تئوری آمادگی مرحله 2

سه شنبه, ۱۹ فروردين ۱۳۹۳، ۰۲:۱۷ ب.ظ

سلام ؛

امید که سال خوبی رو شروع کرده باشید.
یه آزمون براتون میذارم که امیدوارم ازش لذت ببرید.
وقت آزمون 5 ساعت هـست و تعداد سوالاش هم 4 تا.
تا یه مدت دیگه ایده هاش رو میذارم :)

خوب و خوش سرحال باشید!

دانلود

موافقین ۴ مخالفین ۰ ۹۳/۰۱/۱۹
وحید شمس الدینی

نظریه گراف

ترکیبیات

مرحله دو

آزمون تئوری

المپیاد کامپیوتر

نظرات  (۱۲)

۲۰ فروردين ۹۳ ، ۱۵:۵۹ حسین
سوال یکو چقدر پیچوندید پرسپولیسیای سوراخ :)
پاسخ:
برو!برو از خدا بترس!
:)
۲۰ فروردين ۹۳ ، ۲۰:۱۶ حسین
سلام . بازم منم . من فکر می کنم که تونستم هر 4 تا سوالو حل کنم (و چون فکر می کنم که دارم به احتمال زیادی چرت می گم ) می خواستم از شما بپرسم ببینم درست حل کردم یا نه !

سوال اول اثبات برابر بودن اندازه ی مجموعه ی مستقل و پوشش راسی در گراف های دو بخشیه 

سوال دوم فکر می کنم بشه (2n-4) و با استقرا هم ثابت کردم (ولی چون اثباتام اثبات نیست !) و در ضمن چون هر گرافی که مینیمم درجش بزرگتر از 2 باشه توی مسیر ماکسیممش مشکل پیش میاد برای راس های ته مسیر پس راسی با درجه ی 2 وجود داره ، میندازیمش بیرون و خب دو تا هم کم شده ولی توی اینکه برای هر n آیا باید مثال زد یا نه شک دارم (من کلا سر سوال نمی تونم تشخیص بدم که کی باید مثال زد یا نه !) آیا اینجا مثال لازمه ؟
سوال سومم با استقرا . پایه رو بررسی نکردم :) ، اما برای حالت بعدی یه رنگو کلا نادیده می گیریم بعدش هر دو تا طرفو با ان منهای یک رنگ خطاشو رنگ می کنیم و بعدش تمام خطای بین دو مجموعه رو از رنگ جدید می کنیم اینطوری حداقل یکی از اون دو تا مجموعه هست که رنگ جدید توش استفاده نشده 

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

و اینکه کلا دمتون گرم :)

میشه بگید غلط داشتم عایا ؟
پاسخ:
سوال 1 تون فک کنم باید از این استفاده کنید که : ماکسیمم تطابق = مینیم پوشش راسی (اونی که شما نوشتید خودش با استفاده از همون قضیه ای که من نوشتم ثابت میشه)
سوال 2 تون کاملا درسته که خوب واضح هست که باید ارائه ساختار هم بدید که برا این سوال آسونه و قسمت سختش همون اثباتش هست که کاملا درسته :)
سوال 3 هم درسته
سوال 4 فک کنم اینطوری هم به جواب برسه ولی اگه سطر های iو j رو که به هم وصل می کنید با رنگ شماره ی ستونی که حذف ش گند میزنه به این دوتا رنگ کنید فک کنم راحت تر به تناقض برسید ولی به احتمال زیاد اونم به جواب برسه :)
و اینکه خیلی خوب بود راه حلاتون  :D
۲۱ فروردين ۹۳ ، ۱۸:۲۸ حسین
اثبات سوال یک که خیلی هم به اثبات شما مربوط نمیشه ها !!یه نگاهی به صفحه ی 114 وست بندازید 

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

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

در کل ممنون به خاطر آزمونتون ;)
پاسخ:
جناب آقای حسین آقا تو که اینقدر وست رو مثله کف دست بلدی و صفحه میدی برا ما (:دی) باید بدونی که اثبات اینکه تو گراف دوبخشی ماکسیمم مجموعه مستقل برابر هست با مینمم پوشش یالی از سه قضیه زیر استفاده میکنه :
1)ماکسیمم مستقل + مینمم پوشش راسی = n
2)مینمم پوشش راسی = ماکسیمم تطابق (گراف دوبخشی)
3)مینمم پوشش یالی + ماکسیمم تطابق = n
که خوب اون 2 رو من گفته بودم دیگه :)
اون خط دوم و سوم کامنتت رو اصن نمیفهمم خوب از همین قضیه 2 ای که نوشتم استفاده کن بره دیگه :)
اون سوال 2 رو که گفتم درست گفته بودید.
در کل خواهش میشه
۲۲ فروردين ۹۳ ، ۱۱:۵۷ حسین
سلام.
من فکر کنم شما یه ذره عصبانی شدی ! ، به هر حال من که قصد نداشتم ادعا کنم که بلدم و امیدوارم هم شما ناراحت نشید ، یه بحث شبهه علمی بود ! 
دوباره بابت آزمونتون متشکرم ;) 
پاسخ:
:)

۲۵ فروردين ۹۳ ، ۱۵:۰۱ سوال
سلام. ببخشید یه سوال داشتم : سوالای امتحان تئوری رو که نوشتید برای آقای فولادی هستن ، منظورتون یاسره یا هادی ؟
پاسخ:
والا ما اصن اسمی از ایشون نبردیم :)
سوالای این آزمون گرد آوری شده از گروه challenger هست ولی خوب طرح شده نیست ولی از آقای فولادی گرفته نشده!
سوال 1 => قضیه معروف
سوال 2 => سوال sgu هست
سوال 3 => معروف هـ و نمیدونم مال کجاست
سوا 4 => سوال تورنمنت شهر ها هست
:)
۲۶ فروردين ۹۳ ، ۱۷:۰۰ سوال
سلام . منظورم امتحان قبلیتون chtantative (اسمش توی همین مایه ها بود ) که از آقای فولادی نام برده بودید
پاسخ:
جهان آرا: آقای یاسر فولادی.
۲۷ فروردين ۹۳ ، ۲۲:۵۴ بنیامین
:ِD خوشحالم که چلنجر یه تکونی خورده! فقط یه چیزی. الان فقط جواب کامنت اخریه جهانه؟
@وحید: آقا نزاری جهان یه وقت کاری بکنه ها! بچه کنکور داره من می ترسم شیطونی کنه ... :)
@جهان: ...
پاسخ:
 منم خوشحالم که خوش حالید!(:دی)

۳۰ فروردين ۹۳ ، ۲۲:۱۹ SMA KH
سلام
@وحید:
خیلی ممنون از امتحان خوبتون! (البته همون جوری که خودتون هم گفتید سوالاش تکراری بود! (1 2و 4 رو دیده بودم و 1 و 4 رو حلش رو شنیده بودم! ولی برای کسی که نشنیده قطعا امتحان جالبیه و البته فکر کنم یکم زیادی برای م2 سخت باشه!)

@جهان : 
دلم واقعا برات تنگ شده!
ان شاءالله خبر شریفی شدنت رو ما
و خبر شریفی شدن ما رو هم شما بشنوید! (نکته کنکوری: از لحاظ قوائد زبان فارسی الان فعل اولی رو اشتباهی حذف کردم!)

@بنیامین:
مشتاق دیدار!

همگی موفق باشید!
یا علی
پاسخ:
وحید :
آزمون جدید سعی میشه تکراری نداشته باشه :)
جهان : :)))))
دل به دل راه داره :D :)
ایشاالله
شاد و موفق باشی.
بنیامین: منم بلدم جواب بدم! :P :))
منم همین طور :) 

۳۰ فروردين ۹۳ ، ۲۲:۴۹ سید محمد امین سیدزاده
روز مادر مبارک
پاسخ:
تبریک به همه مادر ها <3

۳۰ فروردين ۹۳ ، ۲۳:۳۹ بنیامین
الان که بحث مرحله دو داغه
منم ازمونی که پارسال خودم با پاسخنامه گزاشتمو توصیه می کنم
http://challenger.blog.ir/1392/01/30/M2tentative
این خودشه. اینم پاسخنامه و یه سوال خوب دیگه:
http://challenger.blog.ir/1392/02/05/solch
اگه حل نکردید پارسال فک کنم سوالای خوبی بود ...
پاسخ:
منم توصیه میکنم :))
پ.ن : با اجازه آقا بنیامین : تو آزمون پارسال جواب سوال آخر  به طور قطعی c(n,2 خواهد بود :)
مثال ها زیر رو در نظر بگیرید :
یه گراف یک یالی یا مکملش :)
۳۱ فروردين ۹۳ ، ۱۵:۱۹ جم
سلام.وبلاگ زیباییست.به دردفروشی من هم سری بزنید.نظر فراموش نشه.
پاسخ:
:)
۳۱ فروردين ۹۳ ، ۱۶:۲۷ رضا سلطانی
ممنون بابت سوالا ! :‌)
سوال دو ، سوال 424 اس‌جی‌یو هست اگه اشتباه نکنم ! [همون‌طور که اشاره شد]
پاسخ:
:)

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی
{ ALL COPYRIGHT BY CHALLENGER.BLOG.IR }
.: هزار کوه گرت سد ره شوند برو / هزار ره گرت از پا درافکنند بایست :.
ساخت وبلاگ در بلاگ بیان، رسانه متخصصان و اهل قلم