Algoritmus

Algoritmus je schematický postup pro řešení určitého druhu problémů, který je prováděn pomocí konečného množství přesně definovaných kroků. Ačkoliv se dnes tento pojem používá především v informatice a přírodních vědách obecně, tak je jeho působnost daleko širší (kuchyňské recepty, návody a postupy...). Samotné slovo algoritmus pochází ze jména perského matematika 9. století Abu Jafar Muhammada ibn Mūsā al-Chwārizmího, který ve svých dílech položil základy algebry (arabské číslice, řešení lineárních a kvadratických rovnic).

Vlastnosti algoritmů

  1. Konečnost – algoritmus má konečné množství kroků.
  2. Určitost – všechny kroky algoritmu jsou přesně definovány.
  3. Korektnost – algoritmus skončí pro libovolná (korektní) data správným výsledkem v konečném množství kroků.
  4. Obecnost – algoritmus řeší všechny úlohy daného typu.

Dělení algoritmů

Rekurzivní a iterativní algoritmy

Iterativní algoritmus je takový, který spočívá v opakování určité své části (bloku). Rekurzivní algoritmus naproti tomu opakuje kód prostřednictvím volání sebe sama (obvykle na podproblémech menší velikosti). Každý rekurzivní algoritmus lze převést do iterativní podoby. Samotný převod často řeší automaticky kompilátor nebo virtuální stroj daného programovacího jazyka.

Výhoda rekurzivních algoritmů je v jejich snadno čitelném a kompaktním zápisu. Nevýhodou je spotřeba dodatečných systémových prostředků pro udržení jednotlivých rekurzivních volání.

Deterministické a nedeterministické algoritmy

Deterministický je takový algoritmus, který má v každém svém kroku právě jednu možnost, jak pokračovat. Nedeterministický jich má více. Příkladem může být deterministický a nedeterministický automat.

Sériové, paralelní a distribuované algoritmy

Sériový algorimus vykonává všechy kroky v sérii (jeden po druhém), paralelní algoritmus tyto kroky vykonává zároveň (ve více vlákech) a distribuovaný algoritmus kroky vykovává zároveň na více strojích.

Asymptotická složitost algoritmu

Asymptotická složitost algoritmu charakterizuje počet provedených operací v závislosti na velikosti dat. Například pokud procházíme pole, pak složitost bude lineární (na každý prvek připadá konstantní množství operací), pokud jej ovšem řadíme například bubble sortem, pak složitost bude kvadratická (na n prvků bude připadat n^{2} operací).

Třída složitosti

Hierarchie tříd složitosti
Hierarchie tříd složitosti

Třída složitosti stanovuje obtížnost rozhodnutelnosti daného problému na Turingově stroji.

  • Třída P – obsahuje problémy rozhodnutelné v polynomiálním čase.
    • Má daný graf kostru o velikosti maximálně k?
    • Existuje v daném acyklickém grafu mezi uzly a a b cesta, jejíž délka je nejvýše k?
  • Třída NP – obsahuje problémy, které jsou rozhodnutelné pomocí nedeterministického Turingova stroje v polynomiálním čase – tzn. jsme schopni ověřit jejich řešení v polynomiálním čase.
    • Lze daný graf obarvit maximálně k barvami?
    • Existuje v daném grafu hamiltonovská kružnice?
    • Existuje v daném grafu klika o alespoň k vrcholech?

Literatura

  • WRÓBLEWSKI, Piotr. Algoritmy : Datové struktury a programovací techniky. Brno : Computer press, 2004. 351 s. ISBN 80-251-0343-9.
  • KVASIL, Bohumil, et al. Algoritmus. In Malá československá encyklopedie. Praha : Academia, 1984. s. 108.
  • VELEBIL, Jiří. Diskrétní matematika : Text k přednášce. Praha : [s.n.], 2007. 197 s.
Hodnocení (20): 4,25

Přečtěte si také

Diskuse





