האוניברסיטה הפתוחה

תיאורי הקורסים
הקורס אינו מוצע עוד

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.

    להשלכות על צבירת נ"ז בשל חפיפה עם קורס(‏ים‎)‏ אחר(‏ים‎)‏, ראו טבלת קורסים חופפים.