אלגוריתם

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

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

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

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

מחלקות של אלגוריתמים

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

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

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

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

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

דוגמאות לאלגוריתמים

• אלגוריתם אוקלידס, למציאת מחלק משותף מקסימלי, מופיע בספרו של אוקלידס, "היסודות", ונחשב לאלגוריתם הקדום ביותר.
• הנפה של ארטוסתנס, למציאת מספרים ראשוניים.
• אלגוריתם מילר-רבין - הבודק בצורה אקראית ומהירה יחסית האם מספר נתון הוא ראשוני.
• אלגוריתם לפירוק לגורמים.
• אלגוריתם הסימפלקס, המשמש לפתרון בעיות של תכנון לינארי.
• שיטת הלכסון של גאוס - אלגוריתם למציאת פיתרונות של מערכת משוואות לינאריות.
• אלגוריתם למציאת הקמור של קבוצת נקודות במישור, למשל אלגוריתם הסריקה של גראהם.
• האלגוריתם של דייקסטרה למציאת מסלול בעל משקל מינימלי מצומת כלשהו בגרף ממושקל לשאר הצמתים בו.
• אלגוריתמים למיון של נתונים וחיפוש ברשימות ממוינות (יש אלגוריתמים רבים למטרות אלה).
• שיטת ניוטון-רפסון למציאת שורש של פונקציה ממשית. זהו תהליך המתקרב אסימפטוטית לתוצאה המדויקת, וכדי להופכו לאלגוריתם יש להוסיף לו תנאי עצירה, כגון "הפסק כשהשגיאה קטנה מ-$\ 10^{-15}$".

תוכנית מחשב

ערך מורחב – תוכנית מחשב

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

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

ראו גם

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

• אלגוריתמים גנטיים
• אלגוריתם חסר נעילות
• אלגוריתם דטרמיניסטי

לקריאה נוספת

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

קישורים חיצוניים

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

• אלגוריתם, באנציקלופדיה ynet
• קורס באלגוריתמים בArsDigita (הרצאות מוקלטות וחומרים)