Какво са Алгоритмите, къде намират приложение и как работят?

Произход на думата "алгоритъм":

Съществуват множество хипотези за произхода на думата "алгоритъм", като няма достатъчно достоверна информация за точния начин, по който се появява терминът за първи път. Най-разпространената хипотеза за произхода ѝ идва от името на арабския математик al-Khowarizmi, който през VIII век описва откриването на десетичната бройна система и представя редица важни концепции в книгата си "Al-jabr wa'l muqabala", която по-късно ще образува добре известната дума алгебра.

Какво е Алгоритъм?

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

Как алгоритмите намират приложение в програмирането?

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

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

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

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

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

Това са само малка част от примерите за широкото приложение на алгоритмите при изграждането и разработката на апликации. Компании, като Google, Amazon, Facebook, Instagram, Netflix и много други отделят голяма част от ресурсите си за развитието на нови и все по-оптимални алгоритми, спрямо непрестанното нарастване на данните, които обработват.

Все по-широко приложение намират и генетичните алгоритми, които са базирани на естествения подбор и теорията за еволюцията на Чарлз Дарвин, за оптимизирането на генерирането на комбинации, както и намирането на подходящи елементи измежду тях, чрез използването на mutation, crossover and selection. Тези алгоритми са основата на бъдещата медицина, както и за намирането на нови лекарства.

Как работят алгоритмите?

Алгоритмите са разделени измежду различни групи, спрямо техниките, използвани за решението на конкретно множество от проблеми. Често един алгоритъм може да реши широка гама от проблеми, спадащи към същата категория. Някои от основните групи алгоритми са: Searching, Sorting, Graph Theory, Searching with Backtracking, Divide and Conquer, Dynamic Programming, Greedy Algorithms etc.

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

Можем да сведем проблема до под проблеми, започвайки от дефиниция на решението, което искаме да намерим и връщайки се назад всяка стъпка към началното състояние, за което имаме известно решение – този подход се нарича "top-to-bottom approach".

Друг начин е да тръгнем от известното решение да намерим взаимовръзката между това решение и всяко следващо решение, и чрез тази зависимост между решенията да намерим глобалното такова – този подход се нарича "bottom-up approach".

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

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

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

Включете се в своето алгоритмично приключение с практически насоченото обучение „Algorithms Advanced (with C#) – Януари 2021“! Ще придобиете ключови умения за работата с алгоритми с C#, чрез множество практически задачи и възможности за разрешаване на казуси и проблеми. Очакваме ви!