הצגת המקור של הדף "אלגוריתם"

'''אלגוריתם''' הוא דרך שיטתית, [[אבסטרקציה (מדעי המחשב)|אבסטרקטית]] וחד-משמעית לביצוע של משימה מסוימת, במספר סופי של צעדים, המכסה את כלל האפשרויות הרלוונטיות.<ref>{{צ-ספר|מחבר=Donald E. Knuth|שם=The Art of Computer Programming. Vol. 1: Fundamental Algorithms. 3rd ed.|מקום הוצאה=Reading, MA|מו"ל=Addison-Wesley|שנת הוצאה=1997|עמ=1-9|קישור=https://seriouscomputerist.atariverse.com/media/pdf/book/Art%20of%20Computer%20Programming%20-%20Volume%201%20(Fundamental%20Algorithms).pdf}}</ref><ref>{{צ-ספר|שם=Introduction to Algorithms. 3rd ed.|קישור=http://ir.harambeeuniversity.edu.et/bitstream/handle/123456789/1552/Introduction%20to%20Algorithms%252C%20Third%20Edition%20(%20PDFDrive.com%20).pdf|מו"ל=MIT Press|שנת הוצאה=2009|ISBN=978-0-262-53305-8|מחבר=Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein|מקום הוצאה=Cambridge, MA|עמ=5-10}}</ref><ref>{{צ-מאמר|מחבר=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|קישור=https://maths-code.fr/NSI/terminale/calculabilite/Turing_Paper_1936.pdf}}</ref><ref>{{צ-ספר|מחבר=Edsger W. Dijkstra|שם=A Discipline of Programming|מקום הוצאה=Upper Saddle River, NJ|מו"ל=Prentice-Hall|שנת הוצאה=1976|קישור=https://seriouscomputerist.atariverse.com/media/pdf/book/Discipline%20of%20Programming.pdf}}</ref> [[מתכון]] להכנת [[עוגה]] דומה לאלגוריתם, אך הוא לא תמיד חד-משמעי (למשל, מה בדיוק המשמעות של "לערבב עד שמתקבל מרקם אחיד") ואינו מכסה את כל האפשרויות הרלוונטיות (למשל, מה עושים כשחסר מרכיב). אלגוריתם תקין חייב להיות מתוכנן כך שלא יצריך חשיבה אנושית או יצירתיות, גם במקרים של תקלות, שגיאות או מקרי קצה. בדרך-כלל משמש מונח זה לכינוי שיטת [[פתרון בעיות]] ב[[מתמטיקה]] או ב[[מדעי המחשב]] ובעיקר ביחס לנתונים תוויים כלשהם. האלגוריתם הוא אבסטרקטי במובן זה שהוא מתייחס למתמטיקה נתונה אבל לא לשפת תכנות מסוימת או למקרה גשמי מסוים, אלא ניתן לתיאור וליישום על בסיס אותה מתמטיקה במגוון שפות ודרכים ועבור מגוון מקרים רלוונטיים.

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

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

תיאור [[החזיית מידע|ויזואלי]] ב'''אלגוריתמיקה''' ניתן באמצעות [[תרשים זרימה]].

==מקור המונח==
מקור המילה בהגייה [[לטינית]] של שם ה[[מתמטיקאי]] הפרסי המוסלמי בן [[המאה ה-9|המאה התשיעית]], [[מוחמד אבן מוסא אל-ח'ואריזמי]].<ref>{{צ-ספר|שם=Digital Keywords|קישור=http://dx.doi.org/10.1515/9781400880553-004|מו"ל=[[Princeton University Press]]|שנת הוצאה=2016-12-31|מקום הוצאה=Princeton|ISBN=978-1-4008-8055-3|עמ=18–30|מחבר=Tarleton Gillespie}}</ref> שחי ב[[בגדאד]] ב[[המאה ה-9|מאה התשיעית]]. כאשר ספרו על שיטות [[חישוב]] [[תרגום|תורגם]] ללטינית, נכתב שמו של אל ח'ואריזמי כ"אלגוריתמי" (ככל הנראה שיבוש בתעתיק שנגרם מהחלפת האות '''[[خ]]'''-ח', באות '''[[ج]]''' -ג, ולאחר מכן החלפת האות '''[[ز]]'''-ז באות '''[[ذ]]'''-ד' -שבשפות אירופיות נהגית כ-th וכך ״אל-'''ח''''וארי'''ז'''מי״ הפך ל״אל-'''ג'''ורי'''ת''''מי״), והקוראים טעו לחשוב שמדובר ב[[צורת רבים]] של המושג שיטת חישוב. המילה [[אלגברה]] נלקחה מספר אחר שלו - "חיסאב אל-ג'אבר ואל-מוקאבלה". על פי הספר, פעולת ההשלמה, אל-ג'אבר, היא אחת משתי הפעולות שניתן לבצע על [[משוואה]] על מנת לפשט אותה.

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

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

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

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

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

==דוגמאות לאלגוריתמים==
*[[אלגוריתם אוקלידס]], למציאת [[מחלק משותף מקסימלי]], מופיע בספרו של [[אוקלידס]], "היסודות", ונחשב לאלגוריתם הקדום ביותר.
*[[הנפה של ארטוסתנס]], למציאת מספרים ראשוניים.
*[[אלגוריתם מילר-רבין]] - הבודק בצורה אקראית ומהירה יחסית האם מספר נתון הוא ראשוני.
*אלגוריתמים שונים ל[[פירוק לגורמים של מספר שלם]].
*[[אלגוריתם הסימפלקס]], המשמש לפתרון בעיות של [[תכנון ליניארי]].
*[[שיטת החילוץ של גאוס]] - אלגוריתם למציאת פתרונות של [[מערכת משוואות ליניאריות]].
*אלגוריתם למציאת ה[[קמור]] של קבוצת נקודות במישור, למשל אלגוריתם [[הסריקה של גראהם]].
*[[האלגוריתם של דייקסטרה]] למציאת מסלול בעל משקל מינימלי מצומת כלשהו ב[[גרף ממושקל]] בעל משקלים אי שליליים לשאר הצמתים בו.
*אלגוריתמים ל[[מיון (מדעי המחשב)|מיון]] של נתונים וחיפוש ברשימות ממוינות (יש אלגוריתמים רבים למטרות אלה).
*[[שיטת ניוטון-רפסון]] למציאת שורש של [[פונקציה]] ממשית. זהו תהליך המתקרב אסימפטוטית לתוצאה המדויקת, וכדי להופכו לאלגוריתם יש להוסיף לו [[תנאי עצירה]], כגון "הפסק כשהשגיאה קטנה מ-<math>10^{-15}</math>".
*[[אלגוריתם רשויות ורכזים|אלגוריתם חיפוש - אלגוריתם רשויות ורכזים]]
*[[אלגוריתם קורי העכביש]] (COBWEB) משמש לסידור מערכת גדולה שבה קיימת היררכיה של קיבוץ קונספטואלי.

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

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

==ראו גם==
{{תקציר פורטל|מדעי המחשב}}
*[[היוריסטיקה]]
*[[טראבל שוטינג]]
*[[תרשים זרימת נתונים]]

==לקריאה נוספת==
*קורמן, לייזרסון, ריבסט, '''מבוא לאלגוריתמים''', [[הוצאת MIT]], תורגם לעברית על ידי [[האוניברסיטה הפתוחה]].
*ג'ק וינשטין, '''מבני נתונים ומבוא לאלגוריתמים''', מדריך [[למידה]] לספר "מבוא לאלגוריתמים".
*ג'ון קליינברג, אווה טארדוש, '''פיתוח אלגוריתמים''', הוצאת "Addison Wesley", תורגם לעברית על ידי האוניברסיטה הפתוחה.
{{-}}

==קישורים חיצוניים==
{{מיזמים|ויקימילון=אלגוריתם|ויקיספר=מבני נתונים ואלגוריתמים - מחברת קורס}}
*{{אנציקלופדיה למתמטיקה|Algorithm}}
*[http://aduni.org/courses/algorithms/ קורס באלגוריתמים ב-ArsDigita] (הרצאות מוקלטות וחומרים באנגלית)
*{{MathWorld}}
* {{בריטניקה}}
* {{דף שער בספרייה הלאומית|987007293927505171|אלגוריתמים}}
<div class="mw-content-ltr">
* {{JSTOR|[[דונלד קנות'|Donald E. Knuth]]|Algorithms|24953982|Scientific American|Vol. 236, No. 4 (April 1977), pp. 63-81}}
</div>

==הערות שוליים==
{{הערות שוליים}}

{{מדעי המחשב}}

{{בקרת זהויות}}

[[קטגוריה:אלגוריתמים|*]]
[[קטגוריה:לוגיקה מתמטית]]
[[קטגוריה:מילים וביטויים בערבית]]