Алгоритъм

Алгоритъм (от името на учения ал–Хорезми) е термин от математиката, информатиката, лингвистиката и други области, с който се описва сложно действие чрез редица от елементарни (достатъчно прости) действия, които изпълняващият може да извърши в последователни стъпки без допълнителни обяснения. Обикновено изпълнението на алгоритъма включва изчисление или обработка на данни.

По-строго дефинирано, алгоритъмът е ефективен метод за изчисляване на функция, който може да бъде изразен в рамките на крайно време и пространство и чрез добре дефиниран формален език. Започвайки от начално състояние и входни данни (понякога празни), инструкциите описват пресмятания, чието изпълнение преминава през краен брой добре дефинирани последователни състояния и завършва с крайно състояние, като в процеса се получават крайни резултати. Не е задължително преходът между състоянията да е детерминиран (еднозначно определен): някои алгоритми, известни като вероятностни алгоритми, съдържат елемент на случайност.

Концепцията за алгоритмите съществува от векове, но частичното формулиране на понятието започва с опитите да се реши 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 на определено място и в определен формат.

Концепцията за „алгоритъм“ се използва и за дефиниране на понятието решимост, което играе централна роля за обяснението как формалните системи възникват от малък набор аксиоми и правила. В логиката времето, необходимо за изпълнение на даден алгоритъм, не може да се измери, тъй като то не е свързано с обичайното физично измерение. Подобни несигурности, които характеризират текущите изследвания в тази област, водят до липсата на дефиниция за „алгоритъм“, която да съответства както на конкретната, така и на абстрактната употреба на термина.

Формализации

Алгоритмите са от съществено значение за начините, по които компютрите обработват информацията. Много компютърни програми съдържат алгоритми, които определят специфични инструкции, които компютърът трябва да изпълни в строго определен ред, за да се реши дадена задача. В този смисъл, алгоритъмът може да се разглежда като произволна поредица от операции, които могат да се симулират от пълна по Тюринг система. Към този възглед се придържат автори като Мински, Савидж и Гуревич:

Но ние също така ще твърдим, като Тюринг..., че всяка процедура, която може „естествено“ да бъде наречена ефективна, всъщност може да бъде реализирана от (проста) машина. Макар че това може да изглежда крайно, аргументите... в полза на това е трудно да се отхвърлят.

Неформалният аргумент на Тюринг в полза на неговата теза доказва и по-силно твърдение: всеки алгоритъм може да бъде симулиран от машина на Тюринг... според Савидж [1987], алгоритъм е изчислителен процес, дефиниран от машина на Тюринг.

Обичайно, когато един алгоритъм е свързан с обработка на информация, данните се четат от входа, изпращат се на изхода и/или се съхраняват за по-нататъшна обработка. Съхранените данни се разглеждат като част от вътрешното състояние на обекта, изпълняващ алгоритъма. На практика, състоянието се пази в една или повече структури от данни.

За всеки подобен изчислителен процес трябва строго да се дефинира един алгоритъм, като се определи така, че да е приложим при всички възможни обстоятелства, които могат да възникнат. Това ще рече, че систематично трябва да се разгледат всички условни разклонения, случай по случай, като критериите за всеки от случаите трябва да са ясно дефинирани и изчислими.

Тъй като алгоритъмът е точно определен списък от точно определени стъпки, редът на изчислението им винаги е от критично значение за работата на алгоритъма. Обикновено се предполага, че инструкциите са изрично изброени и са описани отначало-докрай, така както се изобразява една блок-схема. Това разбиране за формализацията на алгоритъма е основано на принципите на императивното програмиране. Други алтернативни концепции за алгоритмите предоставят функционалното и логическото програмиране.

Представяне

Алгоритмите могат да се представят с много различни видове нотация, в това число естествени езици, псевдокод, блок-схеми или програмни езици. Описанието на алгоритми на естествен език страда от обичайната склонност на езика към многословие и многосмисленост и поради това рядко се използва за формулирането на сложни алгоритми. Псевдокодът и блок-схемите представляват структурирани начини за изразяване на алгоритми, които избягват двусмислиците на естествения език и са независими от конкретния програмен език, на който алгоритмите се реализират. Програмните езици са главно насочени към изразяването на алгоритми в изпълним от компютър вид, но често се ползват и за да онагледяват, дефинират или документират алгоритмите.

