(۰۳ اسفند ۱۳۹۷ ۰۴:۱۶ ب.ظ)Fot30 نوشته شده توسط:  سلام
تحلیل کلی سوالات امروز
درس ساختمان سوال متوسط نداشت بنظرم ، یا سخت یا ساده.مباحث گراف و مرتب سازی شاکله اصلی سوالات بود. الیته یک سوال هم تکراری داشت.
سیستم تقریبا مثل همیشه با یک سوال تکراری .
پایگاه با سه سوال تکراری پرچمدار بود ولی غیر تکراری های مفهومی خوبی داشت.

بنظرم کلید سوالات
سوال اول در جستجوی ماتریس مرتب سطری ستونی از مرتبه n
سوال دوم هر دو رابطه صحیح
سوال سوم یادم نمیاد
سوال ۴ ماکس فلو اونی ک kc ضرب داشت
ارایه درختی حداکثر ۸ خانه
ارزش رئوس گراف m+n
درخت جستجو ک نویز داشت از مرتبه n
رنگ زدن ۱۱ تا
اونی ک گفت تو bfs و dfs ی جورن میشد از مرتبه nlogn گراف کامل مثال نقض سه گزینه دیگه است
هافمن هم ۲۸ کاراکتر
اون یال کم خطر پرخطر هم درست درست
جانسون هم ۰ ارجاع به
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


ی مرتب سازی بود رادیکال n به فرجه ۴ میشد nlog n
اون ادغامی ک درجی مرتب میشد تا سطح رادیکال n میشد n رادیکال n
مسئله پیدا کردن کوتاهترین مسیر در گراف که همه رئوس رک یکبار ببینه گمونم np_hard هستش

اینا یادم بود
دیگه باقیش خاطرم نیس بگید شاید بیاد تو ذهنم

(۰۴ اسفند ۱۳۹۷ ۰۳:۰۲ ب.ظ)Fot30 نوشته شده توسط:  رادیکال لاگ ان برا زمانی میشد ک ما جای عناصر نامرتب رو داشتیم.
در اون صورت با لاگ ان و درج رادیکال ان تا عنصر میشد مرتب کرد.
اما چون گفت جاهاشو نمیدونیم دقیقا نمیشه تشخیص داد .
یعنی مکانیزمی برای درک درست جای اونها وجود ندارد.
اگر بشه با مرتبه n تشخیص داد ک جای عناصر نا مرتب کجاس بله در اونصورت رادیکال n لاگ ان میشه

تو bds و dfs یه جورن نمیشد o(n) ؟
برای گراف کامل مثلا چهار راسی abcd ترتیب یکسان داره هر دو پیمایش.
در نتیجه ممکنه n^2 تا یال داشته باشه پس امگا nlogn صحیح تره.

خانه های خالی آرایه درخت دودویی هم بنظرم ۶ زدم
۶ هم ممکن بود ، ولی حداکثر فضای بلا استفاده زمانی بود ک زیر درخت راست فرزند راستش و زیر درخت چپ فرزند چپش پر باشه.در اون صورت ۸ تا صحیحه.

---

(۰۴ اسفند ۱۳۹۷ ۰۷:۳۵ ب.ظ)mstfvi نوشته شده توسط:  

(04 اسفند ۱۳۹۷ ۰۳:۰۲ ب.ظ)Fot30 نوشته شده توسط:  رادیکال لاگ ان برا زمانی میشد ک ما جای عناصر نامرتب رو داشتیم.
در اون صورت با لاگ ان و درج رادیکال ان تا عنصر میشد مرتب کرد.
اما چون گفت جاهاشو نمیدونیم دقیقا نمیشه تشخیص داد .
یعنی مکانیزمی برای درک درست جای اونها وجود ندارد.
اگر بشه با مرتبه n تشخیص داد ک جای عناصر نا مرتب کجاس بله در اونصورت رادیکال n لاگ ان میشه

تو bds و dfs یه جورن نمیشد o(n) ؟
برای گراف کامل مثلا چهار راسی abcd ترتیب یکسان داره هر دو پیمایش.
در نتیجه ممکنه n^2 تا یال داشته باشه پس امگا nlogn صحیح تره.

خانه های خالی آرایه درخت دودویی هم بنظرم ۶ زدم
۶ هم ممکن بود ، ولی حداکثر فضای بلا استفاده زمانی بود ک زیر درخت راست فرزند راستش و زیر درخت چپ فرزند چپش پر باشه.در اون صورت ۸ تا صحیحه.

---

