 שנה"ל תש"ף | |||||||||||||||||||||||||
 |
 |
||||||||||||||||||||||||
|
סיבוכיות
Computational Complexity |
0368-3168-02 | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| מדעים מדויקים | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
סילבוס מקוצר
סיבוכיות זמן וזיכרון. המחלקות 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.
דרישות קדם:
יעילות של חישובים, מודלים חישוביים
מדעים מדויקים
0368-3168-02 סיבוכיות
Computational Complexity
שנה"ל תש"ף | סמ' א' | מר קוזלוב דניאל
666סילבוס מפורט/דף מידע
לצפייה בסילבוס נא ללחוץ כאן