מציאת מעגל מכוון בעזרת DFS

[אלוהים1980]

בחישוביות אני לא אמור להוכיח נכונות

של אלגוריתמים. מספיק עשיתי את זה בקורס אלגוריתמים. אם לבודק היה מספיק שאני ארשום שהשתמשתי בוריאציה של BFS שמופעלת מכל צומת, אז לא נראה לי שצריכה להיות לו בעיה עם וריאציה על DFS כמו ש ahab הזכיר. רק צריך להראות לו שאכן קיימת כזאת. חוץ מזה - מה יש לי להפסיד?

 

[vinney]

מה???

מה זאת אומרת אתה לא אמור להוכיח נכונות אלגוריתם? אתה נותן אלגוריתם, מי מבטיח לך שלא טעית ושהוא נכון? אם אתה מסתמך על אלגוריתם שמופיע בחומר הלימוד - מילא. כל השאר - חובה להוכיח נכונות. אם אתה אומר שהשתמשת ב"וריאציה" של BFS, זה בכלל לא מספיק. אני יכול להגיד שהשתמשתי בוריאציה של BFS לפתרון בעית סוכן נוסע בP, אז מה, זה נכון? תראה את הוריאציה, ותוכיח שהיא נכונה, אחרת אין לך שום זכות להשתמש בה. אם אני הייתי המרצה שלך, הייתי מוריד לך חצי מהנקודות, רק על הלך המחשבה הזה

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

 

[אלוהים1980]

באמת תתחיל להוכיח נכונות?

באמת תתחיל להוכיח נכונות של אלגוריתמים לא ממש פשוטים במבחן בקורס חישוביות? במיוחד אחרי שאמרו לנו במפורש לא להתמקד בדברים כאלו אלא יותר בלהראות מדוע רדוקציות שאנחנו עושים הן תקפות וכו'? הלוואי שהטכניון היה מוסד לשינונים - בפועל, הקשר בין המבחן לבין מה שנלמד בהרצאות הוא הרבה פעמים מקרי ביותר, כך שאין לך מושג ממש מה לשנן.

 

[vinney]

דווקא שיננת

לא במודע, אבל הסתמכת על מה שחשבת שלמדת בקורס אחר, במקום פשוט לכתוב אלגוריתם פשוט (כמו שהמרצה התכוון, מההערה שלו). גם אם למדת כזה אלגוריתם (ואני בספק), המטרה של לימודים אקדמאים היא לא שתזכור כל אלגוריתם שאי פעם תתקל בו, אלא שתדע לבנות אלגוריתם. ואת זה לא עשית, ולא נדרש ממך פה משהו ממש ממש מסובך - רק לזכור : מעגלים => BFS, מינימלי => מכל צומת + השוואת תוצאות, זהו, זה הכל. לשחזר מזה אלגוריתם תוכל תמיד, ולא רק אלגוריתם שנדרש ממך, אלא הרבה ואריאציות עליו.

 

[ahab]

די, vinney...

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

 

[DadleFish]

זה כבר תלוי במרצה שבודק את המבחן.

המבחן האחרון שעשיתי היה "פרקים במדעי המחשב התיאורטיים" בתואר השני. לכל הדעות, לא מדובר בקורס בסיסי באלגוריתמיקה - ובכל זאת, בכל מקום שכתבנו אלגוריתם וטענו לגביו איזושהי טענה - היינו צריכים להוכיח את נכונות הטענה מההתחלה ועד הסוף. אם המרצה לא היה פורמלי כל כך, אולי אפשר היה להסתפק בנפנופי ידיים... אבל כשהמרצה מקפיד על כל פיפס - ובצדק לדעתי - יש להוכיח הכל. זוהי המיומנות הנדרשת ממי שעושה תואר שני או קורס ליבה מתקדם כמו חישוביות.

 

[vinney]

עובדה שהורידו לו על זה נקודות

אם אתה מסתמך על חומר הלימוד, זה בסדר, אני לא אומר להעתיק הוכחות מהספר. אבל להגיד ש"למדנו פעם אז זה נכון", כשלא באמת למדנו פעם, זה כבר בעייתי. גם אם אלגוריתם כזה באמת קיים (כמו שהראת), זה עדיין לא אומר שמי שכתב בבחינה שהוא קיים באמת יודע להראות אותו (ועובדה שלא), ולכן נדרשת ההוכחה.

 

[DadleFish]

זה נכון, אם"ם

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

 

[ahab]

תשמע..

לגבי הערעור, זה נראה מאוד פשוט: אתה צריך להראות שלמדתם את זה באלגוריתמים. הדרך הכי טובה שהצלחתי לחשוב עליה היא: 1. מצא קלסר אלגוריתמים בבוידם, ופתח אותו. 2. לכל עמוד בקלסר 2.1. בדוק האם האלגוריתם המבוקש כתוב בעמוד 2.2. אם כן, סיים, ופלוט את מספר העמוד. 3. סיים, ופלוט "נו, טוב... הלכו 5 נקודות"

 

[ahab]

oops, תיקון...

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

 

[אלוהים1980]

סוף סוף מישהו מבין על מה אני מדבר.

כי הבודק בהערה שלו לא רשם לי "איפה ההוכחה לנכונות האלגוריתם" או "היית צריך לתאר במדוייק את הוריאציה" אלא פשוט הקיף בעיגול את המילה DFS שרשמתי, והחליף אותה ב BFS, וכתב "צריך להריץ מכל צומת!".

 

[vinney]

תבדוק בחומר לימוד של אלגוריתמים

אולי מה שתמצא שם זה וריאציה של BFS, ולזה הוא התכוון?

 

[אלוהים1980]

לא מצאתי.

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

 

[vinney]

הלך הערעור

 

[vinney]

../images/Emo6.gif

 

[DadleFish]

אכזבת אותי,

איפה בדיקות תקינות לבוידעם?

 

[sneaker]

V4

תריץ מכל צומת DFS מוגבל עומק מ עומק 1 עד

. עבור כל הרצה תמיין את כל המעגלים שקיבלת והמעגל אם האורך הקצר ביותר הוא המבוקש.(אם מצאת מעגל או יותר עבור DFS עם עומק K אין מה להמשיך לעומק לK+1 ). נניח ש DFS לוקח V*V אז סיבוכיות V פעמים עבור כל עומק V פעמים עבור כל צומת סה"כ V*V*V*V