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

מטרת היחידה

לערוך היכרות עם תחום תאורטי של מדעי המחשב, המתאר מכונות חישוב באמצעות כמה מודלים ומנתח את כוחם ותכונותיהם של מודלים אלה.

ביבליוגרפיה

1. האונ' הפתוחה (1991), אוטומטים ושפות פורמליות, כרכים א' ו-ב'.

2. הראל ד. (1991), אלגוריתמיקה, יסודות מדעי המחשב, האונ' הפתוחה.

3. Barwise, Etchemendy (1993), Turing’s World, An Introduction to Computability Theory, CLSI Publications.

4. Davis, Sigal, Weyuker (1994), Computability, Complexity and Languages, Fundamentals of Theoretical Computer Science, Academic Press.

5. Hopcroft, Ullman (1979), Introduction to Automata Theory, Languages and Computations, Addison-Wesely.

6. היחידה מחולקת לשלושה חלקים:

   אוטומט סופי.

   אוטומט מחסנית.

   מכונות טיורינג .

   חלק ראשון – האוטומט הסופי ( פרקים 1 – 4 )

   חלק זה נוטל נתח עיקרי מהזמן המוקדש ליחידת לימוד זו. כאן מוקנים לתלמידים בהדרגה הכלים, דרכי החשיבה בתחום והמונחים המקובלים בו תוך עיסוק במשפחת השפות הרגולריות (באמצעות האוטומטים הסופיים). המודלים שמוצגים בחלק זה הם האוטומט הסופי הדטרמיניסטי, האוטומט הסופי הדטרמיניסטי הלא מלא והאוטומט הסופי הלא דטרמיניסטי.

   חלק שני – אוטומט המחסנית ( פרקים 5 – 6 )

   חלק זה עוסק במשפחת השפות חופשיות ההקשר ומציג אותה באמצעות מודל אוטומט המחסנית.

   חלק שלישי – מכונת טיורינג ( פרק 7 )

   חלק זה מציג מודל לתכנית מחשב – מכונת טיורינג – ונערך בו דיון על התיזה של צ'רץ' וטיורינג ועל מגבלותיו של המחשב.

פרק 1: תיאור מערכות ופתרון חידות ( 6 שעות )

מטרת הפרק

1. להכיר את המושגים הבסיסיים בתחום.

פירוט התכנים

תיאור גרפי של מערכות: דוגמאות ומושגים (מצב, קלט, מעבר, מצב התחלתי). פתרון חידות בעזרת תיאור גרפי: דוגמאות ומושגים (מצב מקבל, מצב מלכודת).

פרק 2: אוטומט סופי דטרמיניסטי ( 15 שעות )

מטרות הפרק

1. להציג מודל האוטומט הסופי הדטרמיניסטי.

2. לתרגל בניית אוטומטים.

פירוט התכנים

אוטומט סופי דטרמיניסטי; מסלול חישוב מקבל ולא מקבל; תיאור אוטומט בדרך גרפית או על-ידי פירוט מרכיביו תוך שימוש בטבלת מעברים או בפונקציית מעברים. אוטומטי ספירה, חיפוש.

פרק 3: מילים ושפות פורמליות ( 15 שעות )

מטרות הפרק

1. להכיר מושגים בסיסיים בתורת השפות הפורמליות.

2. לחקור את כוחו של מודל האוטומט הסופי הדטרמיניסטי ואת תכונות משפחת השפות הרגולריות.

פירוט התכנים

מושגים בסיסיים: אות, א"ב, מילה, אורך מילה, המילה הריקה, שפה פורמלית. פעולות על מילים ועל שפות: שרשור, חזקה, היפוך. שפה רגולרית, שפות שאינן רגולריות, תכונות סגירות של משפחת השפות הרגולריות: דיון בסגירות לחלקיות, משלים, חיתוך ואיחוד.

פרק 4: מודלים נוספים של אוטומט סופי ( 15 שעות )

מטרות הפרק

1. להבין כיצד אפשר – על-ידי שינוי הגדרה קיימת של מודל חישובי – לקבל מודלים חדשים.

2. להכיר את מושג האי-דטרמיניזם ולדון בהשוואת כוחם של מודלים חישוביים.

פירוט התכנים

אוטומט סופי דטרמיניסטי לא מלא; אוטומט סופי לא דטרמיניסטי; שקילות של מודל האוטומט הסופי הדטרמיניסטי ומודל האוטומט הסופי הלא דטרמיניסטי; תכונות סגירות של משפחת השפות הרגולריות: דיון בסגירות לשרשור, היפוך ואיחוד.

פרק 5: אוטומט המחסנית ( 12 שעות )

מטרת הפרק

1. להכיר את מודל אוטומט המחסנית הלא דטרמיניסטי.

2. לתרגל את בניית אוטומט המחסנית.

פירוט התכנים

השימוש במחסנית כמבנה עזר, אוטומט מחסנית לא דטרמיניסטי.

פרק 6: כוחו ומגבלותיו של מודל אוטומט המחסנית ( 12 שעות )