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

פקולטה: מדעי המחשב
|תואר ראשון |תארים מתקדמים

מקצועות קדם

234247 - אלגוריתמים 1


מקצועות ללא זיכוי נוסף

46002 - תכן וניתוח אלגוריתמים 97447 - מבוא לחישוביות וסיבוכיות 106843 - תורת החישוביות ס' 214912 - מודלים חישוביים לפרחי הוראה


מקצועות ללא זיכוי נוסף (מכילים)

94250 - מבוא לחישוביות


מידע סמסטריאלי