۱
subtitle
ارسال: #۱
  
بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
سلام دوستان
گفتم یک تاپیک ایجاد کنم تا در این قسمت هر کس جواب سوالاتی که یادش هست رو بگه تا درموردشون صحبت کنیم
در کل سوالات امسال رو چه جوری ارزیابی میکنید؟
گفتم یک تاپیک ایجاد کنم تا در این قسمت هر کس جواب سوالاتی که یادش هست رو بگه تا درموردشون صحبت کنیم
در کل سوالات امسال رو چه جوری ارزیابی میکنید؟
۲
ارسال: #۲
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
با سلام خدمت همه دوستان
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمیداد
سوال ورودی به احتمال i/1 داشت اون بازه داشت میشد.فک کنم از یک ان ام تا یک آی ام
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمیداد
سوال ورودی به احتمال i/1 داشت اون بازه داشت میشد.فک کنم از یک ان ام تا یک آی ام
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
ارسال: #۳
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۴ اسفند ۱۳۹۶ ۰۶:۵۷ ب.ظ)Fot30 نوشته شده توسط: با سلام خدمت همه دوستان
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمیداد
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
سلام
دقیقا با نظر شما در این موافق هستم: اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن.
درست میگید احتمالا چون نخونده بودم بنظرم اینطور اومد.
ممنون میشم جواب سوالاتی از سیستم عامل و پایگاه داده که یادتون هست رو هم بگید.
ارسال: #۴
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۴ اسفند ۱۳۹۶ ۰۶:۵۷ ب.ظ)Fot30 نوشته شده توسط: با سلام خدمت همه دوستاناون سوال پیشوندی و پسوندی درخت کامل و سوال یک رو چی زدین؟
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمیداد
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
راستی اون سوال lock point
و
اون سوال بالاییش چی میشد
ارسال: #۵
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۴ اسفند ۱۳۹۶ ۰۷:۱۹ ب.ظ)Seza نوشته شده توسط:(04 اسفند ۱۳۹۶ ۰۶:۵۷ ب.ظ)Fot30 نوشته شده توسط: با سلام خدمت همه دوستاناون سوال پیشوندی و پسوندی درخت کامل و سوال یک رو چی زدین؟
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمیداد
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
راستی اون سوال lock point
و
اون سوال بالاییش چی میشد
حقیقتش من خیلی سیستم عامل نخوندم و فقط ی کتاب پوران خودندم،چند سال اخیر رو آنالیز کرده بودم قبل کنکور ،متاسفانه امثال سوال تکراری ک هیچ حتی سوال مشابه هم طرح نشده بود، عملا اگر نظری بدم غیر منطقی و نادرست هست.
نگران سیستم نباشید چون من ندیدیم از دوستانم ک شانس خوبی هم برای رتبه برتر شدن دارن کسی سیستم تونسته باشه جواب بده.
در مورد سوال پایگاه بنظرم ی ردیف تراکنش داشتیم و دیگری توالی اجرای اونها،
هیچ توجهی نمیشد کرد حتی تو گزینه ها زمان ۱۰ هم بود ک حداکثر ۸ واحد زمانی زمان میبرد،بنظرم تست غلط املایی داشت و متغییز c می بایست ،b میشد.
اون الگوریتم کراسکال قطع به یقین m هست.
من صورت سوال پیمایش یادم نمیاد چی بود تردید دارم بین ۲ یا هر سه مورد
اگر گفته باشه پیمایش میان ترتیب و درخت کامل دودویی داریم بله در زمان n بنظرم بشه ایجاد کرد.
غیر این سوال پیمایش باقی گزینه های ک گفتم تا ۹۰ درصد صحیح هستن
اون سوال ک گفت یک سری آدم تو ی جا هستن ک باهم در ارتباطند و ی پیام بدیم سایرین بفهمن، پیدا کردن مولفه همبند گراف معادل دوبار پیمایش عمقی بود،در صورتی ک گراف جهت دار نبود مسئله آن پی کامل میشد.
اون درخت بی آف اس هم گمونم میشد نوه یک نود با گره از سمت دیگر درخت اشتراک ندارد.ی چیز تو این مایه ها.
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۵ ب.ظ)shivap نوشته شده توسط: یک سوال هم بود که در مورد bfs بود، یادتونه؟؟
بالاتر توضیح دادم
ارسال: #۶
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
اره منم زدم ۲ تاش درسته
چون مورد سومی گفته بود ک براساس پیمایش میانوندی درخت دودویی کامل میشه یک درخت جستجوی دودویی ساخت
ب جز این دوتای دیه رو میشد در زمان خطی حل کرد
بله
حتی اگه مرتب صعودی یا نزولی هم نبود ساخت درخت جستجوی دودویی درحالت میانگین nlogn هست و نمیشه در n ساختش
چون مورد سومی گفته بود ک براساس پیمایش میانوندی درخت دودویی کامل میشه یک درخت جستجوی دودویی ساخت
ب جز این دوتای دیه رو میشد در زمان خطی حل کرد
بله
حتی اگه مرتب صعودی یا نزولی هم نبود ساخت درخت جستجوی دودویی درحالت میانگین nlogn هست و نمیشه در n ساختش
ارسال: #۷
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
اره به نظر منم ی مشکلی داشت ولی من ی گزینه ای ک توش ۴ داشت زدم. به نظرم این درست تر بود پس اینم اشتباه ردم
ارسال: #۸
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۴ اسفند ۱۳۹۶ ۰۶:۵۷ ب.ظ)Fot30 نوشته شده توسط: با سلام خدمت همه دوستان
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمیداد
سوال ورودی به احتمال i/1 داشت اون بازه داشت میشد.فک کنم از یک ان ام تا یک آی ام
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
[font=Tahoma][font=Tahoma]سلام.
به نظر من هم الگوریتم و ساختمان داده خیلی نرمال بود. پایگاه داده هم خوب بود. البته من خیلی اشتباه داشتم.
سال گذشته رتبه ۳۴۶ آوردم که اصلا دعوت به مصاحبه نشدم. ایشالا امسال اوضاع بهتر باشه.
ارسال: #۹
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۴ اسفند ۱۳۹۶ ۱۰:۵۶ ب.ظ)Seza نوشته شده توسط: اره منم زدم ۲ تاش درسته
چون مورد سومی گفته بود ک براساس پیمایش میانوندی درخت دودویی کامل میشه یک درخت جستجوی دودویی ساخت
ب جز این دوتای دیه رو میشد در زمان خطی حل کرد
بله
حتی اگه مرتب صعودی یا نزولی هم نبود ساخت درخت جستجوی دودویی درحالت میانگین nlogn هست و نمیشه در n ساختش
به نظر من مورد سوم هم با مرتبه n حل میشه. چون پیمایش میانوندی به معنی مرتب بودن کلیدها هستش، از اونجایی که درخت کامل مدنظر سوال بود، میشه با روش میانه گیری (پارتیشن بندی) درخت جستجوی معادل اون رو پیدا کرد.
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۳ ب.ظ)shivap نوشته شده توسط: اگر یک الگوریتمی اثبات اینکه راه حلی دارد np کامل باشه اثبات اینکه راه حل نداره هم ان پی کامل است؟
به نظر من که اون هم ان پی کامل هستش. مسئله تصمیم گیری که جواب بله یا خیر داره، به نظرم وقتی میشه جواب بله، ان پی کامل باشه، جواب خیر هم ان پی کامل هستش.
به نظرم جمله دوم اون سوال هم غلط بود. چون اگه قراره مسئله اول به مسئله دوم قابل کاهش باشه، به این معنیه که مسئله اول نسبت به مسئله دوم سخت تر نیست. یعنی مسئله اول یا برابر با دومه یا آسون تر از اون.
و البته که جمله سوم درسته، چون دقیقا عکس جمله دوم بود.
(۰۶ اسفند ۱۳۹۶ ۰۸:۳۰ ق.ظ)Fot30 نوشته شده توسط:جواب سوال ۱ و ۲ رو من هم مثل شما زدم و به نظرم درست هم هستن.(06 اسفند ۱۳۹۶ ۱۲:۳۵ ق.ظ)tabestan نوشته شده توسط: سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
کدوم سوال مرتبه زمانی؟
رشد توابع؟
یا اون دومی ک دوتا رابطه بازگشتی داشت؟
ولی هردو رو توضیح میدم
رشد توابع اونی ک لگاریتم توان و نما بود از همه بیشتر بود،
بعد لگاریتم n! تو مرتبه بعدی
بعد لاگ استار
و آخرشم لاگ nساده
دقت کنید اگر جای n! در حالت لاگ استار n بود ،کمتر از لاگ n میشد.
تو اولی دقیق یادم نمیاد گزینه ها چ میشد
ولی اونی ک دوتا رابطه بازگشتی داشت
اونی ک مجموع ضرایب داخل رابطه بازگشتی از یک کمتر بود مرتبه n و
دیگری ک برابر یک بود nlogn بود.
ارسال: #۱۰
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۶ اسفند ۱۳۹۶ ۰۷:۱۴ ب.ظ)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 بود.
۰
ارسال: #۱۱
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۴ اسفند ۱۳۹۶ ۰۴:۳۴ ب.ظ)Seza نوشته شده توسط: سلام دوستانمن فکر میکنم سوالات از سالهای قبل راحتتر بودن ولی خب متاسفانه من هیچی نخونده بودم. سوالات برام آشنا بودن ولی دقیق یادم نبودن که بتونم جواب مطمئنی بدم.
گفتم یک تاپیک ایجاد کنم تا در این قسمت هر کس جواب سوالاتی که یادش هست رو بگه تا درموردشون صحبت کنیم
در کل سوالات امسال رو چه جوری ارزیابی میکنید؟
خودتون چه کردید؟
جواب سوال اول الگوریتم چی میشد؟ گزینه ۲ یا ۴؟
۰
ارسال: #۱۲
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
سلام
ایشالا همه روز خوبی داشتن
واقعا ینی از سالای قبل آسون تر بود
سوالای پایگاه تا حد زیادی تکراری بود (اگه نگیم همش) ولی سیستم عامل به نظر من سخت بود (شاید هم نه) و استعداد هم من فقط تونستم ۱۰ رو جواب بدم. ولی سوالای الگوریتم و ساختمان بگی نگی خوب بودن.
امید به خدا
ایشالا همه روز خوبی داشتن
واقعا ینی از سالای قبل آسون تر بود
سوالای پایگاه تا حد زیادی تکراری بود (اگه نگیم همش) ولی سیستم عامل به نظر من سخت بود (شاید هم نه) و استعداد هم من فقط تونستم ۱۰ رو جواب بدم. ولی سوالای الگوریتم و ساختمان بگی نگی خوب بودن.
امید به خدا
ارسال: #۱۳
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۴ اسفند ۱۳۹۶ ۰۶:۵۶ ب.ظ)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 زدم اما. خدا رحم کنه
ارسال: #۱۴
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
توی نرم افزار در مورد تعارضی و اینچیزا سوال نداشتیم مگر اینکه پشت برگه بوده باشه
(۰۴ اسفند ۱۳۹۶ ۰۷:۱۹ ب.ظ)Seza نوشته شده توسط:lock point ، برای هر تراکنش جایی که اولین قفل باز میشود، بایستی پشت سرهم می بودن. من که زدم ۵و۶ فکر کنم(04 اسفند ۱۳۹۶ ۰۶:۵۷ ب.ظ)Fot30 نوشته شده توسط: با سلام خدمت همه دوستاناون سوال پیشوندی و پسوندی درخت کامل و سوال یک رو چی زدین؟
در حالت کلی کنکور هیچ وقت ساده نیست.
دو حالت وجود داره،اول اینکه نخونده باشید و برید سر جلسه حس میکنید سوالات آشنا هستن
ولی در واقع سوالات غالبا سهل و ممتنع هستند.
حالت دوم اینکه شما خونده باشید و نظر بدید این بهتره و قابل استناد.
اما سوالات تا جایی که یادمه از الگوریتم و ساختمان حد نرمال سوال دادن
سوال دوم پیچیدگی زمانیش اونی که مجموع ضرایبش مساوی با یک بود nlogn و دیگری n میشد،
سوال هافمن گمونم ۱۷
اون هیپ از مرتبه o(n(
هیپ آرایه ای ۷۱ نابجایی
سوال بعدیش n بار استفاده از ریورس
سوال که کمترین n برای عدم پاسخ درست الگوریتم ۵ بود
سوال پیدا کردن میانه از مرتبهnlogn
الگوریتم کراسکال از مرتبه m میشد
دوتا از اون تغییرات در وزن گراف طراحی مسیر رو تغییر نمیداد
ضرب ماتریس ۴۰۵
اون بازی هم گمونم loglogn
اون طول مسیر به اندازه kرو تردید داشتم نزدم
دیگه خاطرم نمیاد سوالات چی بودن
درس سیستم عامل از منبع جدیدی سوال طرح شد ک برای من شناخته شده نبود و طبعا نظری ندارم.
درس پایگاه حدودا ۴ سوال تکراری و مشابه نسبت به سال ۹۴ و ۹۶ داشت.
در مجموع غیر از سیستم عامل سوالات دارای بالانس معقول و منطقی بود.
موفق و پیروز باشید
راستی اون سوال lock point
و
اون سوال بالاییش چی میشد
ارسال: #۱۵
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
سوال کروسکال همونی بود که گفته بود وزن یال ها یک و دو هستند؟ در واقع ما میتونیم همه رو با اضافه کردن یک سری راس و یال همون وزن یک بگیریم و بعد جون وزن یال ها با هم یکی است هر زیر مجموعهm تایی یک mst است؟ البته میتونیم بگیم که هر پیمایشی رو گراف که در اون صورت میشه باbfs یا dfs، من m زدم اما. خدا رحم کنه
[/quote]
منم m زدم ولی اینجوری که چون همه اعداد توی یک بازه مشخصی هستند مرتب سازیشون با مرتب سازی شمارشی خطی بدست میاد پس کراسکالم هطی میشه
[/quote]
منم m زدم ولی اینجوری که چون همه اعداد توی یک بازه مشخصی هستند مرتب سازیشون با مرتب سازی شمارشی خطی بدست میاد پس کراسکالم هطی میشه
ارسال: #۱۶
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
lock point ، برای هر تراکنش جایی که اولین قفل باز میشود، بایستی پشت سرهم می بودن. من که زدم ۵و۶ فکر کنم
[/quote]
به نظر من اشتباه بود گزینه هاش ولی از بین گزینه های موجود فقط میشد همین ۵ و ۶ رو زد
[/quote]
به نظر من اشتباه بود گزینه هاش ولی از بین گزینه های موجود فقط میشد همین ۵ و ۶ رو زد
۰
ارسال: #۱۷
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
اما قطعا واسه شما هم بوده
سوالی که میگفت با timestamp کار میکنه داشتید؟
همون کهگفته بود آیا توالی پذیر هست یا نه؟
سوالی که میگفت با timestamp کار میکنه داشتید؟
همون کهگفته بود آیا توالی پذیر هست یا نه؟
ارسال: #۱۸
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
۰
ارسال: #۱۹
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
اگر یک الگوریتمی اثبات اینکه راه حلی دارد np کامل باشه اثبات اینکه راه حل نداره هم ان پی کامل است؟
ارسال: #۲۰
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۴ اسفند ۱۳۹۶ ۰۸:۱۳ ب.ظ)shivap نوشته شده توسط: اگر یک الگوریتمی اثبات اینکه راه حلی دارد np کامل باشه اثبات اینکه راه حل نداره هم ان پی کامل است؟
من کتاب clrs نگاه کردم ، گفنه "هنوز هیچ کس نمی داند که آیا NP-c تحت عمل مکمل بسته است یا خیر"
(۰۴ اسفند ۱۳۹۶ ۰۷:۵۱ ب.ظ)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))
[/quote]
اون سوال پیشوندی و پسوندی درخت کامل و سوال یک رو چی زدین؟
تحلیل من این بود که ممکن است ترتیب پیمایش جوری باشد که به صورت صعودی یا نزولی مرتب شده باشند ارتفاع درخت دودویی (O(n)) میشود و زمان ایجادش O(n^2) ولی دوتای دیگر رو میشود در O(n)ا تبدیل کرد
۰
ارسال: #۲۱
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
یک سوال هم بود که در مورد bfs بود، یادتونه؟؟
ارسال: #۲۲
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
ارسال: #۲۳
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
ارسال: #۲۴
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۵ اسفند ۱۳۹۶ ۱۱:۵۱ ق.ظ)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]
۰
ارسال: #۲۵
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
کلا جواب دادن به سوالای استعداد ریسکه، طراج با یه سری فرض تو ذهن خودش سوالو طراحی میکنه
ارسال: #۲۶
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
۰
ارسال: #۲۷
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
ارسال: #۲۸
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۶ اسفند ۱۳۹۶ ۱۲:۳۵ ق.ظ)tabestan نوشته شده توسط: سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
کدوم سوال مرتبه زمانی؟
رشد توابع؟
یا اون دومی ک دوتا رابطه بازگشتی داشت؟
ولی هردو رو توضیح میدم
رشد توابع اونی ک لگاریتم توان و نما بود از همه بیشتر بود،
بعد لگاریتم n! تو مرتبه بعدی
بعد لاگ استار
و آخرشم لاگ nساده
دقت کنید اگر جای n! در حالت لاگ استار n بود ،کمتر از لاگ n میشد.
تو اولی دقیق یادم نمیاد گزینه ها چ میشد
ولی اونی ک دوتا رابطه بازگشتی داشت
اونی ک مجموع ضرایب داخل رابطه بازگشتی از یک کمتر بود مرتبه n و
دیگری ک برابر یک بود nlogn بود.
ارسال: #۲۹
  