با o)n( میشه جاشونو مشخص کرد بشرط اینکه همگی نامرتبها پشت سر هم باشند. نمیشه؟

برای آرایه درخت گفته بود حداکثر؟

(۰۴ اسفند ۱۳۹۷ ۰۹:۵۸ ب.ظ)marzieh_kheirabadi نوشته شده توسط:  سلام دوستان
سوال الگوریتم لمپارت جوابش چی میشه؟
انتخاب رهبر؟
یه الگوریتم داده بود که بن بست یا گرسنگی یا اینکه هیچ مشکلی نداره و درسته؟
جواب سوالات رو کسی میدونه؟

(۰۴ اسفند ۱۳۹۷ ۰۹:۳۹ ب.ظ)Fot30 نوشته شده توسط:  

(04 اسفند ۱۳۹۷ ۰۷:۳۵ ب.ظ)mstfvi نوشته شده توسط:  

(04 اسفند ۱۳۹۷ ۰۳:۰۲ ب.ظ)Fot30 نوشته شده توسط:  رادیکال لاگ ان برا زمانی میشد ک ما جای عناصر نامرتب رو داشتیم.
در اون صورت با لاگ ان و درج رادیکال ان تا عنصر میشد مرتب کرد.
اما چون گفت جاهاشو نمیدونیم دقیقا نمیشه تشخیص داد .
یعنی مکانیزمی برای درک درست جای اونها وجود ندارد.
اگر بشه با مرتبه n تشخیص داد ک جای عناصر نا مرتب کجاس بله در اونصورت رادیکال n لاگ ان میشه

تو bds و dfs یه جورن نمیشد o(n) ؟
برای گراف کامل مثلا چهار راسی abcd ترتیب یکسان داره هر دو پیمایش.
در نتیجه ممکنه n^2 تا یال داشته باشه پس امگا nlogn صحیح تره.

خانه های خالی آرایه درخت دودویی هم بنظرم ۶ زدم
۶ هم ممکن بود ، ولی حداکثر فضای بلا استفاده زمانی بود ک زیر درخت راست فرزند راستش و زیر درخت چپ فرزند چپش پر باشه.در اون صورت ۸ تا صحیحه.

---

با o)n( میشه جاشونو مشخص کرد بشرط اینکه همگی نامرتبها پشت سر هم باشند. نمیشه؟

برای آرایه درخت گفته بود حداکثر؟

اینکه چطور بشه با مرتبه n جای نامرتب ها رو تشخیص داد بنظرم ممکن نیس چون وقتی بخواهیم جای درست عنصری رو پیدا کنیم باید یا مرتب بشه یا بعنوان محور در افراز باشه.
فرض کن وسط ی آرایه مرتب عناصر نامرتب داشته باشه مثل ۴،۵،۶،۷،۸،۱،۲،۳،۹،۱۰
ایتجا ۱،۲،۳ خودشون مرتبن و این بدترین حالته.میتونه ۱ فقط تشخیص بده جای غلطه بقیه رو جای صحیح تشخیص میده چون نسبت به قبل و بعد مرتبن.

بهترین حالت برای مرتب سازی ارایه تقریبا مرتب ، درجی هستش، ولی آرایه تفریبا مرتب ی حد آستاته داره. اگر تعداد اعداد نا مرتب کمتر از لاگ ان باشه مرتب سازی درجی به صرفه هست در غیر این صورت بصرفه نیس.


بله برای ارایه درخت گفته بود حداکثر فاصله

نقل قول: ینکه چطور بشه با مرتبه n جای نامرتب ها رو تشخیص داد بنظرم ممکن نیس چون وقتی بخواهیم جای درست عنصری رو پیدا کنیم باید یا مرتب بشه یا بعنوان محور در افراز باشه.
فرض کن وسط ی آرایه مرتب عناصر نامرتب داشته باشه مثل ۴،۵،۶،۷،۸،۱،۲،۳،۹،۱۰
ایتجا ۱،۲،۳ خودشون مرتبن و این بدترین حالته.میتونه ۱ فقط تشخیص بده جای غلطه بقیه رو جای صحیح تشخیص میده چون نسبت به قبل و بعد مرتبن.

بهترین حالت برای مرتب سازی ارایه تقریبا مرتب ، درجی هستش، ولی آرایه تفریبا مرتب ی حد آستاته داره. اگر تعداد اعداد نا مرتب کمتر از لاگ ان باشه مرتب سازی درجی به صرفه هست در غیر این صورت بصرفه نیس.


بله برای ارایه درخت گفته بود حداکثر فاصله


وای حداکثر را ندیدم
برای اون مرتب سازی همین مثالی که زدید که در یک مرتب سازی صعودی یه دفعه با ظاهر شدن ۱ بعد از ۸ نمیشه شروع را تشخیص داد؟ طولشم که رادیکال n هست

(۰۴ اسفند ۱۳۹۷ ۱۰:۲۹ ب.ظ)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 بود که جواب ندادم.

(۰۴ اسفند ۱۳۹۷ ۱۰:۲۹ ب.ظ)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 بود که جواب ندادم.