پایان‌نامه‌های بچه‌های یزد

دکتر فرشی پایان‌نامه‌ها را روی صفحه شخصی‌شان لینک کردند. امروز شانسی یکی را پیدا کردم.

نمونه سوال الگوریتم تصادفی (هارپلد)

https://sarielhp.org/teach/13/b_574_rand_alg/final/practice.pdf

لینک درس: https://sarielhp.org/teach/13/b_574_rand_alg/

نسخه‌ی تغییریافته‌ی جمع‌کننده‌ی کوپن (coupon collector)

http://phillong.info/misc/coupon.pdf
بار دیگر به من اثبات شد هیچی از الگوریتم تصادفی بلد نیستم.
شاید بد نباشد بشینم سوالهای کتاب متوانی را حل کنم. آنجا حساب کردن جمع آن جمله‌های آخر را به عنوان سوال دارد. باز آدم آنها را بلد باشد شاید بتواند این را حل کند.
من هر چی حل کردم رسید به یک جایی که نمی‌شد حسابش کرد.
برای رابطه بازگشتی هم سعی کردم مستقیم مال احتمال را به دست بیارم، در حالی که این مثلاً اومده جمع را در آورده.
سر همین که چرا می‌توانسته امید ریاضی جمع وزنها را برای حساب کردن امید ریاضی آن یکی به کار ببره هم فکر کردم تا فهمیدم چون مخرجش وابسته به آن نبوده ثابت به حساب می‌آمده و از امید ریاضی می‌شده که بیاریمش بیرون.

iccg 2020

http://iccg.aut.ac.ir/

جنگل اشتاینر

https://maktabkhooneh.org/course/365/chapter/1/lesson/19/

قالب تک اسلاید فارسی

http://cs.yazd.ac.ir/farshi/index_files/Slide-Farsi.zip

کتابچه دومین کنفرانس ICCG

http://iccg.math.sharif.ir/proceedings.pdf

نوشتن فارسی در Ipe

http://farshi.blog.ir/1392/08/10/%D8%AC%D8%B2%DB%8C%DB%8C%D8%A7%D8%AA-%D9%81%D8%A7%D8%B1%D8%B3%DB%8C-%D9%86%D9%88%DB%8C%D8%B3%DB%8C-%D8%AF%D8%B1-IPE-Drawing

CS273: Foundations of Parallel and Distributed Systems

https://people.eecs.berkeley.edu/~satishr/cs273/

Prize Collecting Steiner Tree

https://maktabkhooneh.org/course/365/chapter/1/lesson/15/

به نظرم در اثبات ضریب تقریب نمی‌تواند بگوید جمع روی یک مجموعه کمتر از جمع روی کل با متغیرهای مشخصه است چون اینجا متغیرهایش ۰ و ۱ نیستند. ولی نکته این است که با همین نامساوی‌ها با تابع هدف خود LP درست است در نتیجه فقط یک گام اشتباه است و نتیجه درست است.

برای قسمت پیدا کردن آلفا هم فقط اگر بخواهیم جمع آنها بشود ضریبی از تابع هدف LP باید ضریبهایشان را مساوی بگذاریم. وگرنه باید خودشان را مساوی بگذاریم که تنها اگر دو تا جمله خودش با هم مساوی باشند کمینه می‌شود.

این راه‌حل مثلاً منتشر نشده هم توی کتاب الگوریتم تقریبی ویلیامسون و اشمویس فصل ۵.۷ صفحه ۱۱۸ آمده است! (قسمت اول هم مربوط به ۴.۴ صفحه ۸۸ است).

http://mhbateni.com/academic/pubs/pcst09.pdf