Algoritmus: Porovnání verzí
Z WikiKnihovna
| Řádek 23: | Řádek 23: | ||
== Vlastnosti algoritmů == | == Vlastnosti algoritmů == | ||
| − | + | Jak již bylo řečeno výše, každý postup musí splňovat definované vlastnosti, abychom jej mohli klasifikovat jako algoritmus. Jaké to jsou vlastnosti je nastíněno dále v textu, nejprve je však nutné varovat, že teorie se zde trochu rozchází. Můžeme nalézt jak rozličné definice vlastností, tak nesjednocenou terminologii. Proto v textu zaměříme pouze na ty nejdůležitější. | |
| − | + | ; ''Konečnost'' : Každý algoritmus musí obsahovat pouze konečné množství kroků, po kterých skončí (jinými slovy, nezacyklí se). Bez této vlastnosti by byl algoritmus nepoužitelný. | |
| − | ; '' | + | ; ''Opakovatelnost'' : Jsou-li zadána stejná data, algoritmus vždy dospěje ke stejným výsledkům |
| − | ; ''Opakovatelnost'' : | + | ; ''Rezultativnost'' :Algoritmus vede vždy ke správnému výsledku |
| − | ; ''Rezultativnost'' : Algoritmus vede ke správnému výsledku. | + | V literatuře je možné se dočíst také o dalších vlastnostech, jako je např. obecnost, determinovatelnou, hromadnost, jednoznačnost, aj. |
== Dělení algoritmů == | == Dělení algoritmů == | ||
| − | Algoritmy můžeme klasifikovat různými způsoby, přičemž jeden algoritmus může patřit zároveň do více skupin | + | Algoritmy můžeme klasifikovat různými způsoby, přičemž jeden algoritmus může patřit zároveň do více skupin. Narozdíl od vlastností algoritmů, zde je terminologie poměrně sjednocená. |
| − | * '''Rekurzivní algoritmy''' | + | * '''Rekurzivní algoritmy ''' - využívají a odkazují sami na sebe |
| − | * '''Hladové algoritmy''' se k řešení | + | * '''Hladové algoritmy''' - propracovávají se k řešení pomocí jednotlivých rozhodnutí, která jakmile jsou učiněna, už nejsou dále revidována |
| − | * '''Algoritmy typu rozděl a panuj''' | + | * '''Iterativní algoritmy ''' - opakují některou svou část (cykly) |
| − | * '''Algoritmy dynamického programování''' | + | * '''Algoritmy typu rozděl a panuj''' - problém na menší podproblémy a dílčí řešení slučují |
| − | * '''Pravděpodobnostní algoritmy''' | + | * '''Algoritmy dynamického programování''' - řeší problémy od nejjednodušších po složitější, přičemž využívají výsledky již vyřešených jednodušších problémů |
| − | * | + | * '''Pravděpodobnostní algoritmy ''' - některá rozhodnutí provádějí náhodně |
| − | * '''Genetické algoritmy''' | + | * '''Paralelní algoritmy''' - využívají více počítačů, úlohu mezi ně rozdělí a díky tomu dospějí k rychlejšímu výsledku |
| − | * '''Heuristické algoritmy''' | + | * '''Genetické algoritmy''' – napodobují biologické evoluční procesy |
| + | * '''Heuristické algoritmy''' – nehledají přesná řešení, pouze nějaká vhodná přiblížení | ||
| + | |||
| + | |||
== Reprezentace a zápis algoritmů == | == Reprezentace a zápis algoritmů == | ||
| − | * ''' | + | [[Soubor:diagram.jpg|thumb|right|ukázka vývojového diagramu]] |
| − | * ''' | + | Zde je vysvětleno několik základních způsobů, jak můžeme zapsat algoritmy. Správně zapsat algoritmus je důležité především pro jeho další využití, případně úpravu. |
| − | * ''' | + | * '''Slovní popis''' – slovní popis v přirozeném jazyce. Vysvětlení krok po kroku, co algoritmus v dané fázi provádí a jak bude reagovat |
| − | * '''Datově | + | * '''Vývojový diagram''' - grafické znázornění algoritmu, řešení úlohy jednotnými značkami a zkratkami |
| − | * '''Rozhodovací | + | * '''Strukturogram''' – Úspornější znázornění algoritmu, kombinace grafického a textového popisu |
| + | * '''Datově orientovaný diagram HIPO ''' – (z angl. Hierarchy plus Input- Process- Output), je grafickým vyjádřením funkčního členění problému, struktury dat a postupu řešení problému při různém stupni podrobnosti [[#Literatura|[3]]]. | ||
| + | * '''Rozhodovací tabulka''' – používá se zejména při složitějších větvení, tabulka rozdělená do kvadrantů | ||
Verze z 29. 6. 2010, 14:25
Autor: Petr Věžník
Klíčová slova: algoritmus, vlastnosti algoritmů, definice algoritmů, reprezentace a zápis algoritmů
Synonyma: návod, postup
Související pojmy:
nadřazené - informatika, matematika
podřazené - vývojový diagram, strukturogram, rozhodovací tabulka, HIPO diagram
Definice
Slovo algoritmus pochází ze jména významného perského matematika žijícího v první polovině 9. století (cca 780–840 n. l.), kterým byl Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī. Tento učenec ve svém díle prakticky vytvořil systém arabských číslic a základy algebry (konkrétně metody řešení lineárních a kvadratických rovnic), jejíž název pochází přímo z titulu tohoto díla (Kitūb al-jabr waāl-muqūbala). Jeho jméno bylo do latiny převedeno jako algorismus, a původně znamenalo: „provádění aritmetiky pomocí arabských číslic
Pojem algoritmus je jedním ze základních pojmů v matematice. Algoritmem se rozumí soubor přesně stanovených pravidel, určující pořadí daného konečného systému operací, který zabezpečuje řešení všech úloh daného typu.
Přestože se pojem algoritmus objevuje především v informatice, do jisté míry se s ním můžeme setkat i v dalších vědních oborech. V širším slova smyslu se jedná o jakýsi návod nebo postup. V užším slova smyslu se algoritmem rozumí pouze takové postupy, které splňují jasně definované vlastnosti (viz dále).
Vlastnosti algoritmů
Jak již bylo řečeno výše, každý postup musí splňovat definované vlastnosti, abychom jej mohli klasifikovat jako algoritmus. Jaké to jsou vlastnosti je nastíněno dále v textu, nejprve je však nutné varovat, že teorie se zde trochu rozchází. Můžeme nalézt jak rozličné definice vlastností, tak nesjednocenou terminologii. Proto v textu zaměříme pouze na ty nejdůležitější.
- Konečnost
- Každý algoritmus musí obsahovat pouze konečné množství kroků, po kterých skončí (jinými slovy, nezacyklí se). Bez této vlastnosti by byl algoritmus nepoužitelný.
- Opakovatelnost
- Jsou-li zadána stejná data, algoritmus vždy dospěje ke stejným výsledkům
- Rezultativnost
- Algoritmus vede vždy ke správnému výsledku
V literatuře je možné se dočíst také o dalších vlastnostech, jako je např. obecnost, determinovatelnou, hromadnost, jednoznačnost, aj.
Dělení algoritmů
Algoritmy můžeme klasifikovat různými způsoby, přičemž jeden algoritmus může patřit zároveň do více skupin. Narozdíl od vlastností algoritmů, zde je terminologie poměrně sjednocená.
- Rekurzivní algoritmy - využívají a odkazují sami na sebe
- Hladové algoritmy - propracovávají se k řešení pomocí jednotlivých rozhodnutí, která jakmile jsou učiněna, už nejsou dále revidována
- Iterativní algoritmy - opakují některou svou část (cykly)
- Algoritmy typu rozděl a panuj - problém na menší podproblémy a dílčí řešení slučují
- Algoritmy dynamického programování - řeší problémy od nejjednodušších po složitější, přičemž využívají výsledky již vyřešených jednodušších problémů
- Pravděpodobnostní algoritmy - některá rozhodnutí provádějí náhodně
- Paralelní algoritmy - využívají více počítačů, úlohu mezi ně rozdělí a díky tomu dospějí k rychlejšímu výsledku
- Genetické algoritmy – napodobují biologické evoluční procesy
- Heuristické algoritmy – nehledají přesná řešení, pouze nějaká vhodná přiblížení
Reprezentace a zápis algoritmů
Zde je vysvětleno několik základních způsobů, jak můžeme zapsat algoritmy. Správně zapsat algoritmus je důležité především pro jeho další využití, případně úpravu.
- Slovní popis – slovní popis v přirozeném jazyce. Vysvětlení krok po kroku, co algoritmus v dané fázi provádí a jak bude reagovat
- Vývojový diagram - grafické znázornění algoritmu, řešení úlohy jednotnými značkami a zkratkami
- Strukturogram – Úspornější znázornění algoritmu, kombinace grafického a textového popisu
- Datově orientovaný diagram HIPO – (z angl. Hierarchy plus Input- Process- Output), je grafickým vyjádřením funkčního členění problému, struktury dat a postupu řešení problému při různém stupni podrobnosti [3].
- Rozhodovací tabulka – používá se zejména při složitějších větvení, tabulka rozdělená do kvadrantů
Použitá literatura
- DVORSKÝ, Jiří. Algoritmy I : Pracovní verze skript [online]. 2008 [cit. 2010-06-10]. Dostupné z WWW: <http://www.cs.vsb.cz/dvorsky/Download/Algoritmy/ZakladyAlgoritmizace28022007.pdf>.
- ŠALÁT, Tibor. Malá encyklopedie matematiky. 1. vyd. Bratislava : Obzor, 1967. 692 s. ISBN 65-083-87.
- Algoritmy: Teoretický úvod [online]. 2006 [cit. 2010-06-11]. Dostupný z WWW: <http://www.manualy.net/article.php?articleID=12>.
- History of mathematics for young mathematicians: Al-Khwarizmi [online]. [cit. 2010-06-11]. Dostupný z WWW: <http://www.mathsisgoodforyou.com/people/alkhwarizmi.htm>.
