מידע כללי
הקורס מספק מבוא לתורת החישוביות והסיבוכיות. הנושאים שיילמדו כוללים: אוטומט סופי דטרמיניסטי ושפות רגולריות, אוטומט לא דטרמיניסטי, שפות נטולות הקשר ואוטומט מחסנית, אלגוריתמים על אוטומטים, מכונות טיורינג, מושג הכריעות. במסגרת סיבוכיות ילמדו המחלקות 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 שעות תרגול
אחראים
פרופ. קוטין שי
מבחנים
מועד א: 25-07-2023 09:00 - 12:00- אולמן 300. 301. 302. 303. 305. 307. 309.
- אולמן 200. 202. 206. 300. 301. 303. 305.
קבוצות רישום
|
|
|
|
|
|
|
|
שעות שבועיות
2.5 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול
אחראים
פרופ. שטריכמן עופר
מבחנים
מועד א: 02-08-2022 13:00 - 16:00- אולמן 703. 705. 706. 707. 708. 801. 802. 803. 804. 805. 806.
- נהול 112. 214. 215. 216.
- בלומפילד 151. 152. 153. 424. 526.
בחנים
מועד א: 18-05-2022 16:30 - 17:30- אולמן 100, 103, 105, 200, 201, 202, 203, 205, 206, 300, 302, 304, 305, 306, 307, 308,
קבוצות רישום
|
|
|
|
|
|
|
|
|
|
|
|
שעות שבועיות
2.5 נקודות אקדמיות • 2 שעות הרצאה • 1 שעות תרגול
הערות
-
נפתח עי מדור מעקב
קבוצות רישום
|
|