קורסים שאינם מקנים נקודות זכות
20440 אוטומטים ושפות פורמליות1
4 נקודות זכות ברמה רגילה
שיוך: מדעים / מדעי המחשב
ידע קודם דרוש: הקורסים מבוא למדעי המחשב ושפת Java,2 מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים. ידע קודם מומלץ: הקורסים חשבון אינפיניטסימלי 1 (20474),3 אלגברה לינארית 1 (או אלגברה ליניארית לתלמידי מדעים ) 4.
כתיבה: פרופ' שמואל זקס, פרופ' נסים פרנסיז
יועצים: פרופ' דוד הראל, פרופ' עמירם יהודאי, פרופ' יעקב שוויקה
פיתוח: פרופ' יהודית גל-עזר, בני פרידמן, ד"ר ענת לרנר, יוסי קאופמן, ד"ר מיכל ארמוני; בת-שבע כהן (עריכה)
הקורס כלול בסדרה של קורסים המקנים את היסודות התאורטיים במדעי המחשב, ודן בבעיות מתמטיות בסיסיות המונחות ביסודם של מדעי המחשב.
מטרת הקורס היא הכרת המודלים החישוביים היסודיים והשוואת כוח החישוב שלהם, ובמקביל – הכרת המשפחות היסודיות של שפות פורמליות.
חומר הלימוד
|
יחידה 1 |
מושגים בסיסיים |
|
יחידה 2 |
אוטומט סופי דטרמיניסטי |
|
יחידה 3 |
אוטומט סופי לא-דטרמיניסטי וביטויים רגולריים |
|
יחידה 4 |
תכונות של שפות רגולריות |
|
יחידה 5 |
אפיון אלגברי של השפות הרגולריות |
|
יחידה 6 |
דקדוקים |
|
יחידה 7 |
פישוטים וצורות נורמליות של דקדוקים חופשיי-הקשר |
|
יחידה 8 |
אוטומט-מחסנית |
|
יחידה 9 |
תכונות של שפות חופשיות-הקשר |
1 להשלכות על צבירת נ"ז בשל חפיפה עם קורס(ים) אחר(ים), ראו פירוט החפיפה.
2 או שני הקורסים מבוא למדעי המחשב ושפת Java א (20453, 3 נ"ז) ומבוא למדעי המחשב ושפת Java ב (20454, 3 נ"ז).
3 או הקורס חשבון אינפיניטסימלי 1 (20106), שאינו מוצע עוד.
4 בעבר נקרא הקורס אלגברה לינארית לתלמידי מדעי הטבע.