صفحه‌ها: ۱ ۲
(۰۴ اسفند ۱۳۹۶ ۰۷:۱۹ ب.ظ)Seza نوشته شده توسط:(04 اسفند ۱۳۹۶ ۰۶:۵۷ ب.ظ)Fot30 نوشته شده توسط: با سلام خدمت همه دوستاناون سوال پیشوندی و پسوندی درخت کامل و سوال یک رو چی زدین؟
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمی‌داد
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
راستی اون سوال lock point
و
اون سوال بالاییش چی میشد
حقیقتش من خیلی سیستم عامل نخوندم و فقط ی کتاب پوران خودندم،چند سال اخیر رو آنالیز کرده بودم قبل کنکور ،متاسفانه امثال سوال تکراری ک هیچ حتی سوال مشابه هم طرح نشده بود، عملا اگر نظری بدم غیر منطقی و نادرست هست.
نگران سیستم نباشید چون من ندیدیم از دوستانم ک شانس خوبی هم برای رتبه برتر شدن دارن کسی سیستم تونسته باشه جواب بده.
در مورد سوال پایگاه بنظرم ی ردیف تراکنش داشتیم و دیگری توالی اجرای اونها،
هیچ توجهی نمیشد کرد حتی تو گزینه ها زمان ۱۰ هم بود ک حداکثر ۸ واحد زمانی زمان میبرد،بنظرم تست غلط املایی داشت و متغییز c می بایست ،b میشد.
اون الگوریتم کراسکال قطع به یقین m هست.
من صورت سوال پیمایش یادم نمیاد چی بود تردید دارم بین ۲ یا هر سه مورد
اگر گفته باشه پیمایش میان ترتیب و درخت کامل دودویی داریم بله در زمان n بنظرم بشه ایجاد کرد.
غیر این سوال پیمایش باقی گزینه های ک گفتم تا ۹۰ درصد صحیح هستن
اون سوال ک گفت یک سری آدم تو ی جا هستن ک باهم در ارتباطند و ی پیام بدیم سایرین بفهمن، پیدا کردن مولفه همبند گراف معادل دوبار پیمایش عمقی بود،در صورتی ک گراف جهت دار نبود مسئله آن پی کامل میشد.
اون درخت بی آف اس هم گمونم میشد نوه یک نود با گره از سمت دیگر درخت اشتراک ندارد.ی چیز تو این مایه ها.
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۵ ب.ظ)shivap نوشته شده توسط: یک سوال هم بود که در مورد bfs بود، یادتونه؟؟
بالاتر توضیح دادم
کلا جواب دادن به سوالای استعداد ریسکه، طراج با یه سری فرض تو ذهن خودش سوالو طراحی میکنه
اره منم زدم ۲ تاش درسته
چون مورد سومی گفته بود ک براساس پیمایش میانوندی درخت دودویی کامل میشه یک درخت جستجوی دودویی ساخت
ب جز این دوتای دیه رو میشد در زمان خطی حل کرد
بله
حتی اگه مرتب صعودی یا نزولی هم نبود ساخت درخت جستجوی دودویی درحالت میانگین nlogn هست و نمیشه در n ساختش
(۰۴ اسفند ۱۳۹۶ ۱۰:۲۴ ب.ظ)nazanin2020 نوشته شده توسط: کلا جواب دادن به سوالای استعداد ریسکه، طراج با یه سری فرض تو ذهن خودش سوالو طراحی میکنه
بله واقعا
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۵ ب.ظ)shivap نوشته شده توسط: یک سوال هم بود که در مورد bfs بود، یادتونه؟؟من اون گزینه ک میگفت گره با نوه ش هیچ اشتراک بازه ای نداره همچین چیزی
رو زدم
(۰۵ اسفند ۱۳۹۶ ۰۱:۱۹ ق.ظ)nazanin2020 نوشته شده توسط:(04 اسفند ۱۳۹۶ ۰۸:۱۵ ب.ظ)shivap نوشته شده توسط: یک سوال هم بود که در مورد bfs بود، یادتونه؟؟من اون گزینه ک میگفت گره با نوه ش هیچ اشتراک بازه ای نداره همچین چیزی
درسته
اره به نظر منم ی مشکلی داشت ولی من ی گزینه ای ک توش ۴ داشت زدم. به نظرم این درست تر بود پس اینم اشتباه ردم
(۰۴ اسفند ۱۳۹۶ ۰۶:۵۷ ب.ظ)Fot30 نوشته شده توسط: با سلام خدمت همه دوستان
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمی‌داد
سوال ورودی به احتمال i/1 داشت اون بازه داشت میشد.فک کنم از یک ان ام تا یک آی ام
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
[font=Tahoma][font=Tahoma]سلام.
به نظر من هم الگوریتم و ساختمان داده خیلی نرمال بود. پایگاه داده هم خوب بود. البته من خیلی اشتباه داشتم.
سال گذشته رتبه ۳۴۶ آوردم که اصلا دعوت به مصاحبه نشدم. ایشالا امسال اوضاع بهتر باشه.
(۰۵ اسفند ۱۳۹۶ ۱۱:۵۱ ق.ظ)Fot30 نوشته شده توسط:(05 اسفند ۱۳۹۶ ۰۱:۱۹ ق.ظ)nazanin2020 نوشته شده توسط:(04 اسفند ۱۳۹۶ ۰۸:۱۵ ب.ظ)shivap نوشته شده توسط: یک سوال هم بود که در مورد bfs بود، یادتونه؟؟من اون گزینه ک میگفت گره با نوه ش هیچ اشتراک بازه ای نداره همچین چیزی
درسته
(۰۶ اسفند ۱۳۹۶ ۱۲:۱۶ ق.ظ)shivap نوشته شده توسط:(05 اسفند ۱۳۹۶ ۱۱:۵۱ ق.ظ)Fot30 نوشته شده توسط:(05 اسفند ۱۳۹۶ ۰۱:۱۹ ق.ظ)nazanin2020 نوشته شده توسط:(04 اسفند ۱۳۹۶ ۰۸:۱۵ ب.ظ)shivap نوشته شده توسط: یک سوال هم بود که در مورد bfs بود، یادتونه؟؟من اون گزینه ک میگفت گره با نوه ش هیچ اشتراک بازه ای نداره همچین چیزی
درسته
فکر کنم منم همینو زدم چون اول والد از صف میاد بیرون و بعد فرزندش میره داخل صف
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۹ ب.ظ)izeh_ninja نوشته شده توسط:اون سوال پیشوندی و پسوندی درخت کامل و سوال یک رو چی زدین؟(04 اسفند ۱۳۹۶ ۰۸:۱۳ ب.ظ)shivap نوشته شده توسط: اگر یک الگوریتمی اثبات اینکه راه حلی دارد np کامل باشه اثبات اینکه راه حل نداره هم ان پی کامل است؟
من کتاب clrs نگاه کردم ، گفنه "هنوز هیچ کس نمی داند که آیا NP-c تحت عمل مکمل بسته است یا خیر" آها یعنی اگر درست گفته بود دیگه که اگر یک مسئله ای np compelete باشد چه اثبات اینکه راه حل دارد np است و چه اثبات اینکه راه حل ندارد. درسته؟
(۰۴ اسفند ۱۳۹۶ ۰۷:۵۱ ب.ظ)shivap نوشته شده توسط:(04 اسفند ۱۳۹۶ ۰۶:۵۶ ب.ظ)izeh_ninja نوشته شده توسط: سلام
ایشالا همه روز خوبی داشتن
واقعا ینی از سالای قبل آسون تر بود
سوالای پایگاه تا حد زیادی تکراری بود (اگه نگیم همش) ولی سیستم عامل به نظر من سخت بود (شاید هم نه) و استعداد هم من فقط تونستم ۱۰ رو جواب بدم
امید به خدا
به نظر من استعدادش واقعا بد بود. البته من وقت هم کم آوردم. و کلا از استعداد متنفرم. یک درس بسخود و بی سر و ته
سوالات اصلا راحت نبودن دوست عزیز. شما نخوندین گ به نظرتون همش آشنا می اومده!!
سوالات ساختمان داده و طراحی الگوریتم مهندسی فناوری اطلاعات گاقعا نسبت به سالهای قبل سخت تر بود و اصولا هیچ شباهتی به سالهای قبل نداشت و برخلاف سالهای قبل اصلا سوالی نداشت که راحت بشه حلش کرد.
سوالات ساختمان داده ما و شما و همینطور پایگاه داده همپوشانی دارند.
سوال اینکه اگر یک schedule تعارضی باشد نمایی و نتیجه ای هست چی میشد؟ همین میشد؟
سوالی داشتید که یکی از گزینه هاش np-hard باشه؟ گزینه آخرش، یادم نیست سوالش چی بود، تو ساختمان داده، چی بود اون؟
من خیلی ناراحتم.
(۰۴ اسفند ۱۳۹۶ ۰۷:۱۹ ب.ظ)Seza نوشته شده توسط:(04 اسفند ۱۳۹۶ ۰۶:۵۷ ب.ظ)Fot30 نوشته شده توسط: با سلام خدمت همه دوستاناون سوال پیشوندی و پسوندی درخت کامل و سوال یک رو چی زدین؟
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمی‌داد
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
راستی اون سوال lock point
و
اون سوال بالاییش چی میشد
سوال کروسکال همونی بود که گفته بود وزن یال ها یک و دو هستند؟ در واقع ما میتونیم همه رو با اضافه کردن یک سری راس و یال همون وزن یک بگیریم و بعد جون وزن یال ها با هم یکی است هر زیر مجموعهm تایی یک mst است؟ البته میتونیم بگیم که هر پیمایشی رو گراف که در اون صورت میشه باbfs یا dfs، من m زدم اما. خدا رحم کنه
چون وزن یال های ۱ و ۲ بود می توان از مرتب سازی شمارشی استفاده کرد (O(n)) و چون تعداد یال ها می تواند بیشتر از گره ها بشود، زمان الگوریتم وابسته با زمان بررسی یالها می شود (o(m))
تحلیل من این بود که ممکن است ترتیب پیمایش جوری باشد که به صورت صعودی یا نزولی مرتب شده باشند ارتفاع درخت دودویی (O(n)) میشود و زمان ایجادش O(n^2) ولی دوتای دیگر رو میشود در O(n)ا تبدیل کرد
[/quote]
سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
(۰۶ اسفند ۱۳۹۶ ۱۲:۳۵ ق.ظ)tabestan نوشته شده توسط: سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
کدوم سوال مرتبه زمانی؟
رشد توابع؟
یا اون دومی ک دوتا رابطه بازگشتی داشت؟
ولی هردو رو توضیح میدم
رشد توابع اونی ک لگاریتم توان و نما بود از همه بیشتر بود،
بعد لگاریتم n! تو مرتبه بعدی
بعد لاگ استار
و آخرشم لاگ nساده
دقت کنید اگر جای n! در حالت لاگ استار n بود ،کمتر از لاگ n میشد.
تو اولی دقیق یادم نمیاد گزینه ها چ میشد
ولی اونی ک دوتا رابطه بازگشتی داشت
اونی ک مجموع ضرایب داخل رابطه بازگشتی از یک کمتر بود مرتبه n و
دیگری ک برابر یک بود nlogn بود.
(۰۶ اسفند ۱۳۹۶ ۰۸:۳۰ ق.ظ)Fot30 نوشته شده توسط:ممنون بابت توضیحات(06 اسفند ۱۳۹۶ ۱۲:۳۵ ق.ظ)tabestan نوشته شده توسط: سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
کدوم سوال مرتبه زمانی؟
رشد توابع؟
یا اون دومی ک دوتا رابطه بازگشتی داشت؟
ولی هردو رو توضیح میدم
رشد توابع اونی ک لگاریتم توان و نما بود از همه بیشتر بود،
بعد لگاریتم n! تو مرتبه بعدی
بعد لاگ استار
و آخرشم لاگ nساده
دقت کنید اگر جای n! در حالت لاگ استار n بود ،کمتر از لاگ n میشد.
تو اولی دقیق یادم نمیاد گزینه ها چ میشد
ولی اونی ک دوتا رابطه بازگشتی داشت
اونی ک مجموع ضرایب داخل رابطه بازگشتی از یک کمتر بود مرتبه n و
دیگری ک برابر یک بود nlogn بود.
(۰۴ اسفند ۱۳۹۶ ۱۰:۵۶ ب.ظ)Seza نوشته شده توسط: اره منم زدم ۲ تاش درسته
چون مورد سومی گفته بود ک براساس پیمایش میانوندی درخت دودویی کامل میشه یک درخت جستجوی دودویی ساخت
ب جز این دوتای دیه رو میشد در زمان خطی حل کرد
بله
حتی اگه مرتب صعودی یا نزولی هم نبود ساخت درخت جستجوی دودویی درحالت میانگین nlogn هست و نمیشه در n ساختش
به نظر من مورد سوم هم با مرتبه n حل میشه. چون پیمایش میانوندی به معنی مرتب بودن کلیدها هستش، از اونجایی که درخت کامل مدنظر سوال بود، میشه با روش میانه گیری (پارتیشن بندی) درخت جستجوی معادل اون رو پیدا کرد.
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۳ ب.ظ)shivap نوشته شده توسط: اگر یک الگوریتمی اثبات اینکه راه حلی دارد np کامل باشه اثبات اینکه راه حل نداره هم ان پی کامل است؟
به نظر من که اون هم ان پی کامل هستش. مسئله تصمیم گیری که جواب بله یا خیر داره، به نظرم وقتی میشه جواب بله، ان پی کامل باشه، جواب خیر هم ان پی کامل هستش.
به نظرم جمله دوم اون سوال هم غلط بود. چون اگه قراره مسئله اول به مسئله دوم قابل کاهش باشه، به این معنیه که مسئله اول نسبت به مسئله دوم سخت تر نیست. یعنی مسئله اول یا برابر با دومه یا آسون تر از اون.
و البته که جمله سوم درسته، چون دقیقا عکس جمله دوم بود.
(۰۶ اسفند ۱۳۹۶ ۰۸:۳۰ ق.ظ)Fot30 نوشته شده توسط:جواب سوال ۱ و ۲ رو من هم مثل شما زدم و به نظرم درست هم هستن.(06 اسفند ۱۳۹۶ ۱۲:۳۵ ق.ظ)tabestan نوشته شده توسط: سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
کدوم سوال مرتبه زمانی؟
رشد توابع؟
یا اون دومی ک دوتا رابطه بازگشتی داشت؟
ولی هردو رو توضیح میدم
رشد توابع اونی ک لگاریتم توان و نما بود از همه بیشتر بود،
بعد لگاریتم n! تو مرتبه بعدی
بعد لاگ استار
و آخرشم لاگ nساده
دقت کنید اگر جای n! در حالت لاگ استار n بود ،کمتر از لاگ n میشد.
تو اولی دقیق یادم نمیاد گزینه ها چ میشد
ولی اونی ک دوتا رابطه بازگشتی داشت
اونی ک مجموع ضرایب داخل رابطه بازگشتی از یک کمتر بود مرتبه n و
دیگری ک برابر یک بود nlogn بود.
(۰۶ اسفند ۱۳۹۶ ۰۷:۱۴ ب.ظ)damash نوشته شده توسط:(04 اسفند ۱۳۹۶ ۱۰:۵۶ ب.ظ)Seza نوشته شده توسط: اره منم زدم ۲ تاش درسته
چون مورد سومی گفته بود ک براساس پیمایش میانوندی درخت دودویی کامل میشه یک درخت جستجوی دودویی ساخت
ب جز این دوتای دیه رو میشد در زمان خطی حل کرد
بله
حتی اگه مرتب صعودی یا نزولی هم نبود ساخت درخت جستجوی دودویی درحالت میانگین nlogn هست و نمیشه در n ساختش
به نظر من مورد سوم هم با مرتبه n حل میشه. چون پیمایش میانوندی به معنی مرتب بودن کلیدها هستش، از اونجایی که درخت کامل مدنظر سوال بود، میشه با روش میانه گیری (پارتیشن بندی) درخت جستجوی معادل اون رو پیدا کرد.
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۳ ب.ظ)shivap نوشته شده توسط: اگر یک الگوریتمی اثبات اینکه راه حلی دارد np کامل باشه اثبات اینکه راه حل نداره هم ان پی کامل است؟
به نظر من که اون هم ان پی کامل هستش. مسئله تصمیم گیری که جواب بله یا خیر داره، به نظرم وقتی میشه جواب بله، ان پی کامل باشه، جواب خیر هم ان پی کامل هستش.
به نظرم جمله دوم اون سوال هم غلط بود. چون اگه قراره مسئله اول به مسئله دوم قابل کاهش باشه، به این معنیه که مسئله اول نسبت به مسئله دوم سخت تر نیست. یعنی مسئله اول یا برابر با دومه یا آسون تر از اون.
و البته که جمله سوم درسته، چون دقیقا عکس جمله دوم بود.
(۰۶ اسفند ۱۳۹۶ ۰۸:۳۰ ق.ظ)Fot30 نوشته شده توسط:جواب سوال ۱ و ۲ رو من هم مثل شما زدم و به نظرم درست هم هستن.(06 اسفند ۱۳۹۶ ۱۲:۳۵ ق.ظ)tabestan نوشته شده توسط: سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
کدوم سوال مرتبه زمانی؟
رشد توابع؟
یا اون دومی ک دوتا رابطه بازگشتی داشت؟
ولی هردو رو توضیح میدم
رشد توابع اونی ک لگاریتم توان و نما بود از همه بیشتر بود،
بعد لگاریتم n! تو مرتبه بعدی
بعد لاگ استار
و آخرشم لاگ nساده
دقت کنید اگر جای n! در حالت لاگ استار n بود ،کمتر از لاگ n میشد.
تو اولی دقیق یادم نمیاد گزینه ها چ میشد
ولی اونی ک دوتا رابطه بازگشتی داشت
اونی ک مجموع ضرایب داخل رابطه بازگشتی از یک کمتر بود مرتبه n و
دیگری ک برابر یک بود nlogn بود.
دوستان در این قسمت به بررسی سوالا بپردازیم که دو جا نباشه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۶ اسفند ۱۳۹۶ ۰۷:۱۴ ب.ظ)damash نوشته شده توسط:خب با این وجود بازم ساخت درخت جستجوی دورویی به nlogn نیاز داره نه n(04 اسفند ۱۳۹۶ ۱۰:۵۶ ب.ظ)Seza نوشته شده توسط: اره منم زدم ۲ تاش درسته
چون مورد سومی گفته بود ک براساس پیمایش میانوندی درخت دودویی کامل میشه یک درخت جستجوی دودویی ساخت
ب جز این دوتای دیه رو میشد در زمان خطی حل کرد
بله
حتی اگه مرتب صعودی یا نزولی هم نبود ساخت درخت جستجوی دودویی درحالت میانگین nlogn هست و نمیشه در n ساختش
به نظر من مورد سوم هم با مرتبه n حل میشه. چون پیمایش میانوندی به معنی مرتب بودن کلیدها هستش، از اونجایی که درخت کامل مدنظر سوال بود، میشه با روش میانه گیری (پارتیشن بندی) درخت جستجوی معادل اون رو پیدا کرد.
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۳ ب.ظ)shivap نوشته شده توسط: اگر یک الگوریتمی اثبات اینکه راه حلی دارد np کامل باشه اثبات اینکه راه حل نداره هم ان پی کامل است؟
به نظر من که اون هم ان پی کامل هستش. مسئله تصمیم گیری که جواب بله یا خیر داره، به نظرم وقتی میشه جواب بله، ان پی کامل باشه، جواب خیر هم ان پی کامل هستش.
به نظرم جمله دوم اون سوال هم غلط بود. چون اگه قراره مسئله اول به مسئله دوم قابل کاهش باشه، به این معنیه که مسئله اول نسبت به مسئله دوم سخت تر نیست. یعنی مسئله اول یا برابر با دومه یا آسون تر از اون.
و البته که جمله سوم درسته، چون دقیقا عکس جمله دوم بود.
(۰۶ اسفند ۱۳۹۶ ۰۸:۳۰ ق.ظ)Fot30 نوشته شده توسط:جواب سوال ۱ و ۲ رو من هم مثل شما زدم و به نظرم درست هم هستن.(06 اسفند ۱۳۹۶ ۱۲:۳۵ ق.ظ)tabestan نوشته شده توسط: سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
کدوم سوال مرتبه زمانی؟
رشد توابع؟
یا اون دومی ک دوتا رابطه بازگشتی داشت؟
ولی هردو رو توضیح میدم
رشد توابع اونی ک لگاریتم توان و نما بود از همه بیشتر بود،
بعد لگاریتم n! تو مرتبه بعدی
بعد لاگ استار
و آخرشم لاگ nساده
دقت کنید اگر جای n! در حالت لاگ استار n بود ،کمتر از لاگ n میشد.
تو اولی دقیق یادم نمیاد گزینه ها چ میشد
ولی اونی ک دوتا رابطه بازگشتی داشت
اونی ک مجموع ضرایب داخل رابطه بازگشتی از یک کمتر بود مرتبه n و
دیگری ک برابر یک بود nlogn بود.