מקצוע מידע על מקצוע : מבוא לחישוביות וסיבוכיות - 097447

097447 - מבוא לחישוביות וסיבוכיות
לא ינתן השנה
נקודות
זיכוי
2.5
 
עבודת
בית
פרויקט
או סמינר
מעבדה תרגול הרצאה  
2     1 2 שעות
שבועיות

קביעת הציון עפ"י מעקב במשך הסמסטר ובחינה סופית.


  094224 מבני נתונים ואלגוריתמים       מקצועות קדם
  234247 אלגוריתמים 1     או
 
  236343 תורת החישוביות       מקצועות ללא זיכוי נוסף
 
  094250 מבוא לחישוביות       מקצועות ללא זיכוי נוסף (מוכלים)


הקורס מספק מבוא לתורת החשיבויות והסיבוכיות. הנושאים שיילמדו כוללים: אוטומט סופי דטרמיניסטי ושפות רגולריות, אוטומט לא דטרמיניסטי, שפות נטולות הקשר ואוטומט מחסנית, אלגוריתמים על אוטומטים, מכונות טיורינג, מושג הכריעות. במסגרת סיבוכיות ילמדו המחלקות p, np, np-hard, np-complete, pspace. בסיום הקורס הסטודנטים:
1. יכירו מושגי יסוד בחישוביות, כולל תורת האוטומטים, מכונות טיורינג, שפות רגולריות וכריעות.
2. יכירו מושגי יסוד בתורת הסיבוכיות, כולל המחלקות המרכזיות p,np, np-c, pspace.
3. ידעו להוכיח חברות של בעיה במחלקת סיבוכיות, וידעו להוכיח כריעות או אי כריעות של בעיה.
4. יכירו את המשפט המראה שמספר הבעיות הכריעות הוא בר מניה, בעוד שמספר הבעיות הבלתי כריעות הוא לא בר מניה.




מערכת שעות לסמסטרים
סמסטר קודם מידע סמסטריאלי לסמסטר 02/2019 , 2019/2020 אביב תש"ף


ספרי לימוד
שנת הוצאה מוציא לאור מחברים ספר
1998 prentice-hall h.r. lewis, and c.h. papadimitriou elements of the theory of computation )2nd ed.(
2013 cengage learning michael sipser introduction to the theory of computation, 3rd edition

נערך בתאריך 23/10/2020 בשעה 09:15:52