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

שנה"ל תש"ף

  מודלים חישוביים
  Computational Models  
0368-2200-06
מדעים מדויקים
סמ'  ב'1000-1300001 צ'ק פוינטשיעור ד"ר בטנסקי ניר
פרופ שרן רודד
ש"ס:  4.0

סילבוס מקוצר

אוטומטים סופיים ושפות רגולריות. למות ניפוח. משפט Myhill–Nerode. אוטומטי מחסנית, דטרמיניסטיים ואי דטרמיניסטיים. דקדוקים ושפות חסרות הקשר. מכונות Turing. מודלים נוספים ושקילותם למכונות Turing (כולל RAM). התאזה של Church  ו– Turing. מכונות Turing אוניברסליות. אי כריעות של בעיית העצירה. רדוקציות מיפוי. משפט Rice. בעיות אי כריעות נוספות. סיבוכיות Kolmogorov. הבעיה העשירית של Hilbert (סקירה). משפט הרקורסיה. מחלקות זמן דטרמיניסטיות ואי דטרמיניסטיות. המחלקה NP. משפט Cook-Levin (ניסוח וסקירת ההוכחה). רדוקציות פולינומיאליות, מושגי  NP שלמות ו– NP קושי: הגדרות ודוגמאות.

סילבוס מפורט

מדעים מדויקים
0368-2200-06 מודלים חישוביים
Computational Models
שנה"ל תש"ף | סמ'  ב' | ד"ר בטנסקי ניר

סילבוס מפורט/דף מידע
לצפייה בסילבוס נא ללחוץ כאן

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


אוניברסיטת ת