אלגוריתם

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

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

[עריכה] מחלקות של אלגוריתמים

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

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

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

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

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

[עריכה] דוגמאות לאלגוריתמים

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