Алгоритъм (от името на учения ал–Хорезми) е термин от математиката, информатиката, лингвистиката и други области, с който се описва сложно действие чрез редица от елементарни (достатъчно прости) действия, които изпълняващият може да извърши в последователни стъпки без допълнителни обяснения. Обикновено изпълнението на алгоритъма включва изчисление или обработка на данни.
По-строго дефинирано, алгоритъмът е ефективен метод за изчисляване на функция, който може да бъде изразен в рамките на крайно време и пространство и чрез добре дефиниран формален език. Започвайки от начално състояние и входни данни (понякога празни), инструкциите описват пресмятания, чието изпълнение преминава през краен брой добре дефинирани последователни състояния и завършва с крайно състояние, като в процеса се получават крайни резултати. Не е задължително преходът между състоянията да е детерминиран (еднозначно определен): някои алгоритми, известни като вероятностни алгоритми, съдържат елемент на случайност.
Концепцията за алгоритмите съществува от векове, но частичното формулиране на понятието започва с опитите да се реши 10-ия проблем на Хилберт – „Задача за разрешимост на диофантово уравнение“, поставен от Давид Хилберт през 1900 година на Втория световен конгрес по математика в Париж. Последващите формулировки, при които се цели дефинирането на „ефективна изчислимост“ или „ефективен метод“, включват рекурсивните функции на Ербран-Гьодел-Клини от 1930, 1934 и 1935 година, ламбда смятането на Алонсо Чърч от 1936 година, „Формулировка 1“ на Емил Пост от 1936 година и машината на Тюринг от 1936 – 1937 и 1939 година. Създаването на формална дефиниция на алгоритъм, съответстваща на интуитивното понятие, остава отворен въпрос и в наши дни.
Неформална дефиниция При все че няма общоприета формална дефиниция на алгоритъм, неформално понятието може да се определи като „набор от правила, които точно дефинират някаква поредица от операции“. Това определение обхваща всички компютърни програми, включително тези, които не извършват числени изчисления, стига те да прекратяват работа след краен брой операции.
Класически пример за „алгоритъм“ е алгоритъмът на Евклид чрез изваждане за намиране на най-големия общ делител (НОД) на две цели числа, по-големи от 1. При него се изпълнява следната поредица от стъпки: На стъпка i, се дели X на Y и остатъкът се означава с R. Ако R = 0, резултатът на задачата е Y. В противен случай, резултатът съвпада с НОД на числата R и Y. Такъв алгоритъм, при който за намирането на решение е необходимо да бъде решена аналогична, но „по-малка“ задача, се нарича рекурсивен.
Американските учени Джордж Булос и Ричард Джефри дават следното неформално определение за алгоритъм в своя класически учебник по математическа логика:
Никое човешко същество не може да пише достатъчно бързо или достатъчно дълго, или достатъчно дребно, за да изброи всички елементи на дадено изброимо безкрайно множество, изписвайки техните имена, едно след друго, с една и съща нотация. Но хората могат да направят нещо също толкова полезно в случая с някои изброими безкрайни множества – те могат да дадат експлицитни указания за определяне на n-тия елемент на множеството за произволно крайно n. Такива указания могат да бъдат дадени съвсем експлицитно, във форма, в която могат да бъдат изпълнени от изчислителна машина или от човек, който може да извършва само съвсем елементарни операции със символи.
Изброимо безкрайно множество е такова множество, за чиито елементи може да се дефинира биективно съответствие с множеството на естествените числа. Така според Булос и Джефри алгоритъмът съдържа инструкции за процес, който „създава“ резултатни цели числа от произволно входно цяло число (или входни числа), което на теория може да бъде произволно голямо. По този начин алгоритъмът може да бъде алгебрично уравнение, като y = m + n – две произволни „входни променливи“ m и n, които създават резултат y. В същото време опитите на различни автори да дефинират понятието показват, че под „алгоритъм“ се разбира много повече от това:
Точни указания (на език, разбираем за „компютъра“) за бърз, ефективен, „добър“ процес, който специфицира „движенията“ на „компютъра“ (машина или човек, оборудван с необходимата вътрешна информация и способности), за да намери, декодира и обработи произволни входни числа/символи m е n, символи + и = ... и „ефективно“ да произведе, за „разумно“ време, краен резултат y на определено място и в определен формат.
Концепцията за „алгоритъм“ се използва и за дефиниране на понятието решимост, което играе централна роля за обяснението как формалните системи възникват от малък набор аксиоми и правила. В логиката времето, необходимо за изпълнение на даден алгоритъм, не може да се измери, тъй като то не е свързано с обичайното физично измерение. Подобни несигурности, които характеризират текущите изследвания в тази област, водят до липсата на дефиниция за „алгоритъм“, която да съответства както на конкретната, така и на абстрактната употреба на термина.
Формализации Алгоритмите са от съществено значение за начините, по които компютрите обработват информацията. Много компютърни програми съдържат алгоритми, които определят специфични инструкции, които компютърът трябва да изпълни в строго определен ред, за да се реши дадена задача. В този смисъл, алгоритъмът може да се разглежда като произволна поредица от операции, които могат да се симулират от пълна по Тюринг система. Към този възглед се придържат автори като Мински, Савидж и Гуревич:
Но ние също така ще твърдим, като Тюринг..., че всяка процедура, която може „естествено“ да бъде наречена ефективна, всъщност може да бъде реализирана от (проста) машина. Макар че това може да изглежда крайно, аргументите... в полза на това е трудно да се отхвърлят.
Неформалният аргумент на Тюринг в полза на неговата теза доказва и по-силно твърдение: всеки алгоритъм може да бъде симулиран от машина на Тюринг... според Савидж , алгоритъм е изчислителен процес, дефиниран от машина на Тюринг.
Обичайно, когато един алгоритъм е свързан с обработка на информация, данните се четат от входа, изпращат се на изхода и/или се съхраняват за по-нататъшна обработка. Съхранените данни се разглеждат като част от вътрешното състояние на обекта, изпълняващ алгоритъма. На практика, състоянието се пази в една или повече структури от данни.
За всеки подобен изчислителен процес трябва строго да се дефинира един алгоритъм, като се определи така, че да е приложим при всички възможни обстоятелства, които могат да възникнат. Това ще рече, че систематично трябва да се разгледат всички условни разклонения, случай по случай, като критериите за всеки от случаите трябва да са ясно дефинирани и изчислими.
Тъй като алгоритъмът е точно определен списък от точно определени стъпки, редът на изчислението им винаги е от критично значение за работата на алгоритъма. Обикновено се предполага, че инструкциите са изрично изброени и са описани отначало-докрай, така както се изобразява една блок-схема. Това разбиране за формализацията на алгоритъма е основано на принципите на императивното програмиране. Други алтернативни концепции за алгоритмите предоставят функционалното и логическото програмиране.
Представяне Алгоритмите могат да се представят с много различни видове нотация, в това число естествени езици, псевдокод, блок-схеми или програмни езици. Описанието на алгоритми на естествен език страда от обичайната склонност на езика към многословие и многосмисленост и поради това рядко се използва за формулирането на сложни алгоритми. Псевдокодът и блок-схемите представляват структурирани начини за изразяване на алгоритми, които избягват двусмислиците на естествения език и са независими от конкретния програмен език, на който алгоритмите се реализират. Програмните езици са главно насочени към изразяването на алгоритми в изпълним от компютър вид, но често се ползват и за да онагледяват, дефинират или документират алгоритмите.
Има голямо разнообразие от начини за представяне на алгоритмите – дадена програма за машина на Тюринг може да се опише като поредица от машинни таблици, като блок-схема, като рудиментарен машинен код или асемблерен код.
Представянията на алгоритмите могат да се класифицират в три нива на описание на машината на Тюринг: 1 Описание от високо ниво „...текст за описване на алгоритъм, игнориращ подробностите на реализацията му. На това ниво няма нужда да се отбелязва как машината управлява своята памет или глава.“ 2 Описание на реализацията „...текст, използван за дефиниране на начина, по който машината на Тюринг използва своята глава, и начина, по който съхранява данните в паметта си. На това ниво не се дават подробности за състоянията или преходните функции.“ 3 Формално описание Най-подробното, „на най-ниско ниво“, задава „таблица на състоянията“ на машината на Тюринг.
Компютърни алгоритми При компютърните системи алгоритмите са по същество група логически инструкции, формулирани като софтуер, така че да бъдат ефективни за дадения компютър, който трябва да произведе краен резултат от зададени (потенциално празни) входни данни. Оптимален алгоритъм, дори изпълняван на стар хардуер, би дал по-бърз резултат от неоптимален (с по-висока времева сложност) алгоритъм със същото предназначение, изпълняван на по-ефективен хардуер. По тази причина алгоритмите, както и компютърния хардуер, се смятат за част от компютърната техника.
Някои автори говорят за „елегантни“ (компактни) и „добри“ (бързи) компютърни програми:
... стремим се към добри алгоритми в някакъв общо дефиниран естетически смисъл. Един критерий за това... е продължителността на времето за изпълнение на алгоритъма... Друг критерий е адаптивността на алгоритъма към различни компютри, неговата простота и елегантност.
... една програма е елегантна, под което разбирам, че тя е най-малката възможна програма, за получаване на нейния краен резултат.
Последната дефиниция е съпътствана с коментар, че елегантността на програмите не може да бъде доказана, тъй като такова доказателство би било решение на проблема за спирането.
За изчисляването на дадена функция могат да съществуват множество алгоритми. Това е вярно дори без да се разширява наборът от инструкции, достъпни за програмиста. Както отбелязват някои изследователи, „Важно е да се разграничини понятието „алгоритъм“, т.е. процедура, и понятието „функция, изчислима чрез алгоритъм“, т.е. съответствие, получено чрез процедура. Една и също функция може да има няколко различни алгоритъма.“ В много случаи изискванията за скорост и компактност са противоположни – компактна програма може да изисква повече стъпки за изпълнението си от друга, по-малко компактна.
Друг дискусионен проблем при компютърните алгоритми е моделът на самия компютър. Компютърът (или човек-„изчислител“) може да се разглежда като ограничен тип машина, „дискретно детерминистично механично устройство“, което сляпо следва своите инструкции. Примитивните модели на Мелзак и Ламбек редуцират това определение до четири елемента: дискретни, различими локации дискретни, неразличими броячи агент списък от инструкции, ефективни спрямо възможностите на агента
Мински описва реалистичен вариант на модела на Ламбек – машината на Мински изпълнява последователно своите пет инструкции, освен ако условна (IF–THEN GOTO) или безусловна (GOTO) инструкция за преход не промени последователността на изпълнение. Наред с инструкцията за прекратяване (HALT), машината на Мински включва три операции за присвояване – нулиране (ZERO), увеличение (SUCCESSOR) и намаление с единица (DECREMENT). На практика програмистите много рядко пишат реален код с толкова ограничен набор от инструкции, но Мински демонстрира, че неговата машина е цялостна по Тюринг със само четири общи типа инструкции.
Класификация на алгоритмите Съществуват различни начини да се класифицират алгоритмите.
Според имплементацията Рекурсивни или итеративни