 שנה"ל תשע"ה | |||||||||||||||||||||||||
 |
 |
||||||||||||||||||||||||
|
סיבוכיות
Computational Complexity |
0368-3168-07 | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| מדעים מדויקים | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
ש"ס: 3.0
סילבוס מקוצר
סיבוכיות זמן וזיכרון. המחלקות L,NL,P,NP ו PSPACE. רדוקציות ובעיות שלמות למחלקות הנ"ל. משפט Savitch. NL=coNL. משפט Cook-Levin. דוגמאות לבעיות NP שלמות. אלגוריתמי קירוב לבעיות NP שלמות. רדוקציות משמרות קירוב. ההיררכיה הפולינומית. חישובים מטילי מטבעות, המחלקה BPP. המחלקה BPP מוכלת ב S2. משפט ה PCP וקושי של קרוב בעיות NP קשות.
ספרי לימוד:
· C. Papadimitriou, Computational complexity.
· M. Sipser, Introduction to the theory of computation.
· V. Vazirani, Approximation Algorithms.
דרישות קדם:
יעילות של חישובים, מודלים חישוביים