این سوال گراف ۲۰۰ بار تو کنکور های قبل اومده.
وقتی به همه‌ی یالها یک مقدار ثابت اضافه بشه.
درخت پوشا فرقی نمی کنه.(الگوریتم کروسکال یا پریم)
ولی کوتاهترین مسیر بین دو راس فرق می کنه
وقتی تمام یالها یکی اضافه میشه طول همه مسیر‌ها هم اضافه می شه
مثلا شما بین دو گره یه مسیر داشتین ۳+۳ یکی ۷
حالا اون میشه ۴+۴ اون یکی ۸ یعنی الان دیگه اینکه کدوم مسیر رو بریم فرقی نداره هر دو مساوی است!
در اینکه درخت پوشا و کوتاه ترین مسیر یکی هستش شکی نیست اما مجموعه برش یعنی اون مجموعه ای که تا حالا در یک طرف جزو گره های انتخابی هستش و با اضافه شدن یال من با مثال به این رسیدم که فرق میکنه
تو کوتاهترین مسیر یکی نیست!!
توضیحش رو که دادم!
مثلا یه مسیر داریم ۲+۲+۲ یکی ۷ بار اول اون مسیر ۳ یال رو انتخاب میکنیم
بعد میشه ۳+۳+۳ , ۸ که دفعه بعد اون تک یال انتخاب میشه!
من با مثال حل کردم به سه تاش رسیدم ...بچه‌ها سوالارو ندارید
راست میگی حالا زیاد مهم نیست دعا کن ۲ تا گزارش درست باشه چون من زدم ۲ تا گزاره البته فک نکنم ۳ تا گزارش درست باشه اخه
(۲۹ بهمن ۱۳۸۹ ۰۸:۱۳ ب.ظ)javadjj نوشته شده توسط: بریم سراغ سوال فاکتوریل من رابطه بازگشتی رو تشکیل دادم و همه جوره به اونی که رادیکال ۵ داشت رسیدم و شما دوستان؟این سوال برنامه نویسی پویا بود چون از حافظه (آرایه)داشت استفاده می کرد.می شه O(n)
(۲۹ بهمن ۱۳۸۹ ۰۸:۱۳ ب.ظ)javadjj نوشته شده توسط: بریم سراغ سوال فاکتوریل من رابطه بازگشتی رو تشکیل دادم و همه جوره به اونی که رادیکال ۵ داشت رسیدم و شما دوستان؟منم مثل شما، یادم به این رابطه، "رابطه طلایی " میگن که توی ساختمان گسسته خوندمش.
هوش مصنوعی:
۱- من هم هرس آلفا بتا زدم گزینه‌ی ۳ (یعنی همونی که با ۹ شروع میشد!)
۲- سئوال آخر هوش رو مطمئنم یا گزینه‌ی ۱ میشه یا ۲! من گزینه‌ی یک رو زدم!
۳- سئوال مونوتونیک رو حل نکردم!
۴- سئوال جستجو رو زدم هر دو bfs و با مثال رفتم و به نظرم درست میشد...
۵- احتمال شهر‌ها هم میشد D!!! راستش من به این سئوال شک کردم
آخه این کجاش هوش بود! اینقدر آسون بود که حتی برای آمار هم چنین سئوالی نمیدن! برای همین شک دارم!!! شاید واقعاً یک نکته‌ی خاصی داشته باشه!!!
۶- اون سئوال دانش آموزها هم میشد:
به ازای همه‌ی xها، (if student(x آنگاه وجود دارد z و yیی که (y!=z ^ friend(x,z) ^ friend (x,y
۷- اونی که درباره‌ی راه حل آگاهانه و ناآگاهانه بود رو زدم یکی درست! ولی این یکی رو اصلاً مطمئن نیستم!!!!
سئوال هوش چیز دیگه ای بود؟!!!
طراحی الگوریتم:
۱- با اینکه میدونستم دارم اشتباه میکنم مرتب سازی سریع تصادفی رو زدم logn!!! لعنت!!! تقریباً مطمئن بودم n میشه ولی نمیدونم چرا لحظه‌ی آخر زدم logn!!!
۲- گزینه های اون سئوالی که میگفت چند تاش صحیحه و درباره‌ی این بود که به یالها یکی واحد اضافه کنیم چی بود؟!!! یادم نیست!!! من برای هر سه تاش مثال نقض رو دارم! اگر یادتون هست بگید تا توضیح بدم! برای همین اون رو زدم صفر تا صحیح!!!!
۳- اون فیبوناچی مطمئنم به روش پویا بود! ولی یادم نبود که روش پویا زمانش چی میشه! احساس کردم میشه n!!! ولی مثل اینکه بچه‌ها میگن روش پویا جوابش رادیکالیه میشه!!! (چرا من فکر میکردم n میشه!!!؟ احساس میکردم مقسمی نوشته بود روش پویا میشه n!)
۴- اون سئوال کلاسها رو زدم nlogn و با Maryam-X موافقم! این دقیقاً مثل زمانبندیه سخنرانی هاست!!! پیدا کردن کمترین کلاس توی زمان nlogn صورت میگیره! به این صورت که یک کلاس رو در نظر میگیریم و بیشترین تعدادی که میشه در اون کلاس قرار داد رو مشخص میکنیم (با مرتب کردن زمان خاتمه‌ی کلاس ها) اون موقع به تعدادی که درس باقی میمونه، کلاس میگذاریم!!!!
۵- اون سئوالی هم که E و V داده بود رو من اشتباه خواندم!!! مثل اینکه گفته بود که گراف بدون دور باشه! و من حواسم نبود!!!! (نمیدونم چرا من همیشه سئوال رو اشتباه میخوانم!!!)
دیگه سئوال‌ها یادم نیست!!!
۱- من هم هرس آلفا بتا زدم گزینه‌ی ۳ (یعنی همونی که با ۹ شروع میشد!)
۲- سئوال آخر هوش رو مطمئنم یا گزینه‌ی ۱ میشه یا ۲! من گزینه‌ی یک رو زدم!
۳- سئوال مونوتونیک رو حل نکردم!
۴- سئوال جستجو رو زدم هر دو bfs و با مثال رفتم و به نظرم درست میشد...
۵- احتمال شهر‌ها هم میشد D!!! راستش من به این سئوال شک کردم
آخه این کجاش هوش بود! اینقدر آسون بود که حتی برای آمار هم چنین سئوالی نمیدن! برای همین شک دارم!!! شاید واقعاً یک نکته‌ی خاصی داشته باشه!!!۶- اون سئوال دانش آموزها هم میشد:
به ازای همه‌ی xها، (if student(x آنگاه وجود دارد z و yیی که (y!=z ^ friend(x,z) ^ friend (x,y
۷- اونی که درباره‌ی راه حل آگاهانه و ناآگاهانه بود رو زدم یکی درست! ولی این یکی رو اصلاً مطمئن نیستم!!!!
سئوال هوش چیز دیگه ای بود؟!!!
طراحی الگوریتم:
۱- با اینکه میدونستم دارم اشتباه میکنم مرتب سازی سریع تصادفی رو زدم logn!!! لعنت!!! تقریباً مطمئن بودم n میشه ولی نمیدونم چرا لحظه‌ی آخر زدم logn!!!
۲- گزینه های اون سئوالی که میگفت چند تاش صحیحه و درباره‌ی این بود که به یالها یکی واحد اضافه کنیم چی بود؟!!! یادم نیست!!! من برای هر سه تاش مثال نقض رو دارم! اگر یادتون هست بگید تا توضیح بدم! برای همین اون رو زدم صفر تا صحیح!!!!
۳- اون فیبوناچی مطمئنم به روش پویا بود! ولی یادم نبود که روش پویا زمانش چی میشه! احساس کردم میشه n!!! ولی مثل اینکه بچه‌ها میگن روش پویا جوابش رادیکالیه میشه!!! (چرا من فکر میکردم n میشه!!!؟ احساس میکردم مقسمی نوشته بود روش پویا میشه n!)
۴- اون سئوال کلاسها رو زدم nlogn و با Maryam-X موافقم! این دقیقاً مثل زمانبندیه سخنرانی هاست!!! پیدا کردن کمترین کلاس توی زمان nlogn صورت میگیره! به این صورت که یک کلاس رو در نظر میگیریم و بیشترین تعدادی که میشه در اون کلاس قرار داد رو مشخص میکنیم (با مرتب کردن زمان خاتمه‌ی کلاس ها) اون موقع به تعدادی که درس باقی میمونه، کلاس میگذاریم!!!!
۵- اون سئوالی هم که E و V داده بود رو من اشتباه خواندم!!! مثل اینکه گفته بود که گراف بدون دور باشه! و من حواسم نبود!!!! (نمیدونم چرا من همیشه سئوال رو اشتباه میخوانم!!!)
دیگه سئوال‌ها یادم نیست!!!
(۳۰ بهمن ۱۳۸۹ ۰۲:۱۰ ق.ظ)Mansoureh نوشته شده توسط: طراحی الگوریتم:
۱- با اینکه میدونستم دارم اشتباه میکنم مرتب سازی سریع تصادفی رو زدم logn!!! لعنت!!! تقریباً مطمئن بودم n میشه ولی نمیدونم چرا لحظه‌ی آخر زدم logn!!!
۲- گزینه های اون سئوالی که میگفت چند تاش صحیحه و درباره‌ی این بود که به یالها یکی واحد اضافه کنیم چی بود؟!!! یادم نیست!!! من برای هر سه تاش مثال نقض رو دارم! اگر یادتون هست بگید تا توضیح بدم! برای همین اون رو زدم صفر تا صحیح!!!!
۳- اون فیبوناچی مطمئنم به روش پویا بود! ولی یادم نبود که روش پویا زمانش چی میشه! احساس کردم میشه n!!! ولی مثل اینکه بچه‌ها میگن روش پویا جوابش رادیکالیه میشه!!! (چرا من فکر میکردم n میشه!!!؟ احساس میکردم مقسمی نوشته بود روش پویا میشه n!)
۴- اون سئوال کلاسها رو زدم nlogn و با Maryam-X موافقم! این دقیقاً مثل زمانبندیه سخنرانی هاست!!! پیدا کردن کمترین کلاس توی زمان nlogn صورت میگیره! به این صورت که یک کلاس رو در نظر میگیریم و بیشترین تعدادی که میشه در اون کلاس قرار داد رو مشخص میکنیم (با مرتب کردن زمان خاتمه‌ی کلاس ها) اون موقع به تعدادی که درس باقی میمونه، کلاس میگذاریم!!!!
۵- اون سئوالی هم که E و V داده بود رو من اشتباه خواندم!!! مثل اینکه گفته بود که گراف بدون دور باشه! و من حواسم نبود!!!! (نمیدونم چرا من همیشه سئوال رو اشتباه میخوانم!!!)
دیگه سئوال‌ها یادم نیست!!![/align]
دوست عزیز اون فیبوناچی به روش پویا نبود چراکه خود تابع فراخونی میشد و نه آرایه( نامردا اسم آرایه و تابع رو شبیه گزاشته بودن تا از استرس ما سر جلسه سوء استفاده کنن)
در ضمن فکر کنم گفته بود گراف بدون یال موازی و حلقه( طوقه) نه دور( گراف بدون دور که درخته و یه حالت بیشتر نداره که ما رو بپیچونن)
نه پویا بود این که اول تابع میگفت اگه f[n] بزرگتر از صفره مقدارشو برگردون واسه این بود که دو بار حساب نکنه!
در مورد دومی حق با شماست منظورش حلقه بوده
(۳۰ بهمن ۱۳۸۹ ۰۲:۲۴ ق.ظ)afagh1389 نوشته شده توسط: نه پویا بود این که اول تابع میگفت اگه f[n] بزرگتر از صفره مقدارشو برگردون واسه این بود که دو بار حساب نکنه!
در مورد دومی حق با شماست منظورش حلقه بوده
بابا مگه یادت رفته کل آرایه مقدار -۱ داشته، و این شرطی که میگید فقط شرط پایانی هست.
در مورد جواب به نظر من و آقا جواد( دوست خوبم )گزینه ۴ میشه( اونی که رادیکال داشت) چراکه به این رابطه، رابطه طلایی میگن که برا مسائلی مثل فیوناچی بکار میره، البته این رابطه مقدارش رو میده و شاید جواب گزینه الف باشه اما من ۴ زدم.
راستی حق با شما بود یعنی کی؟؟؟
طراحی آلگوریتم (به قول استادم که تو کانادا دکتری خونده)
سوال اول الگوریتم- مجموع اعضای مجموعه: اونی بود که تقسیم بر m بعد منهای np داشت ،سوال قبلا دیده بودم
گراف کمینه: نزدم
رابطه فیبوناچی: به نظرم خودش گفته بود بازگشتی و آقای پروفسور روزن حل کرده بود و به رادیکال ان رسیده بود
پارتیشن با زمان ثابت c: گزینه logn زدم که جواد جان میگه کرمن گفته n (کرمن بگم خدا چی کارت کنه!)
برنامه کلاسها: به نظرم زمانبندی با مهلت معین بود که جناب مقسمی گفته مرتب سازی کارها logn می شود ولی بررسی کارها n^2 است که همان چیره می شود
گراف - امکانپذیر نباشد: نزدم، دقت کنید که دور نگفته بود و حلقه گفته بود و رابطه اندازه گره‌ها بزرگتر از اندازه نصف یالها در گرافهای کامل بزرگ! صادق نیست مثلا گراف کامل ۷ تایی ؛ هفت گره و بیست و یک یال دارد که هفت از بیست و یک بزرگتر نیست
هوش:
اگر آگاهانه باشد ناآگاهانه داریم و ...: نزدم، شرمنده
دانش آموزان: اونی که y مخالف z بود و آنگاه داشت و E برعکس داشت زدم
تور:اول سطحی و دومی عمقی زدم که آقا رامین(رهنمون) گفته هر دو سطحیه
قابل قبول و یکنواخت: هم قابل قبول هم یکنواخت چون بزرگتر تخمین نمی زد و کم هم نمی شد احتمالا
زبان پترانستو:شهر D زدم که از مسائل شبکه باور بود (بعد امتحان فهمیدم) با ضرب احتمالات حل شد
هرس آلفا - بتا: اونی بود که با ۹ شروع می شد -در دفترچه سی گزینه ۳ بود!
منطق:نزدم
(۳۰ بهمن ۱۳۸۹ ۰۳:۱۹ ق.ظ)alavinejad نوشته شده توسط: طراحی آلگوریتم (به قول استادم که تو کانادا دکتری خونده)فکر کنم سوال ۱ الگوریتم اشتباه میکنین چراکه با فرض مثلاً M= 2 و داشتن ۲ کار، فقط گزینه ای درسته که مجموع زمان تقسیم بر M هست، گزینه ای مه میگید اشتباه هست( فکر کنم)
سوال اول الگوریتم- مجموع اعضای مجموعه: اونی بود که تقسیم بر m بعد منهای np داشت ،سوال قبلا دیده بودم
گراف کمینه: نزدم
رابطه فیبوناچی: به نظرم خودش گفته بود بازگشتی و آقای پروفسور روزن حل کرده بود و به رادیکال ان رسیده بود
پارتیشن با زمان ثابت c: گزینه logn زدم که جواد جان میگه کرمن گفته n (کرمن بگم خدا چی کارت کنه!)
برنامه کلاسها: به نظرم زمانبندی با مهلت معین بود که جناب مقسمی گفته مرتب سازی کارها logn می شود ولی بررسی کارها n^2 است که همان چیره می شود
گراف - امکانپذیر نباشد: نزدم، دقت کنید که دور نگفته بود و حلقه گفته بود و رابطه اندازه گره‌ها بزرگتر از اندازه نصف یالها در گرافهای کامل بزرگ! صادق نیست مثلا گراف کامل ۷ تایی ؛ هفت گره و بیست و یک یال دارد که هفت از بیست و یک بزرگتر نیست
هوش:
اگر آگاهانه باشد ناآگاهانه داریم و ...: نزدم، شرمنده
دانش آموزان: اونی که y مخالف z بود و آنگاه داشت و E برعکس داشت زدم
تور:اول سطحی و دومی عمقی زدم که آقا رامین(رهنمون) گفته هر دو سطحیه
قابل قبول و یکنواخت: هم قابل قبول هم یکنواخت چون بزرگتر تخمین نمی زد و کم هم نمی شد احتمالا
زبان پترانستو:شهر D زدم که از مسائل شبکه باور بود (بعد امتحان فهمیدم) با ضرب احتمالات حل شد
هرس آلفا - بتا: اونی بود که با ۹ شروع می شد -در دفترچه سی گزینه ۳ بود!
منطق:نزدم
درباره هرس + سوالی که درباره هیورستیک بود با شما موافقم.