سوال کتاب وزیرانی

سوال ۹.۱. مثال بد برای الگوریتم first-fit برای مسأله‌ی bin-packing

برش بیشینه با روش غیرتصادفی‌کردن

تفاوت جزوه و مباحث الگوریتم تقریبی

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

حل تقریبی (ویرایش ۴)

حل سوالهای ۱ و ۴ بیشتر توضیح داده شده است.

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

maximum coverage

https://www.cs.duke.edu/courses/fall13/compsci530/notes/lec16.pdf

درس ۱۰۰٪ حفظی

(دکتر) آبام اگر درسش حفظی نیست امتحان open book بگیره! :)

اصلاحیه صورت سوال تقریبی

سوال ۷ یک خط سوال اشتباه تایپی است! برای کران L چیزی نمی‌خواهد حساب کنیم.

سوال ۳ هزینه است نه تعداد یال.

race condition

«یک وضعیت رقابتی ^[۱] به انگلیسی Race Condition یا Race Hazard یک نقص در سیستم الکترونیکی یا رایانه ای است که به موجب آن نتیجه خروجی And یا Or به طور غیر منتظره ای به زمانبندی و ترتیب رویدادهای دیگر بستگی دارد.این اصطلاح در اصل به حالتی گفته می شود که دو سیگنال با هم رقابت می‌کنند تا هر یک زودتر به خروجی تاثیر بگذارند.»

منبع: http://fa.wikipedia.org/wiki/%D9%88%D8%B6%D8%B9%DB%8C%D8%AA_%D8%B1%D9%82%D8%A7%D8%A8%D8%AA%DB%8C

در پردازش موازی وقتی در مدلی مثل ERCW یا CRCW این مسأله به خوبی دیده می‌شود. مقدار حافظه‌ای که دو پردازنده همزمان می‌نویسند چه چیزی است؟ با روش‌های مختلفی می‌توان این مدل‌ها را به EREW تبدیل کرد که باعث حل این مشکل هم می‌شود.

phd comics..

اشکال در حل تمرین تقریبی

در سوال ۳ احتمالها یکنواخت نیستند. باید با derandomization (غیرتصادفی کردن) حل می‌کردیم.