אלגוריתמים PDF
Document Details
Uploaded by JovialFlashback
Tags
Summary
מסמך זה מכיל חומר לימוד בנושא אלגוריתמים, כולל נושאים כמו אלגוריתמים חמדניים, תכנון דינמי, אלגוריתמים מבוססי סריקה, ותכנון מערכות. המסמך מכיל הסברים והגדרות. המסמך מועבר ללא מידע נוסף.
Full Transcript
אלגוריתמים 3...................................................................................................................................................................... 1 .1הכפלת פולינומים 3...............................................................................................
אלגוריתמים 3...................................................................................................................................................................... 1 .1הכפלת פולינומים 3....................................................................................................................................................... הגדרות ופעולות בסיסיות של פולינום3..................................................................................................................... אלגוריתם קרטסובה (הפרד ומשול) 5.......................................................................................................................... אלגוריתם –FFTניסיון ראשון5................................................................................................................................... תכונת הנגדיות החלשה6............................................................................................................................................. תכונת הנגדיות החזקה 7.............................................................................................................................................. שורשי היחידה מסדר 8............................................................................................................................................. n אלגוריתם 𝑇𝐹𝐹 9.......................................................................................................................................................... הכללת האלגוריתם 10.................................................................................................................................................. שימושים של האלגוריתם 𝑻𝑭𝑭10............................................................................................................................... .2תכנון דינמי 12............................................................................................................................................................... על השיטה12................................................................................................................................................................ .1מספרי פיבונאצ'י 12................................................................................................................................................. 13.....................................................................................Maximum Independent Sub-sequence in an Array.2 14.............................................................................................................................Chain Matrix Multiplication.3 16................................................................................................................... Longest Common Subsequence.4 .5בעיית תרמיל הגב בשלמים18................................................................................................................................. .6קבוצה בלתי תלויה גדולה ביותר בעץ 19................................................................................................................ .7תת סדרה עולה ארוכה ביותר (דוגמה להמרת הבעיה בבעיה אחרת)20................................................................ .8בעיית הסטודנטים (דוגמה לשימוש בחישוב מקדים)20......................................................................................... .9משחק סכום 22.................................................................................................................................................... 0 .3אלגוריתמים חמדניים – קוד הופמן 23........................................................................................................................ מבוא23......................................................................................................................................................................... קידודים 23.................................................................................................................................................................... מציאת קידוד תחילי אופטימלי 24............................................................................................................................... האלגוריתם של הופמן 24............................................................................................................................................. הוכחת נכונות 25.......................................................................................................................................................... הוכחת תכונת הבחירה החמדנית26............................................................................................................................ הוכחת תכונת תת המבנה האופטימלי27.................................................................................................................... בעיית בחירת הפעילויות 28......................................................................................................................................... בעיית תרמיל הגב בשברים29...................................................................................................................................... .4עץ פורש מינימום – 𝑆𝑇𝑀30........................................................................................................................................ עץ פורש מינימום – הגדרה והצגת הבעיה 30............................................................................................................. למה - 1תכונת הבחירה החמדנית 30.......................................................................................................................... הוכחת תכונת הבחירה החמדנית31............................................................................................................................ כיווץ קשתות ואלגוריתם גנרי32................................................................................................................................. הוכחת תכונת תת המבנה האופטימלי33.................................................................................................................... האלגוריתם של פרים34............................................................................................................................................... האלגוריתם של קרוסקל 36.......................................................................................................................................... .5אלגוריתם סריקה לעומק 𝑆𝐹𝐷 ושימושיו 39............................................................................................................... הצגת האלגוריתם 39.................................................................................................................................................... טענות שימושיות40..................................................................................................................................................... שימושים 41.................................................................................................................................................................. .6מסלולים קצרים בגרף46.............................................................................................................................................. מבוא46......................................................................................................................................................................... SSSPבמקרה הלא הממושקל – אלגוריתם 𝑆𝐹𝐵48................................................................................................... SSSPבמקרה הממושקל 52......................................................................................................................................... 63........................................................................................................................................................................APSP תקציר67....................................................................................................................................................................... .7כפל מטריצות מהיר ושימושים 68................................................................................................................................ מבוא לכפל מטריצות מהיר 68..................................................................................................................................... קשר בין גרפים לכפל מטריצות 69............................................................................................................................... בעיה – 1הסגור טרנזיטיבי 69..................................................................................................................................... בעיה - 2בעיית 𝑆𝑃𝑆𝐴 עבור גרפים לא מכוונים ולא ממושקלים 72.......................................................................... בעיה 𝐵𝑀𝑀 - 3קומבינטורי וזיהוי משולשים 76........................................................................................................ .8קל כבד 81...................................................................................................................................................................... זיהוי משולשים 81........................................................................................................................................................ מרחק האמינג /ספירת התאמות עבור א"ב כללי 83.................................................................................................. אלגוריתם משולב85..................................................................................................................................................... .9רשתות זרימה 86........................................................................................................................................................... הגדרות ותכונות בסיסיות 86....................................................................................................................................... בעיית זרימת מקסימום 88........................................................................................................................................... הרשת השיורית88........................................................................................................................................................ שיטת פורד פלקרסון88................................................................................................................................................ דוגמת הרצה89............................................................................................................................................................. זמן ריצה90................................................................................................................................................................... הוכחת נכונות האלגוריתם 91...................................................................................................................................... למה 94..................................................................................................................................................................... 10 השיפור של אדמונדס קארפ 95.................................................................................................................................... השיפור של דיניץ 97..................................................................................................................................................... רדוקציות100................................................................................................................................................................ .10אלגוריתמים הסתברותיים 105................................................................................................................................... מבוא105....................................................................................................................................................................... וידוא כפל מטריצות (מונטה – קרלו)106.................................................................................................................... מיון מהיר (לאס – וגאס) 109....................................................................................................................................... בעיית העסקת המזכירה 113........................................................................................................................................ .11שבירת סימטריה 124................................................................................................................................................... מבוא -בעיית זכות הדיבור 124................................................................................................................................... המודל המבוזר המקומי /חישוב מבוזר125................................................................................................................ בעיית הצביעה 126....................................................................................................................................................... אלגוריתמים 1 .1הכפלת פולינומים הגדרות ופעולות בסיסיות של פולינום הגדרה: פולינום הוא כל ביטוי מהצורה: 𝑛−1 𝑖 𝑥 𝑖𝑎 ∑ = )𝑥(𝐴 𝑖=0 פולינום זה הוא מדרגה 𝑛 − 1והוא חסום 𝑘 לכל 𝑛 ≥ 𝑘 פעולות על פולינומים: .3חישוב ערך .2כפל .1חיבור וחיסור בהינתן פולינום )𝑥(𝐴 ו,𝑥0 - )𝑥(𝐵 ∙ )𝑥(𝐴 = )𝑥(𝐶 )𝑥(𝐵 𝐶(𝑥) = 𝐴(𝑥) ± 𝑛+𝑚−2 𝑖 𝑛−1 נרצה לדעת לחשב את 𝑖 𝑥 𝑖𝑐 ∑ = 𝑗𝑐𝑖 = ∑ 𝑎𝑗 𝑏𝑖− 𝑖 𝑥 𝑖𝑐 ∑ = 𝑖𝑏 𝑐𝑖 = 𝑎𝑖 ± ) 𝐴(𝑥0 𝑖=0 𝑗=0 𝑖=0 ייצוגים א.מקדמים: נשתמש במערך בגודל nונשמור בתאיו את המקדמים המתאימים ) (𝑎0 , 𝑎1 , … 𝑎𝑛−1 נכונות :יש פונקציה חח"ע ועל בין קבוצת הפולינומים לבין קבוצת ייצוגים זו ולכן שיטה זו טובה. ב".נקודות": בהינתן 𝑛 ערכים שונים 𝑥0 , 𝑥1 , …. 𝑥𝑛−1נייצג את Aבעזרת הנקודות ) (𝑥0 , 𝑦0 ), … (𝑥𝑛−1 , 𝑦𝑛−1 כאשר: 𝑛−1 𝑖𝑗𝑥 𝑗𝑎 ∑ = ) 𝑖𝑥(𝐴 = 𝑖𝑦 ∀0 ≤ 𝑖 ≤ 𝑛 − 1: 𝑗=0 הוכחת נכונות :בליניארית למדנו כי למשוואה 𝑣 = 𝑥𝐴 יש פתרון יחיד ↔ Aהפיכה אם ערכי Xשונים ,מטריצת ונדרמונד Vהפיכה ולכן יש פתרון יחיד למשוואה ⃗𝑎𝑉 = ⃗𝑦 וא"כ יש לנו פונקצייה חח"ע בין yלבין aוהייצוג טוב. מעבר בין ייצוגים מעבר מנקודות למקדמים -נוסחת לגרנז' מעבר ממקדמים לנקודות פעולה -אינטרפולציה: פעולה :בעזרת nפעולות חישוב ערך על 𝑛−1 𝑥0 , 𝑥1 , …. 𝑥𝑛−1 ) 𝑗𝑥 ∏𝑗≠𝑖(𝑥 − ∙ 𝑖𝑦 ∑ = )𝑥(𝐴 ) 𝑗𝑥 ∏𝑗≠𝑖(𝑥𝑖 − 𝑖=0 סיבוכיות :מעבר משיטת ייצוג אחת לשנייה ייקח ) 𝑂(𝑛2 𝑛−1 )𝑥(𝑀 )𝑥( 𝑘𝑀 = ) 𝑗𝑥 𝑀(𝑥) = ∏(𝑥 − 𝑥𝑗 ) → 𝑀𝑘 (𝑥) = ∏(𝑥 − ∙ 𝑖𝑦 ∑ = )𝑥(𝐴 → 𝑘𝑥 𝑥 − ) 𝑘𝑥( 𝑘𝑀 𝑘≠𝑗 𝑖=0 ביצוע פעולות חיבור: אם )𝑥(𝐵 𝐴(𝑥),מיוצגים ע"י 𝒏 ערכי xזהים ,ניעזר בעובדה ש 𝐶(𝑥) = 𝐴(𝑥) + 𝐵(𝑥) - ולכן ניצור ייצוג(𝑥0 , 𝐶(𝑥0 )), … (𝑥𝑛−1 , 𝐶(𝑥𝑛−1 )) : כפל: אם )𝑥(𝐵 𝐴(𝑥),מיוצגים ע"י 𝟐 𝟐𝒏 −ערכי xזהים ,ניעזר בעובדה ש 𝐶(𝑥) = 𝐴(𝑥) ∙ 𝐵(𝑥) - ולכן ניצור ייצוג(𝑥0 , 𝐶(𝑥0 )), … (𝑥𝟐𝒏−𝟐 , 𝐶(𝑥𝟐𝒏−𝟐 )) : חישוב ערך: אם אנו רוצים לחשב את הערך של פולינום באחד מהערכים ,𝑥0 , 𝑥1 , …. 𝑥𝑛−1אזי נשתמש במנגנון חיפוש ונמצא אותו נקודות כלליות מקדמים אותן נקודות ) 𝑂(𝑛2 )𝑛(𝑂 )𝑛(𝑂 חיבור ) 𝑂(𝑛2 )𝑛(𝑂 ) 𝑂(𝑛2 כפל ) 𝑂(𝑛2 )𝑛𝑔𝑜𝑙(𝑂 )𝑛(𝑂 חישוב ערך אלגוריתם קרטסובה (הפרד ומשול) טענה :אם דרגת הפולינום היא חזקה של ,2ניתן להציגו כך: 𝑛 𝑛 −1 −1 2 2 𝑛 )𝑥(𝑝 𝐴(𝑥) = 𝑞(𝑥) + 𝑥 2 [𝑞(𝑥) = ∑ 𝑎𝑖 𝑥 𝑖 , ] 𝑖 𝑥 𝑖𝑝(𝑥) = ∑ 𝑎𝑛+ 2 𝑖=0 𝑖=0 𝑛 𝑛 𝑛 ))𝑥(𝑠)𝑥(𝑝( 𝑛 𝑥 𝐴(𝑥)𝐵(𝑥) = (𝑞(𝑥) + 𝑥 2 𝑝(𝑥)) (𝑟(𝑥) + 𝑥 2 𝑠(𝑥)) = 𝑞(𝑥)𝑟(𝑥) + 𝑥 2 (𝑝(𝑥)𝑟(𝑥) + 𝑞(𝑥)𝑠(𝑥)) + נגדיר𝐩𝟏 (𝒙) = 𝑞(𝑥)𝑟(𝑥), 𝒑𝟐 (𝒙) = 𝑝(𝑥)𝑠(𝑥), 𝒑𝟑 (𝒙) = (𝑞(𝑥) + 𝑝(𝑥))(𝑟(𝑥) + 𝑠(𝑥)) : כעת מתקייםp3 (x) − p1 (𝑥) − 𝑝2 (𝑥) = 𝑝(𝑥)𝑟(𝑥) + 𝑞(𝑥)𝑠(𝑥) : 𝒏 )𝒙( 𝟐𝒑 𝒏𝒙 𝑨(𝒙)𝑩(𝒙) = 𝒑𝟏 (𝒙) + 𝒙𝟐 (𝐩𝟑 (𝐱) − 𝐩𝟏 (𝒙) − 𝒑𝟐 (𝒙)) + מסקנה :ע"י חישוב שלושת הפולינומים האלה והשקעה של עוד )𝑛(𝑂 זמן בהזזת מקדמים ,חיבור וחיסור ניתן לחשב את הכפל של שני פולינומים מדרגה nבצורה רקורסיבית: 𝑛 ) 𝟑 𝟐𝐠𝐨𝐥𝒏(𝑶 = )𝑛(𝑂 𝑇(𝑛) = 3𝑇 ( ) + 2 אלגוריתם –FFTניסיון ראשון המטרה :לחשב את Aעם דרגה חסומה ,nעם nערכי .X 𝑛.2חזקה של .2 הנחות מקלות 𝑛.1 :ערכים שונים כלי מתמטי 𝑛 𝑛 −1 −1 2 𝐴𝑒𝑣𝑒𝑛 = ∑𝑖=0 𝑎2𝑖 𝑥 𝑖 , 2 𝐴𝑜𝑑𝑑 = ∑𝑖=0 𝑖 𝑥 𝑎2𝑖+1 טענה 𝐴(𝑥) = 𝐴𝑒𝑣𝑒𝑛 (𝑥 2 ) + 𝒙 ∙ 𝐴𝑜𝑑𝑑 (𝑥 2 ) :כאשר: 𝑛 ,וזה חצי מהדרגה החסומה של 𝐴. 2 שים לב :הפולינומים 𝑑𝑑𝑜𝐴 𝐴𝑒𝑣𝑒𝑛 ,הן מדרגה חסומה רעיון: 𝑥0𝟐 , 𝑥1𝟐 , …. 𝑥𝑛−1 𝟐 שלב א -עבור ערכי 𝑥0 , 𝑥1 , …. 𝑥𝑛−1שונים נחשב את 𝑑𝑑𝑜𝐴 𝐴𝑒𝑣𝑒𝑛 ,עבור שלב ב -לאחר מכן נחשב את Aעבור 𝑥0 , 𝑥1 , …. 𝑥𝑛−1על פי הנוסחה שפיתחנו. 𝑛 )𝒏𝒈𝒐𝒍𝒏(𝑶 → )𝑛(𝑂 𝑇(𝑛) = 2𝑇 (2 ) + סיבוכיות: בעיה :קריאה רקורסיבית צריכה לשמור על המבנה של הבעיה הראשונית. בבעיה המקורית אנו מעוניינים לחשב את ( Aהחסום מדרגה 𝑛) 𝑛 ,ערכי xשונים. בבעיה הרקורסיבית יש 2הבדלים: 𝑥0𝟐 , 𝑥1𝟐 , …. 𝑥𝑛−1והם לא בטוח שונים (וזאת על אף ש 𝑥0 , 𝑥1 , …. 𝑥𝑛−1-שונים). 𝟐 א.אנו מחשבים את ב.אנו מחשבים 𝑛 ערכים שונים עם פולינום החסום מדרגה .𝑛/2 תכונת הנגדיות החלשה הגדרה :יהי 𝑘 חזקה של .2 לסדרת ערכי ה 𝑥0 , 𝑥1 , …. 𝑥𝑘−1 x-יש את תכונת הנגדיות החלשה אם אחד מהתנאים הבאים מתקיים: 𝑘 𝑗𝑥( ∀ 0 ≤ 𝑗 ≤ 2 − 1: 𝑥𝑘+𝑗 = −חצי ראשון שווה למינוס החצי השני) .2 𝑘 = 1.1 2 {𝑥0𝟐 , 𝑥1𝟐 , …. 𝑥𝑘𝟐 } = {𝑥𝑘𝟐 , 𝑥𝑘𝟐 , …. 𝑥𝑘−1 𝟐 אבחנה :בקבוצה זו מתקיים } −1 +1 2 2 2 מטרה :לחשב את Aמדרגה חסומה nב n-ערכי xשמקיימים את תכונת הנגדיות החלשה. רעיון: עבור ערכי 𝑥0 , 𝑥1 , …. 𝑥𝑛−1המקיימים נגדיות חלשה: שלב א -נחשב את 𝑛𝑒𝑣𝑒𝐴 𝐴𝑜𝑑𝑑 ,עבור 𝑥0𝟐 , 𝑥1𝟐 , …. 𝑥𝑛𝟐−1 2 𝑛 שלב ב – לכל 0 ≤ 𝑗 ≤ 2 − 1נפעל כך: ) 𝐴(𝑥𝑖 ) = 𝐴𝑒𝑣𝑒𝑛 (𝑥𝑖2 ) + 𝒙𝑖 ∙ 𝐴𝑜𝑑𝑑 (𝑥𝑖2 ) ⏟ 𝐴(−𝑥𝑖 ) = 𝐴𝑒𝑣𝑒𝑛 (𝑥𝑖2 ) − 𝒙𝑖 ∙ 𝐴𝑜𝑑𝑑 (𝑥𝑖2 = ) 𝑖𝐴 (𝑥𝑛+ 2 נגדיות 𝑛 )𝒏𝒈𝒐𝒍𝒏(𝒐 → )𝑛(𝑂 𝑇(𝑛) = 2𝑇 (2 ) + סיבוכיות: בעיה :קריאה רקורסיבית צריכה לשמור על המבנה של הבעיה הראשונית. בבעיה המקורית אנו מעוניינים לחשב את ( Aהחסום מדרגה 𝑛) 𝑛 ,ערכי xהמקיימים נגדיות חלשה. בבעיה הרקורסיבית אנו מחשבים ערכים 𝑥0𝟐 , 𝑥1𝟐 , …. 𝑥𝑛𝟐−1שלא בהכרח מקיימים נגדיות חלשה. 2 תכונת הנגדיות החזקה הגדרה :יהי 𝑘 חזקה של .2 לסדרת ערכי ה 𝑥0 , 𝑥1 , …. 𝑥𝑘−1 x-יש את תכונת הנגדיות החזקה אם אחד מהתנאים הבאים מתקיים: 𝑘 = 1.1 𝑥0 , 𝑥1 , …. 𝑥𝑘−1.2מקיימת נגדיות החלשה וגם 𝑥0𝟐 , 𝑥1𝟐 , …. 𝑥𝑛𝟐−1מקיימת נגדיות החזקה (רקורסיבי). 2 מטרה :לחשב את Aמדרגה חסומה nב n-ערכי xשמקיימים את תכונת הנגדיות החזקה. רעיון: עבור ערכי 𝑥0 , 𝑥1 , …. 𝑥𝑛−1המקיימים נגדיות חזקה: שלב א -נחשב את 𝑛𝑒𝑣𝑒𝐴 𝐴𝑜𝑑𝑑 ,עבור 𝑥0𝟐 , 𝑥1𝟐 , …. 𝑥𝑛𝟐−1 2 𝑛 שלב ב – לכל 0 ≤ 𝑖 ≤ 2 − 1נפעל כך: ) 𝐴(𝑥𝑖 ) = 𝐴𝑒𝑣𝑒𝑛 (𝑥𝑖2 ) + 𝒙𝑖 ∙ 𝐴𝑜𝑑𝑑 (𝑥𝑖2 ) ⏟ 𝐴(−𝑥𝑖 ) = 𝐴𝑒𝑣𝑒𝑛 (𝑥𝑖2 ) − 𝒙𝑖 ∙ 𝐴𝑜𝑑𝑑 (𝑥𝑖2 = ) 𝑖𝐴 (𝑥𝑛+ 2 נגדיות 𝑛 )𝒏𝒈𝒐𝒍𝒏(𝑶 → )𝑛(𝑂 𝑇(𝑛) = 2𝑇 ( ) + 2 סיבוכיות: אם כן ראינו כי עבור האלגוריתם המשופר אנו זקוקים ל n-ערכי xשמקיימים את תכונת הנגדיות החזקה ובזה נתעסק כעת. שורשי היחידה מסדר n הצגה𝑧 = 𝑎 + 𝑖 ∙ 𝑏 = 𝑟(𝑐𝑜𝑠𝜗 + 𝑖 ∙ 𝑠𝑖𝑛𝜗) = : 𝜗𝑖 𝑒 ∙ 𝑟 = 𝜗𝑠𝑖𝑐𝑟 כפל מרוכבים𝑧1 𝑧2 = 𝑟1 𝑟2 𝑐𝑖𝑠(𝜃1 + 𝜃2 ) : משפט :מספר ωנקרא שורש היחידה המרוכב מסדר nאם ,𝜔𝑛 = 1ולכן לכל nמתקיים: 𝝅𝟐 𝝅𝟐 𝒏 ∙𝒊𝒆 = 𝑛𝜔 = 𝜽( ) 𝒏 למה :3 לכל 0 ≤ 𝑘 ≤ 𝑛 − 1מתקיים 𝒌) 𝒏𝝎( הוא שורה יחידה מסדר 𝑛. 𝑘𝑛 𝝅𝟐 ) 𝒏 ∙𝒊𝒆( = 𝑛) 𝑘) 𝑛𝜔(( הוכחה= (𝒆𝒊∙𝟐𝝅 )𝑘 = (𝒆𝒊∙𝟎 )𝑘 = 1𝑘 = 1 : למה 4 ) 𝜔0𝑛 , 𝜔1𝑛 , … , 𝜔(𝑛−1מקיימים את תכונת הנגדיות החלשה. 𝑛 שורשי היחידה מסדר n 𝑛 𝑛 הוכחה :יהי ,𝑛 > 1חזקה של .2נוכיח כי לכל 0 ≤ 𝑘 ≤ 2 − 1מתקיים:𝜔𝑛 2 +𝑘 = −𝜔𝑘𝑛 : 𝒏 𝑛 𝑛 ∙𝝅𝟐 ∙𝒊 𝟐 𝑘𝜔𝑛 2 + = 𝑛𝑘𝜔 𝜔𝑛 2 = 𝑛𝑘𝜔 𝒏 𝒆 𝑛𝑘𝜔= 𝒆𝒊∙𝝅 𝜔𝑘𝑛 = −1 ∙ 𝜔𝑘𝑛 = − למה – 5למת החצייה 𝑛 𝑛 שורשי היחידה מסדר .2 2 ) 𝜔0𝑛 , 𝜔1𝑛 , … , 𝜔(𝑛−1הם בדיוק 𝑛 יהי ,𝑛 > 1חזקה של .2הריבועים של 𝑛 הוכחה :נשים לב כי לכל 0 ≤ 𝑘 ≤ 2 − 1מתקיים: 𝑘 𝒌𝝅𝟐 𝝅𝟐 𝒌𝟐𝝅𝟐 𝒏 ∙𝒊 𝒏 ∙𝒊 𝑘 = ((𝜔𝑛 )𝑘 )2 𝒏 ∙𝒊𝒆 = 𝟐 𝒆 = ) 𝟐 𝒆( ) 𝑛𝜔( = 2 𝝅𝟐 𝑘 𝝅𝟐 𝒏 ∙𝒊 𝒏 ∙𝒊 𝑛 𝑛 𝒆( שורש יחידה מסדר . 2 𝟐 𝒆 הוא שורש יחידה מסדר ,ולכן על פי למה 3גם ) 2 𝟐 𝑛 ) 𝜔0𝑛 , 𝜔1𝑛 , … , 𝜔(𝑛−1נותן את כל שורשי היחידה מסדר 2והחצי השני 𝑛 החצי הראשון של סדרת הריבועים שלך (לפי תכונת הנגדיות החלשה) נותן בדיוק את אותם השורשים. למה 6 יהי ,𝑛 > 1חזקה של .2סדרת nשורשי היחידה מסדר nמקיימת את תכונת הנגדיות החזקה. הוכחה :באינדוקציה.נניח נכונות עד 𝑛 ונוכיח עבור 𝑛.לפי למה 𝑘 4שורשי היחידה מסדר nמקיימים נגדיות חלשה. 𝑛 𝑛 לפי למה ,5ריבועי המחצית הראשונה של השורשים הם 2שורשי היחידה מסדר 2ולפי הנחת האינדוקציה הם מקיימים נגדיות חזקה.אם כן nהשורשים שלנו מקיימים את תכונת נגדיות חזקה. אבחנה n :שורשי היחידה מסדר nשונים זה מזה. אלגוריתם 𝑇𝐹𝐹 סיכום :אם המטריצה היא מטריצה ונדרמונדה שמוגדרת ע"י nמספרים שמקיימים את תכונת הנגדיות החזקה ,אז ניתן לבצע את המכפלה ⃗𝑎 ∙ 𝑇𝐹𝐹 = ⃗𝑦 בזמן )𝒏𝒈𝒐𝒍𝒏(𝑶 אינטרפולציה בחזרה לעיל ראינו כי עבור nערכים שונים המטריצה ונדרמונד הפיכה ולכן קיימת .𝐹𝐹𝑇 −1 נשים לב כי 𝐹𝐹𝑇 −1היא גם מטריצת הסדרה עבור ונדרמונד )−(𝑛−1 𝜔0𝑛 , 𝜔−1ולכן ניתן לחשב את 𝑛𝜔 𝑛 , … , המקדמים של הפולינום Cבאופן הבא: ⃗𝑦 ∙ 𝑐⃗ = 𝐹𝐹𝑇 −1 סיבוכיות( 𝑶(𝒏𝒍𝒐𝒈𝒏) :לפי הטענה הקודמת) תרשים סיכום דגשים n.1הוא חזקה של – 2במידה והפולינום מדרגה נמוכה יותר – ניתן להוסיף לו מקדמי .0 .2ערכי Xחייבים לקיים ניגודיות חזקה. הכללת האלגוריתם ( 𝐴(𝑥) = ∑𝑛−1נניח בה"כ .)m < n 𝑖 𝑚−1 𝑖 קלט𝑖=0 𝑎𝑖 𝑥 , 𝐵(𝑥) = ∑𝑖=0 𝑏𝑖 𝑥 : 𝑛 נחלק את )𝑥(𝐴 לפולינומים קטנים יותר ,כל אחד בגודל 𝑚.למעשה עלינו לחלק את 𝑚 בלוקים כך: 𝑛 אלגוריתם זה צריך לבצע 𝑚 פעולות של כפל פולינומים מדרגה + mסכימה של התוצאות: 𝑛 )𝒎𝒈𝒐𝒍𝒏(𝑶 = )𝑛(𝑂 𝑂 ( 𝑚𝑙𝑜𝑔𝑚) + 𝑚 שימושים של האלגוריתם 𝑻𝑭𝑭 .1בעיית 𝑆𝑈𝑀 − 3 קלט :מערך של nמספרים𝐴[𝑛] = [𝑎0 , 𝑎1 , … 𝑎𝑛 ] : פלט :כן – אם קיימים שלושה מספרים 𝐴 ∈ 𝑘𝑎 𝑎𝑖 , 𝑎𝑗 ,כך שמתקיים.𝑎𝑖 + 𝑎𝑗 = 𝑎𝑘 :אחרת -לא. הנחה מקילה :כל האיברים במערך Aהם מספרים שלמים מהתחום ] .[1,10𝑛1.5 הצגת האלגוריתם: שלב א – נקודד את המערך Aלאלגוריתם מדרגה חסומה 10𝑛1.5בצורה הבאה: המקדם 𝑎𝑖 = 1אם 𝐴 ∈ 𝑖 והמקדם 𝑎𝑖 = 0אם 𝐴 ∉ 𝑖(.סיבוכיות )𝑛(𝑂) שלב ב – נבצע כפל של האלגוריתם בעצמו ע"י FFTמדרגה חסומה (.𝑛1.5סיבוכיות )𝑛𝑔𝑜𝑙 )𝑂(𝑛1.5 שלב ג – נעבור על פולינום המכפלה ונאתר כל ביטוי 𝑘 𝑥 𝑘𝑐 עבורו :𝑐𝑘 ≥ 2 במידה וקיימת חזקה 𝑘 גם בפולינום המקורי Aנחזיר כן.אחרת ,נחזיר לא(.סיבוכיות ) )𝑂(𝑛1.5 סיבוכיות האלגוריתם𝑂(𝑛1.5 𝑙𝑜𝑔𝑛) : נכונות :עקב התכונה המתמטית ,𝑥 𝑖 𝑥 𝑗 = 𝑥 𝑖+𝑗 :כשאנחנו כופלים את הפולינום שמייצג את המערך בעצמו ,פולינום המכפלה מכיל סכומים של איברי המערך.כל ביטוי שהמקדם שלו גדול מ 2-מכילה איבר שמתקבל ע"י שני איברים שונים במערך )𝒋 ≠ 𝒊(. 2 דוגמה𝐴(𝑥) = 𝑥 2 + 𝑥 5 + 𝑥 7 → (𝐴(𝑥)) = 𝑥 2 + 2𝑥 7 + 2𝑥 9 + 𝑥 10 + 2𝑥 12 + 𝑥 14 : כעת כל שנשאר לאלגוריתם לעשות הוא לבדוק בפולינום שמייצג את המערך המקורי שאכן האיבר קיים במערך המקורי ולא נסכם ע”י שני זוגות שונים של איברים. .2מרחק האמינג -אלגוריתם פישר-פטרסון הגדרה :יהיו A,Bמחרוזות באורך זהה 𝑛 – מרחק ההאמינג שלהן הוא: |}]𝑖[𝐵 ≠ ]𝐼[𝐴 | 𝑖{| = )𝐵 𝐻𝐷(𝐴, בעיית התאמת תבניות עם מרחק האמינג קלט :מחרוזת ]𝑛 … 𝑇[1באורך "– nטקסט" ומחרוזת ]𝑚 … 𝑃[1באורך 𝑛 ≤ 𝑚 – "תבנית". פלט :לכל היסט 𝑚 0 ≤ 𝑖 ≤ 𝑛 −את מרחק האמינג של )]𝑚 𝐻𝐷(𝑃, 𝑇[𝑖 + 1, … 𝑖 + הנחה מקילה :המחרוזות הן מעל א"ב בינארי }.{0,1 אינטואיציה נתייחס אל המחרוזות כאל פולינומים מדרגה 𝑚 𝑛,ונבצע פעולת כפל ארוך על 𝑅𝑃𝑇: )]𝑚 (𝑃, 𝑇[𝑛 − 𝑖, … , 𝑛 − 𝑖 + אבחנה :1העמודה 𝑛 ≤ 𝑖 ≤ 𝑚 מימין מתארת למעשה את ההיסט 𝑗𝑏 = 𝑖𝑎 1 { = 𝑗𝑏 ∗ 𝑖𝑎 מסקנה :נגדיר 𝑗𝑏 ≠ 𝑖𝑎 0 כעת סכום כל עמודה יהיה מספר ההתאמות בהיסט אותו היא מייצגת ואז 𝑚𝑢𝑠 .𝐻𝐷 = 𝑚 − זהירות :תוצאת הכפל הארוך איננה מייצגת פעולת * אלא פעולת כפל. ̅̅̅̅̅𝑇 𝑇 ∗ 𝑃𝑅 = 𝑇𝑃𝑅 + 𝑅𝑃 אבחנה :2 ̅̅̅̅̅𝑇 𝑅𝑃 0 1 𝑅𝑃𝑇 0 1 𝑅𝑃 ∗ 𝑇 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 תיאור האלגוריתם שלב א – נמיר את המחרוזות והמשלימים לפולינומים מדרגות 𝑚 𝑛,ונבצע שתי פעולות 𝑇𝐹𝐹. שלב ב – נסכום את התוצאות בכל עמודה. שלב ג – ניקח את מספר ההתאמות בכל היסט ונחסר אותו מ 𝑚-ונקבל את מרחק האמינג הרצוי. סיבוכיות𝑂(𝑛𝑙𝑜𝑔𝑚) : .2תכנון דינמי על השיטה לפיתוח אלגוריתם המבוסס על תכנון דינמי, דרוש אוסף תתי בעיות הנגזרות מן הבעיה המקורית ומקיימות את התכונות הבסיסיות הבאות: .1מספר תתי הבעיות הוא פולינומיאלי. .2אפשר לחשב בקלות מהפתרונות לתתי הבעיות את הפתרון לבעיה המקורית. .3יש סדר של תת הבעיות ,מן "הקטנה ביותר" עד "הגדולה ביותר" ויש נוסחת נסיגה קלה לחישוב. כלומר ,בעוד שפתרון המבוסס על הפרד ומשול נאיבי פותר את תת-הבעיות החופפות מספר פעמים ,פעם אחת עבור כל תת-בעיה, האלטרנטיבה שמציעה שיטת התכנון הדינמי היא פתרון של כל תת-הבעיות בזו אחר זו, כאשר פתרון כל אחת מתת-הבעיות נשמר עבור שימוש עתידי ,.מה שמייעל את סיבוכיות הזמן של האלגוריתם. .1מספרי פיבונאצ'י 𝑓0 = 0 , 𝑓1 = 1 𝑎𝑛𝑑 𝑓𝑜𝑟 𝑖 ≥ 2, 𝑓𝑖 = 𝑓𝑖−1 + 𝑓𝑖−2 הגדרה :מספרי פיבונאצ'י מוגדרים כך: פתרון דינמי איטרטיבי פתרון דינמי רקורסיבי מקום :נשמור בזיכרון את שתי הקריאות מקום :נשמור בזיכרון את הקריאות שחושבו האחרונות שחושבו במערך ].𝑀[0,1 במערך ]𝑛 .𝑀[0,.. תיאור האלגוריתם )𝑛(𝑓: תיאור האלגוריתם )𝑛(𝑓: )If (M[n]=null )If (M[n]=null )If (n=0 or n=1 )If (n=0 or n=1 M[n]=1 M[n]=1 Else: Prev_n2 = prev_n1=1 Else )for(i=2 to n )M[n]=f(n-1)+f(n-2 Curr = prev_n1 +prev_n2 זמן ריצה 𝑂(𝑛) :מקום𝑂(𝑛) : Prev_n2 = prev_n1 Prev_n1= curr זמן ריצה 𝑂(𝑛) :מקום𝑂(1) : Maximum Independent Sub-sequence in an Array.2 הגדרת הבעיה קלט :מערך ]𝑛 𝐴[1, …. ,של מספרים. פלט :תת סדרה בלתי תלויה של מספרים שסכומם מקסימלי. תזכורת :תת סדרה ) 𝑘𝑖𝑎 … (𝑎𝑖1 ,היא בלתי תלויה אם.∀1 ≤ 𝑗 ≤ 𝑘 − 1: 𝑖𝑗 < 𝑖𝑗+1 − 1 : פתרון נאיבי: נעבור על כל תתי הסדרות ( 𝑛 2ת"ס) ,ונבדוק לגבי כל ת"ס אם היא בלתי תלויה ומהו סכומה ,מה שיעלה לנו ) 𝑛.𝑂(𝑛2 פתרון דינמי זמן +מקום – )𝑛(𝑂.כעת נפרט לגבי מקום: ) 1מערך ]𝑛 𝐹[1,.. ,בו בתא ה 𝑖-יישמר הערך המקסימלי של הקריאה ה.𝑖- )2מערך ]𝑛 .𝐷[1,.. , אם ] ,𝐹[𝑖] = 𝐹[𝑖 − 1אז נסמן .𝐷[𝑖] = 1אחרת ] 𝐹[𝑖] = 𝑎𝑖 + 𝐹[𝑖 − 2ונסמן .𝐷[𝑖] = 2 כעת נסביר כיצד לשחזר את תת הסדרה: נעבור באופן רקורסיבי מהסוף להתחלה. 1. i=n אם D[i] = 2אזי: )2. while (i>0 ] 𝐹[𝑖] = 𝑎𝑖 + 𝐹[𝑖 − 2ולכן 𝑖𝑎 נכלל בתת הסדרה האופטימלית ומשם נקפוץ אל .𝑖 − 2 3. ) ]if D[i] = 2 (optimize: if 𝐹[𝑖] = 𝑎𝑖 + 𝐹[𝑖 − 2 אחרת 𝑖𝑎 לא נכלל בתת הסדרה האופטימלית, 4. 𝑖𝑎 print נתעלם ממנו ונעבור אל .𝑖 − 1 5. 𝑖 = 𝑖−2 אופטימיזציה :במקום להשתמש במערך נוסף ]𝑖[𝐷 ,ניתן להשתמש במערך ] F[iבלבד.כיצד? 6. else נבדוק ישירות בשורה 3האם: 7. 𝑖 = 𝑖−1 ]𝐹[𝑖] = 𝑎𝑖 + 𝐹[𝑖 − 2 שים לב :אם אין ברצוננו לדעת מהי ת"ס שנבחרה ,אלא רק הערך המקסימלי – די להשתמש ב 𝑂(1) -מקום משום שבדומה לפיבונאצ'י – כל פעם אנו משתמשים ב 2-הקריאות הקודמות בלבד. הוכחת נכונות באינדוקציה בסיס 𝑛 = 0 :סדרה ריקה ולכן .𝑚𝑎𝑥 = 0עבור 𝑚𝑎𝑥 = 𝑎1 ,𝑛 = 1רק אם .𝑎1 > 0 צעד :נניח נכונות עד nונוכיח כי ∗ 𝑓 = )𝑛(𝑓 (כאשר ∗ 𝑓 הוא הערך המקסימלי). נב"ש כי ∗ 𝑓 < )𝑛(𝑓 ,אזי: אם 𝑛𝑎 לא נמצא בפתרון האופטימלי ,אזי : אם 𝑛𝑎 נמצא בפתרון האופטימלי: )𝑓 ∗ > 𝑓(𝑛) ≥ 𝑓(𝑛 − 1 )𝑓 ∗ > 𝑓(𝑛) ≥ 𝑎𝑛 + 𝑓(𝑛 − 2 כלומר𝑓 ∗ > 𝑓(𝑛 − 1) , כלומר𝑓 ∗ − 𝑎𝑛 > 𝑓(𝑛 − 2) , זוהי סתירה לכך שעפ"י הנחת האינדוקציה זוהי סתירה לכך שעפ"י הנחת האינדוקציה ) 𝑓(𝑛 − 1מחזירה את הערך המקסימלי ) 𝑓(𝑛 − 2מחזירה את הערך המקסימלי לקטע ).(1,.. 𝑛 − 1 לקטע ).(1,.. 𝑛 − 2 Chain Matrix Multiplication.3 הגדרת הבעיה קלט :מערך ]𝑛 𝑃[0, …. ,של מימדי המטריצות בשרשרת ,כאשר: מס' השורות של המטריצה 𝑖𝑀 הוא 𝑃𝑖−1ומס' העמודות של המטריצה 𝑖𝑀 הוא 𝑖𝑃. פלט :סדר הכפלת המטריצות האופטימלי (מינימום פעולות חישוב). פתרון נאיבי: 𝑛4 נעבור על כל האפשרויות להכפיל nמטריצות (מספרי קטלן) ).Θ (𝑛1.5 פתרון דינמי שים לב: .1אנו ממלאים רק את המשולש העליון (.)i0 and j > 0 אם 𝑗𝑦 = 𝑖𝑥 אזי הוא חלק מת"ס ואז נמשיך להדפיס את ).𝑓(𝑖 − 1, 𝑗 − 1 3. 𝑗𝑦 = 𝑖𝑥 if אחרת, 4. 𝑖𝑥 print ת"ס זוהי אם ]𝑗 𝑀[𝑖, 𝑗] = 𝑀[𝑖 − 1,אז 5. )𝑓(𝑖 − 1, 𝑗 − 1 המקסימלית ולכן נלך אל )𝑗 .𝑓(𝑖 − 1, ) ]𝑗 6. else if( 𝑀[𝑖, 𝑗] = 𝑀[𝑖 − 1, אחרת𝑓(𝑖, 𝑗 − 1) , 7. )𝑗 𝑓(𝑖 − 1, זמן ריצה: 8. else טבלה .𝑂(𝑛𝑚) -שחזור 𝑂(𝑛 + 𝑚) - 9. )𝑓(𝑖, 𝑗 − 1 ( Hirschberg's longest common subseqenceכדאי לחפש סרטונים ביוטיוב בשביל המחשה ויזואלית) למה :יהי )𝑗 𝑓(𝑖,פתרון אופטימלי 𝑓 𝑅 (𝑖, 𝑗) ,פתרון אופטימלי של מחרוזות הפוכות ,אזי: 𝑛 𝑛 })𝑘 𝑓(𝑛, 𝑚) = max {𝑓 ( , 𝑘) + 𝑓 𝑅 ( , 𝑚 − 𝑚≤𝑘≤0 2 2 נפעל כך : 𝑛 ונמצא את ה – k * נתמקד בשורה ה – 2 האופטימלי. * נמשיך לעשות זאת באופן רקורסיבי על הרבע הימני התחתון והרבע השמאלי העליון. כך ,נמצא את המסלול של ת"ס המקסימלית. שחזור –כל פעם שעושים צעד אלכסון ,מתקיים 𝑗𝑦 = 𝑖𝑥 ונדפיס את התו. 𝑛 מקום :כל פעם שומרים רק את השורה 2ולכן זה יעלה בפועל בכל שלב }𝑚 𝑂(min {𝑛,ובסה"כ המקום יהיה ליניארי. הוכחת נכונות באינדוקציה בסיס - 𝑗 + 𝑖 = 0 :כאשר 𝑖 = 0 𝑜𝑟 𝑗 = 0ברור כי ת"ס המקסימלית היא בגודל .0 צעד :נניח נכונות עבור 𝑗 + 𝑖 < ℓונוכיח עבור 𝑗 + 𝑖 = ℓכי 𝑘 = )𝑗 ( 𝑙𝑐𝑠(𝑖,כאשר ) 𝑘𝑧 )𝑍 ∗ = (𝑧1 ,.. , נב"ש כי 𝑘 < )𝑗 ,𝑙𝑐𝑠(𝑖,אזי: אם 𝑗𝑦 ≠ 𝑖𝑥 ,אז ∗𝑘𝑍 תת רצף של 𝑗𝑌 𝑋𝑖−1 ,ושל ∗ 𝑍𝑘−1תת רצף של אם 𝑗𝑦 = 𝑖𝑥 = 𝑘𝑧 ,אז ( 𝑋𝑖 , 𝑌𝑗−1אך לא בהכרח אופטימלי) ומתקיים. ( 𝑋𝑖−1 , 𝑌𝑗−1אך לא בהכרח אופטימלי). ≥ 𝑙𝑐𝑠(𝑖, 𝑗) ≥ 𝑙𝑐𝑠(𝑖 − 1, 𝑗 − 1) + 1 ⏟𝑘+1 ≥ 𝑙𝑐𝑠(𝑖, 𝑗) ≥ 𝑙𝑐𝑠(𝑖 − 1, 𝑗 − 1) + 1 ⏟𝑘−1+1 ∗ ∗ וקיבלנו סתירה וקיבלנו סתירה. .5בעיית תרמיל הגב בשלמים הוכחות אלו נעשות באינדוקציה בדומה לדוגמאות הקודמות. פתרון תכנות דינמי: נשתמש במערך דו-ממדי מגודל 𝑛 × 𝐵.נמלא את המערך שורה אחר שורה (וזאת משום שכל תא נעזר במי שמעליו ומשמאלו). מקום :לשמירת כל הטבלה )𝑛𝐵(𝑂.אם לא נדרש שחזור הפתרון ,ניתן ב)𝐵(𝑂 תאי זיכרון ־ לשמור שתי שורות וכל פעם להשתמש רק בהם (בדומה לבעיית ת"ס מקסימלית). שחזור – נעבוד בשיטה הדומה למה שעשינו בת"ס בת"ל מקסימלית ות"ס משותפת מקסימלית. הכללת האלגוריתם (שני תיקים) .6קבוצה בלתי תלויה גדולה ביותר בעץ 𝑣𝑓 – ערכו של הקודקוד .v מונחים :קבוצה בלתי תלויה – קבוצה שאין בה אב ובן. )𝑻𝑶𝑶𝑹(𝑺𝑰𝑴 :נחשב את ערכי 𝐸 ו־ 𝐼 על גבי העץ (אם אי אפשר לגעת בעץ ,ניצור עותק שלו). אלגוריתם (א) )𝑢(𝑆𝐼𝑀 .1אתחול: (ב) )𝑡𝑜𝑜𝑟(𝐼 → )𝑢(𝐸 𝐼(𝑟𝑜𝑜𝑡) + )𝑡𝑜𝑜𝑟(𝐸 → 𝑓𝑟𝑜𝑜𝑡 → 𝐼(𝑟𝑜𝑜𝑡), 0 )𝑡𝑜𝑜𝑟(𝐸 → })𝑢(𝐼 𝐸(𝑟𝑜𝑜𝑡) + max {𝐸(𝑢), (ג) .2כ עת נתחיל את החישוב: .4החזר )𝑡𝑜𝑜𝑟(𝐼 max {𝐸(𝑟𝑜𝑜𝑡), לכל )𝑡𝑜𝑜𝑟(𝑛𝑒𝑟𝑑𝑙𝑖 𝑢 ∈ 𝑐ℎנפעל כך: זמן ריצה – 𝑂(𝑛) -מבצעים בדיקה אחת לעץ הכוללת ביקור בכל קודקוד פעם אחת בלבד. מקום – 𝑂(𝑛) -מוסיפים לכל קודקוד 2ערכים בדיוק. .7תת סדרה עולה ארוכה ביותר (דוגמה להמרת הבעיה בבעיה אחרת) בעיה :לא נוכל לפעול בדרך בה פעלנו בתרמיל הגב ,וזאת משום שעל מנת לצרף אותו לת"ס הרקורסיבית שחישבנו ,עלינו לדעת שהוא איננו קטן מהאיבר האחרון שלה ואין לנו את המידע הזה. אלטרנטיבה :נמצא את ת"ס העולה הארוכה ביותר ש 𝑥𝑖 -הוא האיבר האחרון שבה. }𝑓(𝑖) = 1 + 𝑚𝑎𝑥 {𝑓(𝑗)| 1 ≤ 𝑗 < 𝑖, 𝑥𝑗 ≤ 𝑥𝑖 } ⋃ {0 פתרון :הפתרון לבעיה המקורית הוא })𝑖(𝑓{ . max 𝑛≤𝑖≤1 שיטה דינמית :נשתמש במערך בגודל nבו באינדקס ה – iנשמור את )𝑖(𝑓 ונחזיר את המקסימלי. סיבוכיות מקום .𝑂(𝑛) -סיבוכיות זמן – ) 𝑂(𝑛2 לכל תא נבדוק את כל התאים שלפניו כדי למצוא את jהמתאים ,וזה סכום סדרה חשבונית ) .𝑂(𝑛2לאחר מכן נאתר את המקסימום ב 𝑂(𝑛) -וגם השחזור עולה שחזור :נתחיל מ max 𝑓(𝑖) -ונמשיך אל אינדקס jהמקיים.1 ≤ 𝑗 ≤ 𝑖, 𝑥𝑗 ≤ 𝑥𝑖 , 𝑓(𝑖) = 1 + 𝑓(𝑗) : 𝑛≤𝑖≤1 .8בעיית הסטודנטים (דוגמה לשימוש בחישוב מקדים) בדומה לבעיית תרמיל הגב ,גם כאן אפשר "להקטין את הקלט" בשני כיוונים ־ מספר הסטודנטים ,ומספר הקבוצות.כל חלוקה של 𝑛 הסטודנטים ל k-קבוצות ניתן לתאר כבחירה של גודל הקבוצה האחרונה (נסמנו ב – )sוחלוקה של שאר הסטודנטים )𝑠 (𝑛 −הסטודנטים הראשונים ל – ) (𝑘 − 1קבוצות בצורה אופטימלית. לכן נגדיר את )𝑗 𝑓(𝑖,להיות ־ מספר החברויות הגדול ביותר שניתן לכבד בחלוקה של 𝑖 הסטודנטים הראשונים ל – jקבוצות ,כלומר: = )𝑗 𝑓(𝑖, max })𝑖 {𝑓(𝑖 − 𝑠, 𝑗 − 1) + 𝑅(𝑖 − 𝑠 + 1, )2≤𝑠≤𝑖−2(𝑗−1 כאשר )𝑦 𝑅(𝑥,מייצג את מספר החברויות שיש בקבוצה המכילה את הסטודנטים מהאינדקס ה x-עד ה.y - ניצור טבלה 𝑓 בגודל 𝑘𝑛 בה נשמור את הפתרונות האופטימליים. 𝑠𝑑𝑛𝑒𝑖𝑟𝑓 𝑡𝑜𝑛 0 { = ]𝑗 𝐴[𝑖, ניצור טבלה 𝐴 בגודל 𝑛2כדי לייצג את רשימת החברויות כך שלכל 𝑗 < 𝑖: 𝑠𝑑𝑛𝑒𝑖𝑟𝑓 𝑒𝑟𝑎 1 ניצור מערך 𝑅 בגודל 𝑛2כך ש 𝑅[𝑖, 𝑗] -ייצג את כמות החברויות של הסטודנטים בין 𝑖 לבין 𝑗 נראה 2דרכים לחשב את Rבאופן יעיל: דרך – 1הכלה והדחה נשים לב כי 𝑅[𝑖, 𝑗] = 𝑅[𝑖, 𝑗 − 1] + 𝑅[𝑖 − 1, 𝑗] − 𝑅[𝑖 − 1, 𝑗 − 1] + 𝐴[𝑖, 𝑗] :ולכן ניתן לחשב את המערך 𝑅 באופן איטרטיבי ופשוט. דרך ב – מטריצת עזר 𝐵 מקום 𝑂(𝑛𝑘 + 𝑛2 ) - זמן - 𝑂(𝑛2 𝑘) -יש )𝑘𝑛(𝑂 תאים וחישוב כל תא עולה )𝑛(𝑂. .9משחק סכום 0 משחק :על הלוח סדרה 𝑛𝑣 … .𝑣1 ,כל שחקן יכול לבחור מספר מהקצוות והמטרה להרוויח יותר מהשני. העיבוד המקדים מבוצע בזמן )𝑛(𝑂 ועם תוספת של )𝑛(𝑂 למקום. חישוב הסכום הכולל .𝑂(𝑛) - חישוב רישא – מתקיים 𝑖𝑣 𝑆[𝑖] = 𝑆[𝑖 − 1] +ולכן מילוי המערך עולה )𝑛(𝑂. חישוב סיפא – מתקיים 𝑖𝑣 𝐹[𝑖] = 𝐹[𝑖 + 1] +ולכן מילוי המערך עולה )𝑛(𝑂. .3אלגוריתמים חמדניים – קוד הופמן מבוא תכונת הבחירה החמדנית: האלגוריתם מקבל החלטה מקומית לגבי חלק מהפלט הסופי למופע של הבעיה ,ועל ידי התחייבות לבחירה הלוקאלית הזו ,האלגוריתם יכול להתחייב לפתרון תת מופע אחד באופן רקורסיבי. תת המבנה האופטימלי שילוב של הפתרון שחזר מהרקורסיה יחד עם הבחירה הלוקאלית (החמדנית) מוביל לפתרון (האופטימלי) עבור המופע המקורי. קידודים קידוד בינארי חוקי הגדרה :קידוד בינארי חוקי עבור א"ב ∑ היא פונקציה 𝐶: ∑ → {0,1}+שמקיימת: א∀𝜎, 𝜎 ′ ∈ ∑, 𝑐(𝜎) = 𝑐(𝜎 ′ ) ⇒ 𝜎 = 𝜎′. ב.סדרה של ביטים יכולה לתאר לכל היותר סדרה אחת של תווים מהא"ב. הערה :באופן כללי ,אם נרצה קידוד בינארי חוקי בה לכל 𝜎 𝑐(𝜎) ,באותו אורך ,נצטרך להשתמש ב- ⌉|∑| ⌈log 2ביטים עבור כל )𝜎(𝑐. קידוד תחילי )(prefix code הגדרה :קידוד תחילי עבור א"ב ∑ היא פונקציה 𝐶: ∑ → {0,1}+אם לכל ∑ ∈ 𝜎, 𝜎 ′מתקיים: 𝑐(𝜎) ⇔ 𝜎 ≠ 𝜎 ′אינו רישא של ) 𝑐(𝜎′וגם ) 𝑐(𝜎′אינו רישא של )𝜎(𝑐. טענה :קידוד תחילי הוא קידוד בינארי חוקי. כל קידוד תחילי ניתן לייצוג ע"י עץ תחילי? זהו עץ בינארי המוגדר כך: .1התווים של ∑ מיוצגים ע"י העלים. .2בן שמאלי מתאים ל – 0ובן ימני מתאים ל – .1 𝑐(𝜎).3הוא השרשור של הביטים במסלול מהשורש של העץ התחילי לעלה שמייצג את אם Tהוא עץ תחילי של קוד תחילי ,cעבור 𝜎. ∑ ∈ 𝜎 ,נסמן ב 𝑑𝑇 (𝜎) -את העומק של העלה שמייצג את 𝜎 ב 𝑇-ולכן )𝜎( 𝑇𝑑 = |)𝜎(𝑐| מציאת קידוד תחילי אופטימלי הגדרת הבעיה בהינתן סדרה של תווים מהא"ב ∑ ,נרצה למצוא קידוד תחילי של כך ששרשור הקידודים של התווים בסדרה על פי סדרן בסדרה יהיה כמה שיותר קטן. אבחנה :כדי למצוא קידוד תחילי אופטימלי עבור סדרה כלשהי ,מה שחשוב הוא תדירות ההופעה של כל תו בסדרה ,ולא הסדר שבו התווים מופיעים. הגדרת הבעיה בצורה פורמלית: קלט - :א"ב ∑ -לכל ∑ ∈ 𝜎 תדירות 𝑓𝜎 > 0 פלט :קידוד תחילי 𝑐 עבור ∑ או עץ קידוד תחילי 𝑇 עבור ∑ עם 𝑡𝑠𝑜𝑐 מינימלי ,כאשר: )𝜎( 𝑇𝑑 ∙ 𝜎𝑓 ∑ = |)𝜎(𝑐| ∙ 𝜎𝑓 ∑ = )𝑇(𝑇𝑆𝑂𝐶 ∑∈𝜎 ∑∈𝜎 האלגוריתם של הופמן אינטואיציה :לתת את הקידוד הכי ארוך לתו שמופיע הכי קצת פעמים. תיאור האלגוריתם: ())𝑂(1 -אם |∑| = 1החזר קודקוד יחיד עם ∑ ∈ 𝜎. -נסמן ב 𝑥, 𝑦 -את שני התווים עם התדירויות הנמוכות ביותר. -נגדיר תו חדש ∑ ∉ 𝑧: 𝑧 -יהיה "אבא" של x, yבעץ הקידוד (כלומר x, yעלים אחים בעץ התחילי). 𝑦𝑓 𝑓𝑧 = 𝑓𝑥 + - -נריץ רקורסיה על }𝑦 .∑′ = ∑⋃{𝑧} − {𝑥, -הרקורסיה מחזירה את הקודקוד של 𝑧 ונחבר לו את הבנים .x, y זמן ריצה יש כמה פעולות שעולות יותר מ 𝑂(1) -ואלו מציאת 𝑦 ,𝑥,הכנסת 𝑧 ובניית הא"ב החדש. נשתמש בתור קדימויות (כמו ערימה בינארית) ,כאשר המפתחות הם התדירויות. .1בניית הא"ב עולה )𝑛𝑔𝑜𝑙𝑛(𝑂 – זוהי פעולה חד פעמית. .2בקריאות הרקורסיביות מאתרים ( x,yפעולת ,)minויוצרים א"ב החדש ) (insertשעולות )𝑘𝑔𝑜𝑙(𝑂. )𝑛𝑔𝑜𝑙𝑛(𝑂 → )𝑛𝑔𝑜𝑙(𝑂 𝑇(𝑛) = 𝑇(𝑛 − 1) + סה"כ :סיבוכיות )𝑛𝑔𝑜𝑙𝑛(𝑂. הוכחת נכונות למה 1 אם 𝑇 הוא עץ תחילי אופטימלי עבור ∑ עם תדירות 𝜎𝑓 אזי ל 𝑇-אין קודקוד פנימי שיש לו רק בן אחד [.אם היה קיים צומת פנימי עם בן יחיד ,ניתן היה לשפר את הקידוד על ידי הסרת הצומת הפנימי וחיבור הבן ישירות להורה של הצומת.בכך המסלול לעלה היה מתקצר וקיבלנו סתירה]. למה ( 2תכונת הבחירה החמדנית) יהי ∑ א"ב מגודל לפחות .2יהי 𝜎𝑓 התדירות של כל תו בא"ב ,ויהיו ∑ ∈ 𝑦 2 𝑥,התווים בא"ב עם התדירויות הנמוכות ביותר (שבירת תיקו נעשית בצורה שרירותית) ,אזי: קיים עץ תחילי אופטימלי עבור ∑ ותדירויות 𝜎𝑓 הנ"ל ,שבו 𝑦 𝑥,עלים אחים [העמוקים ביותר!] למה ( 3תת המבנה האופטימלי) יהי ∑ א"ב מגודל לפחות .2יהי 𝜎𝑓 התדירות של כל תו בא"ב. יהיו ∑ ∈ 𝑦 2 𝑥,התווים בא"ב עם התדירויות הנמוכות ביותר ויהי ∑ ∉ 𝑧 ונגדיר 𝑦𝑓 .𝑓𝑧 = 𝑓𝑥 + יהי }𝑦 ∑′ = ∑⋃{𝑧} − {𝑥,ויהי 𝑇′עץ תחילי אופטימלי עבור ∑′ אזי ,העץ Tשיתקבל מ 𝑇′-ע"י הוספת 𝑦 𝑥,כבניו של 𝑧 הוא עץ תחילי אופטימלי עבור ∑. הוכחת נכונות האלגוריתם טענה :קוד הופמן מחזיר עץ קידוד אופטימלי עבור א"ב מגודל 𝑛. בסיס - 𝑛 = 1 :מחזיר קודקוד בודד וזה אכן אופטימלי. צעד :נניח נכונות עבור 𝑘 < 𝑛 ונוכיח נכונות עבור 𝑘 = 𝑛: לפי למה ,3שילוב הפתרון שהתקבל מהרקורסיה (שהוא אופטימלי לפי הנחת האינדוקציה כי גודל הא"ב קטן מ )𝑘-יחד עם הבחירה הלוקלית של שני התווים בעלי התדירות הנמוכה ביותר מוביל לעץ קידוד תחילי אופטימלי עבור א"ב 𝑘. סיכום מבנה הוכחה נוכיח את נכונות האלגוריתם באינדוקציה. בדרך כלל ,במהלך האינדוקציה ניעזר בתכונת תת-הבנייה האופטימלית (הנובעת מתכונת הבחירה החמדנית). אמנם ,במקרים מסוימים ניתן להוכיח ישירות באמצעות תכונת הבחירה החמדנית כמו למשל באלגוריתם לחיפוש בינארי. הוכחת תכונת הבחירה החמדנית למה ( 2תכונת הבחירה החמדנית) יהי ∑ א"ב מגודל לפחות .2יהי 𝜎𝑓 התדירות של כל תו בא"ב ,ויהיו ∑ ∈ 𝑦 2 𝑥,התווים בא"ב עם התדירויות הנמוכות ביותר (שבירת תיקו נעשית בצורה שרירותית) ,אזי: קיים עץ תחילי אופטימלי עבור ∑ ותדירויות 𝜎𝑓 הנ"ל ,שבו 𝑦 𝑥,עלים אחים [העמוקים ביותר!] הוכחה יהי Tעץ קידוד תחילי אופטימלי עבור ∑. נסמן ב – 𝑎 את העלה העמוק ביותר ב.T-עפ"י למה 1יש לו אח – נסמן את האח ב.𝑏 -נשים לב כי bחייב להיות עלה (אחרת a ,איננו העלה העמוק ביתר).לסיכום – a,bעלים עמוקים ביותר ב.T- כמו כן ,אנו יודעים כי 𝑦 𝑥,עלים ב( T-כל תו מיוצג בעלה). )𝑥( 𝑇𝑑 ≤ )𝑎( 𝑇𝑑 )𝑦( 𝑇𝑑 ≤ )𝑏( 𝑇 𝑑 𝑏𝑓 ≤ 𝑎𝑓. כמו כן נניח בה"כ כי 𝑦𝑓 ≤ 𝑥𝑓 נבנה עץ קידוד תחילי 𝑇′שנבנה מ – 𝑇 ע"י החלפת 𝑥 ב – 𝑎 ואת yב b -ואז מתקיים: 𝑑𝑇 (𝑥) = 𝑑𝑇′ (𝑎) , )𝑥( 𝑑𝑇 (𝑎) = 𝑑𝑇′ )𝑏( 𝑑 𝑇 (𝑦) = 𝑑𝑇′ )𝑦( 𝑑𝑇 (𝑏) = 𝑑𝑇′ נחשב ) :𝐶𝑂𝑆𝑇(𝑇) − 𝐶𝑂𝑆𝑇(𝑇 ′ מצד אחד העץ 𝑇 אופטימלי ולכן מתקיים .𝐶𝑂𝑆𝑇(𝑇) − 𝐶𝑂𝑆𝑇(𝑇 ′ ) ≤ 0 מצד שני אם נפתח את הנוסחה ,ונאמץ את האי שוויונות הנ"ל ,נקבל .𝐶𝑂𝑆𝑇(𝑇) − 𝐶𝑂𝑆𝑇(𝑇 ′ ) ≥ 0 מסקנה 𝐶𝑂𝑆𝑇(𝑇) − 𝐶𝑂𝑆𝑇(𝑇 ′ ) = 0 :והעץ 𝑇′הוא עץ תחילי אופטימלי עבור ∑ שבו 𝑦 𝑥,הם עלים אחים (עמוקים ביותר). הוכחת תכונת תת המבנה האופטימלי למה ( 3תת המבנה האופטימלי) יהי ∑ א"ב מגודל לפחות .2יהי 𝜎𝑓 התדירות של כל תו בא"ב. יהיו ∑ ∈ 𝑦 2 𝑥,התווים בא"ב עם התדירויות הנמוכות ביותר ויהי ∑ ∉ 𝑧 ונגדיר 𝑦𝑓 .𝑓𝑧 = 𝑓𝑥 + יהי }𝑦 ∑′ = ∑⋃{𝑧} − {𝑥,ויהי 𝑇′עץ תחילי אופטימלי עבור ∑′ אזי ,העץ Tשיתקבל מ 𝑇′-ע"י הוספת 𝑦 𝑥,כבניו של 𝑧 הוא עץ תחילי אופטימלי עבור ∑. הוכחה נשים לב: ( 𝑑𝑇 (𝑥) = 𝑑𝑇 (𝑦) = 𝑑𝑇′ (𝑧) + 1.1שהרי יש להם אב משותף 𝑧) .2לכל }𝑦 𝜎 ∈ ∑ − {𝑥,כי מתקיים )𝜎( 𝑑𝑇 (𝜎) = 𝑑𝑇′וכן התדירויות זהות. ניעזר בשני האבחנות הנ"ל ונפתח את הנוסחה ) :𝐶𝑂𝑆𝑇(𝑇) − 𝐶𝑂𝑆𝑇(𝑇 ′ מסקנה𝐶𝑂𝑆𝑇(𝑇) = 𝐶𝑂𝑆𝑇(𝑇 ′ ) + 𝑓𝑧 : יהי ̂𝑇 עץ קידוד תחילי אופטימלי עבור ∑. מלמה 2ניתן להניח בה"כ שבעץ זה 𝑦 𝑥,הם עלים אחים (עמוקים ביותר). יהי 𝑇̂′עץ קידוד תחילי העץ שמתקבל מ 𝑇̂ - ע"י הסרת 𝑦 𝑥,מ 𝑇̂ -וסימון אביהם ב – 𝑧 (כעת הוא עלה).באופן דומה למקודם ניתן להסיק כי 𝑧𝑓 𝐶𝑂𝑆𝑇(𝑇̂) = 𝐶𝑂𝑆𝑇(𝑇̂ ′ ) + נשים לב כי 𝑇′אופטימלי עבור ∑′ואילו ̂𝑇 אופטימלי עבור ∑ ,ולכן מצד אחד: )𝑇(𝑇𝑆𝑂𝐶 ≤ )̂𝑇(𝑇𝑆𝑂𝐶 𝐶𝑂𝑆𝑇(𝑇′) ≤ 𝐶𝑂𝑆𝑇(𝑇̂ ′ ), והרי מצד שני )𝑇(𝑇𝑆𝑂𝐶 = 𝑧𝑓 𝐶𝑂𝑆𝑇(𝑇̂) = 𝐶𝑂𝑆𝑇(𝑇̂ ′ ) + 𝑓𝑧 ≥ 𝐶𝑂𝑆𝑇(𝑇 ′ ) + מסקנה 𝑇 :עץ קידוד תחילי אופטימלי עבור ∑. בעיית בחירת הפעילויות בעיית תרמיל הגב בשברים מיון 𝑂(𝑛𝑙𝑜𝑔𝑛) -וכל שאר הפעולות עולות סה"כ )𝑛(𝑂. .4עץ פורש מינימום – 𝑆𝑇𝑀 עץ פורש מינימום – הגדרה והצגת הבעיה הגדרה יהי )𝐸 𝐺 = (𝑉,מולטי גרף קשיר וממושקל עם פונקציית משקל .𝑤: 𝐸 → ℝ יהי ) 𝑇𝐸 𝑇 = (𝑉,עץ פורש של 𝐺 ,אזי נאמר שהמשקל של Tהוא: )𝑒(𝑤 ∑ = )𝑇(𝑤 𝐸∈𝑒 עץ פורש מינימום של (MTS) Gהוא עץ פורש שמשקלו קטן ביותר ,ובאופן פורמלי: ) 𝑇 𝑖𝑠 𝑀𝑇𝑆 ⇔ ∀𝑠𝑝𝑎𝑛𝑖𝑛𝑔 𝑡𝑟𝑒𝑒 𝑇 ′ : 𝑤(𝑇) ≤ 𝑤(𝑇 ′ בעיית מציאת עפ"מ קלט 𝐺 = (𝑉, 𝐸):קשיר ו .𝑤: 𝐸 → ℝ - פלט :עץ פורש מינימום של 𝐺 (ביחס לפונקציית המשקל 𝑤). למה - 1תכונת הבחירה החמדנית חתך יהי )𝐸 𝐺 = (𝑉,ויהי 𝑉 ⊏ 𝑆 ≠ ∅.החלוקה של הקודקודים ל )𝑆\𝑉 (𝑆,נקראת חתך של .G קשתות בחתך קשת שמחברת בין קודקוד ב S-לקודקוד ב – 𝑆\𝑉 נקראת קשת בחתך /חוצה את החתך. קשת קלה ביותר בחתך יהי )𝐸 𝐺 = (𝑉,קשיר לא מכוון עם פונקציה משקל . 𝑤: 𝐸 → ℝ קשת 𝐸 ∈ )𝑣 𝑒 = (𝑢,קשת בחתך 𝑒.נקראת קשת קלה ביותר בחתך )𝑆\𝑉 (𝑆,אם: לכל קשת 𝑒′שחוצה את החתך מתקיים.𝑤(𝑒) ≤ 𝑤(𝑒 ′ ) : למה – 1תכונת הבחירה החמדנית יהי )𝐸 𝐺 = (𝑉,מולטי-גרף קשיר עם פונקציית משקל .𝑤: 𝐸 → ℝ יהי )𝑆\𝑉 (𝑆,חתך של Gותהי 𝑒 קשת קלה ביותר בחתך )𝑆\𝑉 .(𝑆,
