אלגוריתמים

[גל אדום]

אלגוריתמים

כרגיל, שתי שאלות שאני מתקשה לפתור: א) הצע דרך לייעל אלגוריתם למציאת איבר מינימלי בערימה בינומית. רעיונות?! אם השינוי דורש שינויים בפעולות רגילות של ערימה בינומית יש להסביר. ב) נתונה ערימה בינומית ובה n רשומות. הראה דרך לפצל את הערימה ל-k ערימות בגודל 2 בחזקת i. k=n/2^i ערך תחתון. ולערימה נוספת שיתכן וקטנה מ-2 בחזקת i. n,k,i נתונים. נתח סיבוכיות זמן של האלגוריתם.

 

[גל אדום]

שכחתי לשאול

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

 

[איפכא מיoתברא]

../images/Emo41.gifלינק מעולה:

http://underwar.livedns.co.il/default.asp אתר מעולה של סטודנט מהטכניון

 

[גל אדום]

תודה לך

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

 

[Zack DA]

Google is your friend

 

[Zack DA]

מה ניסית לעשות ? מה הבעיה בדיוק ?

 

[גל אדום]

תשובות:

לגבי א) אם זו ערימה בינומית שמוכרבת מעצי מינימום, אז בסך הכל צריך לעבור על כל שורשי הערימה הבינומית כדי למצוא את המינימום שביניהם. לא ברור לי מה עוד ניתן לשפר כאן כדי שזה יהיה יותר מהיר. אם אשמור במערך את השורשים זה לא ישנה כלום עדיין צריך לסרוק אותו. אם אני מבין נכון רוצים שיפור כזה שיתן לי ב-O של 1 לדעת ישר מה המינימום. ב) לא ברור לי מה בכלל רוצים לעשות כאן. הערימה הבינומית מורכבת מתתי עצים שהם עצמם ערימה אז פיצול יהיה בעצם לפרק לתתי העצים ?!

 

[Zack DA]

אני אולי מפספס אותך, אבל

אם אנחנו רק רוצים לדעת מה המינימום - אולי כדאי שנשמור את המידע הזה במשתנה כלשהו, שמתעדכן דינאמית בזמן עדכון מבנה הנתונים, ותמיד תוכל לקרוא אותו ב- O של 1.

 

[גל אדום]

יתכן

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

 

[voguemaster]

אבל צחי

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

 

[Zack DA]

אם האיבר החדש מינימלי -

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

 

[voguemaster]

איך אתה יודע שהוא מינימלי ?

 

[Zack DA]

אם הוא קטן מהמינימלי הנוכחי....

 

[אופסשםמשתמש]

../images/Emo99.gif../images/Emo99.gif../images/Emo99.gif../images/Emo99.gif

אין לי מושג איך לפתור את זה אבל אם יש כזה קורס בטכניון אני בטוח אקח אותו.. (הוא בטח בחובה שלי גם ככה אבל אם לא.. he is mine)