אלגוריתם

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

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

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

תיאור ויזואלי של אלגוריתם ניתן באמצעות תרשים זרימה.

מקור המונח

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