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

מנהל: TA_Isana

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

הודעהעל ידי Brk » 22:29 12/07/2010

האם מיון טופולוגי יכול לעזור לי למצוא אם גרף קשיר או לא?
חוץ מבדיקת קשירות הגרף? איזה עוד שימושים יש למיון טופולוגי? :P
ועוד שאלה ,אחת לא קשורה:מתי אתם מפרסמים את הדף הראשון של מבחן מועד ב' במבני?
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי TA_Yoni » 10:36 13/07/2010

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

לגבי דף הבחינה - יום ראשון ב 9 מתאים? 
המתרגל יוני
TA_Yoni
 
הודעות: 236
הצטרף: 13:44 18/10/2009

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

הודעהעל ידי Brk » 10:54 13/07/2010

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?
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי Brk » 11:02 13/07/2010

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

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


נתקלתי במבחן 2002 שאלה 3 סעיף ב' השתמשו במיון טופולוגי כדי להסתכל על סדרה של איברים שמהווה רכיב קשירות שמכיל את קוקוד S.לכן שאלתי :?:
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי TA_Yoni » 11:08 13/07/2010

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


חזור אל - מבני נתונים 2010

מי מחובר

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