שאלה מהמבחן באלגוריתמים 1

[fudge]

נתנו 2 סטים של k צמתים שעומדים זה מול זה, k צמתים מימין ו-k צמתים משמאל. לקחו את המספרים 1, 2, ... n, כך ש- n>=k, ופיזרו אותם בין k הצמתים השמאליים כך שבכל צומת יהיה לפחות מס' אחד, כלומר כל המספרים מ-1 עד n מופיעים בדיוק פעם אחת בסה"כ, ואין צומת שנותר בלי מספרים.

באותו אופן עשו עוד פיזור של המספרים מ-1 עד n, הפעם בין k הצמתים הימניים.

 

ביקשו שני דברים -

 

1. לחבר בין שני הסטים של הצמתים n קשתות לא מכוונות שמחברות את המספרים הרלוונטיים שבתוך הצמתים. למשל אם בצומת שמאלי מסוים הופיעו המספרים 3,5,8 אז צריך לחבר אותו לצמתים הימניים שבהם מופיעים המספרים 3,5 ו-8. אם יש יותר מקשת אחת בין שני צמתים אין בה צורך, המיותרות נופלות.

 

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

 

 

אז מבקשים בעצם לבנות רשימת סמיכויות לגרף ע"ס המספרים שבתוך הצמתים, ואחרי זה להפעיל אלגוריתם למציאת זיווג מקסימלי ולבדוק האם הוא מגודל k. הם מבקשים בנוסף שזה יהיה מסדר nk + k^3.

 

האחרון לוקח nk עפ"י מה שזכרתי מהספר של קורמן (זה גם הופיע בדף הנוסחאות לדעתי), השאלה שלי היא - איך הם רוצים שאבנה את רשימת הסמיכויות בסיבוכיות k^3? איך יכול להיות שאין פה גורם של n, הרי יש n צמתים להוסיף. לי יצא משהו כמו nlogn + nk בשביל שלב 1, אני לא מצליח להבין איך הם רצו שזה ייעשה פה.

 

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

[ohad]

זה הפוך (מבחינת הסיבוכיות),

בניית הגרף לוקחת http://www.codecogs.com/gif.latex?%20O(nk) כי לכל n אתה מחפש פעמיים באיזה מ k הצמתים הוא מופיע.

מציאת שידוך מקסימלי בגרף דו"צ לוקחת http://www.codecogs.com/gif.latex?O(VE) כאשר כאן http://www.codecogs.com/gif.latex?V=O(k) ו http://www.codecogs.com/gif.latex?E=O(k%5E2)

[fudge]

אוהד, תודה על התשובה אבל לא כ"כ הבנתי, אתה מניח במשפט השני שהחיפוש בתוך כל צומת הוא בחינם, למה? אתה הרי מחפש כל פעם מספר אחד מתוך n, שחילקו אותם אקראית בין k קבוצות, אבל אלה עדיין n מספרים.. או שמניחים פה איזשהו מימוש שנותן בזמן O(1)dd את איברי הקבוצה? ואם כן, למה? הרי בסה"כ זה מצטבר ל-n מספרים שצריך לחפש ביניהם.

לגבי מציאת השידוך - מסכים שמס' הצמתים הוא k, אבל בגרף שנוצר יש בדיוק n קשתות, למה אתה מתייחס אליהן כ-k^2 ולא כ-n?


 

[ohad]

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

אפשר לפתור את הבעיה כך:

אתה בונה מטריצה n X k, עובר על כל הקבוצות כמו שאתה אמרת וממלא אותה, זה ייקח http://www.codecogs.com/gif.latex?O(n) ואז באמת ניתן לפתור כמו שאני אמרתי.

 

כי תמיד http://www.codecogs.com/gif.latex?O(E)%20=%20O(V%5E2) כשאין קשתות מקבילות (ופה אין).

[אסף]

 

לגבי מציאת השידוך - מסכים שמס' הצמתים הוא k, אבל בגרף שנוצר יש בדיוק n קשתות, למה אתה מתייחס אליהן כ-k^2 ולא כ-n?

 

למה שיהיו בדיוק n קשתות? אם k=1 תהיה רק קשת אחת.

[GIR]

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

אפשר לפתור את הבעיה כך:

אתה בונה מטריצה n X k, עובר על כל הקבוצות כמו שאתה אמרת וממלא אותה, זה ייקח http://www.codecogs.com/gif.latex?O(n) ואז באמת ניתן לפתור כמו שאני אמרתי.

 

כי תמיד http://www.codecogs.com/gif.latex?O(E)%20=%20O(V%5E2) כשאין קשתות מקבילות (ופה אין).

זה לא אומר שאפשר לבנות את הגרף בO של N?

תיצור מערך באורך N

תעבור על כל הצמתים שבצד שמאל:

עבור כל מספר x שמופיע בצומת תשים את אינדקס הצומת במקום ה x במערך

נגיד אם 5 מופיע בצומת הראשונה תשים 1 בתא ה5 במערך

אם 7 מופיע בצומת ה3, שים 3 במקום ה7 במערך

בגלל שסה"כ יש N מספרים, וכתיבה למקום הN במערך היא O של 1 היצירה של המערך הזה תקח O של N

 

עכשיו תעבור על כל הצמתים בצד ימין

ועבור כל מספר  x שמופיע בצומת תלך לתא ה x במערך - שם יהיה רשום לך באיזה צומת הוא מופיע בצד השני

נגיד אם בצומת הראשונה מופיע לך 7, תקרא מתא 7 במערך ושם יהיה רשום 3 - שזה האינדקס של הצומת שבה מופיע המספר הזה בצד שמאל

ואז אתה יודע שצריך ליצור קשת בין הצומת הראשונה בצד ימין לצומת ה3 בצד שמאל

גם פה אתה צריך לעבור סה"כ על N מספרים אז גם זה O של N

[fudge]

אוהד, נראה שצדקת. תודה על העזרה וגם לשאר העוזרים.

[ohad]

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