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

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

جواب سوال ۲ و ۵ پایان ترم تقریبی

همون طوری که پیش بینی می‌شد سوالها نکاتش همان نکات تمرین‌ها بود. به طرز جالبی بد دادم! :| یکی رو خودم غلط حل کرده بودم، یکی رو سوال راهنمایی اشتباه کرده بود، یکی رو فکر می‌کردم نیست جزو مباحث امتحان، یکی رو هم یادم رفته بود. وقت هم تمدید نشد (نیم ساعت حساب نیست).

نمی‌دونم الآن چطوری باید برای خودم متأسف باشم! :| این سری هم نفر آخر کلاس میشم. (تازه اگه شانس بیارم!)

http://personal.vu.nl/l.stougie/Courses/ALP/col10.pdf

http://www.cse.cuhk.edu.hk/~chi/csc5160-2008/notes/L10-stable.pdf

پایان ترم الگوریتم تقریبی

با کیفیت افتضاح تصویر :)

به دست آوردن آلفا در semidefinite program مسأله MAX 2Sat

مرجع: http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf

2sat vector program

۲۶۴ وزیرانی

سر کار بودن (تمرین تقریبی)

الآن داشتم صورت سوال رو برای یکی دیگه می‌گفتم دیدم گفته همه‌ی رأسهای گراف هستند. (من از صبح دارم سعی می‌کنم یک زیرمجموعه از رأسها بردارم.)

کی صورت سوال رو انقدر مبهم و غلط انداز می‌نویسه؟ :|

http://mathworld.wolfram.com/Vertex-InducedSubgraph.html

اصلاحیه‌های تمرین تقریبی

به جز موردی که به همه ایمیل زده شد، این دو مورد دیگر هم بود. (به جز غلط املایی سوال ۴)

۱- صورت سوال اول فقط اسم مسأله را نوشته، به فصل ۲۴ کتاب مراجعه کنید. سوال هم از تمرین‌های همین فصل است ولی اختلاف زیادی با صورت سوال دارد که اصلاً نمی‌ارزد توضیح بدهم!

اشکال دوم:

سوال ۳ هم گفته است با روش Set Cover مسأله را حل کنید. برخلاف نمونه‌ای که در کتاب هست که فقط ۲ متغیر دارد، اینجا جمع یک سری متغیر را داریم پس نمی‌شود نتیجه گرفت اگر بعضی‌ها را اپسیلون تا زیادتر کنیم نصف دیگر اپسیلون تا کم می‌شوند.

سوال ۵ هم قسمتی که باید زیرگراف را به دست بیاوریم و آن را چک کنیم که همبند است یا نه، هیچ ایده‌ای ندارم که چطوری باید شرط بگذاریم.

IP for k-connected graph

http://www.cc.gatech.edu/~vempala/papers/focskconn.ps

Matching using Linear Programming

http://www.imsc.res.in/~meena/matching/lecture5.pdf

semi definite programming

strict quadratic program:

شبیه linear programming است فقط به جای اینکه توابع خطی باشند درجه ۲ یا ثابت اند.

حاصل relax کردن چنین برنامه‌ای یک vector program است و ضرب متغیرها را بر حسب ضرب داخلی بردارها می‌نویسیم پس هر بردار باید به تعداد متغیرها درایه داشته باشد.

لازم نیست همیشه vector program را با این روش به دست بیاوریم.

معمولاً از این روش برای حل مسائل np-hard استفاده می‌شود.

اگر ضرایب ماتریسی تشکیل بدهند که به ازای هر بردار حقیقی x عبارت x^t A x >=0 باشد به آن positive semidefinite می‌گویند.

یک semidefinite program شبیه linear programming است اما به جای اینکه با بردارها کار کنیم با ماتریس‌ها کار می‌کنیم و باید ماتریس مقادیر متغیرها positive semidefinite و متقارن باشد. ضرب دو ماتریس به جای یک رابطه خطی یک ماتریس می‌دهد که برای به دست آوردن رابطه خطی جمع عناصر قطر اصلی آن (trace) را حساب می‌کنند.

separating oracle: به ازای هر نقطه غیرمجاز جواب اگر بتوان ابرصفحه‌ای پیدا کرد که آن را از جوابهای مجاز جدا کند به این ابر صفحه separating oracle می‌گویند. چنین چیزی را در زمان چندجمله‌ای می‌توان به دست آورد.

نتیجه: هر semidefinite program می‌تواند در زمان چندجمله‌ای بر حسب n و log(1/epsilon) با خطای جمعی اپسیلون با استفاده از روش ellipsoid حل شود.

نحوه محاسبه:

ابتدا باید امکان پذیر بودن ماتریس جواب A را چک کنیم. اگر در قیود صدق کرد و semidefinite بود و متقارن بود جواب است. این کار در زمان چندجمله‌ای ممکن است. در غیر این صورت برای آن می‌توان separating oracle پیدا کرد:

اگر A متقارن نیست به ازای یک درایه آن مقدار قرینه‌ی آن نسبت به قطر اصلی از خودش بیشتر است پس متغیر متناظر آنها با جهت نامساوی برعکس جواب است.

اگر A یک ماتریس positive semidefinite نباشد حتما مقدار ویژه‌ی منفی دارد. بردار متناظر آن را پیدا می‌کنیم. vYv^t>=0 جواب است. (Y ماتریس متغیرهاست.)

اگر هر قیدی نقض شود، خودش یک ابرصفحه جداکننده می‌دهد.

(می‌توان برای حل vector programming از رند کردن تصادفی بردارها استفاده کرد.)