درس پیچیدگی محاسباتی (بهار ۹۳-۹۴)

منبع

صورت تمرین نمره اضافه و منبع تمرین نمره اضافه

آزمون کلاسی اول
آزمون کلاسی دوم
آزمون کلاسی چهارم
آزمون کلاسی ششم

آزمون پایان‌ترم
آزمون پایان‌ترم ۲

آزمون جبرانی اول
آزمون جبرانی دوم

مباحث درس

ماشین تورینگ

ماشین تورینگ و معادل بودن ماشین‌های تورینگ مختلف

  • شبیه‌سازی ماشین تورینگ با الفبای زیاد با ماشین تورینگ با الفبای کم
  • شبیه‌سازی ماشین تورینگ با چند نوار به صورت کارا با ماشین تورینگ با یک (دو) نوار
  • قضیه گودل

تکلیف اول از فصل اول کتاب «Computational Complexity, a Modern Approach»: تمرین‌های ۷ و ۹ و ۱۳.g و ۱۴.b

کلاس پیچیدگی P و NP

کلاس پیچیدگی P و NP و قضیه Cook-Levin

تمرین ۲: تمرین‌های ۵ و ۱۰و ۱۷و ۳۱ از فصل ۲ کتاب

قطری‌سازی

قطری‌سازی روشی است برای اثبات ناتوانی‌های ماشین تورینگ. از این روش برای اثبات موارد زیر استفاده می‌کنیم:

  • قضیه سلسله مراتب زمانی
  • قضیه سلسله مراتب زمانی غیر قطعی
  • وجود زبانی که نه در P و نه در NP-C است
  • اثبات‌های نسبی (relativezed) برای اثبات یا رد P=NP کم هستند.

پیچیدگی حافظه

همان‌طور که می‌توان در مورد پیچیدگی زمان الگوریتم‌ها صحبت کرد، می‌توان در مورد حدود پایین و بالای لازم برای حافظه یک الگوریتم نیز قضایایی اثبات کرد.

  • تعریف کلاس‌های SPACE و NSPACE
  • NSPACE(S(n)) \subseteq SPACE(S(n)^2)
  • PATH \in NL-Complete
  • NL=coNL

تمرین سری سوم (فصل قطری‌سازی و فصل پیچیدگی حافظه):
از فصل ۳: ۲ و ۶ و ۷
از فصل ۴: ۲ و ۶ و ۹
هم‌چنین مسئله زیر: ثابت کنید مسئله ۲SAT عضو رده پیچیدگی NL-Complete است.

سلسله مراتب چندجمله‌ای

تعمیم کلاس‌های پیچیدگی P و NP در قالب کلاس‌های جدید.

  • کلاس‌های سیگما و پای
  • کلاس PH.
  • ماشین تورینگ تناوبی
  • قضیه عدم توانایی حل SAT با محدودیت حافظه و زمان

تمرین سری ۴ (سلسله مراتب چند جمله‌ای): از فصل ۵: ۱ و ۳ و ۶ و تمرین امتیازی: ۱۳

پیچیدگی مدارهای منطقی

مدارهای منطقی را نیز می‌توان به عنوان ابزاری برای محاسبه مانند ماشین تورینگ به حساب آورد. مباحث زیر در این موضوع بررسی می‌شوند:

  • کلاس پیچیدگی P/poly
  • ماشین‌های تورینگ که راهنمایی می‌گیرند
  • رابطه P/Poly با دیگر کلاس‌های پیچیدگی
  • رابطه الگوریتم‌های موازی و مدارهای منطقی

الگوریتم‌های تصادفی

آیا استفاده از بیت‌های تصادفی می‌تواند ماشین‌های تورینگ را تقویت کند؟

  • کلاس‌های مختلف پیچیدگی الگوریتم‌های تصادفی

تمرین سری ۵ (پیچیدگی مدارهای منطقی و الگوریتم‌های تصادفی): از فصل ۶:‌ ۱، ۵، ۱۲. و از فصل ۷:‌ ۱، ۴، ۶.

اثبات‌های تعاملی

آشنایی با اثبات تعاملی. مثال برای زبان نابرابری گراف‌ها.

اثبات‌های قابل بررسی تصادفی

از مهم‌ترین قضیه‌های اخیر در پیچیدگی محاسبات که با استفاده از آن عدم قابلیت تولید الگوریتم‌های تقریبی اثبات می‌شود.

ارائه دانشجویان

نام خانوادگی نام موضوع تاریخ فصل از کتاب
شفیعی راضیه Decision trees ۲۷ اردیبهشت ۱۲ گزارش
نویدی فاطمه Derandomization ۲۷ اردیبهشت ۲۰ گزارش
تقوی شیخ لیلا Quantum Computing ۲۷ اردیبهشت - گزارش
احمدی موغاری فاطمه average case ۲۹ اردیبهشت ۱۸ گزارش
خانیکی عرفان Natural Proofs ۲۹ اردیبهشت ۲۳ گزارش
رحیمی احمدرضا Pseudorandom constructions: Expanders and extractors ۲۹ اردیبهشت ۲۱
ستاری جاوید علی Big data ۳ خرداد - گزارش
خوئینی محمدصادق Streaming Algorithms ۳ خرداد -
یاسائی‌میبدی فاطمه Communication complexity ۳ خرداد ۱۳
علیزاده زهرا Proof Complexity ۵ خرداد ۱۵ گزارش
اسگندانی محمدامی Algebraic computation models ۵ خرداد ۱۶
دستغیب دره السادات Cryptography ۵ خرداد ۹ گزارش
پورربیع رودسری حمی Hardness Amplification ۱۰ خرداد ۱۹ گزارش
جوان مجید Circuit Lower bounds ۱۰ خرداد ۱۴
صیام پور فرزانه Complexity of counting ۱۰ خرداد ۱۷