Tel-Aviv University
School of Computer Science
Algorithms
0368.2160
Fall Semester 2011/2012
News
איך למצוא פתרון פיזיבילי בסיסי
In the "General Information" tab.
The first thing the Simplex algorithm does is find a feasible solution (with INITIALIZE-SIMPLEX). This was not covered in the lectures. We have written up a document explaining how to do this. The document includes a very detailed running of the algorithm to find a feasible solution, and also the running of the Simplex algorithm to find the optimal solution.
If you feel that you need more practice with Linear Programming, thoroughly reading this document should clear many things up.
(26 Jan 2012 08:37)
רמזים לתרגיל
שאלות 5 ו-7
שימו לב שדף התרגילים מכיל כעת רמזים לשאלות 5 ו-7 מהתרגיל.
(25 Jan 2012 15:20)
תרגול חזרה ושעות קבלה מיוחדות
פרטים בדף השאלות לקראת הבחינה
יומיים לקראת הבחינה (07.02) נערוך תרגול חזרה.
אם יש לכם שאלות שאתם רוצים שנפתור בתרגול החזרה, שלחו לנו אותן עד יום ראשון ה05.02 בערב.
בנוסף, בשבוע שלפני כן נערוך סדרת שעות קבלה שאתם מוזמנים להגיע אליהן עם שאלות.
הזמנים והמיקומים של כל שעות הקבלה ושל תרגול החזרה נמצאים בתחתית דף השאלות לקראת הבחינה.
(25 Jan 2012 10:27)
דף חדש באתר
לקראת הבחינה
הוספנו לאתר דף חדש בשם Exam FAQ.
תוכלו למצוא בו הסברים על מבנה הבחינה, ותשובות לשאלות נוספות שאולי יהיו לכם לקראת הבחינה.
(22 Jan 2012 22:40)
שעות קבלה
לשי יש מעכשיו ועד סוף הסמסטר שעות קבלה מסודרות: יום ראשון ושלישי ב
14:00-15:00
שעות הקבלה הן ב
open space
בשרייבר.
בקומת המרתף. אם אף אחד לא באזור לפתוח את הדלת, תדפקו חזק.
אם למישהו אף אחת מהשעות הנ"ל לא נוחות, ניתן עדיין לתאם שעת קבלה אחרת במייל.
שעות הקבלה עם אדם נותרו ללא שינוי.
כלומר, אין שעות שבועיות קבועות. במקום, מתאמים במייל שעה שנוחה לכולם.
(15 Jan 2012 11:17)
ציונים מעודכנים ופתרונות
בדף התרגילים באתר
בדף התרגילים באתר, תוכלו כעת למצוא:
1. קובץ ציונים מעודכן, שמכיל גם הציונים של תרגיל 3. אנא ודאו שהציונים שרשומים עבורכם נכונים!
2. קובץ עם פתרונות לשאלות קשות מתרגילי הבית. בינתיים הקובץ מכיל רק שני פתרונות, אך לקראת הבחינה אנחנו מתכננים להוסיף אליו תרגילים שנבין מכם שהיו קשים במיוחד.
ספציפית, שאלה 8ב שכבר בקובץ הייתה בעייתית במיוחד, ורק סטודנטים אחדים הגיעו לזמן הריצה שחשבנו עליו.
(13 Jan 2012 09:57)
תרגול דיניץ
ביום ראשון הקרוב (15.1) שי יעביר תרגול חזרה על דיניץ ועוד כמה דברים בשעה 14:05-15:05 בשרייבר 309
ביום ראשון הקרוב (15.1) שי יעביר תרגול חזרה על דיניץ ועוד כמה דברים בשעה 14:05-15:05 בשרייבר 309
לא ילמד חומר חדש - התרגול יהיה חזרה על חומר שנלמד בשיעורים.
בתרגול אני אסביר שוב את האלגוריתם עצמו ואנתח אותו, אגע קצת ברשתות 0-1 (הכנה לשיעור הבא בו פרופ' שריר ידבר עוד קצת על רשתות 0-1) ואם יהיה זמן אדבר קצת על
max-capacity flow augmentation.
(12 Jan 2012 13:15)
תרגילי שלוש הבדוקים חזרו
כרגיל, תוכלו למצוא אותם בחדר הצילום
תרגילי 3 הבדוקים חזרו, ותוכלו למצוא אותם בחדר הצילום.
אנו מקווים גם להעלות קובץ ציונים מעודכן בימים הקרובים.
(12 Jan 2012 10:50)
Maximum Capacity Flow Augmentation proofs
The proofs for the Maximum Capacity Augmentation variant of Ford Fulkerson given in class are not in any of the text books, so we have written them up. The file is under the "General Information" Tab.
The proofs for the Maximum Capacity Augmentation variant of Ford Fulkerson given in class are not in any of the text books, so we have written them up. The file is under the "General Information" Tab.
(11 Jan 2012 13:03)
We wrote you a dynamic programming guide
In the "General Information" tab
We just wrote a guide for people that have a hard time using dynamic programming.
It's the first draft, so we'll be happy to get some feedback: bugs, unclear sentences, and any other suggestions.
(28 Dec 2011 11:42)
עוד נושאי שביתה
תרגולי השלמה ותרגילי בית
כמה עדכונים בעקבות השביתה:
קודם כל, עקב התרגול שבוטל יהיו תרגולי השלמה.
אנחנו נבצע שני תרגולים זהים. אתם מוזמנים לבוא לזה שנוח לכם.
התרגול הראשון יהיה בשישי מיד לאחר שיעור ההשלמה, ויועבר על ידי אדם.
התרגול השני יהיה ביום שני ה-02 לינואר, ב-18:00, ויועבר על ידי שי.
אלו מכם שלא יכולים להגיע לשני המועדים יוכלו למצוא את מצגת התרגול באתר, ולפנות אלינו לשאלות.
ועכשיו נעבור לחדשות הטובות - דחינו את המועד של תרגיל 4 בשבוע, ל-12 בינואר.
(וכנראה שבקרוב יהיו חדושות טובות נוספות בנושא תרגילי הבית)
לגבי החדרים של התרגולים, נפרסם אותם בדף ה
course scheule
ברגע שנדע מה הם. בתקווה מחר.
(26 Dec 2011 11:03)
Assignment #2 is back
and the grades file is updated
You can find the graded assignment #2 in the copy room.
Also, you can check your grades in the exercises page (and verify that we got your grades right!)
(22 Dec 2011 13:47)
נושאי שביתה
תרגילים, השלמות, ועוד
שלום לכולם,
כמו שבטח שמתם לב, היום אין תרגולים עקב השביתה.
לכן, גם אם השביתה תפסק, מחר לא יהיו תרגולים
כיוון שיש סטודנטים שלא נמצאים באוניברסיטה בחמישי עקב השביתה, אנחנו מזיזים את מועד הגשת התרגיל ליום שני הקרוב. בבקשה אל תנצלו את זה ותבקשו הארכה נוספת בגלל שאתם לא נמצאים ביום שני באוניברסיטה.
בנוסף, אל תשכחו שביום ראשון הקרוב אין שיעור עקב חנוכה.
במקום, ניתן להגיע לשיעור של יום שלישי, או לשיעור השלמה שיערך ביום שישי בשבוע הבא. פרטים על שיעור ההשלמה ניתן למצוא בדף הלו"ז שבאתר.
(21 Dec 2011 12:42)
New --- a grades file
In the exercises page
The exercises page now contains the grades of the first assignment (in a pdf file).
You can identify your grade according to the last four digits of your ID.
(20 Dec 2011 21:21)
The first assignment is back
You can find it in the copy room
The graded first assignments can be found in the copy room (room 114).
(08 Dec 2011 12:37)
תיקון בתרגיל 2
בשאלה 3
הייתה לנו טעות מטופשת בשאלה 3 של תרגיל 2.
לא שינינו את קובץ התרגיל, אלא הוספנו הערה בתחתית דף התרגילים (שבכלל שווה לשים לב מה כתוב בו).
אנא שימו לב אל ההערה.
(20 Nov 2011 14:48)
יש לכם שאלות על התרגילים?
אתם מוזמנים להשתמש בפורום של האתר
היות שאף אחד עדיין לא השתמש בו, רציתי לציין שיש לנו פורום באתר.
אם יש לכם שאלות על תרגילי הבית (או על כל נושא אחר), אתם מאוד מוזמנים להשתמש בו.
(13 Nov 2011 08:08)
Welcome to the TAU algorithms website
All the news and the material of the course can be found here
באתר הזה נשתדל לשים את כל החומר הקשור לקורס. בין היתר האתר יכיל את תרגילי הבית, הציונים של תרגילי הבית, המצגות, עדכונים בקשר לקורס, ועוד.
משהו שאולי אתם כבר תוהים לגביו - ניתן ללכת לכל שיעור ותרגול שנוח לכם. כל שבוע מרצה אחד יעביר את שני השיעורים (אתם יכולים לראות מי יהיה המרצה של כל שבוע בדף הלו"ז שבאתר). לגבי התרגולים, אדם משתמש במצגות ושי כותב על הלוח. כך שאם יש לכם העדפה, אתם יכולים ללכת למה שמתאים לכם.
(31 Oct 2011 05:56)
Recent Forum Posts
שאלה 3, מבחן סמסטר א' תשע"א, מועד ב' 23.10.11: Re: שאלה 3, מבחן סמסטר א' תשע"א, מועד ב' 23.10.11
By adamsh on 27 Jan 2012 15:07
היי נתנאל,
צודק.
זה אכן אמור להיות קטן שווה ולא גדול שווה.
אדם
שאלה 3, מבחן סמסטר א' תשע"א, מועד ב' 23.10.11: שאלה 3, מבחן סמסטר א' תשע"א, מועד ב' 23.10.11
By Netanel on 27 Jan 2012 14:44
היי,
רק רציתי לברר אם יש מצב שנפלה טעות בשאלה..?
אנחנו רוצים למצוא קיי קשתות שהסרתן תביא לזרימה המקסימאלית הכי קטנה, תחת הנתון שקיי גדול שווה למספר הקשתות בגרף.
הנתון אמור להיות שקיי קטן שווה למספר הקשתות?
כי אחרת, האופציה היחידה היא להוריד את כל הקשתות… או שאני מפספס משהו?
תודה רבה!
דייקסטרה עם חסם על המשקל של הקשתות: Re: דייקסטרה עם חסם על המשקל של הקשתות
By adamsh on 27 Jan 2012 10:56
היי אליאב,
בתרגיל הזה ביצענו שינוי של האלגוריתם של דייקסטרה.
דוגמא לא תעזור להבין את השינוי, כיוון האלגוריתם שאנו מריצים הוא עדיין דייקסטרה.
כלומר, כל דוגמא של הרצה של דייקסטרה על גרף עם משקלים של 0,1,2 תהיה זהה להרצה של האלגוריתם החדש שבנינו.
זה המצב כיוון שהדבר היחידי ששינינו זה את תור העדיפויות. במקום להשתמש בערמת פיבונאצ'י בנינו תור חדש.
דייקסטרה מבקש מהתור שלו לבצע מספר מספר לינארי של פעולות, והתור החדש יודע לבצע כל פעולה בזמן קבוע. לכן מתקבלת גרסא של דייקסטרה שרצה בזמן לינארי.
להסביר מההתחלה עד הסוף איך התור החדש עובד יהיה ארוך ומסובך מדי לפורום. אתה מוזמן לשאול כאן שאלות יותר ספציפיות לגבי מה בדיוק לא מסתדר לך, או, אם אתה רוצה לשמוע הסבר מלא, להגיע לשעת קבלה של שי או שלי.
אדם
דייקסטרה עם חסם על המשקל של הקשתות: דייקסטרה עם חסם על המשקל של הקשתות
By אליאב on 27 Jan 2012 10:31
שלום לכולם,
בתרגול 6 עסקנו בשאלה האם ניתן לשפר את הסיבוכיות של דייקסטרה אם המשקל על הקשתות שייך לקבוצה {0,1,2}.
האם אפשר דוגמא של הרצה של הפתרון על גרף פשוט? או הסבר קצת יותר מעמיק?
תודה רבה
אליאב
עד איזו שעה ניתן להגיש את התרגיל ביום ההגשה?: Re: עד איזו שעה ניתן להגיש את התרגיל ביום ההגשה?
By Shai V on 25 Jan 2012 05:55
אין מגבלת זמן. ניתן להגיש את התרגיל עד חצות.
שי
עד איזו שעה ניתן להגיש את התרגיל ביום ההגשה?: עד איזו שעה ניתן להגיש את התרגיל ביום ההגשה?
By The_Comedian on 24 Jan 2012 22:50
אהלן,
פעם ראשונה שאני כנראה אגיש ביום ההגשה ולא לפני כן, ולכן השאלה המתבקשת: עד איזו שעה ניתן להגיש את התרגיל ב26.01?
תודה!
תרגיל 5 שאלה 5:
By adamsh on 22 Jan 2012 15:59
אני מצטער, אבל לענות על זה יהיה לפתור חלק גדול מהשאלה.
אם אתה לא מסתדר עם הנושא, אתה תמיד מוזמן לפנות אלי או אל שי באופן פרטי.
אדם
תרגיל 5 שאלה 5:
By עומר on 22 Jan 2012 08:14
לצערי גם זה לא קידם אותי יותר מדי, במיוחד כי לא ברור איך הגרף צריך להיראות (מה יהיו הקשתות והקיבולים עליהן בעיקר…)
תרגיל 5 שאלה 5:
By adamsh on 21 Jan 2012 21:49
היי עומר,
אי אפשר להשתמש בתכנות לינארי לצורך הפתרון של זה.
כלומר, אנחנו מחפשים אלגוריתם שיפתור את השאלה בסיבוכיות טובה, ולא למדנו אלגוריתם כזה לבעיות תכנות לינארי.
אני אחזור שוב על מה שכתוב בשאלה - זה לא קשור לזרימה. זה קשור לחתך מינימלי.
להסתכל על זה מנקודת מבט של זרימה ולא של חתך לא יעזור יותר מדי.
אדם
