מידע כללי
מכונות טורינג, מודלי חישוב שונים ושקילותם למכונות טורינג. התזה של צ'רץ. מושג המכונה האוניברסלית. בעיות בלתי כריעות. סיבוכיות זמן וסיבוכיות מקום. מושג הרדוקציה והרדוקציה הפולינומית. חסמים לחישוב דטרמיניסטי ולא דטרמיניסטי והקשר ביניהם. משפט קוק. תוצאות למידה: בסיום הקורס הסטודנט יהיה מסוגל: 1. להכיר מודלים של חישוב, בפרט את מודל מכונת טיורינג. 2. להבדיל בין בעיות כריעות לבעיות בלתי כריעות. 3. להכיר את מושג החישוב היעיל (בזמן או בזיכרון), ויוכל לסווג בעיות לכאלה הניתנות לפתרון יעיל ובעיות "קשות חישובית". 4. להבין וליישם את מושג הרדוקציה בין בעיות.
פקולטה: מדעי המחשב
|תואר ראשון
|תארים מתקדמים
מקצועות קדם
מקצועות ללא זיכוי נוסף
46002 - תכן וניתוח אלגוריתמים 97447 - מבוא לחישוביות וסיבוכיות 106843 - תורת החישוביות ס' 214912 - מודלים חישוביים לפרחי הוראה 237343 - תורת החישוביות
מקצועות ללא זיכוי נוסף (מוכלים)
ספרי המקצוע
- 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 שעות פרוייקט
ניווט לדף המקצוע
אחראים
פרופ. קושילביץ איל
מבחנים
מועד א: 27-08-2024 מועד ב: 30-09-2024בחנים
מועד א: 29-07-2024קבוצות רישום
|
|
|
|
|
|
|
|
|
|
|
|
שעות שבועיות
3 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול • 1 שעות פרוייקט
ניווט לדף המקצוע
אחראים
פרופ. ישי יובל
הערות
-
קבוצה 77 מיועדת לסינים בלבד.
מבחנים
מועד א: 18-04-2024 09:00 - 12:00- אולמן 307. 500. 501. 502. 503. 504. 505. 506. 507. 600. 601. 603.
- אולמן 100. 103. 104. 105. 200. 201. 203. 205. 206. 300. 301. 305. 307.
בחנים
מועד א: 03-03-2024 17:30 - 19:30- אולמן 604, 606, 700, 701, 704, 706, 707, 708, 800, 802, 803, 804, 805, 806,
קבוצות רישום
|
|
|
|
|
|
|
|
|
|
|
|
שעות שבועיות
3 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול • 1 שעות פרוייקט
ניווט לדף המקצוע
אחראים
פרופ. קושילביץ איל
מבחנים
מועד א: 23-07-2023 09:00 - 12:00- אולמן 703. 704. 705. 706. 707. 708. 800. 801. 802. 803. 804. 805. 806.
- אולמן 500. 505. 507. 600. 601. 602. 603. 604. 605. 606. 607.
בחנים
מועד א: 04-06-2023 17:30 - 19:30- אולמן 700, 701, 702, 703, 704, 705, 706, 707, 708, 800, 801, 802, 803, 804, 805, 806,
קבוצות רישום
|
|
|
|
|
|
|
|
|
|
|
|