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

תוכן העניינים:

1. ההגדרות הפורמליות של האובייקטים
2. קידודים של אובייקטים סופיים
3. פונקציה חשיבה בזמן פולינומיאלי
4. ההגדרה של רדוקציה פולינומיאלית
5. הכתיבה המלאה של רדוקציה פולינומיאלית

הערות נוספות:

1. סיכומים: לכל שיעור מצורף קובץ PDF הניתן להורדה, ובו מופיע כל מה שנכתב במהלך השיעור.
2. ידע קודם: לא נדרש ידע קודם.

לכניסה ישירה >>

היכרות עם טכניקות שימושיות לרדוקציות העוסקות בצביעות של גרפים.

תוכן העניינים:

1. הוספת רכיב קשה לצביעה
2. קיבוע של צבעים

הערות נוספות:

1. סיכומים: לכל שיעור מצורף קובץ PDF הניתן להורדה, ובו מופיע כל מה שנכתב במהלך השיעור.
2. ידע קודם נדרש: היכרות והתנסות עם ההגדרה של רדוקציה בזמן פולינומיאלי.
3. הקורס לא עוסק בכתיבה פורמלית אלא בדוגמאות: כתיבה פורמלית של רדוקציה נלמדת בקורס "יסודות לרדוקציות בזמן פולינומיאלי".
4. משך הגישה: חומר הלימוד יהיה זמין לרוכשים למשך ארבעה חודשים.

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

תוכן העניינים:

1. כל גרסאות המילטון והרדוקציות ביניהן
2. המילטון כתת גרף
3. המילטון וגרפים ממושקלים

הערות נוספות:

1. סיכומים: לכל שיעור מצורף קובץ PDF הניתן להורדה, ובו מופיע כל מה שנכתב במהלך השיעור.
2. ידע קודם נדרש: היכרות והתנסות עם ההגדרה של רדוקציה בזמן פולינומיאלי.
3. הקורס לא עוסק בכתיבה פורמלית אלא בדוגמאות: כתיבה פורמלית של רדוקציה נלמדת בקורס "יסודות לרדוקציות בזמן פולינומיאלי".
4. משך הגישה: חומר הלימוד יהיה זמין לרוכשים למשך ארבעה חודשים.

​היכרות עם טכניקות שמתאימות לעבודה עם מספרים, וסקירה של טריקים נפוצים בבחינות. דגש על הבעיות של SUBSET-SUM ו- PARTITION.

תוכן העניינים:

1. שינוי רזולוציה
2. הוספת מספרים גדולים
3. לפחות ולכל היותר
4. שימוש בחזקות של שתיים

הערות נוספות:

1. סיכומים: לכל שיעור מצורף קובץ PDF הניתן להורדה, ובו מופיע כל מה שנכתב במהלך השיעור.
2. ידע קודם נדרש: היכרות והתנסות עם ההגדרה של רדוקציה בזמן פולינומיאלי.
3. הקורס לא עוסק בכתיבה פורמלית אלא בדוגמאות: כתיבה פורמלית של רדוקציה נלמדת בקורס "יסודות לרדוקציות בזמן פולינומיאלי".
4. משך הגישה: חומר הלימוד יהיה זמין לרוכשים למשך ארבעה חודשים.

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

תוכן העניינים:

1. ניפוח מספר ההשמות
2. ניטרול פסוקיות
3. השמות מאוזנות
4. הוספת ליטרלים בתוך פסוקית
5. קיבוע של ערכי אמת

הערות נוספות:

1. סיכומים: לכל שיעור מצורף קובץ PDF הניתן להורדה, ובו מופיע כל מה שנכתב במהלך השיעור.
2. ידע קודם נדרש: היכרות והתנסות עם ההגדרה של רדוקציה בזמן פולינומיאלי. היכרות עם מושגים בסיסיים הקשורים לנוסחאות בוליאניות (פסוקית, השמה, צורת CNF).
3. הקורס לא עוסק בכתיבה פורמלית אלא בדוגמאות: כתיבה פורמלית של רדוקציה נלמדת בקורס "יסודות לרדוקציות בזמן פולינומיאלי".
4. משך הגישה: חומר הלימוד יהיה זמין לרוכשים למשך ארבעה חודשים.

​

סקירה מסודרת של השיטות השונות ברדוקציות עם גרפים לא מכוונים, היכרות עם טכניקות בנייה שימושיות ועם טריקים נפוצים בבחינות. מגוון רחב של דוגמאות. דגש על הבעיות של קליקה (CLIQUE), קבוצה בלתי תלויה (IS), כיסוי קודקודים (VC) וקבוצה שולטת (DS).

תוכן העניינים:

1. הבנת הקשרים בין השפות: CLIQUE IS VC DS
2. חיתוכים ואיחודים של השפות: CLIQUE IS VC DS
3. אובייקטים בגודל מחצית מהגרף
4. אובייקטים בגודל מקורב
5. אובייקטים כמעט תקינים
6. עקרונות ברדוקציות מ – VC

הערות נוספות:

1. סיכומים: לכל שיעור מצורף קובץ PDF הניתן להורדה, ובו מופיע כל מה שנכתב במהלך השיעור.
2. ידע קודם נדרש: היכרות והתנסות עם ההגדרה של רדוקציה בזמן פולינומיאלי. היכרות עם ההגדרה של קליקה, קבוצה בלתי תלוי וכיסוי קודקודים. נושאים אלה נלמדים בקורס "יסודות לרדוקציות בזמן פולינומיאלי".
3. הקורס לא עוסק בכתיבה פורמלית אלא בדוגמאות: כתיבה פורמלית של רדוקציה נלמדת בקורס "יסודות לרדוקציות בזמן פולינומיאלי".
4. משך הגישה: חומר הלימוד יהיה זמין לרוכשים למשך ארבעה חודשים.

​

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

תוכן העניינים:

1. רדוקציה מ- 3SAT ל- CLIQUE ול- IS
2. רדוקציה מ- 3SAT ל- HAMILTON
3. רדוקציה מ- 3SAT ל- SUBSETSUM
4. רדוקציה מ- 3SAT ל-VC
5. רדוקציה מ- 3SAT ל- 3COLOR

הערות נוספות:

1. סיכומים: לכל שיעור מצורף קובץ PDF הניתן להורדה, ובו מופיע כל מה שנכתב במהלך השיעור.
2. ידע קודם נדרש: היכרות והתנסות עם ההגדרה של רדוקציה בזמן פולינומיאלי. היכרות עם מושגים בסיסיים הקשורים לנוסחאות בוליאניות ולגרפים. נושאים אלה נלמדים בקורס "יסודות לרדוקציות בזמן פולינומיאלי".
3. הקורס לא עוסק בכתיבה פורמלית אלא בדוגמאות: כתיבה פורמלית של רדוקציה נלמדת בקורס "יסודות לרדוקציות בזמן פולינומיאלי".
4. משך הגישה: חומר הלימוד יהיה זמין לרוכשים למשך ארבעה חודשים.