Има голямо разнообразие от начини за представяне на алгоритмите – дадена програма за машина на Тюринг може да се опише като поредица от машинни таблици, като блок-схема, като рудиментарен машинен код или асемблерен код.

Представянията на алгоритмите могат да се класифицират в три нива на описание на машината на Тюринг:

1 Описание от високо ниво

„...текст за описване на алгоритъм, игнориращ подробностите на реализацията му. На това ниво няма нужда да се отбелязва как машината управлява своята памет или глава.“

2 Описание на реализацията

„...текст, използван за дефиниране на начина, по който машината на Тюринг използва своята глава, и начина, по който съхранява данните в паметта си. На това ниво не се дават подробности за състоянията или преходните функции.“

3 Формално описание

Най-подробното, „на най-ниско ниво“, задава „таблица на състоянията“ на машината на Тюринг.

Компютърни алгоритми

При компютърните системи алгоритмите са по същество група логически инструкции, формулирани като софтуер, така че да бъдат ефективни за дадения компютър, който трябва да произведе краен резултат от зададени (потенциално празни) входни данни. Оптимален алгоритъм, дори изпълняван на стар хардуер, би дал по-бърз резултат от неоптимален (с по-висока времева сложност) алгоритъм със същото предназначение, изпълняван на по-ефективен хардуер. По тази причина алгоритмите, както и компютърния хардуер, се смятат за част от компютърната техника.

Някои автори говорят за „елегантни“ (компактни) и „добри“ (бързи) компютърни програми:

... стремим се към добри алгоритми в някакъв общо дефиниран естетически смисъл. Един критерий за това... е продължителността на времето за изпълнение на алгоритъма... Друг критерий е адаптивността на алгоритъма към различни компютри, неговата простота и елегантност.

... една програма е елегантна, под което разбирам, че тя е най-малката възможна програма, за получаване на нейния краен резултат.

Последната дефиниция е съпътствана с коментар, че елегантността на програмите не може да бъде доказана, тъй като такова доказателство би било решение на проблема за спирането.

За изчисляването на дадена функция могат да съществуват множество алгоритми. Това е вярно дори без да се разширява наборът от инструкции, достъпни за програмиста. Както отбелязват някои изследователи, „Важно е да се разграничини понятието „алгоритъм“, т.е. процедура, и понятието „функция, изчислима чрез алгоритъм“, т.е. съответствие, получено чрез процедура. Една и също функция може да има няколко различни алгоритъма.“ В много случаи изискванията за скорост и компактност са противоположни – компактна програма може да изисква повече стъпки за изпълнението си от друга, по-малко компактна.

Друг дискусионен проблем при компютърните алгоритми е моделът на самия компютър. Компютърът (или човек-„изчислител“) може да се разглежда като ограничен тип машина, „дискретно детерминистично механично устройство“, което сляпо следва своите инструкции. Примитивните модели на Мелзак и Ламбек редуцират това определение до четири елемента:

1. дискретни, различими локации
2. дискретни, неразличими броячи
3. агент
4. списък от инструкции, ефективни спрямо възможностите на агента

Мински описва реалистичен вариант на модела на Ламбек – машината на Мински изпълнява последователно своите пет инструкции, освен ако условна (IF–THEN GOTO) или безусловна (GOTO) инструкция за преход не промени последователността на изпълнение. Наред с инструкцията за прекратяване (HALT), машината на Мински включва три операции за присвояване – нулиране (ZERO), увеличение (SUCCESSOR) и намаление с единица (DECREMENT). На практика програмистите много рядко пишат реален код с толкова ограничен набор от инструкции, но Мински демонстрира, че неговата машина е цялостна по Тюринг със само четири общи типа инструкции.

Класификация на алгоритмите

Съществуват различни начини да се класифицират алгоритмите.

Според имплементацията

Рекурсивни или итеративни

