Welcome

Tel-Aviv University
School of Computer Science
Algorithms
0368.2160
Fall Semester 2019/2020

News

אלגוריתמים - תרגיל 6 עלה


שלום לכולם,
תרגיל 6 פורסם, והוא להגשה ב-26.1.2020.
בהצלחה,
ג׳אד וטל


(09 Jan 2020 17:19)

אלגוריתמים - תרגיל 5 עלה


שלום לכולם,
תרגיל 5 פורסם, והוא להגשה ב-9.1.2020.
בהצלחה,
ג׳אד וטל


(26 Dec 2019 15:43)

אלגוריתמים - תרגיל 4 עלה


שלום לכולם,
תרגיל 4 פורסם, והוא להגשה ב-26 בדצמבר.
בהצלחה,
ג׳אד וטל


(10 Dec 2019 15:03)

אלגוריתמים - תרגיל 3 עלה


שלום לכולם,
תרגיל 3 פורסם, והוא להגשה ב-12 בדצמבר.
סופ"ש נעים,
ג׳אד וטל


(27 Nov 2019 11:50)

אלגוריתמים - תרגיל 2 עלה


שלום לכולם,
תרגיל 2 פורסם, והוא להגשה ב-28 בנובמבר.
סופ"ש נעים,
טל


(15 Nov 2019 10:54)

תרגיל 1 עלה

תרגיל 1 עלה

שלום לכולם,
תרגיל 1 עלה לאתר הקורס, וניתן להגישו דרך gradescope.
ההגשה פתוחה עד ה-13 בנובמבר, 12:00 בצהריים.
עבודה נעימה.


(31 Oct 2019 17:12)

Recent Forum Posts

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

ציון לאחר ערעור: Re: ציון לאחר ערעור

By RaeNye on 20 Feb 2020 16:04

לא בטוח שהבנתי את כוונתך, אבל ערעור עשוי לשנות ציון של שאלה בבחינה ואז יתבצע אותו חישוב שתיארתי בפוסט של אתמול (ציון בחינה->ציון משולב->ציון סופי).

ציון לאחר ערעור: ציון לאחר ערעור

By student500 on 19 Feb 2020 20:11

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

תודה.

ציוני מועד א: ציוני מועד א

By RaeNye on 19 Feb 2020 17:52

תלמידים יקרים,

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

  • ציון הבחינה חושב בהתאם לסילבוס (כל אחת מ-4 השאלות הטובות שוה 22.5 נק' והפחות טובה שווה 10) בתוספת 5 נקודות.
  • הציון המשולב הוא 0.95*בחינה + 0.1*ש"ב (כן, זה יכול להיות יותר מ-100)
  • הציון הסופי חושב כך:
    • אם ציון הבחינה הוא לפחות 50 והמשולב הוא לפחות 55, אז הציון הסופי הוא המשולב מעוגל וקטום לקטע 60 עד 100;
    • אחרת, הציון הסופי הוא המשולב מעוגל וקטום לקטע 0 עד 55.

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

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

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

בהצלחה בשאר הבחינות!

מועד א: מועד א

By student111 on 03 Feb 2020 17:26

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

תודה.

אלגוריתם קרוסקל מול פרים: Re: אלגוריתם קרוסקל מול פרים

By RaeNye on 01 Feb 2020 17:11

היי אייל,

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

אם $|E|=\omega(|V|)$ אז Prim עדיף בוודאות.
אם $|E|=O(|V|\log|V|)$ והקשתות נתונות ממוינות (או שניתן למיינן בזמן לינארי) אז Kruskal עדיף בוודאות.

שבוע טוב,
ר.

למה מתכוונים ב"מסלול" בקורס?: Re: למה מתכוונים ב"מסלול" בקורס?

By RaeNye on 01 Feb 2020 17:11

היי אלדד,

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

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

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

שבוע טוב,
ר.

2019 semester A moed B: Re: 2019 semester A moed B

By RaeNye on 01 Feb 2020 17:10

היי אליהו,

1. זה באמת אפשרי אמ"מ הגרף הוא DAG, ואז צריך לחפש מסלול ארוך ביותר בקשתות (כלומר לתת משקל מינוס אחד לכל קשת ולחשב מק"ב) מצומת חדש s שרואה את כולם ("הצלם"), ולסדר לפי המרחקים מ-s.
3. נסה להגדיר $o(j),e(j)$ כסכום המקסימלי שמתקבל מתת-סדרה באורך זוגי/אי-זוגי בהתאמה כלשהו שהאיבר האחרון שלה הוא $a_j$. האלגוריתם יוצא לינארי.

שבוע טוב,
ר.

2019 sem a moed b - question 5: Re: 2019 sem a moed b - question 5

By RaeNye on 01 Feb 2020 17:10

היי מנדי,

נסמן ב-$v^*$ את הערך האופטימלי של $P$ (וגם של $D$, מדואליות חזקה), וב-$v_i$ את ערך התכנית $P_i$ שהיא $P$ ללא אילוץ i.
לכל i מתקיים $v_i\ge v^*$, כולל האפשרות ש-$P_i$ לא חסומה. לכן אין טעם במקסימום — הוא יכול להיות אינסוף.

עדיין צריך להסביר למה $\min_i v_i$ שווה ל-$v^*$ ולא גדול ממנו.
זה נובע מכך שהתכנית $D_i$ (שדואלית ל-$P_i$) מתקבלת מ-$D$ ע"י הצבת $y_i=0$, ולכן y פיזיבילי לא רק עבור $D$ אלא גם עבור $D_j$ מסוימת, כלומר $v_j=v^*$.

שבוע טוב,
ר.

בנושא דואליות: Re: בנושא דואליות

By RaeNye on 01 Feb 2020 17:09

היי עמרי,

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

שבוע טוב,
ר.

אלגוריתם קרוסקל מול פרים: אלגוריתם קרוסקל מול פרים

By Eyal Hochstadt on 01 Feb 2020 08:33

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License