نمونه سوال الگوریتم تقریبی با حل

http://www.ti.inf.ethz.ch/mb/projects/

اسلایدهای مدرسه زمستانی هندسه محاسباتی

http://wscg.aut.ac.ir/wscg6/index.php?option=com_content&view=article&id=3&Itemid=2

شباهت منحنی‌ها

http://cs.au.dk/~ld/Thesis_Lasse_Deleuran_June_2012.pdf

http://ce.sharif.edu/~daneshpajouh/publications/posters/shervin-madalgo.pdf

اون تز اولی تهش مقاله‌های دکتر آبام و شروین دانش پژوه رو داره و دومی هم اسلایدهای خودشه.

Team Selection For Prediction Tasks

http://arxiv.org/abs/1406.0140

به خاطر اینکه آذین جزو نویسنده‌هاست آوردمش!

کار گروهی

اومدم برای یکی از بچه‌ها ایده‌ام رو بفرستم استخاره کردم این اومد: :))

نتیجه کلی:

بد است شما را پلکان ترقی خودشان خواهند کرد و در آخر بشما پشت می کنند انجام ندهید.

facility location example

http://www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/facility_location.pdf

مثالش غلطه که! :)) این عین کتاب وزیرانی هم هست...

من ایمیل زدم به تی‌ای عزیزمون پرسیدم:

مثال صفحه‌ی ۲۳۹ کتاب وزیرانی غلط است؟ چون اگر به مرکز facility دوم یک دایره به شعاع یک بزنیم، همه‌ی شهرها روی آن می‌افتند. می‌دانیم c1 از f1 هم فاصله‌ی ۱ دارد، در نتیجه فاصله‌ی f1 از نقاط دایره به مرکز f2 حداکثر در یک نقطه ۳ می‌شود. (در حالتی که دو دایره مماس باشند و c1 نقطه تماس باشد سر دیگر قطر تنها نقطه به فاصله ۳ خواهد بود.)

امتحان‌ها

من از زمان تحویل تمرین دکتر آبام نهایت تشکر را دارم! تنها دلیلی بود که من فهمیدم که امتحان‌هام توی خرداده نه تیر! (فقط هندسه توی تیره)

اولین امتحان تقریبی است که ۲۲ است بعدی موازی است که ۲۷ است بعدی ۳ تیر هندسه محاسباتی پیشرفته است.

ایده‌ی ارائه‌های امروز الگوریتم تقریبی

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

ایده‌ی دیگری که دیدم این بود که فضای مسأله را بر اساس هزینه‌ی آن به صورت یک چندوجهی صعودی/نزولی اکید ذخیره می‌کردند. حتی به صورت ساختمان داده مربوط به آن مسأله خاص.

چیز جدید دیگری که دیدم این بود که نامساوی مثلث را برای یک semidefinite programming به صورت برداری نوشته بودند:

(vi-vj)(vi-vk) >= 0

که هیچ ایده‌ای ندارم چه ربطی به نامساوی مثلث دارد؟

facility location

http://www.cs.cornell.edu/People/mpal/papers/UFL_ESA2003.ppt

اسلایدهای ارائه‌ی سر کلاس تقریبی بچه‌ها

مرجع: http://mahdian.org/pub.html

تمرین ۵ موازی (صورت سوالها)