נקודות זכות באוניברסיטה העברית: 5

תואר: בוגר

היחידה האקדמית שאחראית על הקורס: מדעי המחשב

סמסטר: סמסטר א' או / ו ב'

שפת ההוראה: עברית

קמפוס: קרית א"י ספרא

מורה אחראי על הקורס (רכז): פרופ אורנה קופרמן ודוקטור עודד שוורץ

דוא"ל של המורה האחראי על הקורס: orna@cs.huji.ac.il

שעות קבלה של רכז הקורס: בתיאום מראש בדואר אלקטרוני

מורי הקורס:
פרופ עמרי וינשטין,
פרופ עודד שוורץ,
מר יואב גרוס,
גב נעמה שמש-הלוי,
גב מאיה דותן,
מר עופר לשקוביץ,
פרופ אורנה קופרמן,
מר בדר אבו ראדי

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

להלן פרוט נושאים ספציפיים אפשריים בקורס.

אוטומטיים ושפות פורמליות: אוטומטיים סופיים ושפות רגולריות, תכונות סגור, דטרמיניזציה, מינימליות, שפות חסרות הקשר, דקדוקים, אוטומטי מחסנית. חישוביות: מודל מכונת טיורינג,כריעות ואי כריעות, רדוקציה. .3 סיבוכיות: סיבוכיות זמן וזכרון. המחלקות ,NP,P PSPACE, NLOGSPACE ושלמות במחלקות אלה, משפטי ההיררכיה. נושאים מתקדמים נוספים.

מטרות הקורס:
NA

תוצרי למידה :
בסיומו של קורס זה, סטודנטים יהיו מסוגלים:
NA

דרישות נוכחות (%):
0

שיטת ההוראה בקורס: הרצאות, תרגולים, תרגילים ובחנים.

רשימת נושאים / תכנית הלימודים בקורס:
NA

חומר חובה לקריאה:
אין

חומר לקריאה נוספת:
Introduction to the Theory of Computation by Michael Sipser

הערכת הקורס - הרכב הציון הסופי :
מבחן מסכם בכתב/בחינה בעל פה 80 %
הרצאה0 %
השתתפות 0 %
הגשת עבודה 0 %
הגשת תרגילים 10 %
הגשת דו"חות 0 %
פרויקט מחקר 0 %
בחנים 10 %
אחר 0 %

מידע נוסף / הערות:
NA