פא"ר > החטיבה למדעי המחשב > אוטומטים ושפות פורמליות
שלום אורח  הרשם לפא"ר
אוטומטים ושפות פורמליות - 20440
מרכז/ת ההוראה: יוסי קאופמן

4 נקודות זכות ברמה רגילה

שיוך: מדעים / מדעי המחשב

ידע קודם דרוש: הקורסים מבוא למדעי המחשב ושפת Java,2 מתמטיקה דיסקרטית: תורת הקבוצות, קומבינטוריקה ולוגיקה.3 ידע קודם מומלץ: הקורסים חשבון אינפיניטסימלי 1, אלגברה לינארית 1.

פיתוח הקורס: פרופ' שמואל זקס, פרופ' נסים פרנסיז (כתיבה), פרופ' יהודית גל-עזר, בני פרידמן, ד"ר ענת לרנר, יוסי קאופמן, ד"ר מיכל ארמוני; בת-שבע כהן (עריכה)

יועצים: פרופ' דוד הראל, פרופ' עמירם יהודאי, פרופ' יעקב שוויקה

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

מטרת הקורס היא הכרת המודלים החישוביים היסודיים והשוואת כוח החישוב שלהם, ובמקביל – הכרת המשפחות היסודיות של שפות פורמליות.

חומר הלימוד

יחידה 1

מושגים בסיסיים

יחידה 2

אוטומט סופי דטרמיניסטי

יחידה 3

אוטומט סופי לא-דטרמיניסטי וביטויים רגולריים

יחידה 4

תכונות של שפות רגולריות

יחידה 5

אפיון אלגברי של השפות הרגולריות

יחידה 6

דקדוקים

יחידה 7

פישוטים וצורות נורמליות של דקדוקים חופשיי-הקשר

יחידה 8

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

יחידה 9

תכונות של שפות חופשיות-הקשר

1 להשלכות על צבירת נ"ז בשל חפיפה עם קורס(ים) אחר(ים), ראו טבלת קורסים חופפים.

2 או שני הקורסים מבוא למדעי המחשב ושפת Java א (20453, 3 נ"ז) ומבוא למדעי המחשב ושפת Java ב (20454, 3 נ"ז), או הקורס מבוא למדעי המחשב (20427), שאינו מוצע עוד.

3 או הקורס מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים (20476), שיילמד החל מסמסטר ב2011.