אחד בגודל M והשני בגודל N כאשר N=o(M)
(זאת "או" קטנה)
יש שני אלגוריתמים למציאת המספרים המופיעים גם ב A וגם ב B, יש לנתח את הסיבוכיות:
1. נחפש כל אחד מאברי A ב B על ידי מעבר סדרתי על B.
2. נמיין את שני המערכים ואז נריץ שגרת מיזוג, כשבכל פעם שניתקל באיבר זהה, נדפיס אותו.
שלום לכולם
רציתי לשאול האם פישוט הקוד הוא אחד מהיתרונות הישירים לשימוש ב ADT ?
היתה שאלה אמריקאית במבחן מה אינו אחד מהיתרונות לשימוש ב ADT אז בחרתי בפישוט הקוד , אז רציתי לשאול אם למישהו יש מושג אם בתשובה שלי נכונה ..
תודה מראשץ
במועד א היה לנו את השאלה הבאה:
יהי Alg אלגוריתם מיון (לאו דווקא אחד מאלה שנלמדו בשיעור) במודל ההשוואות. הוכיחו או הפריכו:
א. אם סיבוכיות ריצת Alg על מערך ממוין בגודל n היא n^2 Omega אז סיבוכיות ריצת Alg על מערך בגודל n במקרה הטוב ביותר היא Omegan^2
ב. אם סיבוכיות ריצת Alg על מערך ממוין בגודל n היא Teta של n שורש n אז סיבוכיות ריצת אלגוריתם Alg על מערך בגודל n במקרה הגרוע ביותר היא omega של n שורש n
ג. אם סיבוכיות ריצת Alg על מערך ממויין בגודל n היא O של nlogn, אז סיבוכיות ריצת Alg על מערך בגודל n במקרה הגרוע ביותר היא Omega של nlogn
הבנתי ש א, ג לא נכון וצריך להפריך וב נכון וצריך להוכיח אבל נתקעתי עם דוגמאות הפרכה והוכחה....
אם מישהו יודע, אשמח לתשובה :)
האם מישהו יודע איך להוכיח את המשפט הבא: "הוכיחו שכל עץ מלא יכול להתקבל מאלגוריתם הופמן ע"י מתן שכיחויות מתאימות לעלים"
השאלה נלקחה מהספר קורס הכחול.
לא למדנו איתו הסמסטר ואני עוברת אליו לפני מועד ב ולא מליחה לעלות על רעיון איך להוכיח טענה זו. אני חושבת שצריך בדרך השלילה, אבל מה הניסוח המתאים?
שאלה ראשונה (חישוב זמן ריצה בנוסחת נסיגה והצבה חוזרת): .
שאלה שלישית (השאלה הקשה): : אפשרי. כיוון לאלגוריתם: שימוש בערימות; : אפשרי. פשוט למיין; : לא אפשרי. מוכיחים באמצעות סתירה לחסם התחתון למיון במודל ההשוואות.
שאלה שישית: עשינו בשיעורי הבית. זמן ריצה סופי: .
השאלה עם הערמות: סעיף א, FixHeap על ערימת מקסימום שבה המינימום הוא השורש תקח . סעיף ב, האיבר המקסימלי בערימת מינימום חייב להיות בעלים, כלומר באינדקסים ערך שלם תחתון של n/2 עד n. האיבר השני המקסימלי בעלים או בקודקוד אחרון שאינו עלה רק אם יש לו בדיוק בן אחד והוא המקסימלי.
השאלה עם זמני הריצה: בכל התאים או . בעמודה של טבלת הערבול ב-Find ו-Delete זה ובמציאת מינימום/מקסימום זה .
השאלה עם השוואה בין זמני ריצה f,g: שניים ראשונים O, שניים הבאים .
שאלה 2 ממבחן 21/2/06 (עמוד 69 וחוברת המבחנים): נתונה ערימת מקסימום המכילה n נתונים. נבחר, באופן אקראי, איבר מנתוני הערימה, נקטין את ערכו ונבצע FixHeap. מה תוחלת זמן העבודה של פעולת ה-FixHeap שביצענו?
בחוברת מגיעים לתשובה אם כי לא ברור לי למה. איכשהו הגיעו לנוסחה הזאת: אבל למה דווקא אליה?
שמתי לב גם בתחילת הסימסטר כשפתרנו תרגילים כאלו וגם עכשיו שחישוב רקורסיבי אמור להיות חישוב פשוט. אם מסתבכים יותר מדי עם החישוב הטור רוב הסיכויים הם שלא פישטנו מספיק את הנוסחאות ההתחלתיות. גם את נוסחת הנסיגה הטבעית ניתן היה לפשט במקרה הזה, וגם כאשר יוצרים את הטבלה של מס' קודקודים, עלות קודקוד ועלות רמה, אם מחשבים נכון, רואים דברים מצטמצמים ומגיעים לביטוי פשוט כמו שכתבתי בהודעה הקודמת.
שיטת ההוראה במבני נתונים שונה מאשר בהשלמות חדו"א. רוב החומר נמצא במקראות ומבנה השיעור הוא לא כזה המאפשר סיכום של ההרצאה, ובצדק בגלל קיום המקראות. אני כן מתכננת להעלות סיכומים חלקיים שכתבתי בשיעור, שזה כולל לרוב פתרונות לתרגילים מהמקראה, ואולי אם אספיק גם סיכום של הגדרות ומשפטים
לגבי סעיף א - בעיקרון עיקרון שובך היונים מוכיח את הטענה כמעט ישירות. כל מה שנשאר הוא לנסח את ההוכחה כמו שצריך, אבל בעיקרון שובך היונים זה העיקר.
לגבי סעיף ב - המקרה הטוב לדעתי הוא כאשר האיבר שמחפשים הוא הראשון ברשימה שבתא שאליו הוא ממופה (זה יתכן), ולכן היעילות היא 1. המקרה הגרוע לדעתי הוא שכל המפתחות מופו לאותו תא, והאיבר שאנחנו מחפשים הוא האחרון ברשימה. ואז היעילות תהיה חיפוש על רשימה מקושרת בת mlogn איברים, שזה mlogn. המקרה הממוצע הוא המקרה הנורמלי, שבו העומס הוא הקטן ביותר האפשרי, כלומר האיברים מתחלקים שווה בשווה בין התאים, שזה אומר log n איברים לתא. אזי חיפוש על הרשימה המקושרת במקרה הזה יקח log n.
עכשיו כשחשבתי שוב על הפיתרון של השאלה הזאת אני מגלה שעשיתי מלא טעויות בתרגיל שלי... נו מילא :)
בעצם צריך להוכיח שקיימת קבוצה K שמוכלת ב-U של מפתחות, בגודל log n, כך שכל איבר ב-K ממופה על-ידי h לאותו תא (נניח a). וההוכחה: יש mlogn מפתחות (יונים) ו-m תאים (שבכים), לכן לפי שובך היונים (המורחב) קיים תא אליו ממופים לפחות logn מפתחות. נסמן ב-K קבוצה של log n מפתחות כאלו (הרגע הראנו כי אכן קיימים לפחות log n כאלו), וסיימנו.
תגובות
(זאת "או" קטנה)
יש שני אלגוריתמים למציאת המספרים המופיעים גם ב A וגם ב B, יש לנתח את הסיבוכיות:
1. נחפש כל אחד מאברי A ב B על ידי מעבר סדרתי על B.
2. נמיין את שני המערכים ואז נריץ שגרת מיזוג, כשבכל פעם שניתקל באיבר זהה, נדפיס אותו.
תודה לכל מי שיענה!
רציתי לשאול האם פישוט הקוד הוא אחד מהיתרונות הישירים לשימוש ב ADT ?
היתה שאלה אמריקאית במבחן מה אינו אחד מהיתרונות לשימוש ב ADT אז בחרתי בפישוט הקוד , אז רציתי לשאול אם למישהו יש מושג אם בתשובה שלי נכונה ..
תודה מראשץ
יהי Alg אלגוריתם מיון (לאו דווקא אחד מאלה שנלמדו בשיעור) במודל ההשוואות. הוכיחו או הפריכו:
א. אם סיבוכיות ריצת Alg על מערך ממוין בגודל n היא n^2 Omega אז סיבוכיות ריצת Alg על מערך בגודל n במקרה הטוב ביותר היא Omegan^2
ב. אם סיבוכיות ריצת Alg על מערך ממוין בגודל n היא Teta של n שורש n אז סיבוכיות ריצת אלגוריתם Alg על מערך בגודל n במקרה הגרוע ביותר היא omega של n שורש n
ג. אם סיבוכיות ריצת Alg על מערך ממויין בגודל n היא O של nlogn, אז סיבוכיות ריצת Alg על מערך בגודל n במקרה הגרוע ביותר היא Omega של nlogn
הבנתי ש א, ג לא נכון וצריך להפריך וב נכון וצריך להוכיח אבל נתקעתי עם דוגמאות הפרכה והוכחה....
אם מישהו יודע, אשמח לתשובה :)
האם מישהו יודע איך להוכיח את המשפט הבא: "הוכיחו שכל עץ מלא יכול להתקבל מאלגוריתם הופמן ע"י מתן שכיחויות מתאימות לעלים"
השאלה נלקחה מהספר קורס הכחול.
לא למדנו איתו הסמסטר ואני עוברת אליו לפני מועד ב ולא מליחה לעלות על רעיון איך להוכיח טענה זו. אני חושבת שצריך בדרך השלילה, אבל מה הניסוח המתאים?
תודה רבה, יעל
שיהיה לכם חג שמח!!!!!!!1
(איזה חג?)
בהצלחה גם לנבחנים בבדידה מחר :)
שאלה ראשונה (חישוב זמן ריצה בנוסחת נסיגה והצבה חוזרת):
שאלה שלישית (השאלה הקשה):
שאלה שישית: עשינו בשיעורי הבית. זמן ריצה סופי:
השאלה עם הערמות: סעיף א, FixHeap על ערימת מקסימום שבה המינימום הוא השורש תקח
השאלה עם זמני הריצה: בכל התאים
השאלה עם השוואה בין זמני ריצה f,g: שניים ראשונים O, שניים הבאים
http://carlstrom.com/stanford/cs161/ps3sol.pdf
בחוברת מגיעים לתשובה
נתון מערך A הכולל n מספרים שמתוכם לכל היותר k אינם במקומם.
למשל, אם n = 9 ו- k = 3
אז במערךA = (3, 6, 20, 10, 8, 16, 17, 15)
המספרים 20, 8, 15 לא במקום כי המערך הממוין
הוא (3, 6, 8, 10, 15, 16, 17, 20).
שימו לב, איבר k אינו במקומו אם מקומו במערך A אינו זהה למקומו במערך A לו A היה ממוין.
כתבו אלגוריתם שממיין את A
בזמן O(n + klogk
[סוף השאלה]
לדעתי אי אפשר לזהות את k המספרים שלא במקומם ב-O(n) חייבים למיין את המערך במודל השואות ולכן nlogn...
לא תהיה שאלה כזו במבחן.
האם למישהו יש את הפיתרונות לשלושת השאלות שמופיעות בעמוד 129 באוגדן (שקופית 236)?
נעלם לי מהמחברת...
אשמח אם תוכלו לסרוק ולהעלות לכאן!
תודה!
אבל לא הצלחתי להעביר לעץ
אשמח לכל עזרה בעניין (ואני בעד כיוונים חזקים :) )
האם הגעת לנוסחת הנסיגה הזאת ?
אם לא, יתכן והשלב הזה יביא אותך לשם:
חישוב עץ הרקורסיה (בצירוף עם שיטת הטבלה שלמדנו בכיתה) את צריכה להגיע לעלות רמה כללית של
נראה לי שהבנתי אז תודה רבה
שיהיה לילה טוב
גם את נוסחת הנסיגה הטבעית ניתן היה לפשט במקרה הזה, וגם כאשר יוצרים את הטבלה של מס' קודקודים, עלות קודקוד ועלות רמה, אם מחשבים נכון, רואים דברים מצטמצמים ומגיעים לביטוי פשוט כמו שכתבתי בהודעה הקודמת.
אני כן מתכננת להעלות סיכומים חלקיים שכתבתי בשיעור, שזה כולל לרוב פתרונות לתרגילים מהמקראה, ואולי אם אספיק גם סיכום של הגדרות ומשפטים
תודה :)
בעיקרון עיקרון שובך היונים מוכיח את הטענה כמעט ישירות. כל מה שנשאר הוא לנסח את ההוכחה כמו שצריך, אבל בעיקרון שובך היונים זה העיקר.
לגבי סעיף ב -
המקרה הטוב לדעתי הוא כאשר האיבר שמחפשים הוא הראשון ברשימה שבתא שאליו הוא ממופה (זה יתכן), ולכן היעילות היא 1.
המקרה הגרוע לדעתי הוא שכל המפתחות מופו לאותו תא, והאיבר שאנחנו מחפשים הוא האחרון ברשימה. ואז היעילות תהיה חיפוש על רשימה מקושרת בת mlogn איברים, שזה mlogn.
המקרה הממוצע הוא המקרה הנורמלי, שבו העומס הוא הקטן ביותר האפשרי, כלומר האיברים מתחלקים שווה בשווה בין התאים, שזה אומר log n איברים לתא. אזי חיפוש על הרשימה המקושרת במקרה הזה יקח log n.
עכשיו כשחשבתי שוב על הפיתרון של השאלה הזאת אני מגלה שעשיתי מלא טעויות בתרגיל שלי... נו מילא :)