پروژه های دانشجویی پاسارگاد

معرفی روش‌های تحلیل پیچیدگی الگوریتم‌ها و الگوریتم های احتمالاتی، تصادفی و موازی

بخشی از متن:
تا اینجا مدل استاندارد محاسبات ما ماشین تورینگ قطعی بود. اما هر کس که حتی کوچکترین آشنایی با محاسبات دارد می¬داند که کامپیوترهای دنیای واقعی نیاز ندارند قطعی باشند زمانیکه در "مولدهای اعداد تصادفی " ساخته می¬شوند. در حقیقت این مولدها برای شبیه¬سازی کامپیوتر فرآیندهای "تصادفی" بسیار مفید می¬باشند از قبیل شکافت هسته یا جنبش مولکولی در گازها یا بورس کالا. در این فصل محاسبات احتمالی ، و کلاس¬های پیچیدگی وابسته به آن مطالعه می¬شود.
یادآور می¬شویم که این یک سوال باز است که آیا در جامعه هیچ تصادفی وجود دارد یا نه (که مکانیک کوانتمی تضمین می¬کند که این وجود دارد). در واقع، خروجی "مولدهای اعداد تصادفی" اخیر تضمین نمی¬کنند که به راستی تصادفی باشند، که در بخش¬های بعد این محدودیت بررسی می¬¬شود. اما الان فرض می¬کنیم که مولدهای اعداد تصادفی موجود می¬باشد. آنگاه، یک مدل واقعی برای یک کامپیوتر دنیای واقعی یک ماشین تورینگ با یک مولد عدد تصادفی است، که آنرا ماشین تورینگ احتمالی (PTM) می¬نامیم. طبیعی می¬باشد که تعجب کنیم آیا مسائل سخت نظیر 3SAT به صورت کارامد توسط PTM قابل حل هستند.
کلاس BPP را زبان محاسبه¬پذیر توسط زمان PTM چندجمله¬ای تعریف می¬کنیم و روابط این کلاس را با کلاس¬های که قبلا مطالعه شده از قبیل P/poly و PH مقایسه می¬کنیم. یک نتیجه منطقی این است که اگر PH نتیجه نشود، آنگاه 3SAT الگوریتم¬های احتمالی کارآمد ندارد.
همچنین نشان می¬دهیم که الگوریتم¬های احتمالی توسط نمایش راه¬های کاهش بزرگ خطاهایش به مقدار کاملا کوچک می¬تواند بسیار سودمند باشد.