FANDOM


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

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


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

Algorithms -- overview עריכה

הורדה צפייה

תאריך: 02-01-01

Sorting עריכה

הורדה צפייה

תאריך: 02-02-01


Sorting II עריכה

הורדה צפייה

תאריך: 02-04-01


Searching & Data Structures עריכה

הורדה צפייה

תאריך: 02-05-01


Red-Black Trees עריכה

הורדה צפייה

תאריך: 02-06-01


Graph Algorithms I - Topological Sorting, Prim's Algorithm עריכה

הורדה צפייה

תאריך: 02-07-01


Graph Algorithms II - DFS, BFS, Kruskal's Algorithm, Union Find Data Structure עריכה

הורדה צפייה

תאריך: 02-08-01


Graph Algorithms III: Shortest Pathעריכה

הורדה צפייה

תאריך: 02-09-01


Graph Alg. IV: Intro to geometric algorithms עריכה

הורדה צפייה

תאריך: 02-12-01


Geometric Algorithms: Graham & Jarvis עריכה

הורדה צפייה

תאריך: 02-13-01


Dynamic Programming I עריכה

הורדה צפייה

תאריך: 02-14-01


Dynamic programming II עריכה

הורדה צפייה

תאריך: 02-15-01


Parsing עריכה

הורדה צפייה

תאריך: 02-16-01


Knapsack, Bandwidth Min. Intro: Greedy Algs. עריכה

הורדה צפייה

תאריך: 02-20-01


Greedy Algs. II & Intro to NP Completeness עריכה

הורדה צפייה

תאריך: 02-21-01


NP Completeness II & Reductions עריכה

הורדה צפייה

תאריך: 02-22-01

השיעור מתחיל בחזרה על הגדרת המחלקות P וNP:

בעיות אשר מצויות במחלקה P הן בעיות שניתנות לפתרון דטרמיניסטי (סדרתי) בזמן פולינומיאלי ובעיות השייכות למחלקה NP הן בעיות שניתנות לפתרון לא דטרמיניסטי פולינומיאלי - כאלה שבהן ניתן לבדוק נכונות פתרון מוצע בזמן פולינומיאלי. (אי הדטרמיניזם מתבטא בכך שאין צורך לחפש את הפתרון הנכון, וניתן "להניח" שהוא ייבחר אם הוא קיים, ותתקבל תשובה נכונה בזמן פולינומיאלי.)

כדוגמא לכך ניתנות מספר בעיות:

  1. בעית המסלול ההמילטוני - קיומו של מעגל בגרף אשר מכיל את כל צמתי הגרף. ניתן לבדוק כל פתרון אפשרי (מעגל בגרף) בזמן פולינומיאלי, אבל מספר הפתרונות האפשריים הוא \ n!, (מספר הסידורים של n צמתים בשורה) ומכונה דטרמיניסטית הייתה זקוקה לזמן אקספוננציאלי לפתרון הבעיה.
  2. בעיית הקליקה (גרף שלם) - האם קיימת קליקה מסדר k בגרף? ניתן לבדוק בזמן פולינומיאלי האם k צמתים נתונים מרכיבים קליקה. (האם בין כל שניים מהם קיימת קשת) לכן, מכונה בלתי דטרמיניסטית תוכל לבצע בדיקה זו לכל k צמתים בגרף במקביל ולפתור בעיה זו בזמן פולינומיאלי בעוד שמכונה דטרמיניסטית עלולה להאלץ לבצע את הבדיקה סדרתית לכל בחירה של k צמתים מבין הn. - זמן השווה בקירוב ל\ n^k*, אשר עשוי להיות אקספוננציאלי עבור k התלוי בn. (לעומת זאת, עבור k קבוע, מתקבל זמן ריצה פולינומיאלי)
  3. בעיית התאמה תלת-מימדית (3D-matching) - מציאת מספר שידוכים מקסימלי בכוכב בו אנשים נישאים בשלשות. (עבור קבוצת אנשים מכל אחד משלושת המינים וסדרת הגבלות נתונה הקובעת את השידוכים המותרים)
  • - הערך המדויק הוא \ {n \choose k} אשר עבור ערכים מתאימים של k יהיה שווה בקירוב ל\ n^k. (עבור \ k=n למשל מתקבל זמן ריצה קבוע)

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

  1. רדוקציה מבעיית \ SAT לבעיית \ 3-SAT. (בעיית ספיקות אשר כל הנוסחאות המרכיבות אותה (ומקושרות על ידי סימן "וגם") בעלות שלושה איברים) בדוגמא זו מצוין משפט קוק-לוין.
  2. רדוקציה מבעיית 3-צביעה של גרף לבעיית \ SAT.
  3. רדוקציה מבעיית \ 2-SAT לבעיית מציאת רכיבים קשירים היטב בגרף. (ובכך הוכחה שבעיית \ 2-SAT ניתנת לפתרון פולינומיאלי)

NP Completeness III - More Reductions עריכה

הורדה צפייה

תאריך: 02-23-01

השיעור מתחיל בחזרה על מושג הNP-שלמות והרדוקציות.

רדוקציות המופיעות בשיעור זה הן:

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


סיום ההרצאה בהתייחסות לקירוב-2 לבעיית כיסוי הקודקודים. (בחירת אחד מצדדיה של כל קשת)

NP Completeness IV עריכה

הורדה צפייה

תאריך: 02-26-01


Approximation Algs. עריכה

הורדה צפייה

תאריך: 02-27-01


Alternate Models of Computation עריכה

הורדה צפייה

תאריך: 02-28-01

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

ברחבי אתר Wikia

ויקי אקראית