» «
רקורסיה
מהי רקורסיה?



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

הגדרה אחרת לרקורסיה היא "הגדרת בעיה במונחים של עצמה".

רוצים דוגמה:
"אם הבנת מהי רקורסיה, חזור אל הדף ממנו הגעת. אם לא – קרא בדף זה מהי רקורסיה".

הדוגמה הזו מסבירה בדיוק את הרקורסיה, כי תנאי העצירה הוא "אם הבנת.." ואם לא אז חוזרים לאותה דוגמה כדי ללמוד מהי רקורסיה מחדש ולבסוף מבינים שהרקורסיה היא מה שאתה מתבקש לעשות..

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

לרוב נותנים לרקורסיה כזו את הדוגמה של חישוב n-עצרת במתמטיקה (=מכפלת 1 כפול 2 כפול 3… עד כפול n).

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


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

http://youtu.be/ghZKKaZkzrE


כניסה פנימה לפרקטל - צורה גרפית שנקראת "משולש סירפינסקי" שנבנתה בפונקציה רקורסיבית:

http://youtu.be/P5EkdJRtF-4


והסבר למתכנתים (עברית):

https://youtu.be/B19qH3XFnxY?long=yes
מגדלי האנוי
מהם מגדלי האנוי?



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

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

אגב, לוקאס המציא גם אגדה שמדובר במקדש בראהמי שבו הכהנים מעבירים מגדל בן 64 דיסקיות. על פי האגדה שלו, כשיסיימו הכהנים את עבודתם, יגיע גם סוף העולם..


ישנם כללים להעברה:

א. בכל שלב תעבור רק דיסקית אחת מקום.

ב. אסור שיהיה מצב שדיסקית תהיה מונחת על דיסקית קטנה יותר.


הנה דרך לפתרון של חידת מגדלי האנוי:

http://youtu.be/BMkOBNZHcIs
פרקטל
מהם פרקטלים?



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

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

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


הנה סרטון הסבר למושג הפרקטל (מתורגם):

http://youtu.be/Tm0U2VxFd8Q


הסבר מילולי על הפרקטלים - מהתבניות היותר מעניינות שבטבע (עברית):

http://youtu.be/ofA2tBvcbhw?t=3m38s


המתמטיקה של הפרקטלים בסרטון מקסים לפי ז'אנר הסרט האפל (מתורגם):

https://youtu.be/0C75vRVL5lE


הפרקטלים שבטבע:

https://youtu.be/XwWyTts06tU


עוד פרקטלים בטבע:

https://youtu.be/dZM45mfJQ40


להדגמת הרקורסיה הפשוטה, הנה משולש סרפינסקי שלא נגמר:

http://youtu.be/QsMvoui5WlQ?t=10s


ופרקטל מתמטי ללא סוף, בגרפיקה ממוחשבת ואנימציה מוסיקה נהדרים:

https://youtu.be/hRrBnI5L0u8?long=yes
משולש שרפינסקי
מהו משולש סירפינסקי?



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

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


הנה משולש סרפינסקי שלא נגמר, להדגמת הרקורסיה הפשוטה:

http://youtu.be/QsMvoui5WlQ?t=10s


סרט אפל מתורגם ומדהים על הפרקטלים ומשולש שרפינסקי בתוכם (מתורגם):

https://youtu.be/0C75vRVL5lE


סרטון בגרפיקת מחשב של "משולש סירפינסקי" שנבנה ברקורסיה בתלת-מימד:

http://youtu.be/P5EkdJRtF-4


משולש שרפינסקי מסוכריות של החג הנוצרי המעט מפחיד "ליל כל הקדושים":

http://youtu.be/z8ZWlUamNPI


וכך יוצרים פרקטלים כמו משולש סרפינסקי:

http://youtu.be/XwWyTts06tU?t=1m22s

רקורסיה

פרקטלים טבעיים
איפה יש פרקטלים בטבע?



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

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

אז אומרים לכם שכל כך הרבה פרקטלים יש בטבע ואפשר לראותם כמעט בכל מקום. אבל איפה זה בדיוק בכל מקום?

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

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

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

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


הנה הסבר הפרקטלים שבטבע:

https://youtu.be/Tm0U2VxFd8Q


שלל פרקטלים טבעיים:

https://youtu.be/4IRLvYOZD8A


עוד פרקטלים בטבע:

https://youtu.be/XwWyTts06tU


ואובייקטים טבעיים שהם פרקטלים:

https://youtu.be/dZM45mfJQ40
סדרת פיבונאצ'י
מהי סדרת פיבונאצ'י?



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

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

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

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


הנה הסבר על סדרת פיבונאצ'י (עברית):

https://youtu.be/EAXKR-H_bS0


הסבר מדעי של הסדרה הפיבונאצ'ית (עברית):

http://youtu.be/z5RWfXTd3QU


הדגמה של סדרת פיבונאצ'י:

http://youtu.be/H2aHh5FLX5w


והסבר מתמטי של סדרת ה פיבונאצ'י (מתורגם):

https://youtu.be/SjSHVDfXHQ4
מכונת פון נוימן
מהן מכונות פון ניומן?



מכונות פון-ניומן (Von Neumann Machines) הן מכונות המשכפלות את עצמן שוב ושוב, אבל הרעיון שהוליד את הרעיון ליצור מכונות כאלה, שעדיין לא יוצרו, הוא מעניין אפילו יותר מקיומן.

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

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

המכונות האלה קיבלו את השם הלא-מפתיע "מכונות פון-ניומן". הרעיון שלו היה שתיאורטית יוכלו המכונות להשתלט כך על כל היקום, בעיקר משום שהן מתרבות בגידול אקספוננציאלי, מייצרות שוב ושוב מכונות כמוהן ומנצלות את המשאבים שיש בכוכבים עצמם, מבלי להוביל עימן משאבים מכדור הארץ. אם כל מכונה מייצרת 100 מכונות דומות, בתוך 4 דורות יוכלו מכונות פון נוימן לייצר מיליון מכונות. עוד שני דורות ויש כבר 10 מיליארד כאלה...

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


הנה סיפורן של מכונות פון ניומן (מתורגם):

https://youtu.be/Rpy9Qp7NAaw


הסבר מקיף על הרעיון של מכונות פון-ניומן:

https://youtu.be/4H55wybU3rI


וסרט תיעודי על הרעיון של מכונות המשכפלות את עצמן:

https://youtu.be/V-96C4ExhWM?long=yes
בנואה מנדלברוט
מהי הגאומטריה של מנדלברוט?



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

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

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

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

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

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

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

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

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

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


הנה סרטון שמסביר זאת היטב:

http://youtu.be/Dm-zy5f4qIo


הדמיון העצמי של פרקטל:

http://youtu.be/9G6uO7ZHtK8


הסבריו של מנדלברוט עצמו:

http://youtu.be/pDajf3PXpNI


ודוגמאות שונות לסט מנדלברוט, שמערב סיבוכיות, הרמוניה ויופי בשימוש בנוסחאות פשוטות:

http://youtu.be/G_GBwuYuOOs


אֵאוּרִיקַה - האנציקלופדיה של הסקרנות!

העולם הוא צבעוני ומופלא, אאוריקה כאן בשביל שתגלו אותו...

אלפי נושאים, תמונות וסרטונים, מפתיעים, מסקרנים וממוקדים.

ניתן לנווט בין הפריטים במגע, בעכבר, בגלגלת, או במקשי המקלדת

בואו לגלות, לחקור, ולקבל השראה!

אֵאוּרִיקַה - האנציקלופדיה של הסקרנות!

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