Hušny je pán9.9.2014
Hušny je pán (y)
HUšny je gay9.9.2014
hušny je gay
BRISINGR9.9.2014
ja se asi poseru nasel jsem noveho chlapce a jdu snip prcat za strom kamo je fakt libovej ma velkou predel i pero ja jsem
Vojta zizka a jsem gay ano kdo chce se mnou pichat tak napiste
skila9.9.2014
jo myluju
BRISINGR9.9.2014
ja mi9luju justina bibra to baby ja u toho kazdej den se na to divam a mastim bambus je to fakt huuuuuuuuuuuuuusty
skila9.9.2014
ty nekopiruj
skila9.9.2014
prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata prasata
skila 9.9.2014
nekopiruuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuj
skilla9.9.2014


l

hovada
skila9.9.2014
tri9eu5y98fud999999999jhhggggggggggggggfiddddggjkjhrdzolxfkjvjkbvjkfdzlghnfzkjcvnjil\zdjkfldzbiklfgbhkbdnfz;ghzuhgzdfhniuyhgjbviufiuhajkfalhruiebjkflghrialjvnijrabrbvriafiabnioaniblfigbzku\bvfabvryabvhuiargvjbfdvjkz,dvfbhduofbvkl\bdfvjhkzlbvhjcvbkljb\kdbvdjhkl\bdhjvkc\hklckjbhvhjsdhb\vil\bdvjhld\bdjcvk,bzshdcvjy dkbvlhbdrfavyrkusjzkhgbvfuyrhfhyfufgfidfnfgutfytrjtfuyrhguyrgtfuvfjfuyfodfhcvidnvuyfifbhnbiufjfjgfgdfhogfijhogahuogfihofjngfdjngfjngdfjgfjgfbgfbgdfbgdfbhgzdfbhlgfjbhdfsjhk\zhrbhreuyszvbfejaklbvuhjckxhfbvuaikz\bvjckx\

sdfvknbjzkdzd\fbuzbviurzgvrbfhugdfvubfduivbuzgbvhbzdukvbkcjhhhfnvjdyrifhbnnkhjyoghjkflnjggjhuvugfugf

step12.3.2014
x=0
pro J=2 až 5 (krok 1) dělej
{je/LI j>x pak dělej (x=x+2) }
Leinad27.2.2014
Jak se dá dokázat "Každý rekurzivní algoritmus lze převést do iterativní podoby?"
David11.9.2010
Prosím nevíte kde bych mohl koupit tuto učebnici: Eva Milková, Petr Voborník - Algoritmy : objasnění, procvičení a vizualizace základních algoritmických konstrukcí
Praha : Alfa, 2008, ISBN: 978-80-87197-10-3
ado2122.4.2010
Ahoj,
ak chces mozes ma kontaktovat na newblueman21 gmail com. Mozno mozem niecim prispiet...
iwtu22.4.2010
Co sa tyka teorie algoritmov, velmi mozem doporucit Lev Bukovsky - Teoria Algoritmov, UPJS.
Do algoritmov je asi klasicky najznamejsi Uvod Introduction To Algorithm, MIT
altai5.4.2010
Souhlasim se Paulim. Mam taky Pavla Topfra a muzu jen doporucit.
Dobrá knížka18.2.2010
Eva Milková - Algoritmy : typové konstrukce a příklady
1. vydání, Hradec Králové : Gaudeamus, 2001, ISBN: 80-7041-998-9
Eva Milková, Petr Voborník - Algoritmy : objasnění, procvičení a vizualizace základních algoritmických konstrukcí
Praha : Alfa, 2008, ISBN: 978-80-87197-10-3
Pavel Mička3.2.2010
Paulie: Osobně mám doma jen toho Wróblewskiho, protože vesměs čerpám ze skript k daným oblastem...uznávám, že Wróblewski není pro začátečníky nic moc, ale je to poměrně obsažný přehled i pokročilejších technik.
Na toho Töpfera se podívám, jestli ho někde uvidím, ale s těmito knížkami mám poněkud problém, protože Knuth mi přijde jako docela brutální četba (nejsem přítelem kódu v assembleru), naproti tomu valná část ostatních učebnic poskytuje pouze náhled na jednodušší problematiku.
Paulie2.2.2010
Wróblewskiho knížka není pro studium algoritmů podle mě příliš vhodná - obsahuje spoustu chyb a nelíbí se mi, jak je tam vysvětluje. Pro začátečníky je mnohem lepší učebnice Pavla Töpfera Algoritmy a datové struktury.