Какви типове алгоритми съществуват?

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

Класификация според начина на имплементация

Един от начините да се класифицират алгоритмите е според начина на имплементиране т.е. на внедряване.

• Рекурсивен - рекурсивен алгоритъм е този, който извиква себе си толкова пъти, докато дадено условие не се изпълни (условието е познато още и като „условие за прекратяване“). За целта повтарящите се (т.е. рекурсивни) алгоритми използват най-често конструкции, като цикли и структури от данни (като например стекове), за да решат дадения проблем.
• Логически - един алгоритъм може да се разглежда като контролирана логическа дедукция. Най-общо казано можем да обясним този тип алгоритми като „Логически алгоритъм = логика + контрол“. Логическият компонент изразява аксиомите, които може да се използват в изчисленията, а контролния компонент определя начина по който дедукцията се прилага спрямо аксиомите. При програмните езици, които са базирани на логическия компонент, контролния компонент е вече определен и при внедряването на алгоритъма е необходимо да се изгради само логическия компонент. По този начин се постига една по-елегантна семантика: промяна в аксиомите води до добре-дефинирана промяна в алгоритъма.
• Сериен, паралелен и разпределен - Алгоритъм, който е предназначен да работи в среда, която изпълнява по една инструкция от даден алгоритъм в даден момент, се наричат серийни алгоритми.

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

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

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

• Детерминистични или не-детерминистични - детерминистичен е този алгоритъм, който при определен вход винаги ще дава един и същи резултат, като по време на изпълнение компютъра винаги преминава през един и същи набор от състояния. Детерминистичните алгоритми са може би най-изследваните и познати типове алгоритми, както и едни от най-практичните.
• Не-детерминистичните алгоритми са алгоритми, които при едни и същи входни данни, могат да се получат различни резултати. Това е така, защото при различни пускания на машината е възможно алгоритъма да използва различни типове поведения, които да доведат до различни резултати. В зависимост от поведението не-детерминистичните алгоритми могат да бъдат няколко подтипа:
• Конкурентни алгоритми - конкурентните алгоритми могат да имат различна производителност при различните пускове, поради т.нар. „race condition“. Трябва да се има в предвид, че "race condition"-ът (наричан още и "Race Hazard") обикновено е нежелано поведение, което се появява в следствие от последователността или тайминга на различни процеси, които се опитват да променят едни и същи данни почти едновременно, водейки до непредвидени резултати.
• Стохастични (вероятностни) алгоритми - алгоритми, които използват известна доза случайност, като част от своята логика. Поведението се определя от случайни битове, които се добавят към входящите данни, но и резултатът често е случайна променлива.
• Точни или приблизителни - въпреки че много алгоритми достигат до точно решение, приблизителните алгоритми търсят приблизителност, която да е близко до истинското решение. Тази приблизителност може да бъде постигната чрез използване както на детерминистична, така и на случайна стратегия. Такива алгоритми имат практическо приложение в множество трудни проблеми. Един пример за такъв проблем е т.нар. „Проблем с раницата“ (“Knapsack problem”), пр който имаме набор от дадени предмети, като целта е в раницата да се съберат предмети с максимална обща стойност. Всеки предмет има определено тегло и определена стойност. Общото тегло, което може да се носи е не повече от определеното число Х. Така че решението трябва да включва в себе си както общото тегло, така и стойността на всеки предмет т.е. да балансира между двете стойности.
• Квантови алгоритми - при квантовия компютинг „квантов алгоритъм“ наричаме алгоритъм, който върви върху реалистичен модел на квантови изчисления, като най-често срещания модел от този тип е квантовият верижен модел на изчисление. Класическият (неквантов) алгоритъм е ограничена последователност от инструкции, която се изпълнява стъпка по стъпка, за да се реши даден проблем. Всяка стъпка или инструкция от този алгоритъм може да се изпълни на дигитален (класиески) компютър. Подобно на класическия, квантовия алгоритъм е процедура, която се изпълнява стъпка по стъпка, като всяка стъпка се изпълнява от квантов компютър. Квантовите компютри могат да изпълняват и класически алгоритми. Терминът „квантов алгоритъм“ се използва за тези алгоритми, които по своята същност са квантови или използват значителна степен от свойствата на квантовите изчисления, като квантова суперпозиция или квантово заплитане, за да бъдат изпълнени.

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

На какви други типове се делят алгоритмите?

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

Към какви типове алгоритми клони вашият интерес – това зависи до голяма степен от проблемите които решавате, технологиите които използвате и средата в която го правите. Без значение от това обаче вие трябва да се запознаете с основни понятия и концепции при изграждането на алгоритми. За тази цел сме подготвили изцяло онлайн обучението „Алгоритми – юли 2019“ Запишете се още днес!