کاهش با حفظ ضریب تقریب

http://www.cs.umd.edu/~hajiagha/ALB14/scribe-10-07-2014.pdf

جلسه چهارم نظریه بازی‌ها

http://www.cs.umd.edu/~hajiagha/AGT10/scribe-15-09-2010.pdf

جلسه دوم نظریه الگوریتمی بازی‌ها

http://www.cs.umd.edu/~hajiagha/AGT10/scribe-08-09-2010.pdf

ایده‌ی حل سوالهای میان ترم ۹۱ الگوریتم

۱- تکراری با سوال ۱ ما. (رجوع به پست قبلی)
۲-....
۳- به نظرم رسید با min cut حل کنیم که رأسهای یک طرف جزو مسیر هستند و یالهای طرف دیگر جزو مسیر نیستند. می‌دانیم که رأسها به ترتیب توپولوژیکی هستند (طبق شرط جهت که گذاشته)
برای اینکه رأس تکراری نباشد هم یک کپی از رأسها می‌گذاریم با یال بینهایت وصل می‌کنیم.
۴- به نظرم باید دایجسترا اجرا کنیم (کوتاهترین مسیر چون شار در طول مسیر ثابت است همینکه کوتاهترین مسیر باشد کافی است.)
۵- ب) مشابه مسأله‌ی پروژه‌ها: پروژه ها همان سرمایه گذارها هستند و پیشنیازها بازیگرهای مربوط به آن هستند.

میان ترم الگوریتم پیشرفته

۱- n عنصر و m مجموعه داریم که هر مجموعه k عضو دارد می‌خواهیم عناصر را با k رنگ، رنگ آمیزی کنیم که از هر رنگ یکی در هر مجموعه باشد.
الف) ثابت کنید که این مسأله NP است.
ب) ثابت کنید که برای k=3 ان پی کامل است. (با استفاده از ۳-رنگ پذیری گراف)
ج) ثابت کنید برای k=2 پی است.
جواب:
الف) یک مصداقش در زمان چندجمله‌ای قابل جواب دادن است.
ب) هر رأس و رأسهای مجاور را یک مجموعه بگیرید.
ج) رنگ آمیزی گراف با دو رنگ فقط برای گراف دوبخشی ممکن است (دور فرد نداشته باشد).
۲- مسأله‌ی هش کردن پویا را با فرض اینکه به جای دو برابر رادیکال n برابر کنیم که n تعداد عناصر موجود است حل کنید.
الف) زمان درج هش پویای معمولی چقدر است.
ب) حداکثر جای خالی جدول در این تعریف جدید چقدر است؟ (ثابت کنید از مرتبه رادیکال n است)
ج) زمان درج برای این حالت جدید چقدر است؟ (سرشکنی)
جواب: تابع پتانسیل را تعداد اعداد موجود منهای توان ۲ تعداد جاهای خالی +۱ گرفتم. (اون +۱ برای حالت پایه اش بود که منفی نشه)

۳- یک گراف نامشخص داریم فقط درجه ورودی و خروجی هر رأس را می‌دانیم. گراف را پیدا کنید.

جواب: شار بیشینه. n رأس سمت راست و n رأس سمت چپ می‌گذاریم و از s با درجه خروجی هر رأس و به t با درجه ورودی هر رأس وصل می‌کنیم. بین رأسهای سمت راست و چپ هم یالهای با ظرفیت ۱ می‌گذاریم. این گراف جهت دار بدون یال چندگانه و با طوقه می‌دهد. اگر بخواهیم طوقه نداشته باشد باید رأسها را به خودشان وصل نکنیم. برای یال چندگانه هم ظرفیت بینهایت بگذاریم به جای ۱.

۴- در مورد push relabel به سوالهای زیر جواب بدهید:

الف) ثابت کنید اگر رأس u پیش شار داشته باشد در Gf مسیر از u به s هست.

ب) تعداد عملیات مختلف را به دست بیاورید. non saturating push, saturating push, relabel

*اگر سوالی هست که یادم رفته بنویسم کامنت بگذارید.

جزوه جلسه اول نظریه الگوریتمی بازی‌ها

http://www.cs.umd.edu/~hajiagha/AGT10/scribe-01-09-2010.pdf