קורסים בתאוריה של מדעי המחשב
-
כל נושא מקושר ל-Playlist ביוטיוב.
-
מומלץ לסכם תוך כדי צפייה, חלק מהסיכומים מועלים לאתר (והיתר יעלו בהמשך).
צפייה מהנה :)
תורת הקבוצות (לרוב נלמד במתמטיקה דיסקרטית או לוגיקה ותורת הקבוצות)
-
מבוא לתורת הקבוצות: שייכות, הכלה, תת-קבוצות, הפרדוקס של ראסל, איחוד, חיתוך, השלמה, חוקי דה-מורגן, חוקי פילוג, קבוצת החזקה, איחוד כללי
סיכום מבוא לתורת הקבוצות הנאיבית -
יחסים ופונקציות: מכפלה קרטזית, יחסים, תכונות של יחסים, פעולות על יחסים, יחסי סדר, יחסי שקילות ומחלקות שקילות
סיכום יחסים ופונקציות -
עוצמות של קבוצות: שוויון עוצמות, היחס קטן/שווה בעוצמות, קבוצות בנות-מניה, המלון של הילברט, קבוצות לא בנות-מניה, משפט קנטור
סיכום עוצמות של קבוצות -
אינדוקציית מבנה: הגדרת קבוצה באינדוקציה, הגדרת פונקציה באינדוקציה, הוכחת תכונות באינדוקציה
סיכום אינדוקציית מבנה
אוטומטים ושפות פורמליות (לרוב נלמד באוטומטים ושפות פורמליות או מודלים חישוביים)
-
-
אוטומט סופי דטרמניסטי: שפות רגולריות, סגירות תחת חיתוך, סגירות תחת השלמה, סגירות תחת איחוד סופי, שפות אי-רגולריות, אי-סגירות תחת איחוד אינסופי
סיכום אוטומט סופי דטרמניסטי -
אוטומט סופי אי-דטרמניסטי: אוטומט סופי אי-דטרמניסטי (NFA), שקילות בין NFA ל-DFA, אוטומט החזקה, NFA עם מעברי-אפסילון, שקילות בין NFA עם מעברי-אפסילון ל-NFA, שימושים לאי-דטרמניזם, סגירות שפות רגולריות תחת סגור קלייני
סיכום אוטומט אי-דטרמניסטי -
משפט מייהיל-נרוד: אלגוריתם לצמצום אוטומט סופי דטרמניסטי, יחס מייהיל-נרוד, משפט מייהיל-נרוד, שימוש במשפט מייהיל-נרוד להוכחת אי-רגולריות
סיכום משפט מייהיל נרוד -
ביטויים רגולריים: הגדרה, דוגמאות, שקילות בין ביטויים רגולריים ל-NFA
-
-
שפות חסרות הקשר
-
דקדוקים חסרי הקשר: דקדוקים חסרי הקשר, כל שפה רגולרית היא חסרת הקשר, דקדוק לינארי ימני שקול לשפות רגולריות, שפות חסרות הקשר סגורות תחת איחוד, שרשור וסגור קלייני, שפות חסרות הקשר לא סגורות תחת חיתוך והשלמה, למת הניפוח לשפות חסרות הקשר
-
אוטומט מחסנית: אוטומט מחסנית, דוגמאות, קונפיגורציות, שקילות בין אוטומט מחסנית לדקדוק חסר הקשר
-
פישוטים של דקדוק חסר הקשר: סילוק משתנים מיותרים, סילוק כללי-אפסילון וכללי יחידה, הצורה הנורמלית של חומסקי
-
לוגיקה (לרוב נלמד בלוגיקה למדעי המחשב או לוגיקה ותורת הקבוצות)
-
אינדוקציית מבנה (חומר רקע הכרחי מתורת הקבוצות)
סיכום אינדוקציית מבנה -
תחשיב הפסוקים: סינטקס וסמנטיקה של תחשיב הפסוקים, מערכת שלמה של קשרים, מונחים סמנטיים: טאוטולוגיה, סתירה, ספיקות, גרירה לוגית, תכונות של גרירה לוגית
סיכום תחשיב הפסוקים -
מערכת הוכחה לתחשיב הפסוקים: אקסיומות וכלל היסק, משפט הנאותות, קבוצה עקבית, קבוצה עקבית מקסימלית, משפט השלמות
סיכום מערכת הוכחה לתחשיב הפסוקים -
גדירות בתחשיב הפסוקים: משפט הקומפקטיות, קבוצות השמות גדירות, גדירות באופן סופי, הוכחת אי-גדירות בעזרת משפט הקומפקטיות
סיכום גדירות בתחשיב הפסוקים -
תחשיב היחסים סינטקס וסמנטיקה, מילון, שמות עצם משתנים חופשיים וקשורים, מבנה, השמה
-
גדירות בתחשיב היחסים: גדירות של יחס במבנה, אי-גדירות של יחס במבנה, גדירות של קבוצת מבנים, משפט הקומפקטיות, אי-גדירות של קבוצת מבנים
חישוביות (לרוב נלמד בחישוביות וסיבוכיות או מודלים חישוביים)
-
מכונות טיורינג: מבוא, הגדרה, דוגמאות, קונפיגורציות, מכונות טיורינג שמחשבות פונקציה
-
סוגים שונים של מכונות טיורינג: מכונת טיורינג מרובת סרטים, מכונת טיורינג אי-דטרמניסטית, שקילות בין המודלים.
סיכום מכונות טיורינג וסוגיהן השונים -
מחלקות חישוביות: המחלקות R, RE, coRE. סגירות R תחת איחוד, חיתוך, השלמה, שרשור וסגור קלייני. סגירות RE תחת איחוד, חיתוך, שרשור וסגור קלייני, ואי-סגירות תחת השלמה. R הוא החיתוך בין RE ל-coRE.
סיכום מחלקות חישוביות -
שפות לא כריעות ורדוקציות: קידודים של מכונות טיורינג, המכונה האוניברסלית, שפת האלכסון, משפט הרדוקציה, רדוקציות בין שפות
-
משפט רייס: דוגמאות לשימוש והוכחה
-
מחלקות סיבוכיות פולינומית: המחלקה P, יחס זיהוי ואלגוריתם זיהוי, אלגוריתם אי-דטרמניסטי, המחלקה NP וההגדרות השקולות שלה
-
בעיות NP-שלמות: בעיית P=NP? בעיות NP-שלמות, רדוקציות בין בעיות, משפט קוק-לוין, דוגמאות לבעיות NP-שלמות: כיסוי בצמתים, כיסוי בקבוצות, SAT, 3-SAT, קליקה, מחלקות סיבוכיות נוספות.
קומבינטוריקה (לרוב נלמד במתמטיקה דיסקרטית או קומבינטוריקה למדעי המחשב)
-
עקרונות ספירה: עקרון החיבור, עקרון הכפל, בחירה עם ובלי חזרות ועם ובלי חשיבות לסדר, הבינום של ניוטון, מולטינום, משולש פסקל, מספרי קטלן
-
עקרון שובך היונים: עקרון שובך היונים, הכללות, משפט ארדש-סקרש
-
עקרון ההכלה-הדחה: דוגמאות, הכללת עקרון ההכלה-הדחה
-
נוסחאות נסיגה: סדרת פיבונאצ'י, מספרי סטירלינג, פתרון של נוסחת נסיגה לינארית הומוגנית ולא הומוגנית
אלגוריתמים (חלק מהחומר נלמד גם במבני נתונים)
-
גרפים: הגדרות ותכונות בסיסיות, מבני נתונים לייצוג גרפים: מטריצת שכנויות ורשימת שכנויות
סיכום גרפים -
BFS חיפוש לרוחב: הדגמה, ניתוח סיבוכיות, הוכחת נכונות, שימושים ל-BFS
סיכום BFS -
DFS חיפוש לעומק: הדגמה, ניתוח סיבוכיות, עצי עומק, למת הסוגריים, למת המסלול הלבן, סיווג קשתות (עץ, אחורה, קדימה, חוצה)
-
שימושים ל-DFS: זיהוי מעגלים, מיון טופולוגי, מציאת רכיבים קשירים היטב (רכיבי קשירות חזקה)
סיכום DFS -
אלגוריתמים חמדניים: תזמון תהליכים והוכחה בעזרת טיעון החלפה, מסלולים קלים ביותר, האלגוריתם של Dijkstra, מציאת עצים פורשים מינימלים, האלגוריתם של Kruskal, האלגוריתם של Prim
סיכום אלגוריתמים חמדניים -
הפרד ומשול: מיון מיזוג, ספירת היפוכים במערך, מציאת זוג נקודות קרובות ביותר
סיכום הפרד ומשול -
תכנון דינאמי: מבוא, בעיית תרמיל השק (Knapsack problem), אלגוריתם Bellman-Ford למציאת מסלולים קלים ביותר.
סיכום תכנון דינאמי -
רשתות זרימה: בעיית הזרימה המקסימלית, תכונות של זרימה מקסימלית, אלגוריתם פורד-פלקרסון, מציאת שידוך מקסימלי בעזרת זרימה מקסימלית.
סיכום רשתות זרימה
מבני נתונים
-
ערימה: עץ בינארי, תור קדימויות כערימת מקסימום, תיקון ערימה Heapify, בניית ערימה, פעולות על ערימה: הוצאת והחזרת מקסימום, הכנסת איבר חדש, עדכון מפתח, מיון ערימה.
סיכום ערימה -
עץ חיפוש בינארי: הגדרה, שאילתות: חיפוש, מינימום, מקסימום, עוקב, קודם. הכנסה, הוצאה. סיורים בעץ: סריקה תחילית, תוכית, סופית.
סיכום עץ חיפוש בינארי