פיבונאצ'י
פיבונאצ'י היה מתמטיקאי איטלקי, חי בערך בין 1170 ל-1250. בימים ההם למדו במזרח ותרגמו מדעים לשפות שונות. ידע מתמטי הגיע מאזורי מוסלמים ויהודים לאירופה. פיבונאצ'י הביא חלק מהידע הזה מערבה. הוא למד אצל מורים בערב ונסע למדינות שונות. פגש שם את שיטת הספרות העשרונית, כלומר הדרך לכתוב מספרים עם הספרה אפס....
סדרת פיבונאצ'י
= סדרת פיבונאצ'י = סדרת פיבונאצ'י מתחילה ב־1, 1. כל מספר אחר הוא סכום שני המספרים שלפניו. לדוגמה: 1, 1, 2, 3, 5, 8, 13, 21... פיבונאצ'י היא שם של אדם שמצא את הדוגמה הזאת. הוא דיבר על ארנבים כדי להציג את הרעיון: זוג ארנבים צעיר אחרי חודשיים מתחיל להמליט. = יחס הזהב = כאשר מחלקים מספר בסדרה במספר שק...
ערימת פיבונאצ'י
ערימת פיבונאצ'י היא סוג של ערימה. ערימה היא מבנה נתונים לשמירת דברים לפי סדר. היא עוזרת לעשות פעולות כמו הוספה, מציאת הקטן ביותר והורדת ערך. הורדת ערך פירושה להקטין את הערך של פריט שכבר בערימה. מבנה זה מייעל עבודות כמו דייקסטרה. דייקסטרה הוא דרך למצוא את הדרך הקצרה ברשת. המבנה בנוי מאוסף עצים. ...
היסטוריה של האריתמטיקה
אריתמטיקה היא הדרך לעשות חישובים עם מספרים. אנשים קדמונים השתמשו בעצמות עם חריצים כדי לספור. המצרים בנו פירמידות. הם ייצגו מספרים בסמלים ועשו חישובים לצרכים מעשיים. הבבלים השתמשו בבסיס 60. זה אומר שעובדים עם 60 במקום 10. הם החלו לחלק שעות ודקות לפי 60. היוונים חשבו עמוק על המספרים. הם הוכיחו רעי...
סכום של שני ריבועים
להציג מספר כ־a^2+b^2 פירושו לחבר שני ריבועים. ריבוע הוא מספר כפול עצמו. הבעיה ידועה מאוד. פיבונאצ'י הראה שאם יש הצגה לשני מספרים, אפשר להכין הצגה למכפלה שלהם. לכן מספיק לדעת להצגה של המספרים הראשוניים. פרמה גילה כלל חשוב: ראשוניים שנותרים 1 כשמחלקים ב־4 (משאירים שארית 1) אפשר לכתוב כסכום של שני רי...
מספרי לוקאס
מספרי לוקאס הם סדרה של מספרים בשם לוקאס. הסדרה דומה לפיבונאצ'י. כל מספר שווה לסכום שני הקודמים. המספרים הראשונים: 2, 1, 3, 4, 7, 11, 18. הגדרה קצרה: האיבר ה‑0 הוא 2. האיבר ה‑1 הוא 1. לכל אחד אחר: קח את שני הקודמים והוסף אותם. יש נוסחה עם יחס הזהב. יחס הזהב הוא מספר מיוחד. אפשר גם להעריך כל איבר על י...
קומבינטוריקה
קומבינטוריקה עוסקת בספירה של דרכים לסדר ולבחור דברים. זה עוזר להבין בעיות יומיומיות ומשחקים. תמורה היא סידור של פריטים בסדר מסוים. את מספר כל הסידורים מקבלים על ידי כפל כל המספרים מ‑1 עד n. למשל, לכל ארבעה פריטים יש 1×2×3×4 דרכים, כלומר 24 דרכים. חליפות הן בחירות שבהן הסדר חשוב. אם בוחרים k פר...
רקורסיה
רקורסיה היא מצב שבו דבר אחד מכיל בתוכו עותק קטן של עצמו. אם יש נקודת עצירה, מפסיקים לחזור. אם לא, זה ממשיך לנצח. מראה מול מראה היא דוגמה פשוטה. הגדרה רקורסיבית היא הגדרה שמשתמשת בעצמה כדי להסביר את עצמה. תמונה שבתוכה יש את אותה התמונה שוב. קוראים לזה אפקט דרוסטה. צייר שצייר את התמונה שבה הוא מציי...
חוק המספרים הקטנים
'חוק המספרים הקטנים' הוא רעיון של המתמטיקאי ריצ'רד גאי משנת 1988. הוא מדבר על התנהגויות של מספרים קטנים. חוק אחד אומר שלפעמים אין מספיק מספרים קטנים כדי להגשים את הציפיות שלנו. כלומר, דברים שקורים כשיש הרבה פריטים לא תמיד קורים כשיש מעט פריטים. חוק שני מראה שלפעמים מספרים נראים כמו סדרה מוכרת, אבל...
הבעיה העשירית של הילברט
ה"בעיה העשירית" שאלה דבר פשוט למראית עין. היא ביקשה חוק שמסביר אם למשוואה של מספרים שלמים יש פתרון. חוק כזה נקרא אלגוריתם - זה כלל שמחשב יכול לבצע. הילברט הציג את השאלה ב-1900. הרבה שנים חשבו שאולי יש חוק כזה. אחרי זמן רב הוכיחו שזה בלתי אפשרי. מתמטיקאים הבינו שיש קבוצות של מספרים שניתן "לרשום" על...
יחס הזהב
יחס הזהב הוא מספר שקרוב ל־1.618. המספר נקרא גם "חתך הזהב". האות φ משויכת לפידיאס, פסל יווני. אם נחלק שני גדלים נכון, נקבל את היחס המיוחד הזה. הוא יוצא שוב ושוב בצורות טבעיות ואמנות. סדרת פיבונאצ'י מתחילה 1,1 ואז כל מספר הוא סכום של שני קודמים. כשמצמידים ריבועים בגודל לפי הסדרה, נוצרת צורה שמזכי...
תכנון דינמי
תכנון דינמי הוא שיטה לפתור בעיות חכמות. השיטה הוצגה ב-1953 על ידי ריצ'רד בלמן. פרד ומשול זה לחלק בעיה לבעיות קטנות. רקורסיה זה כשפתרון משתמש בפתרון של בעיות קטנות יותר. לפעמים הבעיות הקטנות חוזרות על עצמן. פתרון חוזר מבזבז זמן. תכנון דינמי זוכר פתרונות קטנים, כך שלא צריך לחשב אותם שוב. ביישומים מש...
נוסחת נסיגה
נוסחת נסיגה היא כלל שמספר איך לבנות רשימת מספרים, שנקראת סדרה. היא אומרת איך לקבל כל מספר מהמספרים שלפניו. המילה "רקורסיבי" אומרת בדיוק את זה: משתמשים בקודמים כדי למצוא את הבא. יש שני חלקים חשובים: 1) תנאי התחלה, המספרים הראשונים שמתחילים את הסדרה. 2) כלל (נוסחת נסיגה), איך מחשבים כל מספר מהקו...
ערימה
ערימה היא דרך לארגן נתונים בעץ. עץ כאן הוא מבנה עם צומת עליון ושכבות מתחתיו. יש שתי צורות עיקריות. בערימת מקסימום כל ילד קטן או שווה לאב. לכן השורש הוא הגדול ביותר. בערימת מינימום ההפך: השורש הוא הקטן ביותר. ערימות עוזרות לתעדף. לדוגמה בחדר מיון מטפלים קודם במי שדחוף יותר. אם שומרים את המטופלים בע...