Welcome

Tel-Aviv University
School of Computer Science
Algorithms
0368.2160
Spring Semester 2019

News

תזכורת לסטודנטים של התירגול בחמישי ב-13:00


עקב יום הסטודנט, לא יתקיים התירגול של יום חמישי ב-13:00 השבוע.
הסטודנטים הרשומים לקבוצה מתבקשים להגיע לכל אחת מקבוצות התירגול האחרות.


(20 May 2019 08:17)

תירגולי השלמה - APSP


שלום לכולם,
השבוע נקיים תירגולי השלמה בנושא APSP.
לנוחיותכם, מוצעים שלושה מועדים, שאפשר להגיע לכל אחד מהם, להלן:
יום שלישי 21.05 15:00 שנקר 204
יום שלישי 21.05 19:00 שנקר 204
יום שישי 24.05 11:00 אורנשטיין 102

שבוע טוב.


(19 May 2019 11:27)

בשבוע הבא לא יתקיימו תרגולים באלגוריתמים עבור כל הקבוצות (גם לא ביום שני)


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


(13 Apr 2019 16:18)

תרגיל 2 עלה


שלום לכולם,
תרגיל 2 עלה, והוא להגשה ב-4 באפריל, עד 12:00 בצהריים.
עבודה נעימה.


(20 Mar 2019 14:52)

הודעה לחוזרים על הקורס


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


(17 Mar 2019 14:45)

תזכורת: תרגולי השלמה בשבוע של פורים (שבוע הבא)


יתקיימו בזמנים ובמיקומים הבאים:
שלישי 19.03 16:00-17:00 אורנשטיין 103
שלישי 19.03 19:00-20:00 אורנשטיין 103
רביעי 20.03 18:00-19:00 הולצבלט 007

ניתן להגיע לכל אחת מהאפשרויות.


(15 Mar 2019 14:09)

תרגיל 1 עלה


שלום לכולם,
תרגיל 1 עלה, והוא להגשה ב-20 במרץ, עד 12:00 בצהריים.
ההגשה היא דרך gradescope.
עבודה נעימה.


(07 Mar 2019 15:47)

Recent Forum Posts

תרגיל 5 שאלות 3 ו-7: תרגיל 5 שאלות 3 ו-7

By Itamar Zafrir on 25 May 2019 20:14

הי,

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

תודה!

ex5 q8: ex5 q8

By yota1234 on 24 May 2019 20:24

שלום,
בתרגול "LP1" בתרגיל 3, נוסחה בעיית תכנות לינארי אבל בצורה לא סטנדרטית:
פוקנציית המטרה אינה מכילה משתנים כלל, אלא "T", שהינו חלק מהאילוצים שנכתבו פר w(e).
מדוע זהו פתרון לגיטימי או במילים אחרות מדוע הפתרון כפי שנכתב הוא בכלל linear program? זה לא עונה על הדרישות הבסיסיות של הגדרה פורמלית של תוכנית לינארית.

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

תרגיל 7: Re: תרגיל 7

By omerc on 24 May 2019 14:49

תודה!

תרגיל 7: Re: תרגיל 7

By tal_yank on 24 May 2019 08:09

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

linear programmign questions in hw5: Re: linear programmign questions in hw5

By tal_yank on 24 May 2019 07:58

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

תרגיל 5 שאלה 7א: Re: תרגיל 5 שאלה 7א

By tal_yank on 24 May 2019 07:47

היי להב,
לעיתים מגדירים את R+ כממשיים חיוביים ולעיתים מגדירים את R+ כממשיים אי-שליליים, כאן הכוונה לשני.
טל

תרגיל 7: תרגיל 7

By omerc on 23 May 2019 17:42

בתרגיל 7 אנו מתבקשים לכתוב תוכנית לינארית ולמצוא את הבעיה הדואלית שלה.
התוכנית הלינארית המקורית שמתבקשים לכתוב אינה בצורה הסטנדרטית (נדרש מציאת מינימום ולא מקסימום).
האם הבעיה הדואלית מוגדרת רק עבור תוכנית לינארית בצורה הסטנדרטית, או שניתן באופן כללי לבצע שחלוף למטריצת האילוצים\מטרה גם עבור תוכנית לא סטנדרטית, על מנת לשמר את המבנה הקריא של הבעיה?
(כמובן שניתן בקלות לעבור מהבעיה הדואלית של הצורה הסטנדרטית לצורה קריאה, השאלה אם מעברי הביניים נדרשים, או שניתן לעבור ישירות בין בעיות שקל להבין את הבעיה שעולה מהן).

linear programmign questions in hw5: linear programmign questions in hw5

By yota1234 on 23 May 2019 11:10

שלום
האם צריכים לספק הוכחה כי התוכנית הלינארית שמצאנו בשאלה 2 וכו' היא נכונה ואכן פותרת את הבעיה המקורית?

או רק לספק הגדרה פורמלית של הבעיה בצורת LP ?

תרגיל 5 שאלה 7א: תרגיל 5 שאלה 7א

By Lahav on 22 May 2019 16:41

מתקיים

(1)
\begin{align} R^+ = \left \{ x \in R \mid x > 0 \right \} \end{align}

ועל כן נובע שיש אילוצי $x_i > 0$, אך אלו לא אילוצים חוקיים ב LP.

האם אני מפספס משהו, או שהכוונה היא שהפונקציה $f$ יכולה למפות גם ל 0?

תודה.

תרגיל 5 שאלה 2: Re: תרגיל 5 שאלה 2

By tal_yank on 18 May 2019 18:10

כן, אפשר.

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