Nejlepší odpověď
Klasifikace podle účelu
Každý algoritmus má cíl, například účelem algoritmu Quick Sort je seřadit data vzestupně nebo sestupně. Počet cílů je však nekonečný a musíme je seskupit podle druhu účelu.
Klasifikace podle implementace
Algoritmus lze implementovat podle různých základních principů.
- Rekurzivní nebo iterativní Rekurzivní algoritmus je algoritmus, který se opakovaně volá, dokud se neshoduje určitá podmínka. Je to metoda běžná pro funkční programování. Iterativní algoritmy používají opakující se konstrukce jako smyčky. Některé problémy jsou vhodnější pro jednu nebo druhou implementaci. Například věže Hanojského problému jsou v rekurzivní implementaci dobře pochopeny. Každá rekurzivní verze má iterativní ekvivalentní iterativ a naopak.
- Logické nebo procedurální Algoritmus lze považovat za řízenou logickou dedukci. Logická komponenta vyjadřuje axiomy, které lze použít při výpočtu, a řídicí komponenta určuje způsob, jakým se na axiomy aplikuje dedukce. To je základ logického programování. V čistě logických programovacích jazycích je ovládací komponenta pevná a algoritmy jsou specifikovány dodáním pouze logické komponenty.
- Serial nebo paralelní Algoritmy se obvykle diskutují s předpokladem, že počítače provádějí jednu instrukci algoritmu najednou. Toto je sériový algoritmus, na rozdíl od paralelních algoritmů, které využívají výhod počítačových architektur ke zpracování několika instrukcí najednou. Rozdělí problém na dílčí problémy a předají je několika procesorům. Iterační algoritmy jsou obecně paralelizovatelné. Algoritmy řazení lze efektivně paralelizovat.
- deterministické nebo nedeterministické Deterministické algoritmy řeší problém předdefinovaným procesem, zatímco nedeterministický algoritmus musí v každém kroku provádět odhady nejlepšího řešení pomocí heuristiky.
Klasifikace podle návrhového paradigmatu
Návrhové paradigma je doménou výzkumu nebo třídou problémů, která vyžaduje vyhrazený druh algoritmu:
- Rozděl a panuj Algoritmus rozdělení a panování opakovaně redukuje instanci problému na jednu nebo více menších instancí stejného problému (obvykle rekurzivně), dokud nejsou instance dostatečně malé snadno vyřešit. Jedním z takových příkladů rozdělení a dobývání je sloučení třídění. Třídění lze provést na každém segmentu dat po rozdělení dat na segmenty a třídění celých dat lze získat ve fázi dobývání jejich sloučením. Algoritmus binárního vyhledávání je příkladem varianty rozdělení a dobývání s názvem algoritmus snižování a dobývání , který řeší stejný dílčí problém a k jeho řešení využívá řešení tohoto dílčího problému větší problém.
- Dynamické programování Nejkratší cestu ve váženém grafu lze najít pomocí nejkratší cesty k cíli ze všech sousedních vrcholy. Když lze optimální řešení problému zkonstruovat z optimálního řešení do dílčích problémů, použití dynamického programování se vyhne opětovnému výpočtu řešení, která již byla vypočítána. – Hlavní rozdíl v přístupu „rozděl a panuj“ je v tom, že dílčí problémy jsou nezávislé na rozdělení a panování, kde v dynamickém programování dochází k překrývání dílčích problémů. – Dynamické programování a memoizace jdou dohromady. Rozdíl oproti přímé rekurzi spočívá v ukládání do mezipaměti nebo memoizaci rekurzivních volání. Tam, kde jsou dílčí problémy nezávislé, je to k ničemu. Použitím memoizace nebo udržováním tabulky již vyřešených dílčích problémů dynamické programování snižuje exponenciální povahu mnoha problémů na polynomiální složitost.
- Chamtivá metoda Chamtivý algoritmus je podobný algoritmu dynamického programování, ale rozdíl je v tom, že řešení dílčích problémů nemusí být známa v každé fázi. Místo toho lze „chamtivě“ zvolit, co pro danou chvíli vypadá nejlépe. Nejpopulárnějším chamtivým algoritmem je nalezení minimálního kostry, jak uvádí Kruskal.
- Lineární programování Problém je vyjádřen jako sada lineárních nerovnosti a poté se provede pokus o maximalizaci nebo minimalizaci vstupů. To může vyřešit mnoho problémů, jako je maximální tok pro směrované grafy, zejména pomocí simplexního algoritmu.Složitá varianta lineárního programování se nazývá celočíselné programování, kde je prostor řešení omezen na všechna celá čísla.
- Redukce nazývaná také transformovat a dobýt Vyřešte problém jeho transformací na jiný problém. Jednoduchý příklad: nalezení mediánu v netříděném seznamu nejprve převede tento problém na problém řazení a najde prostřední prvek v seřazeném seznamu. Hlavním cílem redukce je nalezení nejjednodušší možné transformace.
- Používání grafů Mnoho problémů, například hraní šachů, lze modelovat jako problémy na grafech. Používají se algoritmy průzkumu grafů. Tato kategorie zahrnuje také vyhledávací algoritmy a zpětné sledování.
- Pravděpodobnostní a heuristické paradigma Pravděpodobnostní Ti, kteří rozhodují náhodně. Genetické Pokus o nalezení řešení problémů napodobováním biologických evolučních procesů s cyklem náhodných mutací, které povedou k následným generacím „řešení“. Napodobují tedy reprodukci a „přežití nejschopnějších“. Heuristické Jejich obecným účelem není najít optimální řešení, ale přibližné řešení, kde čas nebo zdroje k nalezení dokonalého řešení nejsou praktické.
Klasifikace podle složitosti
Některé algoritmy se dokončují v lineárním čase a některé v exponenciálním čase a některé nikdy nedokončí.
Zdroj: Klasifikace algoritmů
Kontrolované učení: Klasifikace
Odpověď
Následující je další způsob klasifikace algoritmů.
V konkurenčním programování existují 4 hlavní problémy – paradigmata řešení.
Jinými slovy, vzhledem k problému jsou zde různé přístupy / nástroje, které byste k jeho řešení měli použít.
- Brute Force / Complete Search: Metoda, která zkoumá všechny možnosti a vybírá nejlepší řešení.
- Klady: jednoduché, měli byste vždy najít řešení, protože se díváte na všechny možnosti
- Nevýhody : neproveditelné jako počet možností exponenciálně roste s rostoucím počtem položek
- Divide and Conquer: Metoda, která rozděluje problém na menší části a poté řeší části. Přemýšlejte o binárním vyhledávání.
- Chamtivý přístup: Metoda, která si v současné době vybere nejlepší možnost bez ohledu na budoucnost.
- Klady: rychlé, jednoduché, mohou získat nejlepší řešení nebo se trochu přiblížit
- Nevýhody: většinu času nezískáme nejlepší řešení
- Dynamické programování: Metoda, která vytváří řešení pomocí dříve nalezených dílčích řešení. Určitě jedna z pokročilejších technik, ale mimořádně výkonná a použitelná.
- Klady: najde optimální řešení mnoha problémů v polynomiálním čase ( zatímco hrubá síla by trvala exponenciálně)
- Nevýhody : obtížně uchopitelné a použitelné, pochopení různých stavů a opakování vyžaduje čas
Zdroje
Halim, Steven a Felix Halim. Konkurenční programování: Nová spodní hranice programovacích soutěží . Lulu, 2013.