FANDOM


20417 - אלגוריתמים
מדעי המחשב
'
כללי
רמה: רגילה
נקודות זכות: 4 נ"ז ברמה רגילה
קורסים נדרשים: אלגברה לינארית I, מבני נתונים ומבוא לאלגוריתמים
סוגי הנחיה רגילה, מוגברת

לידיעון הקורסים
לאתר הקורס בתלם



נושאי הקורסעריכה

פרק א'עריכה

פרק זה עוסק בתכונות של גרפים ועצים, ובאלגוריתם החיפוש לרוחב. (BFS) (סעיפים 5.4, 5.5, 23.1, 23.2 בספר של קורמן)

פרק ב'עריכה

פרק זה עוסק באלגוריתמים למציאת מסלולים קצרים ביותר מצומת נתון בגרף. בפרק זה נלמדים האלגוריתם של דייקסטרה ואלגוריתם בלמן-פורד. (סעיפים 25.1-25.3 בספר של קורמן)

פרק ג'עריכה

פרק זה עוסק בעצים פורשים מינימליים, ובפרט מלמד את האלגוריתם של פרים והאלגוריתם של קרוסקל למציאת עפ"מ בגרף קשיר נתון. (פרק 24 וסעיפים 22.2, 22.1 בספר של קורמן)

פרק ד'עריכה

פרק זה עוסק באלגוריתם החיפוש לעומק (DFS) ובשני יישומים שלו - מיון טופולוגי של גמ"ל (גרף מכוון ללא מעגלים) ומציאת רכיבים קשירים היטב בגרף מכוון. (סעיפים 23.3-23.5 בספר של קורמן)

פרק ה'עריכה

פרק זה עוסק ביישום נוסף של אלגוריתם החיפוש לעומק - מציאת רכיבים דו קשירים בגרף לא מכוון וקשיר. (מבוסס על בעיה 23-2 בספר של קורמן)

פרק ו'עריכה

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

יישום מרכזי של רשתות הזרימה בפרק זה הוא בפתרון בעיות זיווג מקסימלי.

פרק ז'עריכה

פרק זה עוסק באלגוריתם של שטראסן לכפל מטריצות. (סעיפים 31.2, 31.1 בספר של קורמן)

יישום מרכזי של אלגוריתם זה הוא בחישוב מספר המסלולים מאורך k נתון המחברים שני צמתים u,v בגרף.

פרק ח'עריכה

פרק זה עוסק בהתמרת פוריה המהירה המשמשת לכפל פולינומים מהיר. (סעיפים 32.2, 32.1 בספר של קורמן)

הבחינהעריכה

מבנה הבחינהעריכה

המבחן מורכב מחמש שאלות אשר מתוכן צריך לענות על ארבע, משקל כל שאלה - 25 נקודות.

  • השאלה הראשונה עוסקת לרוב באלגוריתמים למציאת מסלולים קצרים ביותר בגרף.
  • השאלה השניה עוסקת בעצים פורשים מינימליים.
  • השאלה השלישית עוסקת בחיפוש לעומק ויישומיו.
  • השאלה הרביעית עוסקת ברשתות זרימה.
  • השאלה החמישית עוסקת בכפל מטריצות או בכפל פולינומים.

חומר עזרעריכה

בבחינה כל חומר עזר מותר לשימוש.

קישורים חיצוניים עריכה

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

ויקי אקראית