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

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

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

اشکال دوم:

سوال ۳ هم گفته است با روش 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

۳ مورد کلی!

اول اینکه من حل تمرین‌هامو نمی‌ذارم.

دوم اینکه به این نتیجه رسیدم که خودم متن مقاله را بنویسم ایمیل کنم برای استادم شانس اینکه اسم همه‌ی آدمها مورد علاقه‌اش که کوچکترین کمکی به پروژه من نکردن و دردسر بودن رو بنویسه کمتر میشه. (چرا باید اسم یکی رو بنویسم که تنها کاری که کرده این بوده که بیاد حرفهای منو تکرار کنه؟ من که این ایده رو می‌دادم استادم می‌گفت نمی‌شه حالا اون که می‌داد می‌گفت به‌به چه ایده خوبی! حالا غلط هم بود ولی خودم یک راه حل برایش پیدا کردم.)

سوم اینکه هر وقت به این نتیجه رسیدید که حداقل احترام بگذارید به کسی که داره چیزی یادتون میده من بقیه نکته‌های درس رو اینجا می‌نویسم.

Latex: how break a line when summing over two things

http://stackoverflow.com/questions/1952797/latex-how-break-a-line-when-summing-over-two-things

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 از رند کردن تصادفی بردارها استفاده کرد.)

نمایش مجموعه اعداد حقیقی در latex

http://www.latex-community.org/forum/viewtopic.php?f=44&t=8863

In LaTeX, how do I represent the hollow "R" symbol that designates the real number space?

\documentclass{report}
\usepackage{amssymb}

\begin{document}

$\mathbb{R}$

\end{document}

جواب سوال ۱ تمرین الگوریتم تقریبی

http://www.cs.uu.nl/research/techreps/repo/CS-1997/1997-39.pdf

واقعاً اینکه نسبت جوابها خود پارامتر مسأله بشود را هم می‌گویند unbounded؟ من فکر می‌کردم باید حتماً بینهایت بشود ولی در خود مقاله هم این طوری گفته.

LP-based approximation algorithms for capacitated facility location

دریافت
حجم: 197 کیلوبایت

توضیحات: http://link.springer.com/article/10.1007%2Fs10107-010-0380-8

پروژه مالتی‌مدیا

با خوشه‌بندی k-میانگین تعداد رنگ‌های عکس را کم می‌کند. (C#)

یادم است که TA عزیز این درس به نصف کلاس ایمیل نزده بود زمان تحویل پروژه را و سری دوم تحویل پروژه را انداخت خیلی دیرتر که دیگر من مسافرت بودم.

لذتی که توی برنامه نویسی هست توی هیچ چیز دیگه‌ای نیست. می‌خواستم پروژه‌ی کارشناسی‌ام را که با جاوا نوشتم بگذارم اما می‌ترسم به خاطر رعایت نکردن کپی‌رایت توی دردسر بیفتم. جالبه که دنبالش گشتم توی کتابخانه دانشگاه نبود! :| چرا واقعاً؟!

دریافت
حجم: 5.92 کیلوبایت

دریافت
حجم: 1.05 مگابایت