נושא: מבנה נתונים

נשלח בתאריך: 25 August 2007 בשעה 22:52 | IP רשוּם

שלום לכולם!

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

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

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

שאלתי היא- האם יש דרך להוכיח למרצה שמשמעות "מבנה העץ" היא לאו דווקא גובה אלא גם אפשר להוכיח על מספר קודקודים?

בבקשה-אשמח מאוד מאוד לשמוע תשובה נכונה שיש בסיס איתן ואמיתי מאחוריה.

הניקוד לשאלה הזו רב מאוד ויכול לשפר את הציון שלי ממש!!

שוב, אודה לכם מאוד על התייחסותכם! 

נשלח בתאריך: 26 August 2007 בשעה 03:54 | IP רשוּם

שלום,

1.את מדברת על "עץ מסויים" ו-"משפט מסויים", ו-"מבנה עץ". 
מה סוג העץ? מה המשפט? מה הכוונה למושג "מבנה עץ"?
קשה מאד לעזור או לנסות לטעון משהו בלי הנתונים האלה.

2.בהנחה ש-המושג "מבנה עץ" שאת משתמשת בו מתייחס למבנה העץ אז:
אני באופן אישי לא רואה שום קשר בין ה-"מבנה עץ" לגובה שלו או למס' הקודודים שלו.
באופן כללי ידוע שכמות הקשתות בעץ היא תמיד מס' הקודקודים - 1.
לגובה העץ יש משמעות כאשר מדובר בעצים בינאריים מלאים.
מההגדרה ל"מבנה עץ" ידוע כי אסור שבין בנים תקשר קשת...וזהו בערך.

בקיצור תשפכי עוד קצת אור בנושא.

נשלח בתאריך: 26 August 2007 בשעה 12:23 | IP רשוּם

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

למשל:בעץ בינארי מורחב בעל n צמתים יש בדיוק n+1 עלים.(גם המשפט שנבחנתי עליו היה קשור למ"ס העלים בעץ)

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

תודה!

נשלח בתאריך: 27 August 2007 בשעה 17:29 | IP רשוּם

שתי הוכחות באינדוקציה:

הוכחה על מ"ס קודקודים:

http://www.cs.biu.ac.il/~89-120/Material/Trees_1.ppt#36

הוכחה על גובה עץ:

לפרק לקודקוד(שורש) ול2 תתי עצים.מניחים שהמשפט נכון עבור כל תת עץ ואז כשמוסיפים את הקודקוד(n+1)נכון עבור כל העץ.

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

(מי החליט מה ההגדרה של "מבנה עץ"?!?!?)

מקווה שהסברתי את עצמי קצת יותר טוב....

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

אשמח לעזרתכם....

(ד"א- אשמח לקבל מיילים של המרצים שלכם במבנה נתונים.אולי זה יעזור...)

תודה רבה רבה!!

נשלח בתאריך: 04 September 2007 בשעה 18:16 | IP רשוּם

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

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

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

אשמח לשמוע דעות נוספות.