Algoritmus: Porovnání verzí
Z WikiKnihovna
m (26 revizí: IMPORT 1: °import všech stránek v hl. jmenném prostoru z KiskWiki (http://kisk.phil.muni.cz/)) |
|||
| (Není zobrazeno 6 mezilehlých verzí od jednoho dalšího uživatele.) | |||
| Řádek 1: | Řádek 1: | ||
'''Autor:''' Petr Věžník | '''Autor:''' Petr Věžník | ||
| − | '''Klíčová slova:''' | + | '''Klíčová slova:''' algoritmus, vlastnosti algoritmů, definice algoritmů, reprezentace a zápis algoritmů |
| − | '''Synonyma:''' | + | '''Synonyma:''' návod, postup |
'''Související pojmy:''' | '''Související pojmy:''' | ||
<blockquote> | <blockquote> | ||
| − | ''nadřazené'' - </blockquote> | + | ''nadřazené'' - informatika, matematika </blockquote> |
<blockquote> | <blockquote> | ||
| − | ''podřazené'' - | + | ''podřazené'' - vývojový diagram, strukturogram, rozhodovací tabulka, HIPO diagram </blockquote> |
== Definice == | == Definice == | ||
| − | [[Soubor:portret.jpg|thumb|right| | + | [[Soubor:portret.jpg|thumb|right|al-Khwārizmī]] |
| − | + | Samotné slovo algoritmus je odvozeno ze jména významného perského matematika a astronoma jménem Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī[[#Literatura|[4]]]. Ten ve svém díle vytvořil systém arabských číslic a základy algebry. Jeho jméno bylo do latinky převedeno jako algoritmus a stalo se synonymem pro označení různých matematických postupů. Teprve zhruba od 20. století se používá v dnešním významu slova a je jedním ze základních pojmů v matematice. ''„Algoritmem rozumíme 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"''[[#Literatura|[2]]]. Nebo také můžeme říci, že ''„algoritmus je možno chápat i jako mlýnek na data. Nasypeme-li do něj správná data a zameleme, obdržíme požadovaný výsledek“'' [[#Literatura|[3, s. 28]]]. | |
| − | + | Přestože se pojem algoritmus objevuje především v informatice a matematice, 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í definované vlastnosti. | |
| − | |||
== 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ě |
| − | * ''' | + | * '''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ů == | ||
| + | [[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 | ||
| + | * '''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 [[#Literatura|[3]]]. | ||
| + | * '''Rozhodovací tabulka''' – používá se zejména při složitějších větvení, tabulka rozdělená do kvadrantů | ||
| + | |||
| + | |||
== Použitá literatura == | == 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>. | # 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, | + | # Š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>. | # ''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>. | # ''History of mathematics for young mathematicians: Al-Khwarizmi'' [online]. [cit. 2010-06-11]. Dostupný z WWW: <http://www.mathsisgoodforyou.com/people/alkhwarizmi.htm>. | ||
Aktuální verze z 6. 2. 2012, 10:40
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
Samotné slovo algoritmus je odvozeno ze jména významného perského matematika a astronoma jménem Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī[4]. Ten ve svém díle vytvořil systém arabských číslic a základy algebry. Jeho jméno bylo do latinky převedeno jako algoritmus a stalo se synonymem pro označení různých matematických postupů. Teprve zhruba od 20. století se používá v dnešním významu slova a je jedním ze základních pojmů v matematice. „Algoritmem rozumíme 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"[2]. Nebo také můžeme říci, že „algoritmus je možno chápat i jako mlýnek na data. Nasypeme-li do něj správná data a zameleme, obdržíme požadovaný výsledek“ [3, s. 28].
Přestože se pojem algoritmus objevuje především v informatice a matematice, 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í definované vlastnosti.
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>.
