הקורס מספק מבוא לתורת החישוביות והסיבוכיות. הנושאים שיילמדו כוללים: אוטומט סופי דטרמיניסטי ושפות רגולריות, אוטומט לא דטרמיניסטי, שפות נטולות הקשר ואוטומט מחסנית, אלגוריתמים על אוטומטים, מכונות טיורינג, מושג הכריעות. במסגרת סיבוכיות ילמדו המחלקות P, NP, NP-HARD, NP-COMPLETE, PSPACE. תוצאות למידה: בסיום הקורס הסטודנטים: 1. יכירו מושגי יסוד בחישוביות, כולל תורת האוטומטים, מכונות טיורינג, שפות רגולריות וכריעות. 2. יכירו מושגי יסוד בתורת הסיבוכיות, כולל המחלקות המרכזיות P,NP, NP-C, PSPACE. 3. ידעו להוכיח חברות של בעיה במחלקת סיבוכיות, וידעו להוכיח כריעות או אי כריעות של בעיה. 4. יכירו את המשפט המראה שמספר הבעיות הכריעות הוא בר מניה, בעוד שמספר הבעיות הבלתי כריעות הוא לא בר מניה.

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

מקצועות קדם

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


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

236343 - תורת החישוביות 237343 - תורת החישוביות


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

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


מידע סמסטריאלי