מידע כללי
מכונות טורינג, מודלי חישוב שונים ושקילותם למכונות טורינג. התזה של צ'רץ. מושג המכונה האוניברסלית. בעיות בלתי כריעות. סיבוכיות זמן וסיבוכיות מקום. מושג הרדוקציה והרדוקציה הפולינומית. חסמים לחישוב דטרמיניסטי ולא דטרמיניסטי והקשר ביניהם. משפט קוק. תוצאות למידה: בסיום הקורס הסטודנט יהיה מסוגל: 1. להכיר מודלים של חישוב, בפרט את מודל מכונת טיורינג. 2. להבדיל בין בעיות כריעות לבעיות בלתי כריעות. 3. להכיר את מושג החישוב היעיל (בזמן או בזיכרון), ויוכל לסווג בעיות לכאלה הניתנות לפתרון יעיל ובעיות "קשות חישובית". 4. להבין וליישם את מושג הרדוקציה בין בעיות.
פקולטה: מדעי המחשב
|תואר ראשון
|תארים מתקדמים
מקצועות קדם
מקצועות ללא זיכוי נוסף
46002 - תכן וניתוח אלגוריתמים 97447 - מבוא לחישוביות וסיבוכיות 106843 - תורת החישוביות ס' 214912 - מודלים חישוביים לפרחי הוראה
מקצועות ללא זיכוי נוסף (מכילים)
ספרי הקורס
- 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
- מבוא לתורת החישוביות - גולדרייך, עודד
מידע סמסטריאלי
שעות שבועיות
3 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול • 1 שעות פרוייקט
אחראים
פרופ. ישי יובל
מבחנים
מועד א: 31-01-2022 מועד ב: 27-02-2022בחנים
מועד א: 02-01-2022 17:30 - 19:30- אולמן 601, 603, 604, 607, 701, 703, 704, 705, 801, 802, 803, 804, 805,
קבוצות רישום
|
|
|
|
|
|
|
|
|
|
שעות שבועיות
3 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול • 1 שעות פרוייקט
אחראים
פרופ. קושילביץ איל
הערות
-
בקורס ייאכפו דרישות קדם וצמודים המתפרסמים באתר לימודי הסמכה.
מבחנים
מועד א: 21-07-2021 09:00 - 12:00- אולמן 500. 501. 502. 503. 504. 600. 601. 602. 603. 604. 605. 606. 607.
- אולמן 101. 102. 103. 104. 105. 300. 302. 303. 304. 305. 306. 307. 309. 310. 311. 502. 505.
בחנים
מועד א: 23-05-2021 17:30 - 19:30- אולמן 500, 501, 502, 503, 504, 505, 506, 600, 601, 602, 603, 604, 605, 606, 607, 800, 801, 802, 803,
קבוצות רישום
|
|
|
|
|
|
|
|
|
|
|
|
שעות שבועיות
3 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול • 1 שעות פרוייקט
אחראים
פרופ. ישי יובל
מבחנים
מועד א: 31-01-2021 13:00 - 16:00 מועד ב: 02-03-2021 13:00 - 16:00בחנים
מועד א: 03-01-2021 17:30 - 19:30קבוצות רישום
|
|
|
|
|
|
|
|
|
|
|
|
|
|