Алгоритъм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[редактиране | редактиране на кода]