Smart-World Surf

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

קורס 20604

מדעי המחשב · מרחב למידה אישי — יחידות, מושגים ומבחנים

שדרגו את הדף עם קובץ

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

אם לא סימנתם — הקובץ נקרא לחילוץ עובדות בלבד ואז נמחק מהמערכת (זכויות יוצרים). העובדות שנלמדו נשארות ומשפרות את הקורס.

גרסת הקהילה

📊 התקדמות הלמידה

0
הושלמו
12
סה"כ יחידות

לחצו על העיגול שליד כל יחידה כדי לסמן שהשלמתם אותה

📚 יחידות הקורס

12 יחידות

1
מבוא ורקע מתמטי
היסודות המתמטיים הדרושים להבנת מודלים חישוביים.
2
אוטומטים סופיים ושפות רגולריות
המודל החישובי הפשוט ביותר ויכולותיו.
3
תכונות של שפות רגולריות
הבנת המגבלות והיכולות של שפות רגולריות.
4
דקדוקים חסרי הקשר ואוטומטי מחסנית
מודלים חזקים יותר לתיאור שפות תכנות.
5
תכונות של שפות חסרות הקשר
ניתוח המאפיינים והמגבלות של שפות חסרות הקשר.
6
מכונות טיורינג
המודל האוניברסלי של חישוב והגדרת החישוביות.
7
שפות כריעות וניתנות לזיהוי
הבחנה בין בעיות שניתן לפתור לבעיות שניתן רק לזהות.
8
אי-כריעות ורדוקציות
הוכחת אי-כריעות של בעיות באמצעות רדוקציות.
9
מבוא לסיבוכיות חישובית
ניתוח יעילות אלגוריתמים ומשאבי חישוב.
10
מחלקות סיבוכיות P ו-NP
הבנת ההבדל בין בעיות הניתנות לפתרון מהיר לבעיות הניתנות לאימות מהיר.
11
שלמות NP ורדוקציות פולינומיות
זיהוי הבעיות הקשות ביותר במחלקת NP.
12
נושאים מתקדמים בחישוביות
הצצה למודלים ותיאוריות מעבר ליסודות.
📖

מושגים חשובים לבחינה

כל המושגים שכדאי להכיר לבחינה ✨

אלפבית (Alphabet)🔥 גבוה · מתוך 1 מבחנים
קבוצה סופית ולא ריקה של סמלים המשמשים לבניית מילים.הרחבה ←
מילה (String)🔥 גבוה · מתוך 1 מבחנים
סדרה סופית של סמלים מתוך אלפבית נתון.הרחבה ←
שפה (Language)🔥 גבוה · מתוך 1 מבחנים
קבוצה של מילים מעל אלפבית נתון.הרחבה ←
אוטומט סופי דטרמיניסטי (DFA)🔥 גבוה · מתוך 1 מבחנים
מודל חישובי המקבל או דוחה מילים על בסיס מעברים דטרמיניסטיים בין מצבים.הרחבה ←
אוטומט סופי לא דטרמיניסטי (NFA)🔥 גבוה · מתוך 1 מבחנים
מודל חישובי המאפשר מספר מעברים אפשריים ממצב נתון עבור סמל קלט נתון.הרחבה ←
ביטוי רגולרי (Regular Expression)🔥 גבוה · מתוך 1 מבחנים
דרך קומפקטית לתיאור שפות רגולריות באמצעות אופרטורים מוגדרים.הרחבה ←
למת הניפוח לשפות רגולריות (Pumping Lemma for Regular Languages)🔥 גבוה
כלי תיאורטי המשמש להוכחה ששפה מסוימת אינה רגולרית.הרחבה ←
דקדוק חסר הקשר (Context-Free Grammar - CFG)🔥 גבוה · מתוך 1 מבחנים
מערכת כללים פורמלית ליצירת שפות, שבה צד שמאל של כל כלל הוא משתנה יחיד.הרחבה ←
אוטומט מחסנית (Pushdown Automaton - PDA)🔥 גבוה
מודל חישובי בעל זיכרון מחסנית, המקביל בכוחו לדקדוקים חסרי הקשר.הרחבה ←
למת הניפוח לשפות חסרות הקשר (Pumping Lemma for CFLs)🔥 גבוה · מתוך 1 מבחנים
כלי תיאורטי המשמש להוכחה ששפה מסוימת אינה חסרת הקשר.הרחבה ←
מכונת טיורינג (Turing Machine - TM)🔥 גבוה · מתוך 1 מבחנים
מודל חישובי תיאורטי בעל סרט אינסופי, הנחשב למודל החזק ביותר של חישוב.הרחבה ←
תזת צ'רץ'-טיורינג (Church-Turing Thesis)בינוני
ההשערה שכל פונקציה שניתנת לחישוב באופן אינטואיטיבי ניתנת לחישוב על ידי מכונת טיורינג.הרחבה ←
שפה כריעה (Decidable Language)🔥 גבוה · מתוך 1 מבחנים
שפה שעבורה קיימת מכונת טיורינג שעוצרת על כל קלט ומכריעה אם הקלט בשפה או לא.הרחבה ←
שפה ניתנת לזיהוי (Recognizable Language)🔥 גבוה · מתוך 1 מבחנים
שפה שעבורה קיימת מכונת טיורינג שעוצרת ומקבלת את כל המילים בשפה, ועשויה לא לעצור על מילים שאינן בשפה.הרחבה ←
בעיית העצירה (Halting Problem)🔥 גבוה · מתוך 1 מבחנים
הבעיה הבלתי כריעה של קביעה האם מכונת טיורינג נתונה תעצור על קלט נתון.הרחבה ←
רדוקציה (Reduction)🔥 גבוה · מתוך 1 מבחנים
טכניקה להוכחת אי-כריעות או שלמות NP של בעיה על ידי המרתה לבעיה אחרת.הרחבה ←
מחלקת P (Class P)🔥 גבוה
מחלקת בעיות ההכרעה שניתנות לפתרון בזמן פולינומיאלי על ידי מכונת טיורינג דטרמיניסטית.הרחבה ←
מחלקת NP (Class NP)🔥 גבוה · מתוך 1 מבחנים
מחלקת בעיות ההכרעה שניתנות לאימות בזמן פולינומיאלי על ידי מכונת טיורינג דטרמיניסטית.הרחבה ←
בעיה שלמה ל-NP (NP-Complete Problem)🔥 גבוה · מתוך 1 מבחנים
בעיה במחלקת NP שכל בעיה אחרת ב-NP ניתנת לרדוקציה אליה בזמן פולינומיאלי.הרחבה ←
אי-כריעות (Undecidability)🔥 גבוה · מתוך 1 מבחנים
תכונה של בעיה שאין אלגוריתם (מכונת טיורינג) שיכול לפתור אותה עבור כל קלט.הרחבה ←
חישוביות (Computability)בינוני
ענף במדעי המחשב החוקר אילו בעיות ניתנות לפתרון אלגוריתמי.הרחבה ←
סיבוכיות (Complexity)בינוני
ענף במדעי המחשב החוקר את משאבי החישוב (זמן וזיכרון) הנדרשים לפתרון בעיות.הרחבה ←
🎓