Рекурсивният алгоритъм е алгоритъм, който прави поредица от обръщения към себе си дотогава, докато не се изпълни определено условие. Този метод на имплементация е характерен за функционалното програмиране. За да решат същите задачи, итеративните алгоритми използват повтарящи се конструкции (цикли), а понякога и допълнителни структури от данни като стекове. Някои проблеми са формулирани така, че е естествен изборът на едната или другата имплементация. Всяка рекурсивна версия на алгоритъм има еквивалентна (повече или по-малко сложна) итеративна версия, и обратно.

Логически

Алгоритъмът може да се разглежда като контролирана логическа дедукция. Понятието алгоритъм е дефинирано през 1979 от Роберт Ковалски като

Алгоритъм = Логика + Управление

Логическият компонент изразява изходните аксиоми, а контролният компонент изразява правилата за извод, които се прилагат над аксиомите. Това лежи в основата на логическото програмиране. В чистите езици за логическо програмиране, управляващият компонент е фиксиран и алгоритмите се различават само по своите логически компоненти.

Серийни, паралелни или разпределени

При дискутирането на алгоритмите обикновено се прави допускането, че компютрите изпълняват една команда на един такт. Проектираните по този начин алгоритми се наричат серийни, за сравнение с паралелните и разпределените алгоритми. Паралелни алгоритми се реализират тогава, когато компютърната архитектура се състои от няколко микропроцесора, които могат едновременно да работят над изпълнението на алгоритъма, докато разпределените алгоритми използват ресурсите на множество машини, свързани в мрежа. Паралелните и разпределените алгоритми разделят изпълнението на задача на повече на брой подзадачи и след това събират резултатите от тях. При такива имплементации намаленото натоварване на отделните процесори се заплаща с комуникацията и синхронизацията между тях. Някои задачи могат да се реализират само със серийни алгоритми.

Детерминирани и недетерминирани

Детерминираните алгоритми решават даден проблем, като винаги преминават през точно определена последователност от стъпки и при даден вход винаги извеждат един и същ резултат. Недетерминираните алгоритми използват различни техники, базирани на евристики и случайност.

Точни и приблизителни

При все че много алгоритми достигат до точно решение на даден проблем, по различни причини в практиката се използват и приблизителни алгоритми, които (по горната класификация) могат да бъдат както недетерминирани, така и детерминирани.

Според дизайна

Някои често срещани принципи в дизайна на алгоритми са следните:

„Груба сила“

Това е опростен метод, при който се опитва всяко възможно решение и се определя най-доброто.

„Разделяй и владей“

Алгоритмите, основани на парадигмата „разделяй и владей“, последователно (обикновено чрез рекурсия) раздробяват даден проблем на два и повече подпроблеми дотогава, докато те станат достатъчно малки, за да бъдат лесно решени. Пример за алгоритъм от този вид е алгоритъмът за сортиране чрез сливане. Сортирането се извършва, като целия масив от числа се раздели на сегменти и се сортират първо отделните сегменти, и след това (във фазата на „завладяването“) се слеят отделните сегменти.

Динамично програмиране

Когато за дадена задача е известно, че оптималното решение може да бъде конструирано на база оптималните решения на поредица подзадачи, и то такива припокриващи се подзадачи, които също се свеждат до решаването на подзадачи, то се прилага подход, наречен динамично програмиране, при който се избягва необходимостта да се извършват повторно вече направени изчисления. Например, най-краткият път между начален и целеви връх в граф с тегла по дъгите може да се намери като се използва най-краткия път до целевия граф от всичките върхове, с които той е свързан.

Основната разлика между динамичното програмиране и „разделяй и владей“ е, че подзадачите са малко или много независими при „разделяй и владей“, докато подзадачите при динамичното програмиране се припокриват. Разлика между динамичното програмиране и обикновената рекурсия е в кеширането или мемоизацията на рекурсивните заявки. Когато подзадачите са независими, мемоизацията не е от полза, и следователно динамичното програмиране не е ефективно. С използването на мемоизация или с поддържането на таблица на вече решените подзадачи, динамичното програмиране свежда изчислението на много задачи, решавани с експоненциална сложност до задачи, решавани с полиномиална сложност.

Линейно програмиране

