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

[roey8]

שאלות תכנותיות בפסאדו קוד

יש לי 2 שאלות שאני לא מצליח להבין אודה לעוזרים:

1) נתון עץ בינארי בעל N איברים עם תכונת הערימה. הצע אלגוריתם היוצר בנוסף עץ חיפוש מאברי הערימה

מבלי לשנות את הערימה. מהי סיבוכיות האלגוריתם? האם ניתן לממש את האלגוריתם בזמן O(N? הוכח או הפרך

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

שיקיים את תכונת עץ חיפוש ביחס למפתחות ואת יחס הערימה ביחס לעדיפות.

האם ניתן לארגן כל קבוצת איברים באופן כזה?

אם כן הסבר איך, אם לא תן דוגמא נגדית

[שניצל]

שנה בבקשה את הכותרת כך שתכיל את תמצית השאלה.

[Zelig]

אפשר לבנות עץ לא מאוזן באופן טריוויאלי בסיבוכיות לינארית.

מה ערימה עושה? היא מאפשרת לך תמיד לקבל את האיבר הכי קטן בסיבוכיות של (1)O.

אז פשוט תבנה את העץ מלמטה למעלה. עבור הערימה 1 4 7 9 העת יהיה

    9
    /
   7
   /
  4
 /
1

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

לגבי 2, התשובה היא לא, ויש דוגמא נגדית טריוויאלית. תנסבה לבנות עץ כזה עבור האיברים הבאים: (1,1) ו-(2,2).

אם 1,1 בשורש אז תכונת הערימה מתקיימת אבל תכונת עץ החיפוש לא. אם 2,2 בשורש אז זה עץ חיפוש אבל לא ערימה.

טעות! הדוגמא הזו לא נכונה בכלל.

[roey8]

תודה על התגובה

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

לגבי 1 אני יודע כמה איברים יש מראש, כאמור בשאלה, N.

כמו כן, לא הבנתי כל כך את כוונתך

תוכל לרשום את האלגוריתם עצמו (בפסאדו קוד)?

[Zelig]

תודה על התגובה

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

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

לגבי 1 אני יודע כמה איברים יש מראש, כאמור בשאלה, N.

כמו כן, לא הבנתי כל כך את כוונתך

תוכל לרשום את האלגוריתם עצמו (בפסאדו קוד)?

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

[roey8]

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

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

הפתרון שהצאתי הוא לסדר את סדר ההכנסה לפי העדיפות, כלומר האיבר הראשון שיוכנס לעץ יהיה (2,2).

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

[br]פורסם בתאריך: 17.08.2008 בשעה 10:58:47

---

לגבי 1 יש לך רעיון?

הכוונה אולי פשוט לפונקציית HEAPIFY השומרת על תכונת הערימה?

[Zelig]

הפתרון שהצאתי הוא לסדר את סדר ההכנסה לפי העדיפות, כלומר האיבר הראשון שיוכנס לעץ יהיה (2,2).

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

[br]פורסם בתאריך: 17.08.2008 בשעה 10:58:47

---

לגבי 1 יש לך רעיון?

הכוונה אולי פשוט לפונקציית HEAPIFY השומרת על תכונת הערימה?

באופן קלאסי בערימה, השורש הוא הקטן ביותר והערימה מספקת את האיבר הקטן ביותר ב-(1)O.

אני מבין שההגדרה שאתה עובד איתה היא הפוכה?

בכל מקרה הדוגמא הנגדית שלי הייתה בכלל לא נכונה. זה ילמד אותי לכתוב תשובות תוך דקה בלי לחשוב או לקשקש על נייר...

יתכן שהאלגוריתם שלך נכון ויתכן שלא.

כיוון להוכחה:

1) המבנה הוא עץ חיפוש כיוון שהכנסת איברים באלגוריתם רגיל של הכנסה לעץ חיפוש.

2) לכל איבר X בעץ, כל האיברים Y1...YM במסלול מ-X לשורש הוכנסו לעץ לפני X.

אתה יכול לעבוד דרך הוכחה על צד השלילה:

נניח שקיים איבר X בעץ החיפוש אשר גורם להפרה של תכונת הערימה... ואז להגיע לסתירה.

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

[roey8]

אני לא מצליח ללכת בכיוון שאתה מציע

יש מצב תנסה שניה ותרשום לי את האלגוריתם אם זה הולך לך?

שאלה אחרונה לקורס..

[roey8]

ייתכן והכוונה פשוט להחליף בין המצביעים של כל שני בנים?

(נתון עץ אם תכונת הערימה וצריך לבנות ממנו עץ חיפוש)

[Zelig]

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

בהחלט יתכן שיש לך את הפתרון. תוכיח או תפריך.

[EAD]

2 - לא אי אפשר.

האמת שאני חושב שזאתי בעיה שהיא NP - אתה יכול לבדוק.

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

1 - לדעתי גם לא אפשרי, לפחות לא עץ מאוזן.

תראה

העניין הוא כזה, אנחנו יודעים שכל פעם האיברים ברמה X יותר גדולים בהכרח מהאיברים ברמה X+1, נכון? עכשו אם נעשה מה שאמרו פה (שלא נכון) וכל פעם נמצא האיבר הכי קטן ברמה הבאה אחרי שנסיר, נקבל LOGN לכל הסרה (בכל מימוש של ערימה זה קיים), ונפתור את זה בNLOGN

ככה שעדיין לא קיבלנו פתרון של O של N.

צריך להוכיח את כל הסיפור וכו'

אבל לדעתי אין פתרון של O של N

[Zelig]

העניין הוא כזה, אנחנו יודעים שכל פעם האיברים ברמה X יותר גדולים בהכרח מהאיברים ברמה X+1, נכון? עכשו אם נעשה מה שאמרו פה (שלא נכון) וכל פעם נמצא האיבר הכי קטן ברמה הבאה אחרי שנסיר, נקבל LOGN לכל הסרה (בכל מימוש של ערימה זה קיים), ונפתור את זה בNLOGN

בהנתן ערימה, אפשר לעשות traversal על האיברים שלה בסיבוכיות זמן (O(N ללא שינויים במבנה עצמו.

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

[EAD]

^^^

אני יוכיח לך שאתה טועה

אתה מסכים איתי שלהרכיב ערימה אפשר בO של N

כן?

עכשו

מה שאתה אומר

שיכולנו בO של N להוציא את האיברים

כלומר

למיין כל מספרים שהם בO של N

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

לכן מה שאתה אומר איננו אפשרי.

[Zelig]

אתה צודק, אני אידיוט.

(וכמובן שעבור comparison sort הסיבוכיות הטובה ביותר האפשרית היא nlogn, כולם יודעים את זה).

אז איפה טעיתי?

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

הסיבוכיות של tree traversal היא אכן לינארית, אבל כמו שאמרתי, tree traversal לא מספיק בשביל להוציא איברים ממויינים.

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

[EAD]

^^^

אתה אומר את זה בציניות או ברצינות??