מודלים חישוביים

2013 סמסטר ב' (אביב)

מרצים: פרופ' ישי מנצור, דר' יפתח הייטנר

מתרגל: אורן זלצמן
אתר הקורס: אתר הקורס

שיעורי בית

ינתנו אחת לשבועיים, להגשה בתיבת העץ מספר 1 בשרייבר (ליד חדר 5).
מהווים 10% מהציון הסופי.

סיכומים:

שבוע ראשון

הרצאה 1

לא התקיימה

תרגול 1

לא התקיים

שבוע שני

הרצאה 2

מבוא וענייני אדמיניסטרציה
אוטומטיים (סופיים) דטרמיניסטים (DFA)
פעולות על שפות
סגירות באיחוד של שפות רגולריות
סיכום

תרגול 2

DFA
סיכום

שבוע שלישי

הרצאה 3

אוטומטים (סופיים) לא דטרמיניסטיים (NFA)
שקילות בין DFA ל NFA
ביטויים רגולריים, ו GNFA
שקילות בין DFA לביטויים רגולריים
סיכום

תרגול 3

NFA
ביטויים רגולריים
מעבר מ NFA ל DFA
סיכום

שבוע רביעי

הרצאה 4

למת הניפוח עבור שפות רגולריות
משפט Myhill-Nerode
פעולת ה"חילוק" של שפות, סגירות של רגולריות לשפת החילוק
סיכום

תרגול 4

הוכחת אי רגולריות:

              -למת הניפוח
              -משפט Myhill-Nerode
              -שימוש במשפטי סגירות של רגולריות

סיכום

שבוע חמישי

הרצאה 5

שפות חסרות הקשר / דקדוקים חסרי הקשר (CFG)
Chunsky Normal Form
למת הניפוח לשפות חסרות הקשר
סיכום

תרגול 5

דקדוקים חסרי הקשר
למת הניפוח לשפות חסרות הקשר
סיכום

שבוע שישי

הרצאה 6

לא התקיימה - פסח

תרגול 6

לא התקיים - פסח

שבוע שביעי

הרצאה 7

אוטומט מחסנית - PDA
שקילות בין PDA ל CFG
תכונות סגירות של שפות ח"ה
הומומורפיזם והומומורפיזם הפוך
ריקות, מלאות ושקילות של CFG
סיכום

תרגול 7

PDA ו CFG

*למת הניפוח לחסרות הקשר

סיכום

שבוע שמיני

הרצאה 8

מכונת טיורינג (TM)
מכונת טיורינג עם כמה סרטים - שקילות ל TM רגילה
מכונת טיורינג לא דטרמיניסטית - שקילות ל TM רגילה
Turing Completeness
סיכום

תרגול 8

TM
סיכום

שבוע תשיעי

הרצאה 9

המחלקה RE, והמחלקה R
שקילות מודלים חישוביים - Curch-Turing-Thesis
דוגמה למודל חישובי "לא סביר"
אנומרטור - Enumerator
המחלקה co-RE
קידוד מכונת טיורינג למחרוזת בינארית, המכונה האוניברסלית
בעיית הקבלה, R!=RE
בעיית העצירה, ורדוקציות
שפה שאינה ב RE ואינה ב co-RE
הוכחה מטעמי ספירה ש"רוב השפות" אינן ב (RE איחוד co-RE)
סיכום

תרגול 9

RE, co-RE, R
אנומרטור
סיכום

שבוע עשירי

הרצאה 10

פונקציה חשיבה (פונקציה שלמה)
EmptyTM, REG-TM, EQ-TM
פונקציית ה- Busy Beaver
רדוקציית מיפוי
סיכום

תרגול 10

רדוקציות מיפוי
סיכום

שבוע אחת עשרה

הרצאה 11

משפט RICE
RE-Completeness
היסטוריית חישוב, קונפיגורציות חישוב
AllCFG
Linear Bounded Automata - LBA
Unrestricted Grammars - שקילות למכונת טיורינג
סיכום

תרגול 11

משפט Rice
LBA
עוד רדוקציות מיפוי
סיכום

שבוע שתיים עשרה

הרצאה 12

סיבוכיות - Complexity
DTime
כל שפה שניתן להכריע בזמן (o(nlogn מקיימת את למת הניפוח של רגולריות
שימוש בשני סרטים
NTime
המחלקה P והמחלקה NP
שפה היא ב NP אם"ם יש לה מוודא פולינומיאלי
סיכום

תרגול 12

NP, P
מוודא פולינומיאלי
סיכום

שבוע שלוש עשרה

הרצאה 13

דוגמאות לבעיות ב NP
אלגוריתם פסודו פולינומיאלי (פולינומיאלי במספר ולא בייצוג הבינארי שלו)
co-NP
NP-Completeness
רדוקציית מיפוי פולינומיאלית
הוכחה ש NPC לא ריקה
SAT, 2-SAT, 3-SAT
שפות ב NPC:

Clique
Independant Set

סיכום

תרגול 13

טענות על P=NP או P!=NP
Partition ו- XS הן NPC
סיכום

שבוע ארבע עשרה

הרצאה 14

הוכחה ש SAT היא NPC (הוכחת Cook-Levin)
הוכחה ש HamPath היא NPC
הוכחה ש Subset-Sum היא NPC
הוכחה ש Integer-Programming היא NPC
הוכחה ש HamPath היא NPC
הוכחה ש 2-SAT היא ב P
סיכום

תרגול 14

DSAT, TSAT,TDSAT
הוכחה ש Vertex-Cover היא NPC
סיכום

שבוע חמש עשרה

הרצאה 15

פונקציות שהן time-constructable
הוכחה שלכל (t(n) > nlog(n יש שפה שניתנת להכרעה ב ((O(t(n ולא ניתנת להכרעה ב

(( ((O((t(n)/ log(t(n

NP-Hardness ורדוקציית Karp
התמודדות עם בעיות NPC :

               קירובים - 2-קירוב ל VC , קירוב ל Set-Cover ו 2-קירוב ל max-cut
               אקראיות - קירוב רנדומי ל 3-SAT
               אלגוריתמים עבור קלטים חסומים או קלטים שאנחנו מניחים עליהם הנחות
               היוריסטיקה - Hueristics