تمرین موازی ۴ و ۵

HW4

From Leighton's

1.190

2.6

2.16

2.24

2.36

2.50

2.51

Deadline: 17/3/93  

HW5

From Parhami's

13.8

13.11

14.5

14.8

14.9

14.11

15.8

​Deadline: Final exam

دوگان LP بدون ماتریس

بالاخره فهمیدم باید چه کار کنم! :))

بعد از اینکه به فرم استاندارد در آوردیم:

اول طرفین هر نامساوی را در یک متغیر جدید ضرب می‌کنیم. بعد مسأله را ماکسیمم به مینیمم (یا برعکس) تغییر می‌دهیم و قیدها را به این صورت تغییر می‌دهیم که به جای یک طرف نامساوی ضریب هر کدام از متغیرهای قبلی و به جای طرف دیگر ضریب آن در تابع هدف را می‌گذاریم.

http://en.wikipedia.org/wiki/Linear_programming#Another_example

اشکال تمرین تقریبی ۲

سوال ۳ تمرین را با روش وزیرانی نمی‌شود حل کرد چون اینجا الآن نمی‌توانیم مطمئن باشیم که دقیقاً ۲ تا متغیر داریم! (فکر کنم سوالش غلط است)

همین مسأله را به روش دیگری LP برایش نوشته و حل شده است اما در صورت سوال ما گفته است که این طوری باید بنویسید.

عالی ۲

بعد از اینکه با کلی زحمت تمرین هندسه را حل کردم دیدم یک هفته دیگر وقت دارد.

The Szemerédi-Trotter theorem and the cell decomposition

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

عالی!

http://maktabkhooneh.org/course?course=abam266

اصلاحیه ترجمه!

additive رو ترجمه می‌کنند خطی نه جمعی! :))

خوشه‌بندی بر مبنای چگالی

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

جزوه..

*اگر از گراف G به ازای هر تقاطع انقدر یال حذف کنیم که دیگر تقاطع نباشد به گراف G' می‌رسیم که مسطح است. چون گراف مسطح است تعداد یالهای آن از مرتبه‌ی تعداد رأسهای آن است. پس m' < m+x است که x تعداد تقاطع‌های گراف G است.

*روش احتمالاتی: هر رأس را با احتمال p در گراف نگه می‌داریم. در نتیجه متوسط تعداد رأسها pn، متوسط تعداد یالها p^2 n و متوسط تعداد تقاطع‌ها p^4 n می‌شود. طبق قضیه قبلی تعداد یالها به صورت متوسط جمع تعداد رأسها و تعداد تقاطع‌ها است.

تقاطع پاره‌خط‌ها

منبع: clarkson 89 applications of random sampling in CG