4 интересни приложения на алгоритми
Историята зад понятието “алгоритъм” е дълга и изпълнена с промени. Как ние използваме въпросното понятие днес, обаче, е относително ново явление. За много учени, началото на това явление се поставя около 1928-ма година, когато известния Entscheidungsproblem (проблем на решението) на Дейвид Хилбърт изисква от великите математици на времето да дадат точно определение на думата “алгоритъм”.
И до днес единно такова определение не съществува, но можем да приемем следното: определен набор правила, точно дефиниращи последователност от действия. С две думи - това е начина, по който работят всички компютърни програми днес. Истината е, че зад всяко иновативно нововъведение стоят алгоритмични действия, дефинирани десетилетия преди да бъдет приложени по интересен начин. Искаме да ви запознаем с четири прекрасни примера за това:
4.Knapsack problem
Въпросния Knapsack проблем може да бъде описан накратко така:
С даден брой предмети с определена стойност (примерно парична) и тегло, трябва да направите избор между какви и колко предмети да поместите в определен лимит на тежестта, като постигате възможно най-висока стойност.
Би трябвало да ви звучи познато, понеже поне веднъж през живота си сте се сблъсквали с такава ситуация в компютърните игри от серията The Elder Scrolls или други RPG-та, в които инвенторията ви има лимит за тежест.
3.Pathfinding в разработката на игри
Някога чудили ли сте се как във всички нови игри получавате най-краткия път до точката, към която искате да се придвижите? Това е така наречения Pathfinding и често се осъществява чрез добре познатия A* (А звезда) алгоритъм , който служи за ефикасно намиране на най-бързия път между две точки (vertices).
2.Google Maps
Следващия път, когато потърсите най-близката пицария до вас се замислете за това как точно всеки път Google Maps ви показва не само най-близките, а и тези които скоро са отворили, пътната обстановка покрай тях и всички други подробности. За да вникнете в начина на работа на Maps, ще трябва да научите за графи - абстрактно представяне на обекти (върхове) и техните връзки (ребра), както и тяхното алгоритмично обхождане.
1.Обработка на огромно количество данни
Най-важното и широко приложение на алгоритми е при наличието на огромен брой данни и нуждата да се обработят бързо. Примерите включват:
- Намиране на най-дългата обща подпоследователност (Longest Common Subsequence) - използвана от сорс контрол системата git
- Комбинаторни алгоритми - намиране на пермутации, вариации и комбинации на елементите, които изследвате
- Рекурсия - рекурсивни операции са приложими почти навсякъде, като един от простите примери е обхождането на файлова система.
Всичко това и повече ще имате шанса да научите на новия ни безплатен курс - Алгоритми - април 2016, който започва на 5-ти април и ще се провежда всеки вторник и четвъртък от 18:30 в сградата на СофтУни.