פורטל הסטודנטים

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

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

מקצועות קדם

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

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

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

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

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

• Computational complexity - Papadimitriou, Christos H.
• Computers and intractability : a guide to the theory of Np-Completeness - Garey, Michael R.
• Introduction to automata theory, languages, and computation - Hopcroft, John E.
• Introduction to automata theory, languages, and computation / John E. Hopcroft, Jeffrey D. Ullman. - Hopcroft, John E.
• Introduction to automata theory, languages, and computation / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. - Hopcroft, John E.
• Introduction to the theory of computation - Sipser, Michael
• Introduction to the theory of computation / Michael Sipser. - Sipser, Michael
• Introduction to the theory of computation / Michael Sipser. - Sipser, Michael
• מבוא לתורת החישוביות - גולדרייך, עודד