סמינר במדעי המחשב 1 ( 236801 )
אלגוריתמים ״פשוטים ״
(עשור לכנס SOSA – Symposium of Simplicity in Algorithms )
מרצה :
ד״ר דוד וייץ
שעות הרצאה :
ג׳ 10:30-12:30
דרישות קדם :
אלגוריתמים 1 או קורס מקביל
הסתברות 1 או קורס מקביל
תאור הקורס
הסמינר יעסוק בתוצאות אלגוריתמיות אלגנטיות במיו חד: מאמרים שבהם רעיון פשוט, חד,
ולעיתים מפתיע מוביל לתוצאה חזקה . נתמקד במאמרים ברוח הכנס SOSA . זהו כנס תאורטי
חדש יחסית , המציין השנה עשור, ושם לעצמו למטרה להציג תוצאות מרכזיות באלגוריתמים
באופן נקי, נגיש ופשוט רעיונית. במהלך הסמינר ניחשף למבחר מודלים ורעיונות מהתאוריה
המודרנית של אלגוריתמים, ונטעם מן השפה, הטכניקות והאסתטיקה של מחקר אלגוריתמי
עכשווי .
במהלך הסמינר נפגוש אלגוריתמים הפועלים תחת מגבלות שונות, ועונים על שאלות כגון :
•
כיצד מחשבים כאשר הזיכרון, התקשורת או זמן הריצה מוגבלים מאוד?
•
כיצד מתחזקים פתרון כאשר הקלט משתנה לאורך זמן?
•
כיצד מקבלים החלטות כשמידע מגיע אונליין?
•
כיצד משיגים קירובים טובים לבעיות קשות?
דרך שאלות אלו ניגע, בין היתר, באלגוריתמים דינמיים, מקוונים, מבוזרים, מקביליים,
תת־לינאריים , אלגוריתמי Streaming , בדיקת תכונות וקירוב .
אופי הסמינר
הסמינר בעל אופי תאורטי ודורש בגרות מתמטית. הוא מיועד לסטודנטים שנהנים מהוכחות
אלגנטיות, טריקים אלגוריתמיים, ותוצאות שבהן רעיון נכון אחד מחליף טכניקה כבדה. נדרשת
נינוחות עם אלגוריתמים והסתברות; חזרה על נושאים אלו לפני הסמינר תועיל למשתתפים .
כמ ה מההרצאות הראשונות יינתנו על ידי המרצה, שייתן רקע על התחום ועל אופן קריאת מאמר
ובניית הרצאה אפקטיביים. (ראו גם לשונית עצו ת באתר הבית של המרצה).
דרישות הקורס
הציון הסופי ייקבע על סמך קריאת מאמר והצגתו (ביחידים), והשתתפות בהרצאות .
רשימת ספרות: תילקח ממאמרי SOSA לאורך השנים. תפורסם בהמשך, באתר הקורס .
רישום לקורס
מספר המקומות מוגבל והרישום ידני. סטודנטים המעוניינים להשתתף מתבקשים לשלוח דוא"ל
למרצה uwajcattechnion.ac.il עם פרטים אישיים, גיליון ציונים, וכמה מילים על רקע רלוונטי או
ניסיון בהצגה (למשל, תרגול), אם יש .
תוצאות למידה
בסיום הקורס הסטודנטים.ות :
1. ידעו כיצד לקרוא, לפרק ולהציג מאמרים אלגוריתמיים .
2. יכירו מודלים חישוביים שונים ותוצאות מרכזיות בהם .
3. יכירו טריקים ורעיונות נפוצים בתכן וניתוח אלגוריתמים מעבר לנלמד בקורסי היסוד .
4. יתנסו בבניית הרצאה תאורטית ברורה סביב רעיון מתמטי מרכזי .