אלגוריתמים חמדניים

Question 1

מהו הסכימה הכללית להוכחת אופטימליות של אלגוריתם חמדן?

Answer 1

Question 2

What is the first thing that Prim’s algorithm does?

Answer 2

“Prim = Pick a node”

Prim’s algorithm randomely picks a starting node.

Question 3

How does Prim’s algorithm for finding an MST decide what edge to add to the final tree?

Answer 3

Prim’s algorithm is gready. Therefore it will choose the smallest edge that connects the curently existing tree to an unvisited node.

Question 4

Assuming that Prim’s algorithm randomely picked the starting node to be node “A”.

What will be the next edge added to the MST?

Answer 4

Question 5

הגדירו עץ.

Answer 5

Question 6

הגדירו:

עץ פורש.

Answer 6

Question 7

הגדירו:

עץ פורש מינימלי - MST.

Answer 7

Question 8

מהו זמן הריצה של אלגוריתם פרים?

Answer 8

(בעזרת שימוש במבנה הנתונים: ערימת פיבונצ’י - שלא נלמד בקורס, ניתן להגיע לזמן ריצה יעיל של):

(O(E + VlogV.

Question 9

מה עושה אלגוריתם קרוסקל?

Answer 9

אלגוריתם קורסקל מוצא עץ פורש מינימלי.

Question 10

איך עובד אלגוריתם קרוסקל?

Answer 10

אלגוריתם קרוסקל מוצא עץ פורש מינימלי.

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

Question 11

מהו זמן הריצה של אלגוריתם קרוסקל?

Answer 11

זמן הריצה של קרוסקל הוא:

(O(E log V.

Question 12

הגדירו:

חתך בגרף.

Answer 12

Question 13

בנוגע לעצים פורשים,

מה אפשר לדעת על צלע בעל משקל מינימלי בחתך כלשהו בגרף?

Answer 13

הצלע המינימלי בחתך מוכל בעפ”מ.

Question 14

מה מקיימת כל קשת בעפ”מ?

Answer 14

כל קשת בעפ”מ היא בעלת משקל מינימלי בחתך שהיא מגדירה.

Question 15

מהו האלגוריתם הגנרי למציאת עפ”מ?

Answer 15

Question 16

מה היה הפתרון של בעיית התאמת הסטודנטים לקרואסונים?

Answer 16

Question 17

אלו 3 אלגוריתמים חמדניים ראינו למצאית עפ”מ:

Answer 17

אלגוריתמים למציאת עפ”מ:

1. האלגוריתם הגנרי (אדום-כחול).
2. קרוסקל.
3. פרים.

Question 18

הגדירו:

מטרואיד.

Answer 18

Question 19

מהו המטרואיד הגרפי?

Answer 19

Question 20

מה הקלט והפלט של האלגוריתם החמדן של המטרואיד?

Answer 20

Question 21

איך עובד האלגוריתם החמדן הגנרי של המטרואיד?

Answer 21

Question 22

נניח שלפנינו בעיית אופטימיזציה. מתי נוכל להשתמש באלגוריתם הגנרי החמדן (בלי להוכיח את נכונותו)?

Answer 22

נוכל להשתמש באלגוריתם הגנרי החמדן במידה ו:

הצלחנו להוכיח שיש בבעיית האופטימיזיציה מטרואיד.

Question 23

נניח שיש לנו מטרואיד <m></m>

<p>איך נוכל למצוא תת קבוצה מקסימלית של I?</p>

</m>

Answer 23

נשתמש באלגוריתם הגנרי החמדן של המטרואיד.

Question 24

יהי מטרואיד

נניח שהאלגוריתם החמדן הגנרי מחזיר קבוצה A.

האם ייתכן שב I קיימת קבוצה שמכילה יותר איברים מאשר בA?

Answer 24

לא.

Question 25

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

Answer 25

Question 26

מה צריך לעשות כשאנו רוצים להשתמש באלגוריתם החמדן הגנרי על בעיה מסויימת?

Answer 26

Question 27

הגדירו:

התאמה בגרף דו צדדי

Answer 27

התאמה בגרף דו צדדי היא תת קבוצה של צלעות שאין בה 2 צלעות שנוגעות באותו קודקוד.

Question 28

בהינתן גרף דו צדדי, איך נמצא התאמה מקסימלית = התאמה של מספר רב ככל האפשר של קודקודים?

Answer 28

נגדיר את מטרואיד השידוכים.

האלגוריתם החמדן (=אלגוריתם המטרואיד) ייתן את התוצאה הרצויה כי:

אנו ניתן לכל קודקוד את בL את המשקל 1.

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

Question 29

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

מה נעשה?

Answer 29

נגדיר מטרואיד <m> כך ש:</m>

S היא קבוצת כל האיברים.

I היא קבוצת תתי הקבוצות עד גודל k.

נמיין את אברי S לפי משקלם מהגדול לקטן, ונריץ את אלגוריתם המטרואיד.

Question 30

נכון או לא נכון:

כל עץ פורש מינימלי הוא גם עץ פורש שבו משקל הקשת המקסימלית בו הוא מינימלי (= “עץ ממזער קשת מקסימלית”)

Answer 30

נכון.

Question 31

איך נוכיח שגרף הוא עץ פורש מינימלי?

Answer 31

נשים לב שצריך להוכיח שהגרף הוא:

1. עץ, כלומר קשיר וחסר מעלים.
2. פורש.
3. מינימלי.