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