חיפוש חדש  חזור
מידע אישי לתלמיד

שנה"ל תשע"ט

  מודלים חישוביים
  Computational Models  
0368-2200-01
מדעים מדויקים
סמ'  א'1300-1600001 נפתלישיעור פרופ היטנר יפתח אילן
ש"ס:  4.0

סילבוס מקוצר

אוטומטים סופיים ושפות רגולריות . למות ניפוח. אוטומטי מחסנית, דטרמיניסטיים ואי דטרמיניסטיים. דקדוקים ושפות חסרות הקשר. מכונות Turing. מודלים נוספים ושקילותם למכונות Turing (כולל RAM). התאזה של Church  ו– Turing. מכונות Turing אוניברסליות. אי כריעות של בעיית העצירה. רדוקציות מיפוי. משפט Rice. בעיות אי כריעות נוספות. סיבוכיות Kolmogorov. הבעיה העשירית של Hilbert (סקירה). משפט הרקורסיה. מחלקות זמן דטרמיניסטיות ואי דטרמיניסטיות. המחלקה NP. משפט Cook-Levin (ניסוח בלבד). רדוקציות פולינומיאליות, מושגי  NP שלמות ו– NP קושי: הגדרות ודוגמאות.
אתר הקורס: moodle.tau.ac.il/course/view.php?id=368220001

 

להצהרת הנגישות


אוניברסיטת ת