תרגול מבחן (AI)

מבחן לדוגמה שנוצר מכל יחידות הקורס — אמריקאיות + פתוחות, מנוקד ונבדק אוטומטית

🎓

📝 מבחנים לתרגול

תרגלו עם מבחנים אמיתיים מהארכיון של הקורס

📋

כניסה לארכיון המבחנים

מבחנים ופתרונות מהשנים האחרונות

61 📄
0 / 61סומנו כהושלמו

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

מבחנים51
סטטוס מבחן שנה הערות
2025 מועד א2 - פתרון 1 2025
2025א מועד 64.84 2025
2025א מועד 64.84 - פתרון 1 2025
2025א מועד 64.84 - פתרון 2 2025
2025א מועד 95 - פתרון 2025
2025א מועד א2 - פתרון 2 2025
2024ב מועד 65 2024
2024ב מועד 84 - פתרון 2024
2024ב מועד 94 - פתרון 2024
openu examsol2 helplesson 2024 bet 2024
20604 · bank67_בחינה לדוגמא 1 2011א משתלה_0 2011
bank67 בחינה לדוגמא 2011א גיליון עבודה 0.xlt 2011
bank67 פתרון גיליון תשובות בחינה לדוגמא 2011א 0 2011
20604 · בחינה לדוגמה 2010ב_1 2010
פתרון בחינה לדוגמה 2010ב 0 2010
בחינה לדוגמא 2006 0 2006
בחינה לאתר 2005א מועד א5 1 2005
exam2003a2b 1 2003
exam2003a4a 1 2003
exam2003b1a 1 2003
exam2003b2b 1 2003
exam2003b3a 1 2003
exam2002b1a 1 2002
exam2002b3a 1 2002
exam2002b4b 1 2002
20604 · doc.בחינה מספר 1_0
20604 · doc.בחינה מספר 2_0
20604 · בחינה 4 קפיטריה_0_1
20604 · בחינה מספר 1 גיליון תשובות _0
20604 · בחינה מספר 2 גיליון תשובות_0
20604 · נספח תשובות בחינה 4 קפיטריה_0
EXAM EXAMPLE final
openu exam example2
openu exam example2
openu exam1 example1 modelim v1
openu exam1 example1 modelim v1 and sol
בחינה מספר 1 0.xlt
בחינה מספר 2 0.xlt
בחינה מספר 4 קפיטריה 0 0.xlt
מבחן לדוגמא 3 לאתר 0.xlt
מבחן1 - איתן סבג
מבחן2 - איתן סבג
מבחן3 - איתן סבג
מבחן4 - איתן סבג
מבחן6 - איתן סבג
מבחן7 - איתן סבג
מבחן8 - איתן סבג
מבחן9 - איתן סבג
פתרון
פתרון שאלות תרגול
שאלון

📖 מקורות עיקריים

חומרי הלימוד והחוקרים שעליהם מבוסס הקורס

📕
Introduction to the Theory of Computation
ספר הלימוד הסטנדרטי והמקיף ביותר בתחום, מומלץ לכל סטודנט.
📕
Introduction to Automata Theory, Languages, and Computation
ספר קלאסי נוסף המכסה את תורת האוטומטים, שפות וחישוביות לעומק.
👥
חלוצי תורת החישוביות
אלן טיורינג, אלונזו צ'רץ', סטיבן קוק, ריצ'רד קארפ – דמויות מפתח בפיתוח התחום.
🎓
Easy Theory (ערוץ יוטיוב)
ערוץ יוטיוב מצוין עם הסברים ברורים ואינטואיטיביים למושגי תורת החישוביות.
🔗
MIT OpenCourseware - Theory of Computation
קורסים פתוחים של MIT המציעים חומרי לימוד, הרצאות ותרגילים בנושאי הקורס.