RE: بررسی سوالات ازمون دکترای سال ۹۷-گرایش نرم افزار
(۰۶ اسفند ۱۳۹۶ ۰۸:۳۰ ق.ظ)Fot30 نوشته شده توسط:ممنون بابت توضیحات(06 اسفند ۱۳۹۶ ۱۲:۳۵ ق.ظ)tabestan نوشته شده توسط: سلام به همگی
میشه بگید که سوال مرتبه زمانی کدوم گزینه درست بود؟
کدوم سوال مرتبه زمانی؟
رشد توابع؟
یا اون دومی ک دوتا رابطه بازگشتی داشت؟
ولی هردو رو توضیح میدم
رشد توابع اونی ک لگاریتم توان و نما بود از همه بیشتر بود،
بعد لگاریتم n! تو مرتبه بعدی
بعد لاگ استار
و آخرشم لاگ nساده
دقت کنید اگر جای n! در حالت لاگ استار n بود ،کمتر از لاگ n میشد.
تو اولی دقیق یادم نمیاد گزینه ها چ میشد
ولی اونی ک دوتا رابطه بازگشتی داشت
اونی ک مجموع ضرایب داخل رابطه بازگشتی از یک کمتر بود مرتبه n و
دیگری ک برابر یک بود nlogn بود.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close