Алгоритъм

от Уикипедия, свободната енциклопедия

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

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

Съдържание 1 Неформална дефиниция 2 Формализации 2.1 Представяне 3 Класификация на алгоритмите 3.1 Според имплементацията 3.2 Според дизайна 3.3 Според приложението 3.4 Според сложността 4 Източници

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Логически

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. ↑ „Проблемы Гильберта“, под редакцията на П. С. Александров, „Наука“, Москва, 1969

Тази страница частично или изцяло представлява превод на страницата „Algorithm“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.