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

[gil levi]

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

הראו שלא קיים אלגוריתם בסיבוכיות O zzz (או שבכלל לא קיים אלגוריתם ללא תלות בסיבוכיות) המבצע את המשימה הבאה: קלט: מערך A שמתאר סריקת LDR של עץ חיפוש בינארי T. פלט: שיחזור של העץ T. האם מספיק להראות שני עצי חיפוש בינאריים שונים עם אותה סריקת DLR (או שצריך לעשות רדוקציה לבעיית העצירה? ) ? מצד אחד זה מראה שלא ניתן לקבוע מהו T, אבל מצד שני אם אפשר להחזיר כפלט את כל העצים המתאימים לסריקה שב A אז T מוחזר. תודה מראש.

 

[gil levi]

תיקון.

בפסקה השניה, במקום DLR צריך להיות LDR כמובן.

 

[vinney]

אתה צריך לעשות רדוקציה, לדעתי

 

[מסית ומדיח]

לדעתי

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

 

[gil levi]

תודה לשניכם.

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

 

[yuvalmadar]

חשוב על מיונים... ../images/Emo8.gif