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

۱- از یک زمانبند حریصانه استفاده می‌کنیم. اگر زمان اجرای یک الگوریتم روی ۴ پردازنده ۲۶۰ ثانیه و روی ۳۲ پردازنده ۹۰ ثانیه باشد؛ آیا مقادیر T1=1024 و Tinfinity = 64 می‌توانند مقادیر معتبری باشند؟

۲-  الگوریتم push-relabel را روی گراف زیر اجرا کنید که همه‌ی یالهای آن وزن ۲ دارند به جز یال آخر که وزن ۱ دارد.

s->v1->....->vn->t

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

۳- یک الگوریتم موازی برای محاسبه‌ی ترانهاده‌ی ماتریس X که n*n است بنویسید و کار و زمان و موازات آن را حساب کنید.

۴- یک شبکه شار داریم که یالهای آن آبی یا قرمز هستند. یالهای آبی ظرفیت ce دارند و یالهای قرمز کران پایین de دارند. شار بیشینه را می‌خواهیم به دست بیاوریم.

الف) برای آن یک LP بنویسید و ثابت کنید زمان آن خطی است.

ب) ثابت کنید اگر یالهای قرمز را بتوانیم خاموش و روشن کنیم؛ مسأله‌ی اینکه این گراف شار k دارد یا نه، np-complete است. (از subset-sum کمک بگیرید.)

۵- ثابت کنید دور فروشنده دوره‌گرد را نمی‌توان بهتر از یک تابع چندجمله‌ای بر حسب n تقریب زد.

۶- تابع پیشوندی در الگوریتم KMP را بنویسید و تحلیل کنید.