אלגוריתם, פרוצדורה שיטתית המייצרת - במספר סופי של שלבים - את התשובה לשאלה או לפיתרון של בעיה. השם מקורו בתרגום הלטיני, אלגוריטמי דה נומרו אינדורום, מתוך החיבור האריתמטי של המתמטיקאי המוסלמי אל-ח'וריזמי מהמאה ה -9 "אל-ח'וריזמי בנוגע לאמנות ההינדואית ההינדית".
מדעי המחשב: אלגוריתמים ומורכבות
אלגוריתם הוא הליך ספציפי לפיתרון בעיה חישובית מוגדרת היטב. פיתוח וניתוח של אלגוריתמים הוא מהותי
לשאלות או בעיות עם מערך מוגדר של מקרים או ערכים בלבד, קיים תמיד אלגוריתם (לפחות באופן עקרוני); זה מורכב מטבלת ערכים של התשובות. באופן כללי, אין זה הליך טריוויאלי כזה לענות על שאלות או בעיות שיש בהן אינסוף מקרים או ערכים שיש לקחת בחשבון, כגון "האם המספר הטבעי (1, 2, 3, …) הוא ראש הממשלה?" או "מה המחלק הנפוץ הגדול ביותר של המספרים הטבעיים a ו- b?" הראשונה מבין השאלות הללו שייכת לכיתה הנקראת להחלפה; אלגוריתם שמייצר תשובה כן או לא נקרא נוהל החלטה. השאלה השנייה שייכת למחלקה הנקראת computable; אלגוריתם שמוביל לתשובה ספציפית נקרא נוהל חישוב.
אלגוריתמים קיימים להרבה סוגים אינסופיים של שאלות; אלמנטים של אוקליד, שפורסמו כ -300 לפנה"ס, הכילו אחד למציאת המחלק המשותף הגדול ביותר מבין שני מספרים טבעיים. כל תלמיד בבית ספר יסודי נקדח בחטיבה ארוכה, המהווה אלגוריתם לשאלה "כאשר מחלקים מספר טבעי a במספר טבעי טבעי b, מהם המנה והשאר?" השימוש בהליך חישובי זה מוביל לתשובה לשאלה הנחזרת "האם b מחלק a?" (התשובה היא כן אם השאר אפס). יישומים חוזרים ונשנים של אלגוריתמים אלה מניבים בסופו של דבר את התשובה לשאלה הנחוצה "האם זה דבר טוב?" (התשובה היא לא אם a מתחלק למספר טבעי קטן יותר מלבד 1).
לפעמים אלגוריתם לא יכול להתקיים לפיתרון סוג בעיות אינסופי, במיוחד כאשר מוגבלת הגבלה נוספת בשיטה המקובלת. למשל, שתי בעיות מהתקופה של אוקליד הדורשות שימוש במצפן וישר (שליט לא מסומן) - חתך זווית ובניית ריבוע בשטח שווה למעגל נתון - נמשכו במשך מאות שנים עד שהוצגו כבלתי אפשריות. בסוף המאה העשרים הציע המתמטיקאי הגרמני המשפיע דייוויד הילברט 23 בעיות למתמטיקאים לפתור במאה הקרובה. הבעיה השנייה ברשימתו ביקשה לחקור את עקביות האקסיומות של חשבון. לרוב המתמטיקאים לא היה ספק רב בהשגת המטרה בסופו של דבר עד שנת 1931, אז הוכיח הלוגיקן יליד אוסטריה קורט גוטל את התוצאה המפתיעה שיש להתקיים הצעות חשבון (או שאלות) שלא ניתן להוכיח או להפריך. בעיקרו של דבר, כל הצעה כזו מובילה להליך קביעה שאינו מסתיים (מצב המכונה בעיית ההפסקה). במאמץ שלא הצליח לברר לפחות אילו הצעות אינן ניתנות לפתור, הגדיר המתמטיקאי והלוגיקן האנגלי אל טיורינג בקפדנות את התפיסה המובנת באופן רופף של אלגוריתם. למרות שטורינג בסופו של דבר הוכיח כי חייבים להתקיים הצעות בלתי ניתנות להחלפה, התיאור שלו את התכונות המהותיות של כל מכונת אלגוריתמים למטרות כלליות, או מכונה טיורינג, הפך לבסיס של מדעי המחשב. כיום נושאי הפירוק והחישוב הם מרכזיים בעיצוב תוכנית מחשב - סוג מיוחד של אלגוריתם.
