נקודות זכות באוניברסיטה העברית: 3

תואר: בוגר

היחידה האקדמית שאחראית על הקורס: מדעי המחשב

סמסטר: סמסטר ב'

שפת ההוראה: עברית

קמפוס: קרית א"י ספרא

מורה אחראי על הקורס (רכז): פרופ יהושע שגיב

דוא"ל של המורה האחראי על הקורס: shukis@savion.huji.ac.il

שעות קבלה של רכז הקורס: בתיאום מראש

מורי הקורס:
פרופ יהושע שגיב

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

מטרות הקורס:
NA

תוצרי למידה :
בסיומו של קורס זה, סטודנטים יהיו מסוגלים:
NA

דרישות נוכחות (%):
0

שיטת ההוראה בקורס: הרצאה + תרגול

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

חומר חובה לקריאה:
NA

חומר לקריאה נוספת:
יינתנו מאמרים

הערכת הקורס - הרכב הציון הסופי :
מבחן מסכם בכתב/בחינה בעל פה 100 %
הרצאה0 %
השתתפות 0 %
הגשת עבודה 0 %
הגשת תרגילים 0 %
הגשת דו"חות 0 %
פרויקט מחקר 0 %
בחנים 0 %
אחר 0 %

מידע נוסף / הערות:
NA