מידע כללי
מכונות טורינג, מודלי חישוב שונים ושקילותם למכונות טורינג. התזה של צ'רץ. מושג המכונה האוניברסלית. בעיות בלתי כריעות. סיבוכיות זמן וסיבוכיות מקום. מושג הרדוקציה והרדוקציה הפולינומית. חסמים לחישוב דטרמיניסטי ולא דטרמיניסטי והקשר ביניהם. משפט קוק._: תוצאות למידה: בסיום הקורס הסטודנט יהיה מסוגל: 1. להכיר מודלים של חישוב, בפרט את מודל מכונת טיורינג. 2. להבדיל בין בעיות כריעות לבעיות בלתי כריעות. 3. להכיר את מושג החישוב היעיל (בזמן או בזיכרון), ויוכל לסווג בעיות לכאלה הניתנות לפיתרון יעיל ובעיות "קשות חישוביות". 4. להבין וליישם את מושג הרדוקציה בין בעיות.
פקולטה: מדעי המחשב
|תואר ראשון
|תארים מתקדמים
מקצועות קדם
מקצועות ללא זיכוי נוסף
236343 - תורת החישוביות 46002 - תכן וניתוח אלגוריתמים 97447 - מבוא לחישוביות וסיבוכיות 106843 - תורת החישוביות ס' 214912 - מודלים חישוביים לפרחי הוראה