חזרה

סילבוס

מספר קורס 0368-2200-05
שם הקורס מודלים חישוביים
יחידה אקדמית הפקולטה למדעים מדויקים ע"ש ריימונד ובברלי סאקלר -
מדעי המחשב
אופן ההוראה תרגיל
שעות סמסטריאליות 1
סמסטר א' תשפ"א
יום ד
שעות 14:00-15:00
בניין
חדר
אין סילבוס

תוכן הקורס ומטרתו

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

שימו לב כי הקורס שונה במידה ניכרת מהקורס שניתן בשנים שעברו





טרם פורסם סילבוס מפורט
מטלות הקורס

ייתכנו מטלות נוספות
רשימת המטלות המלאה תופיע בסילבוס המפורט של הקורס.

קורסי קדם נדרשיםמבוא מורחב למדעי המחשב (03681105) +מתמטיקה בדידה 1 (03681118) +מתמטיקה בדידה 2 (03681119) +הסתברות וסטטיס. (03682002) אומבוא להסתברות לסטטיסטיקאי (03651101) אוהסתברות וסטטיסטיקה (03211836) אומבוא להסתברות וסטטיסטיקה (05092801) אומבוא להסתברות (03662010)

דרישות קדם ספציפיות בקורס בהתאם לתוכנית הלימודים הנלמדת,
מופיעות בדף הידיעון של התוכנית



tau logohourglass00:00