אלגוריתם חיפוש
אלגוריתם חיפוש הוא דרך למצוא פריט במחשב. מבנה נתונים הוא איך מסדרים את הפריטים. חיפוש ממצה אומר לבדוק אם הפריט נמצא, ולשלוף אותו אם כן. יש חיפוש בכוח גס: בודקים פריט פריט עד שמוצאים. זה עובד אבל איטי כשיש הרבה פריטים. אם הפריטים מסודרים לפי סדר אפשר להשתמש בחיפוש בינארי. בחיפוש בינארי בודקים את האמ...
אלגוריתמים לייצור מבוכים
מבוך בנוי מתאים שמופרדים בקירות. מבוך טוב מאפשר ללכת מכל תא לכל תא אחר. אפשר לחשוב על מבוך כרשת של נקודות וקווים. נקודה אחת מייצגת תא. קו מייצג מעבר בין תאים. שיטה אחת בונה את המבוך בעזרת חיפוש לעומק. בוחרים תא התחלה. מסמנים אותו ומסתכלים על השכנים באקראי. אם שכן לא בוקר, מסירים את הקיר בינו ובין ה...
אלגוריתם מילר-רבין
מילר-רבין בודק אם מספר הוא ראשוני. מספר ראשוני מחלקים אותו רק בעצמם וב-1. האלגוריתם מהיר ולעיתים קטן יכול לטעות. קודם כותבים את n-1 בצורה n-1 = 2^s · r. זאת אומרת: מחלקים ב-2 עד שהשארית r אי-זוגית. (r הוא המספר שנותר.) בוחרים מספר a שלא מתחלק ב-n. מחשבים חזקות של a ומסתכלים על השארית בחלוקה ב-n. אם...
אלגוריתם גנטי
אלגוריתמים גנטיים הם שיטה מחשבתית שמחפשת פתרונות טובים לבעיות. אופטימיזציה כאן פירושה למצוא את הפתרון הכי טוב. המצאה קשורה למחקר בשנות ה-50 וה-60. ג'ון הולנד פיתח את הרעיון בשנות ה-60. הוא רצה להעתיק את יכולת ההסתגלות של הטבע לתוכנות. מייצרים קבוצה של פתרונות אפשריים. כל פתרון מיוצג כ"כרומוזום", ...
אלגוריתם חמדן
אלגוריתם חמדן זה דרך לפתור בעיות. אלגוריתם = סדרת חוקים לפתרון. חמדן = בוחר את מה שנראה הכי טוב עכשיו. זה בדרך כלל מהיר. לפעמים הוא נותן פתרון טוב. לפעמים לא. חמדנים עוזרים כשאין זמן לחשוב הרבה. יש בעיות שקשה מאוד לפתור מהר. לפעמים הבחירה החמדנית גם היא הכי טובה. - סוכן נוסע: כל פעם נוסעים ליישוב ...
אלגוריתם פלויד-וורשאל
אלגוריתם פלויד-וורשאל מוצא את הדרך הקצרה ביותר בין כל שתי נקודות בגרף. גרף הוא קבוצת נקודות שנקראות צמתים. קשת היא קו שמחבר בין נקודות. משקל הוא עלות או מרחק של קשת. האלגוריתם עובד גם אם יש משקלים שליליים. משקל שלילי פירושו שהקשת מורידה את הסכום במקום להגדיל אותו. אבל אם יש מעגל שלילי, לולאה שסכום...
אלגוריתם דו-כיווניות של יוניקוד
אלגוריתם דו-כיווניות מחליט אם הטקסט זורם מימין לשמאל או להפך. אלגוריתם = כלל בתוכנה שמקבל החלטות. תווים בעברית וערבית זורמים מימין לשמאל. תווים באנגלית זורמים שמאל־לימין. מספרים בדרך כלל שמאל־לימין. סימני פיסוק כמו נקודה הם נייטרליים. = תווים נייטרליים = תווים נייטרליים הם תווים בלי כיוון, כמו נקודה...
אלגוריתם חיפוש לעומק
אלגוריתם חיפוש לעומק (DFS) הוא דרך לבדוק גרף. גרף הוא קבוצת נקודות שמחוברת בקווים. הפעולה: מתחילים מצומת אחד. הולכים לצומת שכן שלא ביקרו בו. אם נתקלנו בקיר, חוזרים אחורה לנקודה קודמת. כך ממשיכים עד שכל הנקודות נבדקו. אם נשארו נקודות שלא בוקרו, מתחילים מהן. התוצאה היא עץ שמראה מי גילה את מי. בעץ כ...
אלגוריתם חיפוש לרוחב
חיפוש לרוחב (BFS) הוא דרך למצוא צמתים (נקודות) בגרף. גרף זה אוסף נקודות שמחוברות בקווים שנקראים קשתות. מתחילים מנקודה אחת. קודם בודקים את כל הנקודות שמחוברות אליה ישירות. אחר כך בודקים את הנקודות שמחוברות למאלה. האלגוריתם משתמש בתור. תור אומר: מוסיפים לסוף ומוציאים מהתחלה. כל פעם שמוצאים שכן שלא נ...
אלגוריתם בלמן-פורד
בלמן-פורד הוא אלגוריתם למציאת המסלול הקצר. גרף מכוון וממושקל זה רשת עם חצים ומספרים על החצים. האלגוריתם מוצא את הדרך הקצרה מצומת אחד לכל שאר הצמתים. הוא יודע לעבוד גם אם לחצים יש מספרים שליליים. אם קיים "מעגל שלילי" אפשר להקטין את המשקל שוב ושוב. האלגוריתם מזהה את הבעיה הזאת. מורידים מרחקים בעזרת פ...
אלגוריתם הפרד ומשול
הפרד ומשול היא דרך לפתור בעיות על ידי חלוקה לחלקים קטנים יותר. כל חלק הוא בעיה דומה. אחרי שמפתרים את כל החלקים, מחברים את התשובות ביחד. אומרים שהדרך היא רקורסיה. רקורסיה זו קריאה של פונקציה לעצמה. אפשר גם לעשות את זה בלי רקורסיה, בעזרת מחסנית (מבנה שמאחסן דברים לפי סדר). השיטה טובה לבעיות קשות. אם...
אלגוריתם
אלגוריתם הוא סדרת צעדים ברורה לפתרון בעיה. זו כמו מתכון לעוגה. המתכון צריך לומר בדיוק מה לעשות. אם הוא לא ברור, ייתכן שיצטרכו לחשוב או לשמש שיפורים. אלגוריתם חייב לעצור בסוף ולתת תשובה נכונה. יש רעיון תאורטי בשם "מכונת טיורינג". זוהי מכונה דמיונית שמדגימה מה אפשר לחשב. יש בעיות שאי אפשר לפתור בכלל ...
אלגוריתם למפל-זיו
אלגוריתם למפל-זיו פותח על ידי אברהם למפל ויעקב זיו. זהו דרך לגרום לקבצים להיות קטנים. דחיסה משמרת מידע אומרת שניתן לשחזר את הקובץ המקורי בלי שגיאות. הרעיון הוא למצוא דברים שחוזרים על עצמם ולהפנות אליהם במקום לכתוב שוב. יש "חלון", אזור קטן שנע על הטקסט. הקידוד שומר מיקום, אורך והתו הבא. החלון מתקד...
אלגוריתם מיון
מיון הוא דרך לסדר דברים לפי מפתח. למשל: לסדר אנשים לפי שם משפחה. יש שני סוגים: מיון עולה, שבו הקטן ביותר ראשון, ומיון יורד, שבו הגדול ראשון. מיון עוזר לעבוד עם מסדי נתונים. מסד נתונים שומר רשימות מסודרות שנקראות אינדקס. אינדקס הוא רשימה שמקלה על מציאת פריטים. כשנתונים מסודרים, אפשר למצוא דברים מה...
אלגוריתם דייקסטרה
דייקסטרה הוא כלי למציאת הדרך הקצרה במפה שמחוברת בנקודות וקווים. נקודות נקראות קודקודים. קווים נקראים קשתות. מתחילים מהנקודה שממנה רוצים לצאת. לכל נקודה נותנים מספר גדול מאוד, חוץ מהמקור שווה ל‑0. כל פעם בוחרים את הנקודה עם המספר הקטן ביותר. דמיין רשת תעלות ומזרים מים במקביל. המים יגיעו קודם לכל המ...
אלגוריתם דטרמיניסטי
אלגוריתם דטרמיניסטי הוא דרך קבועה וברורה לפתור בעיה. אלגוריתם (רשימת צעדים) שמקבל אותו קלט תמיד יעשה את אותם צעדים וייתן את אותו פלט. דוגמה ידועה היא החילוק הארוך. חושבים על מכונה עם מצבים. מצב אומר מה המכונה עושה עכשיו. במכונה דטרמיניסטית המצב הנוכחי והקלט קובעים בדיוק מה יהיה המצב הבא. תוכנית מח...
אלגוריתם אקראי
אלגוריתם אקראי הוא תוכנה שמשתמשת במקריות. מקריות = משהו שקורה בלי דפוס, כמו הטלת מטבע. מחלקים את האלגוריתמים האקראיים לשתי קבוצות עיקריות. חוקרים שואלים אם אלגוריתמים אלה יכולים להיות מהירים יותר מאלגוריתמים רגילים. יש שתי קטגוריות חשובות: BPP ו‑P. BPP = בעיות שנפתרות מהר בעזרת מקריות. P = בעיות ש...
אלגוריתם קירוב
אלגוריתם קירוב הוא דרך למצוא פתרון קרוב לטוב ביותר. זה שימושי כשהפתרון הטוב קשה למצוא. במדע המחשב יש בעיות שקשה מאוד לפתור בדיוק. קוראים להן NP-קשות (בעיות קשות). יש בעיות שאפשר רק לקרב, לא לפתור בדיוק. יש אלגוריתמים שנותנים תשובה קרובה בקבוע מסוים. יש גם סכמות שקוראות לפרמטר קטן ε, ומשפרות את הקר...
מיטוב אלגוריתמים
מיטוב פירושו לגרום לתוכנה לעבוד מהר יותר. (אופטימיזציה = שם בלועזית.) יש מושגים חשובים: אלגוריתם הוא סדרת צעדים לפתור בעיה. מעבד (CPU) הוא הלב של המחשב. מהדר הוא תוכנה שמתרגמת קוד למכונה. המעבד יכול לזכור מה קרה לפני ולנבא מה יקרה אחר כך. זה מקצר זמן עבודה. המהדר יכול לשנות את סדר הקוד או לשכפל ...
האלגוריתם של ג'ונסון
אלגוריתם ג'ונסון מוצא את הדרך הכי קצרה בין כל שתי נקודות בגרף. גרף הוא אוסף נקודות וקווים עם משקל. הרעיון הוא להשתמש בדייקסטרה. דייקסטרה מוצא דרכים קצרות, אבל עובד רק כשהמשקלים לא שליליים. לכן קודם עושים תיקון משקלים בעזרת בלמן‑פורד. בלמן‑פורד יכול לעבוד גם עם משקלים שליליים והוא גם מגלה אם יש מעגל...
האלגוריתם של קרוסקל
קרוסקל היא שיטה למצוא חיבור זול בין כל הנקודות בגרף. הגרף מורכב מקודקודים (נקודות) וקשתות (קווים) עם משקלים. המטרה היא לבחור קווים שמחברים את כל הנקודות. הסכום של המשקלים צריך להיות הכי קטן. איך עושים את זה: 1. ממוינים את כל הקווים לפי משקל מהקטן לגדול. 2. לוקחים את הקו הכי קטן כשרק הוא לא יוצר מע...
האלגוריתם של פרים
האלגוריתם של פרים מוצא את הדרך הזולה לחבר כל הנקודות ברשת. רשת זו נקראת גרף; קשת היא הקו שמחבר נקודות. מתחילים מנקודה אחת שבוחרים. בכל פעם בוחרים את הקו הכי קצר שיוצא מהחיבור שכבר בנו. אסור לבחור קווים שגורמים למעגל. האלגוריתם חמדן אומר: כרגע בחר את האפשרות הכי טובה. משתמשים במבנה שנקרא ערימה כדי למ...
יעילות אלגוריתמית
יעילות אלגוריתמית אומרת כמה משאבים אלגוריתם צורך. משאב הוא זמן או זיכרון. אלגוריתם הוא סדרת פעולות לפתור בעיה. לפעמים צריך לבחור בין פחות זמן ליותר זיכרון. ב-1843 כתבה עדה לאבלייס תוכנית למחשב מכני של בבג'. המחשבים הראשונים היו איטיים ובעלי מעט זיכרון. לכן המציאו אלגוריתמים חיסכוניים. גם היום חשוב ...
ALGOL
ALGOL פירושו ALGOrithmic Language. זו משפחה של שפות תכנות מהשנים הראשונות, משנות ה‑50. "שפת תכנות" היא שפה שאיתה כותבים הוראות למחשב. ALGOL היתה חשובה כי המציאה רעיונות רבים לראשונה. היא שימשה גם כדרך פשוטה לכתוב אלגוריתמים. "אלגוריתם" זה סדרת צעדים לפתור בעיה. לפעמים כותבים אלגוריתם בפסאודו‑קוד. פ...
ריצ'רד קארפ
ריצ'רד קארפ נולד ב-3 בינואר 1935 בבוסטון. הוא מדען מחשב. מדען מחשב הוא מי שחוקר מחשבים ותוכנות. זכה בפרס טורינג ב-1985. זהו פרס חשוב במדעי המחשב. למד בהרווארד והשלים דוקטורט במתמטיקה שימושית ב-1959. עבד במעבדות IBM. הפך לפרופסור באוניברסיטת ברקלי ב-1968. שהה ארבע שנים גם באוניברסיטת וושינגטון בסי...
עיבוד נתונים אוטומטי
עיבוד נתונים אוטומטי, או עיבוד נתונים, הופך נתונים למידע שימושי. פעם זה נעשה במכונות עם כרטיסים מנוקבים. כרטיסים מנוקבים הם כרטיסים עם חורים שאחסנו מידע. היום משתמשים במחשבים. נתונים הם מספרים או אותיות שמספרים על דברים בעולם. כדי לקבל מידע מפעילים אלגוריתם, רשימת צעדים ברורה. אפשר גם לעשות חישוב...
מחשוב
מחשב עוזר לעשות חישובים ולעבד מידע. מחשב מקבל קלט ומוציא פלט. מילה קשה: אלגוריתם, סדר של צעדים לפתור בעיה. מחשוב ענן נותן כוח מחשוב דרך האינטרנט. המשתמש לא צריך לקנות מחשבים גדולים. החומרה נמצאת במקום אחר, בחוות שרתים. דאטה סנטר, בניין עם הרבה מחשבים. וירטואלי, כמו משהו שאינו מוחשי, אבל פועל על מ...
סימון אסימפטוטי
סימון אסימפטוטי מסביר איך פונקציות מתנהגות כשמספרים גדלים מאוד. זה עוזר להשוות מי גדל מהר יותר. יש פונקציה שמשרתת כמדד להשוואה. בדוגמאות לרוב מדובר במספרים טבעיים וחיוביים. O אומר שפונקציה f לא תגדל מהר יותר מהמדרג g, אפילו אם נכפיל את g במספר קבוע. זה עוזר להתמקד בחלק הגדול ביותר בפונקציה. o אומ...
אתר היכרויות
אתר היכרויות הוא אתר או אפליקציה שעוזרת לאנשים לפגוש בני זוג. משתמשים עושים פרופיל עם מידע על עצמם. לפני האינטרנט פרסמו אנשים מודעות בעיתון. מאוחר יותר היו מערכות מחשב שהשוו בין אנשים בעזרת טפסים. האינטרנט הפך את זה ליותר פשוט. יש אתרים חינמיים ויש בתשלום. חלק מיועד לקבוצות מסוימות, כמו דתיים א...
בעיית הלוגריתם הבדיד
בעיית הלוגריתם הבדיד היא למצוא מספר x כך ש-g^x = h בתוך קבוצת מספרים סופית. זה קשה יותר מלוגריתם רגיל. חבורה ציקלית היא קבוצה של איברים שמתקדמים בחזקות. יוצר (פרימיטיבי) הוא איבר שיוצר את כל הקבוצה כאשר מעלים אותו בחזקות. עם המספר הראשוני p=97, יש קבוצה \mathbb{Z}_{97}^*. אם g=5 ו-h=35, אז 5^{32} ...
סיבוכיות מקום
סיבוכיות מקום אומרת כמה זיכרון צריך אלגוריתם. זיכרון זה הוא המקום בו הוא עושה חישובים, ולא המקום שבו שמים את הקלט. חוקרים משתמשים במודל פשוט שנקרא מכונת טיורינג. זו דמיון למחשב עם סרט ארוך שאפשר לקרוא ולכתוב. למדוד רק את "סרט העבודה" עוזר להעריך כמה זיכרון באמת צריך האלגוריתם. אם חזרו על אותו מצב ...
בעיית כיסוי קבוצות
יש קבוצה של פריטים שנקראת U. יש גם אוסף של קבוצות קטנות שנקרא S. כל קבוצה ב־S מכילה חלק מהפריטים ב־U. כיסוי הוא בחירה של קבוצות מ־S כך שכל הפריטים ב־U יהיו כלולים לפחות בקבוצה אחת. נניח U = {1,2,3,4,5}. הקבוצות ב־S הן: {1,2,3}, {2,4}, {3,4} ו־{4,5}. אם בוחרים את {1,2,3} ואת {4,5}, אז כל המספרים מ...
פסאודו קוד
פסאודו קוד נקרא גם קוד מדומה. זו דרך לכתוב הוראות לפתרון בעיה. הוראות כאלה נקראות אלגוריתם (סדרת צעדים לבצע משימה). הפסאודו קוד נראה כמו קוד של תוכנה, אבל הוא כתוב בשביל אנשים. מחשב לא יכול להריץ אותו בלי להמיר אותו לקוד אמיתי. כותבים בו פחות סימנים וטקסטים מסובכים. זה עוזר להבין מהר את הרעיון. מו...
אופטימיזציה קמורה
אופטימיזציה קמורה היא דרך למצוא פתרון טוב לבעיות מתמטיות. "אופטימיזציה" פירושו למצוא את הפתרון הכי טוב. "קמורה" פירושו שהקו בין שתי נקודות נשאר בתוך הצורה. בעיות קמורות נפוצות, ויש להן אלגוריתמים שמוצאים פתרון מהר. יתרון חשוב: כל מינימום מקומי הוא גם הכי טוב בכל הבעיה. זה אומר שאם מוצאים פתרון טוב ב...
תבנית:הידעת? 3 בספטמבר - סדרה 2
המילה "אלגוריתם" באה משמו של מוחמד אבן מוסא אל-ח'ואריזמי. הוא חי בבגדאד במאה התשיעית. כשהספר שלו על חישובים תורגם ללטינית, שמו הפך ל־Algoritmi. אנשים חשבו שזה שם של שיטות חישוב. המילה "אלגברה" באה מספר אחר שלו. שם הספר הוא "חיסאב אל-ג'אבר ואל-מוקאבלה". אל-ג'אבר פירושו "השלמה". זו פעולה שעוזרת לפש...
מחלק משותף מקסימלי
מחלק משותף מרבי הוא המספר הגדול ביותר שמחלק שני מספרים בלי שארית. לדוגמה, המחלק המשותף המרבי של 12 ו‑18 הוא 6. אם לשני מספרים יש את אותם גורמים ראשוניים (מספרים שאי אפשר לחלק אותם עוד), המשותף ביניהם נותן את ה‑gcd. אם אין גורם משותף גדול מ‑1, קוראים להם זרים (אין להם מחלק משותף גדול). אין צורך לפר...
ZPP
ZPP היא קבוצה של בעיות שמתקבלות על ידי אלגוריתם שאף פעם לא טועה. אלגוריתם הסתברותי עושה בחירות אקראיות, כמו הטלת מטבע. תוחלת זמן ריצה היא הזמן הממוצע שהאלגוריתם לוקח. בבעיות מסוימות יש פתרון מהיר שקובע תמיד את אותה תשובה. יש גם אלגוריתמים שמשתמשים באקראיות. חלקם יכולים לטעות לפעמים. ZPP שונה: הוא ת...
PP (מחלקת סיבוכיות)
PP היא קבוצה של בעיות שמחשבים עם מזל יכולים לפתור בזמן קצר. "מזל" כאן פירושו שהאלגוריתם עושה החלטות אקראיות. האלגוריתם עובד בכמות זמן שמתאימה לגודל הקלט. מחלקת PP אומרת: אם התשובה היא "כן", האלגוריתם צריך להגיד "כן" יותר מחצי מהפעמים. אם התשובה היא "לא", הוא לא אמור להגיד "כן" יותר מחצי מהפעמים. ...
RP
RP היא קבוצה של בעיות שמחשב יכול לנסות לפתור במהירות. "Randomized" פירושו שימוש במקריות. "Polynomial time" פירושו זמן סביר יחסית לגודל הבעיה. האלגוריתם משתמש במקריות. אם התשובה היא "כן", הוא אומר "כן" לפחות בחצי מהפעמים. אם התשובה היא "לא", הוא תמיד אומר "לא". כך הוא יכול לטעות רק כשאומר "לא". מריצי...
בעיית הסכומים החלקיים
בעיית הסכום החלקי שואלת: נתונה קבוצת מספרים. האם יש תת־קבוצה לא ריקה שסכומה הוא אפס? לדוגמה: בקבוצה {-7, -3, -2, 8, 5} יש את התת־קבוצה {-2, -3, 5} שסכומה הוא אפס. הבעיה קשה למצוא לה פתרון מהיר לכל קלט. לכן משתמשים בכמה שיטות שונות. שיטה פשוטה בודקת את כל תתי־הקבוצות. יש הרבה תתי־קבוצות, ולכן זה ל...
מתמטיקאי
מתמטיקאי הוא אדם שעוסק בבדיקת רעיונות מתמטיים. מתמטיקאים עובדים באוניברסיטאות. אוניברסיטה היא מקום ללימודים גבוהים. הם מלמדים וחוקרים. הם מגלים משפטים חדשים. הוכחה היא הסבר שמראה שמשהו נכון. לפעמים יש רעיון ללא הוכחה, זה נקרא השערה. גם בתעשייה עובדים מתמטיקאים. הם בונים אלגוריתמים, כלומר סדרת צעד...
קבוצה רקורסיבית
רקורסיבית (או כריעה) אומרת שיש אלגוריתם, סדרת הוראות, שמחליט אם מספר שייך לקבוצה. תת‑קבוצה S של המספרים הטבעיים היא רקורסיבית אם יש פונקציה ניתנת לחישוב f. פונקציה היא חוק שמקבל מספר ומחזיר מספר. f מחזירה 0 כש־x שייך ל‑S, ושונה מאפס אם לא. ...
למידת מכונה
למידת מכונה היא שיטה שבה מחשב לומד מדוגמאות. כלומר, במקום לתת למחשב כללים מדויקים, נותנים לו דוגמאות והוא מנסה להבין מה הכלל. מחשבים יכולים "ללמוד" כך שעם הזמן הם עושים עבודה טובה יותר. הדברים שמכונות לומדות יכולים לעשות: - לקרוא אותיות בתמונה (OCR). האותיות הן מה שהתוכנה מזהה. - להבין דיבור כד...
שיטת האב
שיטת האב היא דרך קצרה לדעת כמה זמן לוקח אלגוריתם שמחלק בעיות לבעיות קטנות. אלגוריתם רקורסיבי חוזר על עצמו על תת־בעיות. כדאי לזכור שלושה דברים שמשפיעים על הזמן: - כמה תת־בעיות יש (קוראים לזה a). - כמה קטנות הן התת־בעיות (קוראים לזה b). - כמה עבודה עושים בלי שוברים את הבעיה (קוראים לזה f(n)). אם ה...
שפת תכנות
שפת תכנות היא השפה שמספרת למחשב מה לעשות. "תחביר" (איך כותבים נכון) ו"סמנטיקה" (מה זה עושה) עוזרים להבין אותה. ברוב הקורסים לומדים קודם תוכנית שמדפיסה "hello world". שפה טובה מקשרת בין המחשב למתכנת. היא עוזרת לארגן רעיונות ולכתוב הוראות ברורות. יש בה פקודות של לולאה (חוזר על פעולה) ותנאי (עושה רק כ...
מדעי המחשב
מדעי המחשב חוקרים איך מחשבים פועלים ומשתמשים בהם. הנושאים כוללים תכנות, אלגוריתמים (הוראות צעד־צעד לפתרון), ורשתות. הרעיון של מחשב קיים כבר מזמן. צ'ארלס בבג' תכנן מחשב מכני. עדה לאבלייס כתבה תוכנה למחשב שלו. במלחמות הפיתוח האיץ את המחקר. דוגמה היא אניגמה, מכונת הצפנה גרמנית. אלן טיורינג עזר לפצח...
הבעיה העשירית של הילברט
ה"בעיה העשירית" שאלה דבר פשוט למראית עין. היא ביקשה חוק שמסביר אם למשוואה של מספרים שלמים יש פתרון. חוק כזה נקרא אלגוריתם - זה כלל שמחשב יכול לבצע. הילברט הציג את השאלה ב-1900. הרבה שנים חשבו שאולי יש חוק כזה. אחרי זמן רב הוכיחו שזה בלתי אפשרי. מתמטיקאים הבינו שיש קבוצות של מספרים שניתן "לרשום" על...
משוואה דיופנטית
משוואה דיופנטית היא משוואה שמחפשים לה פתרונות שהם מספרים שלמים. השם מגיע מהמתמטיקאי דיופנטוס. יש משוואות פולינומיות ומשוואות שאינן פולינומיות. לדוגמה a^x = c + n y היא משוואה עם חזקות. חלק מהמשוואות האלה קלות, וחלקן מאוד קשות. משוואה מפורסמת היא x^2+y^2=z^2. פתרונותיה נקראים שלשות פיתגוריות. יש נו...
אוקלידס
אוקלידס (365, 275 לפנה"ס) היה מתמטיקאי יווני מפורסם. הוא עובד באלכסנדריה במצרים. אנו יודעים מעט על חייו. רוב המידע אודותיו הגיע מאנשים שכתבו עליו מאות שנים אחרי מותו. יתכן שלמד באקדמיה של אפלטון. אוקלידס כתב ספר גדול בשם "היסודות". הספר מסדר רעיונות במתמטיקה בצורה ברורה. הוא השתמש באקסיומות. אקסיו...
שיטת הסימפלקס
סימפלקס (Simplex) היא שיטה לפתור בעיות בתכנון ליניארי. תכנון ליניארי הוא סוג של בעיות מתמטיות. השיטה הומצאה על ידי ג'ורג' דניזיג בשנות ה־40. הרבה תוכנות משתמשות בה. האלגוריתם עובר בין "פתרונות פינתיים", נקודות בקצוות. התחום קמורי, כלומר צורה חלקה. לכן הפתרון הכי טוב נמצא באחת הנקודות האלה....