TUNING FORUM - bazar, chip tuning, auto tuning online

Skočit na: Navigace, Hledání

Algoritmus je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmu se nejčastěji objevuje při programování, kdy se jím myslí teoretický princip řešení problému (oproti přesnému zápisu v konkrétním programovacím jazyce). Obecně se ale algoritmus může objevit v jakémkoli jiném vědeckém odvětví. Jako jistý druh algoritmu se může chápat i např. kuchařský recept. V užším smyslu se slovem algoritmus rozumí takové postupy, které splňují některé silnější požadavky:

Rozděl a panuj

Související informace naleznete v článku Rozděl a panuj.

Klasický případ aplikace postupu odshora dolů. Algoritmy typu rozděl a panuj dělí problém na menší podproblémy, na něž se rekurzivně aplikují (až po triviální podproblémy, které lze vyřešit přímo), po čemž se dílčí řešení vhodným způsobem sloučí.

Zpracovává se množina V složená z n údajů. Tato množinu se rozdělí na k disjunktních podmnožin, které se zpracují každá zvlášť. Získané dílčí výsledky se pak spojíme odvodí se z nich řešení pro celou množinu V.

Klasickým případem je binární vyhledávání, nebo quicksort.
Hladový algoritmus

Související informace naleznete v článku Hladový algoritmus.

Velice přímočarý přístup k řešení určité třídy optimalizačních úloh.

Zpracovává se množina V složená z n údajů. Úkolem je najít podmnožinu W množiny V, která vyhovuje určitým podmínkám a přitom optimalizuje předepsanou účelovou funkci. Jakákoliv množina W, vyhovující daným podmínkám, se nazývá přípustné řešení. Přípustné řešení, pro které nabývá účelová funkce optimální hodnoty, se nazývá optimální řešení.

Hladový algoritmus se skládá z kroků, které budou procházet jednotlivé prvky z V, a v každém kroku rozhodne, zda se daný prvek hodí do optimálního řešení. Prvky V bude vybírat v pořadí určeném jistou výběrovou procedurou. Výběrová procedura bude založená na nějaké optimalizační míře – funkci, která může být odvozena od účelové funkce. V každém kroku ale musíme dostat přípustné řešení. Jakmile je učiněno takové rozhodnutí, už není dále revidováno. Příkladem je třeba hledání nejkratší cesty grafu.