Algoritmus - Historie editací

Michal Klajban: 26 revizí: IMPORT 1: °import všech stránek v hl. jmenném prostoru z KiskWiki (http://kisk.phil.muni.cz/)

2012-02-06T10:40:06Z

26 revizí: IMPORT 1: °import všech stránek v hl. jmenném prostoru z KiskWiki (http://kisk.phil.muni.cz/)

Vezka v 29. 6. 2010, 15:10

2010-06-29T15:10:04Z

Vezka v 29. 6. 2010, 15:08

2010-06-29T15:08:02Z

Vezka v 29. 6. 2010, 15:06

2010-06-29T15:06:28Z

Vezka v 29. 6. 2010, 14:25

2010-06-29T14:25:20Z

Vezka v 13. 6. 2010, 19:13

2010-06-13T19:13:15Z

Vezka v 13. 6. 2010, 19:10

2010-06-13T19:10:19Z

Vezka v 13. 6. 2010, 18:37

2010-06-13T18:37:54Z

Vezka v 13. 6. 2010, 18:04

2010-06-13T18:04:10Z

Vezka v 13. 6. 2010, 18:00

2010-06-13T18:00:42Z

@@ Řádek 16: / Řádek 16: @@
 == Definice ==
 [[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]]].
+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.
@@ Řádek 22: / Řádek 22: @@
 == 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ší.
+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ů ==

@@ Řádek 16: / Řádek 16: @@
 == Definice ==
 [[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 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]]].
+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, 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.
+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.

@@ Řádek 16: / Řádek 16: @@
 == Definice ==
 [[Soubor:portret.jpg|thumb|right|al-Khwārizmī]]
-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
+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 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]]].
-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í definované vlastnosti.
 == Vlastnosti algoritmů ==

@@ Řádek 23: / Řádek 23: @@
 == Vlastnosti algoritmů ==
-; ''Konečnost'' : Požadovaný výsledek musí být poskytnut v „rozumném" čase (pokud by výpočet trval na nejrychlejším počítači např. jeden milion let, těžko bychom mohli hovořit o algoritmu řešení, nemluvě o výpočtu, který by neskončil vůbec). Za rozumný lze považovat čas, kdy nám výsledek výpočtu k něčemu bude.
+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ší.
-; ''Hromadnost'' : Vstupní data nejsou v popisu algoritmu reprezentována konkrétními hodnotami, ale spíše množinami, ze kterých lze data vybrat (např. při řešení trojúhelníka mohou být velikosti stran desetinná čísla). Při popisu algoritmu v programovacím jazyce se to projeví tím, že vstupy do algoritmu jsou označeny symbolickými jmény.
+; ''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ý.
-; ''Jednoznačnost'' : Každý předpis je složen z kroků, které na sebe navazují. Každý krok můžeme charakterizovat jako přechod z jednoho stavu algoritmu do jiného, přičemž každý stav je určen zpracovávanými daty. Tím, jak data v jednotlivých stavech algoritmu vypadají, musí být jednoznačně určeno, který krok následuje (např: V řešení trojúhelníka může nastat situace, kdy vychází na základě vstupních dat jedno nebo dvě řešení. Situace je tedy nejednoznačná, řešení musí být jednoznačné, tzn. v předpisu se s touto možností musí počítat a musí v něm být návod, jak ji řešit.).
+; ''Opakovatelnost'' : Jsou-li zadána stejná data, algoritmus vždy dospěje ke stejným výsledkům
-; ''Opakovatelnost'' : Při použití stejných vstupních údajů musí algoritmus dospět vždy k témuž výsledku.
+; ''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ů ==
-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''', které využívají (volají) samy sebe.
+* '''Rekurzivní algoritmy ''' - využívají a odkazují sami na sebe
-* '''Hladové algoritmy''' se k řešení propracovávají po jednotlivých rozhodnutích, která, jakmile jsou jednou učiněna, už nejsou dále revidována.
+* '''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''' 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čí.
+* '''Iterativní algoritmy ''' - opakují některou svou část (cykly)
-* '''Algoritmy dynamického programování''' pracují tak, že postupně řeší části problému od nejjednodušších po složitější s tím, že využívají výsledky již vyřešených jednodušších podproblémů. Mnoho úloh se řeší převedením na grafovou úlohu a aplikací příslušného grafového algoritmu.
+* '''Algoritmy typu rozděl a panuj''' - problém na menší podproblémy a dílčí řešení slučují
-* '''Pravděpodobnostní algoritmy''' (někdy též probabilistické) provádějí některá rozhodnutí náhodně či pseudonáhodně.
+* '''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ů
-* V případě, že máme k dispozici více počítačů (procesorů nebo jader), můžeme úlohu mezi ně rozdělit, což nám umožní ji vyřešit rychleji; tomuto cíli se věnují '''paralelní algoritmy'''.
+* '''Pravděpodobnostní algoritmy ''' - některá rozhodnutí provádějí náhodně
-* '''Genetické algoritmy''' pracují na základě napodobování biologických evolučních procesů, postupným „pěstováním“ nejlepších řešení pomocí mutací a křížení. V genetickém programování se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápany jako možná řešení daného problému.
+* '''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''' si za cíl nekladou nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používají se v situacích, kdy dostupné zdroje (např. čas) nepostačují na využití exaktních algoritmů (nebo pokud nejsou žádné vhodné exaktní algoritmy vůbec známy).
+* '''Genetické algoritmy''' – napodobují biologické evoluční procesy
 == Reprezentace a zápis algoritmů ==
