מידע כללי
הקורס מספק מבוא לתורת החישוביות והסיבוכיות. הנושאים שיילמדו כוללים: אוטומט סופי דטרמיניסטי ושפות רגולריות, אוטומט לא דטרמיניסטי, שפות נטולות הקשר ואוטומט מחסנית, אלגוריתמים על אוטומטים, מכונות טיורינג, מושג הכריעות. במסגרת סיבוכיות ילמדו המחלקות P, NP, NP-HARD, NP-COMPLETE, PSPACE. תוצאות למידה: בסיום הקורס הסטודנטים: 1. יכירו מושגי יסוד בחישוביות, כולל תורת האוטומטים, מכונות טיורינג, שפות רגולריות וכריעות. 2. יכירו מושגי יסוד בתורת הסיבוכיות, כולל המחלקות המרכזיות P,NP, NP-C, PSPACE. 3. ידעו להוכיח חברות של בעיה במחלקת סיבוכיות, וידעו להוכיח כריעות או אי כריעות של בעיה. 4. יכירו את המשפט המראה שמספר הבעיות הכריעות הוא בר מניה, בעוד שמספר הבעיות הבלתי כריעות הוא לא בר מניה.
פקולטה: הנדסת תעשיה וניהול
|תואר ראשון
|תארים מתקדמים
מקצועות קדם
94224 - מבני נתונים ואלגוריתמים או 234247 - אלגוריתמים 1
מקצועות ללא זיכוי נוסף
236343 - תורת החישוביות 237343 - תורת החישוביות
מקצועות ללא זיכוי נוסף (מוכלים)
מידע סמסטריאלי
שעות שבועיות
2.5 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול
אחראים
פרופ. שטריכמן עופר
מבחנים
מועד א: 02-08-2022 מועד ב: 24-10-2022בחנים
מועד א: 18-05-2022קבוצות רישום
|
|
|
|
|
|
|
|
|
|
|
|
שעות שבועיות
2.5 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול
אחראים
מר גוטמן עופר
מבחנים
מועד א: 27-07-2021 09:00 - 12:00- נהול 214. 215. 216.
- בלומפילד 100. 151. 152. 153. 424.
- ה.אויר 240. 241.
- דיוויס 281. 282. 283. 371. 373.
בחנים
מועד א: 26-05-2021 18:30 - 19:30קבוצות רישום
|
|
|
|
|
|
שעות שבועיות
2.5 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול
אחראים
מר גוטמן עופר
מבחנים
מועד א: 14-07-2020 17:00 - 20:00- נהול 112. 214. 215. 216.
- בלומפילד 151. 152. 153. 424.
- חדרי זום 301. 310.