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

מנהל: TA_Isana

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

הודעהעל ידי ec1 » 11:53 16/07/2010

נתון מערך בגודל n המכיל n איברים שונים. לכל איבר יש מפתח משלו אך המפתחות אינם בהכרח שונים זה מזה. ידוע כי סך כל המפתחות השונים השייכים לאיברי המערך הינו k. המפתחות לאו דווקא מהווים רצף של מספרים.
א. [15 נקודות] תאר אלגוריתם למיון יציב של איברי המערך העובד בזמן ( O( (במקרה הגרוע) כאשר k=O(logn).

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

בסעיף ב' - איך בדיוק מתבצע המיון?

10 נקודות] תאר אלגוריתם למיון יציב של איברי המערך העובד בזמן ממוצע O(n) כאשר ) k= O (.


שאלה הזויה, או שאני כבר לא מצליח להיכנס לפוקוס? :roll:

תודה.
נערך לאחרונה על ידי ec1 בתאריך 11:58 16/07/2010, נערך פעם אחת בסך הכל.
ec1
 
הודעות: 11
הצטרף: 18:16 22/12/2009

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

הודעהעל ידי ec1 » 11:54 16/07/2010

the solution... :

We construct an AVL-tree T of size k=O(logn), containing one node for each key. Each node in T contains a key and a pointer to a Queue that contains elements with the same key.
- Go over the elements in the input array, from left to right.
- For each element X, search T for a node with the same key as that of X.
• If such a node is found, insert X at the tail of the corresponding Queue.
• Otherwise, create a new node in T with the same key as that of X and a pointer to a (new) Queue that contains just one element, X.
- Perform an inorder traversal on T. When travsering a node, all elements of its corresponding Queue are being removed one after another (from head to tail) and are being inserted into the output array.

Running Time – The main loop consists of n iterations, each of which takes O(loglogn) time (notice that the height of T is (loglogn)).
The inorder traversal (including all dequeue operations) takes O(n) time.
Therefore, the total running time is O(n loglogn).
The algorithm is stable due to the use of Queues.
ec1
 
הודעות: 11
הצטרף: 18:16 22/12/2009

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

הודעהעל ידי eliorar » 12:09 16/07/2010

קודם כל נבין את הבעיה.. יש לנו מערך של n אובייקטים שונים אבל בכל אובייקט יש מפתח - שהוא לאו דווקא שונה.
עכשיו רוצים למיין את האובייקטים האלה לפי המפתח - אבל באופן יציב.
הפתרון שהוצע, הוא לבנות עץ AVL שיכיל בכל צומת את כל המפתחות השונים - לפי נתוני השאלה יש בדיוק k כאלו, בכל קודקוד, יהיה קישור לתור, לשם יוכנסו האובייקטים לפי סדר ההכנסה למערך, כלומר יש עץ AVL של תורים.
ככה בזמן שנקרא ב inorder נוציא בתור את כל האיברים שנקרא ראשונים ואז המיון ישאר יציב.

לגבי זמן ריצה, הכנסה תיקח log k ומכיוון ש k=logn אז בסה"כ זה יקח O(log log n) עכשיו מבצעים את ההכנסה על n איברים ובסה"כ n log logn.
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

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

הודעהעל ידי ec1 » 12:17 16/07/2010

תודה!

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

אז למעשה - באשר לסעיף ב' ולשימוש בטבלת גיבוב - הרעיון הוא דומה, נבנה טבלת גיבוב בגודל K כשלכל ערך בטבלה נשרשר את הערכים בעלי אותו המפתח, נמיין את האינדקסים בטבלה ונחזיר אותם? משהו קצת מתפספס בשאלה הזו לדעתי.
ec1
 
הודעות: 11
הצטרף: 18:16 22/12/2009

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

הודעהעל ידי eliorar » 12:26 16/07/2010

כן, בעצם הטריק כאן הוא להציב את מה ששווה k בזמני ריצה.. אין פה משהו יותר מידי מתוחכם חוץ מניסיון לבלבל...
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

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

הודעהעל ידי ec1 » 12:32 16/07/2010

ניסיון מוצלח לבלבל... אגב - התשובה "הרשמית" של סעיף ב' נראית מבלבלת עוד יותר מהשאלה עצמה, הבנת פחות או יותר מה רוצים בה? :


We use a hash table of size (about) 2k with double-hashing (hash table with chaining will do as well).
Denote the appropriate hash-function by h.
Each entry in the table will point to a Queue containing elements with the same key. (By definition of double-hashing, there are no "collisions".)

- Initialize all entries of the table to null.
O(n) in the worst case.

- Go over the elements of the input array (from left to right) and insert them to the hash-table. When inserting an element with key Num, we first search whether there is an entry in the table that points to a linked list that contains elements with key Num.
If so, the inserted element should be placed at the tail of the corresponding Queue.
Otherwise, the null entry (at h(Num)) should point to a (new) Queue containing the inserted element.

Since the load factor alpha is at most 1/2, the average running time of each insertion will be O(1/(1-alpha)) = O(1) and the total average running time of the insertions is thus O(n).

- Order the lists by their key (a null entry is ignored) using mergeSort and output the "ordered" linked lists one after another, into the output array.

The mergeSort running time is O(k logk) = O(n) and the "output" process takes O(n) time as well.

The total average running time of the algorithm is therefore O(n).
The algorithm is stable due to the use of Queues.


ואגב, פרט פיקנטי נחמד - hash table כחלק מהקונטקסט מתורגם בגוגל לביטוי די משעשע - "שולחן חשיש" :)
ec1
 
הודעות: 11
הצטרף: 18:16 22/12/2009

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

הודעהעל ידי eliorar » 13:57 16/07/2010

אוקיי בוא נניח שבנינו "שולחן חשיש" טובה עם פונקציה טובה והכל טוב ויפה אז הכל קורה ב O(1).
הטריק הוא במיון.. mergeSort לוקח O(nlogn) ובמקרה שלנו יש k איברים אז הוא לוקח O(klogk) עכשיו צריך להראות שזה לוקח O(n) (כי זה מה שביקשו בשאלה).
נשים לב שמתקיים ש k = O(√n) ולכן:
k•logk ≤ √n•log(√n) ≤ √n•√n=n

השתמשנו בזהות:
קוד: בחר הכל
log(x)≤x

ולכן O(klogk)=O(n)
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

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

הודעהעל ידי ec1 » 14:11 16/07/2010

תודה :)
ec1
 
הודעות: 11
הצטרף: 18:16 22/12/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד