Start Date

Course is open

Price

Free

Course Duration

12 שבועות | 4-6 שעות בשבוע

מה נלמד?

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

Description:

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

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

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

The course is open. Registration is open

The course staff:

Yonatan Aumann

Lecturer

About Me

Dr. Ron Adany

Teaching Assistant

About Me

Akiva Kleinerman

Teaching Assistant

About Me