Алгоритъм

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

Частична формализация на понятието започва с опитите да се реши 10-тия проблем на Хилберт, „Задача за разрешимост на диофантово уравнение“, поставен от Давид Хилберт през 1900 година на Втория световен конгрес по математика в Париж.[1] Последващите формализации представляват опити да се дефинира „ефективна изчислимост“ (Клини 1943:274) или „ефективен метод“ (Росър 1939:225); включват рекурсивните функции на Ербран-Гьодел-Клини от 1930, 1934 и 1935 година, ламбда смятането на Алонсо Чърч от 1936, „Формулировка 1“ на Емил Пост от 1936, и машината на Тюринг от 1936-7 и 1939 година.

Неформална дефиниция[редактиране | edit source]

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

Класически пример за „алгоритъм“ е алгоритъмът на Евклид чрез изваждане за намиране на най-големия общ делител (НОД) на две цели числа, по-големи от 1. При него се изпълнява следната поредица от стъпки: На стъпка i, се дели X на Y и остатъкът се означава с R. Ако R = 0, резултатът на задачата е Y. В противен случай, резултатът съвпада с НОД на числата R и Y. Такъв алгоритъм, при който за намирането на решение е необходимо да бъде решена аналогична, но „по-малка“ задача, се нарича рекурсивен.

Формализации[редактиране | edit source]

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

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

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

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

Представяне[редактиране | edit source]

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

Класификация на алгоритмите[редактиране | edit source]

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

Според имплементацията[редактиране | edit source]

Рекурсивни или итеративни
Рекурсивният алгоритъм е алгоритъм, който прави поредица от обръщения към себе си дотогава, докато не се изпълни определено условие. Този метод на имплементация е характерен за функционалното програмиране. За да решат същите задачи, итеративните алгоритми използват повтарящи се конструкции (цикли), а понякога и допълнителни структури от данни като стекове. Някои проблеми са формулирани така, че е естествен изборът на едната или другата имплементация. Всяка рекурсивна версия на алгоритъм има еквивалентна (повече или по-малко сложна) итеративна версия, и обратно.
Логически
Алгоритъмът може да се разглежда като контролирана логическа дедукция. Понятието алгоритъм е дефинирано през 1979 от Роберт Ковалски като
Алгоритъм = Логика + Управление
Логическият компонент изразява изходните аксиоми, а контролният компонент изразява правилата за извод, които се прилагат над аксиомите. Това лежи в основата на логическото програмиране. В чистите езици за логическо програмиране, управляващият компонент е фиксиран и алгоритмите се различават само по своите логически компоненти.
Серийни, паралелни или разпределени
При дискутирането на алгоритмите обикновено се прави допускането, че компютрите изпълняват една команда на един такт. Проектираните по този начин алгоритми се наричат серийни, за сравнение с паралелните и разпределените алгоритми. Паралелни алгоритми се реализират тогава, когато компютърната архитектура се състои от няколко процесора, които могат едновременно да работят над изпълнението на алгоритъма, докато разпределените алгоритми използват ресурсите на множество машини, свързани в мрежа. Паралелните и разпределените алгоритми разделят изпълнението на задача на повече на брой подзадачи и след това събират резултатите от тях. При такива имплементации намаленото натоварване на отделните процесори се заплаща с комуникацията и синхронизацията между тях. Някои задачи могат да се реализират само със серийни алгоритми.
Детерминирани и недетерминирани
Детерминираните алгоритми решават даден проблем, като винаги преминават през точно определена последователност от стъпки и при даден вход винаги извеждат един и същ резултат. Недетерминираните алгоритми използват различни техники, базирани на евристики и случайност.
Точни и приблизителни
При все че много алгоритми достигат до точно решение на даден проблем, по различни причини в практиката се използват и приблизителни алгоритми, които (по горната класификация) могат да бъдат както недетерминирани, така и детерминирани.

Според дизайна[редактиране | edit source]

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

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

Според приложението[редактиране | edit source]

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

Според сложността[редактиране | edit source]

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

Бележки[редактиране | edit source]

  1. „Проблемы Гильберта“, под редакцията на П. С. Александров, „Наука“, Москва, 1969
Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Algorithm“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.  

Източници[редактиране | edit source]

  • 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)

Допълнителна литература[редактиране | edit source]