לדף הכניסה של ישרא-בלוג
לדף הראשי של nana10
לחצו לחיפוש
חפש שם בלוג/בלוגר
חפש בכל הבלוגים
חפש בבלוג זה




מלאו כאן את כתובת האימייל
שלכם ותקבלו עדכון בכל פעם שיעודכן הבלוג שלי:

הצטרף כמנוי
בטל מנוי
שלח

RSS: לקטעים  לתגובות 
ארכיון:


4/2018

יחס הזהב ואלגוריתם אוקלידס


מנצל את זה שיש טיפה זמן פנוי בשביל לכתוב פוסט על משהו מגניב שביקשו מאיתנו להוכיח בתרגיל בית האחד הקורסים הסמסטר.

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

 

כמה תזכורות ומושגי יסוד

האלגוריתם של אוקלידס לוקח שני מספרים שלמים (ולשם הפשטות חיוביים), ואומר לנו מהו המספר הגדול ביותר ששניהם מתחלקים בו. האלגוריתם עצמו מפורט בפוסט הזה, ואני שוב ממליץ להעיף בו מבט. המחלק המשותף המקסימלי הזה יכול להגיד לנו הרבה על הקשר בין שני מספרים, ולכן כבר לפני 2000 שנים הייתה מוטיבציה למצוא אלגוריתם יעיל שימצא אותו. אבל עד כמה האלגוריתם של אוקלידס באמת יעיל? מסתבר שמאוד - בפוסט הזה אנחנו נוכיח בדיוק עד כמה.

 

יחס הזהב הוא קבוע מתמטי שמופיע בשכיחות מאוד גבוהה בתופעות טבע, באומנות ובכלל. זה מספר אי-רציונלי שמסומן באות  והוא שווה .  יש הרבה דרכים להגדיר אותו, אבל אנחנו נשתמש בהגדרה הכי נפוצה - באמצעות סדרת פיבונאצ'י. זוהי סדרת מספרים שמוגדרת באופן רקורסיבי - שני האיברים הראשונים בה הם 1, ולאחר מכן כל איבר שווה לסכום שני האיברים שלפניו.

למי שמתחבר לנוסחאות נסיגה, אפשר לבטאה באופן הבא - .

למי שמתחבר לדוגמאות - נסו לראות כיצד הגדרת הסדרה מתבטאת במספר האיברים הראשונים - .

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

 

סיבוכיות זמן ריצה של אלגוריתם היא ביטוי למהו הזמן המקסימלי הלוקח לאלגוריתם מסוים להחזיר את הפלט שאנחנו מבקשים ממנו, כתלות בגודל הקלט. לדוגמה - אם יש לנו ערימה מבולגנת של תקליטים, ואנחנו רוצים לדעת אם האלבום Atom Heart Mother של פינק פלויד נמצא בערימה או לא, האלגוריתם המתבקש הוא פשוט לעבור על כל דיסק בערימה ולבדוק אם זה הוא (במקרה הכי גרוע, נצטרך לעבור על הערימה כולה). במקרה זה, זמן הריצה של האלגוריתם נמצא ביחס ישר לגודל הערימה, ולכן אומרים שהסיבוכיות ליניארית. אם היינו רוצים לקחת את הערימה ולמיין את כל האלבומים שבה לפי האלף-בית, על ידי כך שבכל פעם נשווה בין שני תקליטים ונחליף בין המיקום שלהם אם הם לא ממוינים בסדר נכון (אלגוריתם שנקרא bubble sort), ניתן להראות שזמן הריצה של האלגוריתם תלוי במספר התקליטים בריבוע, ולכן אומרים שהסיבוכיות היא ריבועית.

 

הטענה שנוכיח


 

המטרה שלנו היא להראות שסיבוכיות זמן הריצה של האלגוריתם תלויה בלוגריתם של המספר הגדול יותר - a. אבל לא סתם לוגריתם - לוגריתם בבסיס יחס הזהב . כלומר, נוכיח שבהינתן שני מספרים a, b, הכמות המקסימלית של צעדים שהאלגוריתם ייצטרך לבצע כדי למצוא את המחלק המשותף המקסימלי שלהם היא .

 

שלב ראשון

בשלב הראשון של ההוכחה, נוכיח כי אם האלגוריתם מבצע n איטרציות, אז לכל  (לפי הסימון שלמעלה) מתקיים .