-* '''Slovním popisem''' – slovní popis v přirozeném jazyce
+[[Soubor:diagram.jpg|thumb|right|ukázka vývojového diagramu]]
-* '''Vývojovým diagramem''' (blokové schéma) – grafické znázornění algoritmu řešení úlohy jednotnými značkami a zkratkami (tento způsob kombinovaný se slovním popisem zde budu používat, tudíž přibude i článek na toto téma).
+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.
-* '''Strukturogramy''' – používá obdobné symboly ale přesnější, tento systém přesně splňuje podmínky důležité pro strukturované programování
+* '''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ě orientované diagramy 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.
+* '''Vývojový diagram''' - grafické znázornění algoritmu, řešení úlohy jednotnými značkami a zkratkami
-* '''Rozhodovací tabulky''' – používané při velmi složitých větveních.
+* '''Strukturogram''' – Úspornější znázornění algoritmu, kombinace grafického a textového popisu

@@ Řádek 15: / Řádek 15: @@
 == Definice ==
-[[Soubor:portret.jpg|thumb|right|Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmī]]
+[[Soubor:portret.jpg|thumb|right|al-Khwārizmī]]
 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).
+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ů ==
@@ Řádek 46: / Řádek 46: @@
 * '''Datově orientované diagramy 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.
 * '''Rozhodovací tabulky''' – používané při velmi složitých větveních.
 == Použitá literatura ==

← Starší verze	Verze z 6. 2. 2012, 10:40
(Žádný rozdíl)

@@ Řádek 1: / Řádek 1: @@
 '''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:'''
 	<blockquote>
-''nadřazené'' - </blockquote>
+''nadřazené'' - informatika, matematika </blockquote>
 	<blockquote>
-''podřazené'' - ---</blockquote>
+''podřazené'' - vývojový diagram, strukturogram, rozhodovací tabulka, HIPO diagram </blockquote>
@@ Řádek 20: / Řádek 20: @@
 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.
+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ů ==
@@ Řádek 39: / Řádek 39: @@
 * '''Genetické algoritmy''' pracují na základě napodobování biologických evolučních procesů, postupným „pěstováním“ nejlepších řešení pomocí mutací a křížení. V genetickém programování se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápany jako možná řešení daného problému.
 * '''Heuristické algoritmy''' si za cíl nekladou nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používají se v situacích, kdy dostupné zdroje (např. čas) nepostačují na využití exaktních algoritmů (nebo pokud nejsou žádné vhodné exaktní algoritmy vůbec známy).
 == 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.
+# Š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>.