שאלה לגבי תכונות אסימפטוטיות של בעצים

[lalal6]

שאלה לגבי תכונות אסימפטוטיות של בעצים

שלום,

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

זו השאלה:

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

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

א'. כל צומת בעץ הוא או עלה, או שיש לו שניי בנים.

תשובה:

משפחה של עצים בעלת התכונה שכל צומת בעץ הוא או עלה או שיש לו שניי בנים, איננה מאוזנת.

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

אז מספר הרמות הוא n/2.

התשובה הזו לא ברורה לי...אם למשל אני מסתכל על העץ הבא:

שורש שאקרא לו 1. לשורש יש בן ימני שערכו 2. לקדקד עם הערך 2 יש בן שמאלי עם הערך 3, ובן ימני עם הערך 4. לקדקד עם הערך 4, יש בן שמאלי שערכו 5 ובן ימני שערכו 6. לקדקד שערכו 6, יש בן שמאלי שערכו 7 ובן ימני שערכו 8. (כמובן לא מדובר על עצי חיפוש, אלא סתם עצים בינאריים).

העץ שהצגתי כאן, הוא שרוך שלכל צומת בו יש בן שמאלי.

לפי התשובה שנתנו לשאלה (שהיא אגב נכונה...רק שאני לא מבין אותה), מספר הרמות הוא n/2. כלומר במקרה של העץ שהצגתי כאן - שמספר קדקדיו הוא n=8, מתקיים
שמספר הרמות שלו הוא 8 חלקי 2, שזה 4, ובאמת יש לו 4 רמות.

מצד שני, אם אני מנסה להראות שהוא מאוזן, אני צריך להראות שגובהו קטן שווה מ - c*logn , עבור כל n שגדול מ-no כלשהו.

גובה העץ שלי הוא 4 (יש בו 4 רמות). מספר הקדקדים בו הוא n=8.

zz 4 < clog8 = 3c ==> 4 < 3c zz קבלתי ש-4 קטן מ-3c. אם אבחר למשל c=2, מתקיים באמת ש 4<6. כמו כן, ה-n נעלם...ככה שאין כאן בכלל no שצריך לבחור.

כלמר הראיתי שגובה העץ הוא O(logn), כאשר במקרה שלי n=8.

לכן הוא מאוזן. אבל מצד שני מספר הרמות הוא n/2.

כנראה שאני לא מבין בכלל מה אני עושה.

מישהו מוכן להסביר לי איך פותרים את השאלה הזו, ומה השיגאות שלי???

תודה רבה למי שעונה!

 

[lalal6]

של עצים*

 

[עריסטו]

הסבר

משפחה של עצים בעלת התכונה שכל צומת בעץ הוא או עלה או שיש לו שניי בנים (נקרא לקבוצה הזו A), איננה מאוזנת. זאת משום שהיא מכילה את הקבוצה האינסופית של עצים בעלי התיאור הבא: "עץ שהוא שרוך ימני כשלכל צומת בשרוך הוספנו בן שמאלי". נקרא לקבוצה הזו B. הגובה של העצים בקבוצה B הוא n/2. כלומר, לא קיים שום קבוע c שעבורו גובה כל העצים ב-B הזו קטן מ - c*logn (האם אתה יודע להוכיח זאת?) וממילא לא קיים קבוע כזה עבור הקבוצה A (הרי A כוללת את B).

 

[lalal6]

תגובה

יש כמה דברים שלא מובנים לי עדיין..

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

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

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

 

[סיגמה535]

תשובה

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

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

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

קיים c>0 כך שלכל n טבעי, אם T עץ בעל n צמתים, וגם כל צומת בעץ הוא או עלה, או שיש לו שניי בנים אז הגובה של T אינו גדול מ clogn.

אם נשלול את זה נקבל את הטיעון הבא:

לכל c>0 קיים n כך שקיים עץ T בעל n צמתים, שבו כל צומת בעץ הוא או עלה, או שיש לו שניי בנים וגם הגובה של T גדול מ clogn.

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

האם זה ברור?

 

[lalal6]

תגובה

האמת שעכשיו יותר מובן לי (בצירוף עם השתובה של עריסטו כמובן).

מדוע משפחה אינסופית של עצים בדוגמה שנתתי מקיימת את זה?

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

אז צריך משהו כמו החל מ-n מסוים מתקיים ש- n/2 < clogn , לא?

יכול להיות שבניסוח של הטענה המקורית שלך (זו שלפני השלילה) היה צריך להופיע יחד עם ה"קיים c>0", גם "קיים no כך שלכל n>no, אם T עץ בעל n צמתים..."?

כלומר השלילה שתתקבל היא:

לכל c,no קבועים, קיים n גדול מ-no כך שאם T עץ בעל n צמתים וגם כל צומת בעץ הוא או עלה או שיש לו 2 בנים, אז הגובה של T גדול מ-clogn??

האמת שבשלילה אני עדיין נשאר עם "קיים n".


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

מה אני מפספס..הסתבכתי קצת..

 

[סיגמה535]

תשובה

1. לגבי n0, בהגדרה הפורמלית אכן נדרש שהאי שוויון יתקיים החל מאינדקס מסוים, אבל בעקרון על ידי בחירת c מתאים אפשר לוותר על ההגבלה הזו (אם יש c שטוב החל ממקום מסוים, אז יש c1 שטוב לכל n).
2. יש הבדל בין קבוצה אינסופית של טבעיים לבין קבוצה של טבעיים בעלת משלים סופי. קבוצה A של טבעיים היא אינסופית אם לכל n טבעי יש m טבעי גדול מ n השייך ל A. קבוצה A בעלת משלים סופי אם קיים n כך שלכל m שגדול מ n, מתקיים כי m שייך ל A. כמובן שכל קבוצה של טבעיים בעלת משלים סופי היא אינסופית, אבל ההיפך אינו בהכרח נכון.
3. התרגום שלך לטענה איננו מדויק. אם אתה רוצה לנסח את הטענה המלאה על החסם האסימפטוטי היא תראה כך:
קיים c>0 וקיים n0 טבעי כך שלכל n>n0 ולכל עץ T עם n צמתים, אם ... אז הגובה של T אינו עולה על clogn.
ואז השלילה היא:
לכל c>0 ו n0 טבעי קיים n>n0 וקיים עץ T כך שב T יש n צמתים וגם ... וגם הגובה של T גדול מ clogn.

 

[lalal6]

הערה 2 שלך

לא לגמרי הבנתי על מה ענית לי באמצעות הערה 2.

ולגבי הטענה...אוקיי..כמו שכתבת, הטענה היא:

לכל c>0 ו n0 טבעי קיים n>n0 וקיים עץ T כך שב T יש n צמתים וגם ... וגם הגובה של T גדול מ clogn.

שוב, אין לי כאן הקשר של: קיים no כך שלכל n>no (שזה יוצר לי את האינסופיות.."החל מno מסוים ואילך..").

אלא, עבור כל no, קיים n >no..

רגע..אולי הערה 2 שלך באה לפתור לי את האי הבנה בדיוק בנקודה הזו.

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


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

ותודה רבה בכל מקרה!

 

[סיגמה535]

אכן כך

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

לכן הטענה כפי שניסחתי אותה טוענת לקבוצה אינסופית של עצים.