ההוכחה היא באינדוקציה על i, וכדי לבצע אותה נצטרך להכיר זהות חשובה שקשורה ליחס הזהב - . זו זהות שקל להוכיח אותה באמצעות נוסחת השורשים או באמצעות הצבה ישירה של הערך של , ואני משאיר אותה כתרגיל למי שמעוניין. עכשיו לאינדוקציה:

מקרה הבסיס - i=0. במקרה זה ברור שמתקיים , מפני שאחרת היה מתקיים , אבל לפי האופן שבו הגדרנו לעיל את ריצת האלגוריתם זה אומר שהאלגוריתם היה צריך לסיים לרוץ אחרי n-1 צעדים במקום אחרי n, וזו סתירה להנחה הבסיסית שלנו.

שלב האינדוקציה - אנחנו מניחים שהטענה נכונה עבור כל , ובהתבסס על הנחה זו אנחנו רוצים להוכיח שהטענה נכונה גם עבור . כלומר, אנחנו רוצים להוכיח כי . ואכן:

 

כעת נוכל להשתמש בהנחת האינדוקציה ולהסיק:

ועל פי הזהות השימושית שלנו, זה אומר ש:

וזה בדיוק מה שהיינו צריכים להוכיח.

 

שלב שני
באמצעות התכונה המעניינת שהוכחנו בשלב הראשון, אנחנו יכולים להוכיח עכשיו שהלוגריתם בבסיס יחס הזהב הוא חסם מלעיל לזמן הריצה של האלגוריתם. כלומר - אנחנו נוכיח שאם a הוא המספר הגדול ביותר שאנחנו מכניסים כקלט לאלגוריתם, אז האלגוריתם יבצע לכל היותר  צעדי חלוקה. במילים אחרות, עלינו להוכיח שאם האלגוריתם מבצע n איטרציות, אזי .
כזכור - הוכחנו שמתקיים . כדי לקבל את מה שאנחנו צריכים, אנחנו פשוט נפעיל את הלוגריתם המתאים על שני הצדדים של המשוואה ונציב i=n. לאחר שנעשה זאת נקבל:
(כאשר במעבר האחרון השתמשנו בכך שנתון כי ).
וזה מה שהיה צריך להוכיח.
שלב שלישי ואחרון
אוקיי, אז הראינו שהלוגריתם על בסיס יחס הזהב הוא חסם מלעיל לזמן הריצה של האלגוריתם. אבל אנחנו רוצים להראות שהוא לא רק חסם מלעיל, אלא חסם הדוק. במילים אחרות - הראינו שזמן הריצה של האלגוריתם לעולם לא יהיה גדול יותר מהגודל שמצאנו, אבל אנחנו רוצים להראות שיש מקרים שבהם הוא שווה אליו בדיוק.
זה אומר שפשוט צריך למצוא דוגמה קונקרטית לשני מספרים שאפשר להזין לאלגוריתם כך שזמן הריצה שלו יהיה שווה בקירוב טוב ללוגריתם בבסיס יחס הזהב של המספר הגדול יותר. כדי לעשות זאת, נבצע ניחוש מושכל - אם החסם שלנו הוא הלוגריתם בבסיס יחס הזהב, אז אם נבחר שני מספרים שהיחס ביניהם הוא בקירוב יחס הזהב, אז יש סיכוי טוב שהם יעמדו בקריטריון שלנו, כי האלגוריתם יצטרך לבצע הרבה חלוקות כדי למצוא את המחלק המשותף המקסימלי שלהם.
המקור הכי טוב שאפשר לקבל ממנו שני מספרים שהיחס ביניהם הוא בקירוב יחס הזהב הוא סדרת פיבונאצ'י שעליה כתבתי בתחילת הפוסט - ניקח שני מספרים עוקבים מהסדרה, שכאמור היחס בין כל שני איברים בה הולך ושואף ליחס הזהב. אני לצורך הדוגמה בחרתי את 610 ו-987, אבל יש פה חופש יחסית גדול בבחירה.
אני אחסוך לכם את החישובים עצמם (שאין בהם יותר מדי ערך בעיניי), אבל למי שלא מאמין לי ורוצה לבדוק בעצמו - תריצו את האלגוריתם ותוכלו לראות שמספר הצעדים שווה ללוגריתם ביחס הזהב של 987 (בערכו השלם).
ובכך בעצם מסתיימת ההוכחה - הראינו שהסיבוכיות המקסימלית של האלגוריתם שלנו הוא לוגריתם בבסיס יחס הזהב של הקלט הגדול.
ההסבר האינטואיטיבי
למי שמכיר קצת אלגוריתמים שמבוססים על חלוקה, התוצאה עצמה עשויה להיראות די מוכרת - הסיבוכיות של הרוב המוחלט של אלגוריתמי חלוקה היא לוגריתמית. אבל מה שמעניין באמת זה הבסיס של הלגוריתם עצמו - למה זה דווקא יחס הזהב? זה משהו מאוד לא מובן מאליו, ובהתחלה הקשר ממש לא היה ברור לי.
אבל אחרי שהקדשתי לזה מחשבה, מצאתי הסבר מספק שנשען על אינטואיציה שהיא יותר גיאומטרית. לשם כך, אני רוצה שבהינתן שני מספרים שלמים, נחשוב על המלבן שצלע אחת שלו היא באורך של המספר הראשון, והצלע השנייה היא באורך של המספר השני. האנימציה שלמטה (שאגב, הופיעה גם בפוסט המקורי שלי על אלגוריתם אוקלידס, הרבה לפני ששמעתי על הסיבוכיות שלו) נותנת הסבר חזותי למשמעות של המחלק המשותף המקסימלי:

המחלק המשותף המקסימלי הוא בעצם המלבן הראשון שנכנס "בצורה מושלמת" בתוך המלבן הגדול יותר. זו בעצם המקבילה הגיאומטרית לרעיון של מספר אחד שמחלק את האחר - ניתן להכניס אותו לתוך האחר ללא שאריות.
אז מה הקשר ליחס הזהב? עכשיו כשיש לנו את הגיאומטריה מול העיניים, אני רוצה שנשאל את עצמנו - מתי האלגוריתם ירוץ הכי הרבה פעמים? זה יהיה כשבכל חלוקה של המלבן, המלבן הקטן ייכנס "כמעט בדיוק" בתוך המלבן הגדול, אבל לא בדיוק. במצב כזה, יתקיים בקירוב שבתוך כל מלבן יהיו שני מלבנים יותר קטנים, שסכומם יהיה שווה "כמעט בדיוק" למלבן הגדול.
כלומר, תהיה לנו סדרה של מלבנים, כך שכל מלבן שווה לסכום שני המלבנים שלפניו. נשמע לכם מוכר מאיפשהו? זו בדיוק סדרת פיבונאצ'י שמגדירה בצורה כל כך חשובה את יחס הזהב. זה בעצם אומר לנו שאם המלבנים יתנהגו בקירוב כמו סדרת פיבונאצ'י, האלגוריתם יצטרך לבצע יותר חלוקות, ובדיוק מפה מגיע הלוגריתם על בסיס יחס הזהב. ככה אני מפרש את זה, בכל אופן.
___________________________________________________________________
מקווה שהיה לכם מעניין לקרוא. אני מודע לזה שזה היה פוסט פחות נגיש מהפוסטים שלרוב אני כותב, אבל זה היה רעיון כל כך מגניב שממש התחשק לי לכתוב עליו, גם אם אין לי בנמצא איזשהי אנלוגיה מעניינת או הסבר קליט לרעיון מאחורי המשפט. ממליץ שוב לחזור על החלקים הקצת פחות ברורים, ואם למישהו יש שאלות כלשהן או הערות - אשמח לשמוע מכם! (מוזמנים גם סתם להגיד שלום, לא הייתי פה תקופה ארוכה)
אשתדל לקפוץ לבקר מדי פעם כשיש לי זמן פנוי ולעדכן על דברים מעניינים שלמדתי עליהם. אם יש לכם נושאים שאתם הייתם רוצים לקרוא עליהם, תרגישו חופשי לעדכן.
שבת שלום! חיוך
נכתב על ידי קרל שוורצשילד , 21/4/2018 18:20  
7 תגובות   הצג תגובות    הוסף תגובה   הוסף הפניה   קישור ישיר   שתף   המלץ   הצע ציטוט
 





Avatarכינוי:  קרל שוורצשילד

בן: 23




הבלוג משוייך לקטגוריות: מדע וטכנולוגיה
© הזכויות לתכנים בעמוד זה שייכות לקרל שוורצשילד אלא אם צויין אחרת
האחריות לתכנים בעמוד זה חלה על קרל שוורצשילד ועליו/ה בלבד
כל הזכויות שמורות 2018 © נענע 10 בע"מ