Когато се решава дадена задача със средствата на линейното програмиране, проблемът се свежда до откриването на специфични неравенства, които определят дефиниционното множество на входните данни, и след това се прави опит да се намери максимума (или минимума) на някоя линейна функция над тях. Много задачи (като изчисляване на максимален трансфер по дъга на ориентиран граф) могат да се зададат в термините на линейното програмиране и да се решат с общ (стандартен) алгоритъм, какъвто е симплекс методът. Една по-сложна разновидност на линейното програмиране се нарича целочислено програмиране, при което пространството на решенията е ограничено от множеството на целите числа.

Вероятностни / евристични алгоритми

Алгоритмите в тази група се вписват по-нестрого в дефиницията на алгоритъм.

1. Вероятностните алгоритми са тези, които съдържат елемент на случайност (или псевдослучайност), за решаването на някои проблеми. За някои труднорешими задачи (напр. NP-пълни) съществуват бързи решения, използващи случайност, но негарантиращи оптималност, коректност или дори намиране на решение.
2. Генетичните алгоритми се опитват да намерят решения на задачите, като наподобяват поведението на биологични еволюционни процеси, включващи случайни мутации и кросоверинг (кръстосване), и генериращи поколения от възможни индивиди. Задължителна част от всеки генетичен алгоритъм е дефинирането на възможните индивиди (множеството на коректни решения на поставената задача), схемите на мутация и кросоверинг, както и функция на приспособеност (използвана за оценка на всеки от индивидите). Възпроизводството на поколенията се извършва на цикли, на всяка стъпка от които се извършват мутация и кросоверинг между текущите индивиди, в резултат на което към популацията се добавят и потомствени индивиди, чиято приспособеност също бива оценена. Оцеляването на най-приспособените индивиди от популацията осигурява както регулиране на размера ѝ, така и отсяване на решенията, които не се очаква да допринесат за бъдещите еволюционни стъпки. Класически пример за задача, която бива решавана от генетически алгоритъм е, намиране на минимален хамилтонов път в претеглен граф – за индивиди могат да служат пермутации на върховете, задаващи последователността на обхода, мутацията може да бъде промяна на реда на обхождане на два върха, а кросовера може да съвмещава част от един хамилтонов път, допълнен от оставащите върхове в реда, в който се срещат в друг хамилтонов път. Генетическите алгоритми могат да бъдат приложени към голям клас задачи, но основен недостатък на подхода е липсата на теоретически оценки, гарантиращи намирането на добри решения.
3. Евристичните алгоритми са алгоритми, чиято основна задача е намирането не на оптимално, а на приблизително решение в условия на ограничени памет или време. Примери за такива алгоритми са локално търсене, табу търсене или класа на евристичните вероятностни алгоритмите за симулирано закаляване, при които решението на задача варира в случайни граници. (Терминът „симулирано закаляване“ идва от металургичния термин закаляване на металите и сплавите, при която вследствие от нагряване до определена температура, задържане и последващо бавно охлаждане се постига намаляване структурните дефекти в метала.)

Според приложението

Всяка научна област си има своите специфични задачи за решаване и се нуждае от ефективни алгоритми. Свързани проблеми от една или повече области често се изследват заедно и се решават със сходни средства. Примери за цели класове алгоритми, с приложение в разнообразни области, са: алгоритми за търсене, алгоритми за сортиране, алгоритми за сливане, алгоритми за работа с числа, низове, графи, алгоритми за изчислителна геометрия, комбинаторни алгоритми, алгоритми за машинно обучение, криптографски алгоритми, алгоритми за компресиране на данни, алгоритми за синтактичен анализ (parsing) и други.

Според сложността

Алгоритмите могат да бъдат класифицирани по отношение на времето, което им е необходимо, за да решат проблем спрямо размера (дължината) на подадения вход. Някои алгоритми завършват за линейно време, други за полиномиално, трети за експоненциално време, а някои алгоритми никога не завършват работа. За някои задачи съществуват множество алгоритми с различна степен на сложност, докато за други задачи няма алгоритми за решаване или не са известни ефективни такива. Съществуват и изображения, задаващи съответствия между различни типове задачи. Благодарение на това е станало ясно, че е по-удачно класификацията да се прилага над типовете задачи, вместо над алгоритмите, като те се групират в класове на еквивалентност по отношение сложността на най-ефективните сред алгоритмите за решаването им.

