החיפוש הניב 35 תוצאות

על ידי eliorar
13:09 31/12/2010
פורום: - פיסיקה 1ב רגיל
נושא: תרגיל בית שמונה שאלה שתיים
תגובות: 2
צפיות: 481

Re: תרגיל בית שמונה שאלה שתיים

שאלה נוספת בקשר לתרגיל, סעיף ב': למה הכוונה - נוח לעבור למערכת קואורדינטות הנעה ימינה במהירות v_0 cos(30) ? האם הכוונה היא שמערכת הצירים תמיד תנוע ביחד עם רכיב התנועה והוא יתאפס? אם כן, למה זה טוב? ומדוע מהירות הגוף מיד לאחר ההתנגשות היא לא זו שמצאנו בסעיף א'? (אלא החסרת ממנה ברכיב ה-x את v_0 cos(30...
על ידי eliorar
14:41 17/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה לגבי DFS
תגובות: 1
צפיות: 1705

Re: שאלה לגבי DFS

אוקיי נראה לי שיש לי תשובה: קשת עץ (הרגילות): אם עברנו מאפור ללבן - כל גילוי של קודקוד חדש. קשת אחורית: מאפור u לאפור v, כך ש u צאצא ו v אב קדמון, כלומר נבדוק אם שניהם אפורים וגם d >d[v] קשת קדמית: מאפור לשחור, כלומר אם u אב קדמון ו v צאצא אז d <d[v] קשת חוצה: גם פה זה מאפור לשחור אבל d >d[v] זה נכון?
על ידי eliorar
00:32 17/07/2010
פורום: - מבני נתונים 2010
נושא: 2009 מועד א שאלה 4 סעיפים א' ב'
תגובות: 5
צפיות: 3611

Re: 2009 מועד א שאלה 4 סעיפים א' ב'

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

כנס לאתר הזה: http://www.cse.ohio-state.edu/~bondhugu ... ndex.shtml
יש שם הדגמה טובה של עץ B-Tree
על ידי eliorar
00:29 17/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה לגבי DFS
תגובות: 1
צפיות: 1705

שאלה לגבי DFS

איך אפשר לשנות את הקוד של DFS, כך שידפיס את כל קשת בגרף מכוון G ביחד עם סוגה (כלומר קשת אחורית/קדימה/עץ/חוצה)? יש קשר למשפט הסוגריים שלמדנו, אבל אני לא מצליח ליישם את זה באלגוריתם.. כלומר קשת (u,v) היא קדימה אמ"ם d ≤d[v]≤f[v]≤f - כאשר u הוא אב קדמון של v. (קשת מאבא לצאצא) קשת אחורית אמ"ם d[v]≤d ≤f ≤...
על ידי eliorar
21:59 16/07/2010
פורום: - מבני נתונים 2010
נושא: 2009 מועד א שאלה 4 סעיפים א' ב'
תגובות: 5
צפיות: 3611

Re: 2009 מועד א שאלה 4 סעיפים א' ב'

סעיף א': לא יכול להיות. אם הפעולה האחרונה הייתה הכנסה של 7 אז הצומת שמעליו (3,8,2) היה צריך להתפצל כי יש לו 2t-1 כלומר 3. כפי שרואים הוא לא מפוצל לכן פעולה זו לא יכלה להתקיים. סעיף ב': 1. לא נכון: log f(n) ≤ c • log g(n) => log f(n) ≤ log ( g(n)^c) => f(n) ≤ g(n)^c וזה בהחלט לא גורר ש f(n)≤c • g(n) ...
על ידי eliorar
16:25 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4565

Re: בנייה של עץ AVL

אני מצטט מקורמן: Inserting a key into a B-tree in a single pass down the tree: We insert a key k into a B-tree T of height h in a single pass down the tree, requiring O(h) disk accesses. The CPU time required is O(th) = O(t logt n). The B-TREE-INSERT procedure uses B-TREE-SPLIT-CHILD to guarantee th...
על ידי eliorar
15:41 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4565

Re: בנייה של עץ AVL

אני חושב כמוך.. השימוש יפחת.

אגב, באותו מבחן איך הוכחת בשאלה 3 (הראשונה חח) זאת עם העץ פורש, את סעיף א'?
על ידי eliorar
15:25 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4565

Re: בנייה של עץ AVL

פעולת הכנסה של skipList היא O(logn) בממוצע לכן, הכנסת n איברים לרשימת דילוגים תיקח O(nlogn) בממוצע
על ידי eliorar
15:18 16/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה לגבי BFS
תגובות: 2
צפיות: 2287

Re: שאלה לגבי BFS

כן, בעיקרון אין שום התייחסות לזה באלגוריתם, לפי מה שכתוב בהרצאה, אפור - קודקוד שגילינו אבל עוד לא סיימנו לטפל בו, כלומר עברנו על כל השכנים שלו ואפשר להמשיך הלאה. קודקוד אפור זה קודקוד שנמצא בתור. הוא הופך לשחור אחרי שהוצאנו אותו מהתור. לדעתי זה די מוסתר באלגוריתם, כי כשאנחנו עוברים לטפל בקודקוד הבא ...
על ידי eliorar
15:12 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4565

Re: בנייה של עץ AVL

אם אין לך שום הנחה על הקלט, אז זהו החסם הנמוך ביותר
על ידי eliorar
15:10 16/07/2010
פורום: - מבני נתונים 2010
נושא: הפיכת מיון ערימה/מיון מהיר למיון יציב
תגובות: 1
צפיות: 1998

הפיכת מיון ערימה/מיון מהיר למיון יציב

נתקלתי בשאלה: כיצד ניתן להפוך את מיון ערימה או מיון מהיר למיון יציב. כמה זמן ומקום נוספים נדרש בשיטה שתיארת? אוקיי אז הפתרון הוא די פשוט, לשמור את האינדקסים של האיברים במערך המקורי, ובזמן השוואה להשוות בנוסף לערך של האיבר, גם את האינדקס שלו במערך המקורי. חישוב זמן ריצה: במקרה הכי גרוע כל האיברים שוו...
על ידי eliorar
14:57 16/07/2010
פורום: - מבני נתונים 2010
נושא: מבחן 2007 - מועד א' שאלה 4א
תגובות: 7
צפיות: 5243

Re: מבחן 2007 - מועד א' שאלה 4א

אוקיי בוא נניח שבנינו "שולחן חשיש" טובה עם פונקציה טובה והכל טוב ויפה אז הכל קורה ב O(1). הטריק הוא במיון.. mergeSort לוקח O(nlogn) ובמקרה שלנו יש k איברים אז הוא לוקח O(klogk) עכשיו צריך להראות שזה לוקח O(n) (כי זה מה שביקשו בשאלה). נשים לב שמתקיים ש k = O(√n) ולכן: k•logk ≤ √n•log(√n) ≤ √n•√n=n הש...
על ידי eliorar
13:26 16/07/2010
פורום: - מבני נתונים 2010
נושא: מבחן 2007 - מועד א' שאלה 4א
תגובות: 7
צפיות: 5243

Re: מבחן 2007 - מועד א' שאלה 4א

כן, בעצם הטריק כאן הוא להציב את מה ששווה k בזמני ריצה.. אין פה משהו יותר מידי מתוחכם חוץ מניסיון לבלבל...
על ידי eliorar
13:09 16/07/2010
פורום: - מבני נתונים 2010
נושא: מבחן 2007 - מועד א' שאלה 4א
תגובות: 7
צפיות: 5243

Re: מבחן 2007 - מועד א' שאלה 4א

קודם כל נבין את הבעיה.. יש לנו מערך של n אובייקטים שונים אבל בכל אובייקט יש מפתח - שהוא לאו דווקא שונה. עכשיו רוצים למיין את האובייקטים האלה לפי המפתח - אבל באופן יציב. הפתרון שהוצע, הוא לבנות עץ AVL שיכיל בכל צומת את כל המפתחות השונים - לפי נתוני השאלה יש בדיוק k כאלו, בכל קודקוד, יהיה קישור לתור, ...
על ידי eliorar
12:55 16/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה ב Counting Sort
תגובות: 0
צפיות: 1472

שאלה ב Counting Sort

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

עבור לחיפוש מתקדם