מועדון מתמטי ביום שלישי 3.11.2015 בשעה 12:10 מרצה: אור דונקלמן (חיפה) נושא: חיתוך יעיל בבעיות שריג
בהרצאה זו נראה כי ישנן מספר רב של בעיות
שניתנות להצגה בצורת שריג, עובדה המאפשרת
לפתור אותן תוך שימוש באלגוריתם חדש הנקרא חיתוך, אשר מאפשר המרה בין סיבוכיות זמן וזכרון (ומנצח את כל האלגוריתמים הקודמים לכך). דוגמא טיפוסית לבעיה היא מציאת המפתח של מערכת הצפנה המורכבת משרשור של r מערכות הצפנה סימטריות בלתי תלויות בעלות r מפתחות בלתי תלויים בני n-ביט כל אחד.
עבודות קודמות הראו כי אם האלגוריתם איננו רשאי לטעות, עבור T זמן ריצה ו-M זכרון, חייב להתקיים TM = 2^{rn}, ואם לאלגוריתם מותר “לפספס” את התשובה הנכונה (בסיוכי נמוך) אזי יחס ההמרה מקיים TM = 2^{3r/4 n}. השיטה החדשה שלנו מציגה את האלגוריתם הראשון שאיננו טועה מתחת לעקומת ההמרה הנ”ל (לדוגמא, עבור r=7, האלגוריתם שלנו דורש T = 2^{4n} ו-M = 2^n). יחס השיפור הולך וגדל עם r, ואנו יכולים לשלב בין השיטה החדשה והשיטות הקודמות כדי להציע פתרונות יעילים יותר גם במקרה שלאלגוריתם מותר “לפספס” את הפתרון הנכון.
יתר על כן, מכיוון שבעיות שריג הן נפוצות
מאוד בתחומים רבים, אנחנו מראים כיצד
להשתמש באלגוריתם לצורך פתרון בעיות
קומבינטוריות קשות עם סיבוכיות זמן או
זכרון (או גם וגם), כגון בעית ה-knapsack ומציאת הפתרון הקצר ביותר של קוביה הונגרית.
זוהי עבודה משותפת עם איתי דינור, נתן קלר ועדי שמיר
