עמוד 1 מתוך 1

מיון טופולוגי

הודעהפורסם: 22:29 12/07/2010
על ידי Brk
האם מיון טופולוגי יכול לעזור לי למצוא אם גרף קשיר או לא?
חוץ מבדיקת קשירות הגרף? איזה עוד שימושים יש למיון טופולוגי? :P
ועוד שאלה ,אחת לא קשורה:מתי אתם מפרסמים את הדף הראשון של מבחן מועד ב' במבני?

Re: מיון טופולוגי

הודעהפורסם: 10:36 13/07/2010
על ידי TA_Yoni
אין שום סיבה לבצע מיון טופולגי לבדיקת קשירות של גרף.
כדי לבדוק אם גרף קשיר בצורה יעילה עושים זאת בעזרת BFS או DFS.
שימושים למיון טופולוגי אתה יכול למצוא בתרגול על DFS או במבחנים ( מיון של הקודקודים בשביל מציאת מסלול מקסימלי , למשל )

לגבי דף הבחינה - יום ראשון ב 9 מתאים? 

Re: מיון טופולוגי

הודעהפורסם: 10:54 13/07/2010
על ידי Brk
TA_Yoni כתב:אין שום סיבה לבצע מיון טופולגי לבדיקת קשירות של גרף.
כדי לבדוק אם גרף קשיר בצורה יעילה עושים זאת בעזרת BFS או DFS.
שימושים למיון טופולוגי אתה יכול למצוא בתרגול על DFS או במבחנים ( מיון של הקודקודים בשביל מציאת מסלול מקסימלי , למשל )

לגבי דף הבחינה - יום ראשון ב 9 מתאים? 

חחחחח
לא התכוונתי לדף הזה שמראה לך כמה שאלות+כמה סעיפים יש לך
כמו שפירסמתם במועד א'
http://www.cs.bgu.ac.il/~ds102/wiki.files/firstPage.pdf


שאלה נוספת: לגבי Union Find :
אם אני מייצג כול קבוצה כרשימה מקשורת שאיבריה מכילים מצביעים לאיבר הראשון ברשימה(שהוא הנציג).
הדגימו לנו בההרצאות שפעולת איחוד של קבוצות זרות על ידי שירשור של רשימה ארוכה יותר לקצרה תעלה לנו O(n) במקרה הגרוע ביותר.
הציגו שיפור:נשרשר רשימה קצרה לארוכה מה שיפחית משמעותית את עידכון הנציגים,השאלה כמה זמן יעלה Union במקרה הזה(במקרה הגרוע ביותר)?
בהרצאות וגם במצגות הוצג פנינו כמה זמן סדרה של m פעולות של makeset ,findset וUnion יעלו O(m+nlogn) כאשר makeset ןfindset מתבצעות בO(1) ויש m פעולות כאלו לכן זה מתבצע בכולל O(m) ,האם אני צריך להסיק שm פעולות של Union עולות nlogn?

Re: מיון טופולוגי

הודעהפורסם: 11:02 13/07/2010
על ידי Brk
TA_Yoni כתב:אין שום סיבה לבצע מיון טופולגי לבדיקת קשירות של גרף.
כדי לבדוק אם גרף קשיר בצורה יעילה עושים זאת בעזרת BFS או DFS.
שימושים למיון טופולוגי אתה יכול למצוא בתרגול על DFS או במבחנים ( מיון של הקודקודים בשביל מציאת מסלול מקסימלי , למשל )

לגבי דף הבחינה - יום ראשון ב 9 מתאים? 


נתקלתי במבחן 2002 שאלה 3 סעיף ב' השתמשו במיון טופולוגי כדי להסתכל על סדרה של איברים שמהווה רכיב קשירות שמכיל את קוקוד S.לכן שאלתי :?:

Re: מיון טופולוגי

הודעהפורסם: 11:08 13/07/2010
על ידי TA_Yoni
פעולת UNION לאחר שיפור עדיין תקח (O(n - אם למשל נאחד שתי קבוצות בגודל n/2
מה שראינו בכיתה הוא ניתוח פחת ( הסתכלנו על רצף של כמה פעולות ביחד וניתחנו כמה זמן כולן יקחו )
קיבלנו שעבור ביצוע של m פעולות union,find,makeSet הזמן הכולל הוא (m*log(n , לכן בממוצע כל פעולה לוקחת (log(n