שאלה באלגוריתמים.

[gil levi]

שאלה באלגוריתמים.

גרף מכוון G=(V,E)zzz יקרא גרף חצי קשיר בחוזקה אם לכל שני קודקודים u,v יש מסלול מu לv ו/או יש מסלול מv לu. כתבו אלגוריתם יעיל לבדיקה אם גרף מכוון הוא חצי קשיר בחוזקה. מה שאני חשבתי לעשות הוא להריץ BFS מכל קודקוד בV ולכל קודקוד u בV נשמור רשימה Lu של כל הקודקודים שהמרחק שלהם מu הוא אינסוף. בסוף התהליך יהיו לנו

רשימות Lu כאלו. כעת, לכל קודקוד u ולכל קודקוד v בLu נבדוק האם u מופיע גם בLv. במקרה כזה אין מסלול מu לv ואין גם מסלול מv לu. הבעיה שנדמה לי שהאלגוריתם הזה מאוד לא יעיל. הBFS-ים יקחו זמן של (O של)

*(

+ |E| zzz) שזה עוד בסדר, אבל נראה לי שהחיפוש ברשימות יקח זמן גדול מאוד. הוא חסום ידי

^

, אבל זה זמן ענקי. אולי הניתוח שלי של זמן הריצה לא טוב ואפשר למצוא חסם טוב יותר (הרבה הרבה יותר)? חשבתי גם על וריאציה אחרת: אחרי BFS עבור הקודקוד הראשון, u, אפשר להריץ BFS רק עבור הקודקודים בLu ואז לבדוק אם u יהיה שייך לLv עבור איזשהו קודקוד v בLv, אבל אז אני מסתבך כי אני צריך לבדוק מיד אח"כ עבור כל קודקוד בLv ובכלל אני מריץ BFS על v (שהוא בLu) בלי שיש לי איזשהו מידע על הרשימות שיתאימו לקודקודים האחרים בV, אז נראה לי שבוריאציה הזו אני אריץ יותר מדי BFS-ים. טוב, אחרי כל ההסבר הארוך הזה, מישהו יכול לתת לי כיוון/רמז? תודה מראש.

 

[gil levi]

איזה עצבים!

תפוז מעצבן!

צריך להיות גודל V.

 

[gil levi]

שאלה נוספת- במבני נתונים.

השאלה בתמונה. הפתרון שלי הוא כזה: תאור המבנה: נשתמש ב3 מחסניות: מחסנית R לאיברים שנכנסו בפעולת Enqueue, מחסנית P לאיברים שנכנסו בפעולת Penqueue ומחסנית Temp שתתפקד במחסנית עזר להוצאת האיברים מR. מימוש פעולת Enqueue וניתוח זמן ריצתה: פשוט הכנסה רגילה למחסנית R. מספר קבוצה של פעולות ולכן זמן הריצה טטא(1). מימוש פעולת Penqueue וניתוח זמן ריצה: פשוט הכנסה רגילה למחסנית P. מספר קבוע של פעולות ולכן זמן הריצה הוא טטא(1). מימוש פעולת Denqueu: אם יש לפחות איבר אחד במחסנית P נוציא את האיבר שבראש המחסנית (אז האחרון שנכנס ב Penqueue יצא לפני כל האחרים שנכנסו בפעולת Penqueue). אם P ריקה נעביר את כל איברי R למחסנית Temp, נוציא את מה שהיה אחרון בR ונחזיר את האיברים מTemp לR. אני יודע שאפשר גם עם 2 מחסניות, אבל לא חשבתי על זה במבחן. חוץ מהעובדה שאפשר עם 2 מחסניות, מישהו רואה טעות אחרת? הוא נתן לי 0 על זה. תודה מראש.

 

[copaste]

Dequeue שלך לא O(1)z amortize

תחשוב שעשית n פעולות enqueue ואח"כ n פעולות dequeue . פעולת ה deque הראשונה לוקחת בערך 4n פעולות במחסניות (n פעמים העברה לTemp מ R, פעולת הוצאה מהמחסנית ו n-1 פעולות העברה מ Temp בחזרה ל R ). באופן דומה הdeque הבא יקח כ 4*(n-1) פעולות וכו'. סה"כ תקבל זמן ממוצע של OZ . בשביל שיהיה amortize O(1)Z צריך כשאתה מוציא את האיברים מ Temp להחזיר חצי ל R וחצי ל P (ולא את כל האיברים ל R).

 

[gil levi]

תודה

 

[ron369]

מה זה Amortized?

 

[yuvalmadar]

לשיעורין

Amortized analysis = ניתוח לשיעורין. (לפי התרגום של האו"פ לקורמן)

 

[ron369]

נראה לי שצריך: (לא מתעמק)

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

 

[gil levi]

תודה, אבל יש לי את הפתרון.

רציתי לדעת מדוע הורידו לי כל כך הרבה. עכשיו אני יודע