(۰۴ اسفند ۱۳۹۷ ۱۱:۱۵ ب.ظ)mstfvi نوشته شده توسط: (04 اسفند ۱۳۹۷ ۱۰:۲۹ ب.ظ)damash نوشته شده توسط: سلام و خسته نباشید به همه.
من بیشتر سوالات رو مثل شما زدم، ولی یک تعدادی رو متفاوت زدم.
سوال اول در جستجوی ماتریس مرتب سطری ستونی، همون ماتریس یانگ از مرتبه n بودکه من متاسفاه با اینکه درست زده بودم، به اشتباه تغییرش دادم به logn
درخت جستجو ک نویز داشت رو از مرتبه n2 زدم. با این استدلال که در بدترین حالت ممکنه همه گره ها نویز پیدا کنن و درخت هم ممکنه مورب باشه و تعداد جابجایی بین پدر و فرزندها از مرتبه n2 باشه! که احتمالا استدلال غلطیه.
سوال در مورد LCS هر دو رابطه صحیح بود
سوال درخت با پیش ترتیب و پس ترتیب یکسان حداکثر ۸ خانه بود.
تریپ با ارتفاع ۴ یا ۵ بود یادم نمیاد.
رنگ زدن ۱۳۹۷ نقطه ۱۱ تا رنگ میخواست.
سوال ترتیب bfs و dfs یکسان، میشد از مرتبه nlogn
هافمن هم ۲۸ کاراکتر
در MST هم هر دو جمله یال کم خطر و پرخطر درست بودن
مرتب سازی آرایه نیمه مرتب با رادیکال n به فرجه ۴ عنصر نامرتب رو فکر میکردم با درجی بشه با مرتبه n مرتب کرد.
ترکیب ادغامی و درجی هم زدم n رادیکال n
در مورد پایگاه داده هم ۷ سوال رو جواب دادم ولی دو سوال رو شک دارم.
یک سوال که سریال پذیر بود ولی نمایی و تعارضی نبود چون کل عملیات فقط جمع و تفریق بود.
یک سوال هم این بود که بعضی از طرح های توالی پذیر هستند که با ۲PL بدست میان ولی با پروتکل درختی بدست نمیان و برعکسش هم درسته.
یک سوال هم در مورد چندنسخه سازی مبتنی بر ۲PL بود که زدم بن بست دارد.
یک سوال در مورد Undo ,Redo بود که B=200 و C و A رو یادم نمیاد.
یکی در مورد Log force operation بود که زدم قفل انحصاری X که شک دارم.
یکی هم در مورد WD و WW بود که میدونستم در حالت عادی گرسنگی ندارند، ولی نوشته بود اگه تایم اوت اضافه بشه کدوم دچار گرسنگی میشن که زدم WD که شک دارم.
یک سوال هم در مورد توالی پذیری تعارضی بود که با گراف انتظار به راحتی قابل حل بود.
سه سوال هم در مورد ARIES و بهینه سازی پرسش و پایگاه داده های WAN بود که جواب ندادم.
اون سریال پذیر نبود با همون جمع و تفریقی که انجام داد اگه تست میکردید سازگاری وجود نداشت. اون یکی رو من زدم ww با تایم اوت! بقیه رو باهاتون موافقم.
سوال سریال پذیری تکراری بود و سریال پذیر بود اما سریال پذیر تعارضی یا نمایی خیر.
جفت روش های wwو wd محرومیت ندارند اما اگر رو زمان انتظار wdتایم اوت بذاریم ممکنه موجب گرسنگی بشه ، چون انتظار برای زمانمهر کوچکتر اتفاق میفته
(۰۴ اسفند ۱۳۹۷ ۱۱:۲۸ ب.ظ)shahreyar نوشته شده توسط: (04 اسفند ۱۳۹۷ ۰۳:۰۲ ب.ظ)Fot30 نوشته شده توسط: رادیکال لاگ ان برا زمانی میشد ک ما جای عناصر نامرتب رو داشتیم.
در اون صورت با لاگ ان و درج رادیکال ان تا عنصر میشد مرتب کرد.
اما چون گفت جاهاشو نمیدونیم دقیقا نمیشه تشخیص داد .
یعنی مکانیزمی برای درک درست جای اونها وجود ندارد.
اگر بشه با مرتبه n تشخیص داد ک جای عناصر نا مرتب کجاس بله در اونصورت رادیکال n لاگ ان میشه
تو bds و dfs یه جورن نمیشد o(n) ؟
برای گراف کامل مثلا چهار راسی abcd ترتیب یکسان داره هر دو پیمایش.
در نتیجه ممکنه n^2 تا یال داشته باشه پس امگا nlogn صحیح تره.
خانه های خالی آرایه درخت دودویی هم بنظرم ۶ زدم
۶ هم ممکن بود ، ولی حداکثر فضای بلا استفاده زمانی بود ک زیر درخت راست فرزند راستش و زیر درخت چپ فرزند چپش پر باشه.در اون صورت ۸ تا صحیحه.
من هر جور فک می کنیم می بینم این سوال مشکل داره..... اگر یک درخت n نودی که همه نود ها روی یک خط راست هستن رو در نظر بگیریم.... اون وقت BFS , DFS این درخت یکسان میشه.... در حالی که تعداد n - 1 یال داره و گزینه ۴ رد میشه... آیا اشتباه میگم؟
بله اشتباه میگید چون گرافی ک به شکل مسیر باشه یا ستاره هم جزوی از جوابه و تا اینجا حرفتون درسته
ولی تو گزینه گفت مسیر است
ستاره ای هست
گزینه چهارم گفت می تواند nlogn هم باشد.
چون گزینه چهارم احتمال صدق کردتش هست درنتیجه گزینه های ۱ و ۲ قیدی تحت عنوان اختیار یا وقوع احتنال رو نیاوردن و مشکل دار میشن و از اعتبار ساقط میشن.
این سوال مستقل از صورت سوال اگه به گزینه ها دقت کنید ستاره ای بودن مسیر بودن و از مرتبه n بودن میتونن مترادف باشن ولی قطعا nlog n بودن جدا از ایناس.
یعنی اگر گراف ستاره ای باشه پس گزینه o)n( هم درست میشد و اون حالت درخت مسیر هم درست بود شک نکردین؟؟
