20365 חישוביות ומבוא לסיבוכיות
20365 חישוביות ומבוא לסיבוכיות1
6 נקודות זכות ברמה מתקדמת
שיוך: מדעים / מדעי המחשב
תנאי קבלה: עמידה בדרישות האנגלית ובדרישות ההדרכה הביבליוגרפית בספרייה. ידע קודם דרוש: הקורסים מבני נתונים ומבוא לאלגוריתמים (או מבני נתונים), אוטומטים ושפות פורמליות.
פיתוח הקורס: פרופ' אברהם גינזבורג (מכין הקורס), פרופ' יהודית גל-עזר; יהודית גוגנהיימר (עריכה)
הקורס הוא הנדבך העליון של מערכת הקורסים המהווים את היסודות התאורטיים של מדעי המחשב ברמה של תואר ראשון.
ספר הקורס
M.D. Davis, R. Sigal & E.J. Weyuker, Computability, Complexity and Languages, Fundamentals of Theoretical Computer Science (Academic Press, 1994).
הסטודנטים ילמדו את פרקים 7-1 ו-15 בספר הקורס, באנגלית, בעזרת מדריך למידה מפורט בעברית המלווה את פרקי הספר באופן צמוד ומכיל גם פתרונות לשאלות שבספר ושאלות נוספות.
נושאי הקורס (בהתאמה לפרקי הספר)
פרק 1 |
מבוא |
חלק I |
חישוביות |
פרק 2 |
תכניות ופונקציות הניתנות לחישוב |
פרק 3 |
פונקציות פרימיטיביות רקורסיביות |
פרק 4 |
תכנית אוניברסלית |
פרק 5 |
חישובים של מחרוזות |
פרק 6 |
מכונות טיורינג |
פרק 7 |
תהליכים ודקדוקים |
חלק II |
סיבוכיות |
פרק 15 |
חישובים בזמן פולינומיאלי |
1הקורס נלמד בפעם האחרונה בסמסטר א2008.
להשלכות על צבירת נ"ז בשל חפיפה עם קורס(ים) אחר(ים), ראו טבלת קורסים חופפים.