אלגוריתם
אלגוריתם הוא דרך שיטתית, אבסטרקטית וחד-משמעית לביצוע של משימה מסוימת, במספר סופי של צעדים, המכסה את כלל האפשרויות הרלוונטיות.[1][2][3][4] מתכון להכנת עוגה דומה לאלגוריתם, אך הוא לא תמיד חד-משמעי (למשל, מה בדיוק המשמעות של "לערבב עד שמתקבל מרקם אחיד") ואינו מכסה את כל האפשרויות הרלוונטיות (למשל, מה עושים כשחסר מרכיב). אלגוריתם תקין חייב להיות מתוכנן כך שלא יצריך חשיבה אנושית או יצירתיות, גם במקרים של תקלות, שגיאות או מקרי קצה. בדרך-כלל משמש מונח זה לכינוי שיטת פתרון בעיות במתמטיקה או במדעי המחשב ובעיקר ביחס לנתונים תוויים כלשהם. האלגוריתם הוא אבסטרקטי במובן זה שהוא מתייחס למתמטיקה נתונה אבל לא לשפת תכנות מסוימת או למקרה גשמי מסוים, אלא ניתן לתיאור וליישום על בסיס אותה מתמטיקה במגוון שפות ודרכים ועבור מגוון מקרים רלוונטיים.
כל תוכנית מחשב היא אלגוריתם, או אוסף של אלגוריתמים. בתיאור זה של האלגוריתמים יש עמימות מסוימת. כדי לפזר עמימות זו הגה טיורינג את "מכונת טיורינג", שהיא "מכונה" תאורטית המסוגלת, עקרונית, לבצע כל אלגוריתם. במקביל לטיורינג, הגו עוד מתמטיקאים ולוגיקנים הגדרות למושג האלגוריתם והתברר שכל ההגדרות שלהם היו שקולות זו לזו. לכן, היום אלגוריתם הוא מה שכל אחת מההגדרות האלו מתארות, ובפרט, מה שמכונת טיורינג מסוגלת לבצע.
קיימות משימות מוגדרות שלא קיים פתרון אלגוריתמי עבורן, וכבר טיורינג הוכיח זאת (ענף מדעי המחשב העוסק בסוגיה זו קרוי חישוביות). מצד שני, לביצועה של משימה מסוימת ייתכנו אלגוריתמים אחדים, מצב שמצדיק בחינה של יעילות האלגוריתמים, בהתאם למדדי יעילות נאותים. במסגרת מדעי המחשב נבחנת יעילותם של אלגוריתמים (בענף הקרוי סיבוכיות חישובית) על-פי הזמן והזיכרון הנדרשים לביצוע האלגוריתם כפונקציה של גודל הקלט לאלגוריתם. דהיינו, ככל שזמן הריצה של האלגוריתם ביחס לגודל הקלט קטן יותר, האלגוריתם ייחשב טוב יותר. מקובל להגדיר אלגוריתמים כ"יעילים" אם זמן הריצה שלהם פולינומי בגודל הקלט שלהם.
תיאור ויזואלי באלגוריתמיקה ניתן באמצעות תרשים זרימה.
מקור המונח
עריכהמקור המילה בהגייה לטינית של שם המתמטיקאי הפרסי המוסלמי בן המאה התשיעית, מוחמד אבן מוסא אל-ח'ואריזמי.[5] שחי בבגדאד במאה התשיעית. כאשר ספרו על שיטות חישוב תורגם ללטינית, נכתב שמו של אל ח'ואריזמי כ"אלגוריתמי" (ככל הנראה שיבוש בתעתיק שנגרם מהחלפת האות خ-ח', באות ج -ג, ולאחר מכן החלפת האות ز-ז באות ذ-ד' -שבשפות אירופיות נהגית כ-th וכך ״אל-ח'ואריזמי״ הפך ל״אל-גורית'מי״), והקוראים טעו לחשוב שמדובר בצורת רבים של המושג שיטת חישוב. המילה אלגברה נלקחה מספר אחר שלו - "חיסאב אל-ג'אבר ואל-מוקאבלה". על פי הספר, פעולת ההשלמה, אל-ג'אבר, היא אחת משתי הפעולות שניתן לבצע על משוואה על מנת לפשט אותה.
מחלקות של אלגוריתמים
עריכהבהגדרתו הבסיסית, נדרשות מאלגוריתם שתי דרישות שמבטיחות את איכות ביצועיו: נדרש כי לכל קלט שהוא מקבל האלגוריתם יגיע אל סופו בשלב כלשהו, וכי לאחר שיסיים, התשובה אותה יחזיר היא התשובה הנכונה. טיורינג הוכיח כי קיימות בעיות כדוגמת בעיית העצירה שאותן לא מסוגל המודל של מכונת טיורינג לפתור בהינתן דרישות אלו.
עדיין נהוג לדרוש מאלגוריתם לעצור עבור כל קלט, אחרת תוכניות המחשב שמממשות את האלגוריתם עשויות להיקלע ללולאה אינסופית. עם זאת, קיימות תוכניות מחשב שאמורות להיות מסוגלות לרוץ לנצח (למשל, מערכת ההפעלה של המחשב) וניתן להגדיר גם אלגוריתמים שרצים לנצח ומוציאים פלט בצורה מתמדת תוך כדי הריצה.
דרך נוספת לקטלג אלגוריתמים היא חלוקתם לאלגוריתמים דטרמיניסטיים (באנגלית: deterministic algorithm) ולאלגוריתמים אקראיים (רנדומליים, באנגלית: randomized algorithm). הקטגוריה הראשונה מתייחסת לאלגוריתמים אשר פעולתם תלויה בקלט בלבד (כלומר, שתי הפעלות של האלגוריתם על קלט זהה יניבו תמיד את אותה התוצאה), ואילו הקטגוריה השנייה מתייחסת לאלגוריתמים אשר עשויים "להטיל מטבעות", דהיינו: לקבל החלטות באקראי (ולפיכך ייתכן ששתי הפעלות של האלגוריתם על אותו הקלט יניבו תוצאות שונות). ישנם שני סוגים עיקריים של אלגוריתמים אקראיים: אלגוריתמי מונטה קרלו, אשר מאפשרים סיכוי קטן לטעות בתשובה שהם מחזירים (למשל, אלגוריתם מילר-רבין), ואלגוריתמי לאס וגאס אשר אין סיכוי שיטעו, אך קיים סיכוי קטן שזמן הריצה שלהם יהיה ארוך מאוד. בשתי המחלקות ישנם אלגוריתמים רבים שהסיכוי לבעיות בהרצתם הוא אפסי, מה שהופך אותם לשימושיים מאוד בפועל.
משפחות נוספות של אלגוריתמים מוגדרות על פי "שיטת פעולתם", או במילים אחרות, הכללה של הטכניקה שלהם. משפחות אלה כוללות: אלגוריתמים רקורסיביים בכלל ואלגוריתמי הפרד ומשול (divide and conquer), אלגוריתמים חמדנים, אלגוריתמי תכנות דינמי (באנגלית: dynamic programming, מינוח לא מוצלח גם באנגלית ולכן יש המכנים זאת תכנון דינאמי).
ככלל, מטרתם של אלגוריתמים למצוא פתרון אופטימלי לבעיה נתונה, אולם אלגוריתמים רבים, המוגדרים כאלגוריתמי קירוב (approximation algorithms באנגלית) מוצאים פתרון שאינו פתרון אופטימלי - על פי רוב על מנת לקצר את זמן הריצה של האלגוריתם או על מנת לחשב באופן יעיל בעיה שאחרת היא קשה לחישוב (ולרוב: NP-קשה).
דוגמאות לאלגוריתמים
עריכה- אלגוריתם אוקלידס, למציאת מחלק משותף מקסימלי, מופיע בספרו של אוקלידס, "היסודות", ונחשב לאלגוריתם הקדום ביותר.
- הנפה של ארטוסתנס, למציאת מספרים ראשוניים.
- אלגוריתם מילר-רבין - הבודק בצורה אקראית ומהירה יחסית האם מספר נתון הוא ראשוני.
- אלגוריתמים שונים לפירוק לגורמים של מספר שלם.
- אלגוריתם הסימפלקס, המשמש לפתרון בעיות של תכנון ליניארי.
- שיטת החילוץ של גאוס - אלגוריתם למציאת פתרונות של מערכת משוואות ליניאריות.
- אלגוריתם למציאת הקמור של קבוצת נקודות במישור, למשל אלגוריתם הסריקה של גראהם.
- האלגוריתם של דייקסטרה למציאת מסלול בעל משקל מינימלי מצומת כלשהו בגרף ממושקל בעל משקלים אי שליליים לשאר הצמתים בו.
- אלגוריתמים למיון של נתונים וחיפוש ברשימות ממוינות (יש אלגוריתמים רבים למטרות אלה).
- שיטת ניוטון-רפסון למציאת שורש של פונקציה ממשית. זהו תהליך המתקרב אסימפטוטית לתוצאה המדויקת, וכדי להופכו לאלגוריתם יש להוסיף לו תנאי עצירה, כגון "הפסק כשהשגיאה קטנה מ- ".
- אלגוריתם חיפוש - אלגוריתם רשויות ורכזים
- אלגוריתם קורי העכביש (COBWEB) משמש לסידור מערכת גדולה שבה קיימת היררכיה של קיבוץ קונספטואלי.
תוכנית מחשב
עריכה
ערך מורחב – תוכנית מחשב
טכניקה נפוצה למימוש של אלגוריתמים היא כתיבת תוכנית מחשב העושה זאת. מבני הנתונים, הפקודות ומבני הבקרה של שפת תכנות נתונה משפיעים על מידת הקושי במימושו של אלגוריתם נתון בשפה זו. כשלב ביניים במעבר מהגדרה מילולית של אלגוריתם למימושו בשפת תכנות משמש לעיתים פסאודו קוד - תיאור המשתמש בקונבנציות של שפות תכנות, אך מיועד לקריאה של בני אדם ולא לקריאה על ידי מחשב.
תזת צ'רץ'-טיורינג קושרת בין ההגדרה הפורמלית של אלגוריתם כהליך שניתן לביצוע על ידי מכונת טיורינג, לבין אלגוריתם הממומש על ידי תוכנית מחשב. התזה קובעת שכל אלגוריתם ניתן למימוש כתוכנית מחשב, וכל תוכנית מחשב מממשת אלגוריתם.
ראו גם
עריכה|
עיינו גם בפורטל
פורטל מדעי המחשב הוא שער לכל הנושאים הקשורים במדעי המחשב. ניתן למצוא בו קישורים אל תחומי המשנה של הענף, מושגי יסוד בתחום, מדענים חשובים ועוד. |
לקריאה נוספת
עריכה- קורמן, לייזרסון, ריבסט, מבוא לאלגוריתמים, הוצאת MIT, תורגם לעברית על ידי האוניברסיטה הפתוחה.
- ג'ק וינשטין, מבני נתונים ומבוא לאלגוריתמים, מדריך למידה לספר "מבוא לאלגוריתמים".
- ג'ון קליינברג, אווה טארדוש, פיתוח אלגוריתמים, הוצאת "Addison Wesley", תורגם לעברית על ידי האוניברסיטה הפתוחה.
קישורים חיצוניים
עריכה
- אלגוריתם, באתר אנציקלופדיה למתמטיקה (באנגלית)
- קורס באלגוריתמים ב-ArsDigita (הרצאות מוקלטות וחומרים באנגלית)
- אלגוריתם, באתר MathWorld (באנגלית)
- אלגוריתם, באתר אנציקלופדיה בריטניקה (באנגלית)
אלגוריתמים, דף שער בספרייה הלאומית
- Donald E. Knuth, Algorithms, Scientific American, Vol. 236, No. 4 (April 1977), pp. 63-81, in JSTOR
הערות שוליים
עריכה- ^ Donald E. Knuth, The Art of Computer Programming. Vol. 1: Fundamental Algorithms. 3rd ed., Reading, MA: Addison-Wesley, 1997, עמ' 1-9
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein, Introduction to Algorithms. 3rd ed., Cambridge, MA: MIT Press, 2009, עמ' 5-10, ISBN 978-0-262-53305-8
- ^ A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society s2-42, 1937, עמ' 230–265 doi: 10.1112/plms/s2-42.1.230
- ^ Edsger W. Dijkstra, A Discipline of Programming, Upper Saddle River, NJ: Prentice-Hall, 1976
- ^ Tarleton Gillespie, Digital Keywords, Princeton: Princeton University Press, 2016-12-31, עמ' 18–30, ISBN 978-1-4008-8055-3