Бележки

Цитирани източници

• Александров, П. С. (ред.). Проблемы Гильберта. Москва, „Наука“, 1969. (на руски)
• Boolos, George et al. Computability and Logic. 4th. Cambridge University Press, London, 1999, [1974]. ISBN 0-521-20402-X. (на английски)
• Carroll, Sue et al. Fundamental Concepts for the Software Quality Engineer. American Society for Quality, 2007. ISBN 978-0-87389-720-4. (на английски)
• Chaitin, Gregory. Meta Math!: The Quest for Omega. Pantheon Books, 2005. (на английски)
• Dantzig, George B. et al. Linear Programming 2: Theory and Extensions. Springer-Verlag, 2003. (на английски)
• Davis, Martin. The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York, Raven Press, 1965. ISBN 0-486-43228-9. (на английски)
• Gandy, Robin. Church's Thesis and Principles for Mechanisms // Barwise, J. et al. The Kleene Symposium. North-Holland Publishing Company, 1980. p. 123 – 148. (на английски)
• Gurevich, Yuri. Sequential Abstract State Machines Capture Sequential Algorithms // ACM Transactions on Computational Logic 1 (1). 2000. p. 77 – 111. (на английски)
• Knuth, Donald Ervin. The Art of Computer Programming: Fundamental algorithms. Addison-Wesley Publishing Company, 1973. ISBN 9780201038095. (на английски)
• Lambek, Joachim. How To Program An Infinite Abacus // The Canadian Mathematical Bulletin 4 (3). 1961. p. 295. (на английски)
• Melzak, Z. A. An Informal Arithmetical Approach To Computability And Computation // The Canadian Mathematical Bulletin 4 (3). 1961. p. 283. (на английски)
• Minsky, Marvin. Computation: Finite and Infinite Machines. First. Prentice-Hall, Englewood Cliffs, NJ, 1967. ISBN 0-13-165449-7. (на английски)
• Moschovakis, Yiannis N. What is an algorithm? // Engquist, B. и др. Mathematics Unlimited – 2001 and beyond. Springer, 2001. ISBN 9783540669135.
• Rogers, Hartley. Theory of Recursive Functions and Effective Computability. The MIT Press, 1987. ISBN 0-262-68052-1. (на английски)
• Seig, Wilfred et al. Reflections on the foundations of mathematics: Essays in honor of Solomon Feferman. Natick, MA, Association for Symbolic Logic, A. K Peters, 2002. (на английски)
• Stone, Harold S. Introduction to Computer Organization and Data Structures. New York, McGraw-Hill, 1972. ISBN 0-07-061726-0. (на английски)

Тази страница частично или изцяло представлява превод на страницата Algorithm в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​

Източници

• Kleene C., Stephen (1943). „Recursive Predicates and Quantifiers“. Американско математическо общество, том 54, No. 1: 41 – 73. doi:10.2307/1990131. Публикувана отново в The Undecidable, p. 255ff. Kleene изчиства своята дефиниция за „обща рекурсия“ и продължава в своята глава „12. Алгоритмични теории“ да постулира „Thesis I“ (стр. 274); той по-късно ще повтори своята теза (в Kleene 1952:300) и ще я нарече „Church's Thesis“ (Kleene 1952:317) (the Church thesis).
• Rosser, J.B. (1939). „An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem“. Journal of Symbolic Logic 4. Reprinted in The Undecidable, p. 223ff. Тук е известната дефиниция на Rosser за „ефективен метод“: „...метод, на който всяка стъпка е прецизно определена и който е сигурен в осигуряванета на въпрос на краен брой от стъпки... механизъм, който така ще реши всеки проблем от множеството без човешка интервенция извън въвеждането на въпроса и (по-късно) четенето на отговора“ (стр. 225 – 226, The Undecidable)

Допълнителна литература

• M. H. Alsuwaiyel, Algorithms: Design Techniques and Analysis, World Scientific, 1999