Array ( [0] => 15481334 [id] => 15481334 [1] => cswiki [site] => cswiki [2] => Algoritmus [uri] => Algoritmus [3] => [img] => [4] => [day_avg] => [5] => [day_diff] => [6] => [day_last] => [7] => [day_prev_last] => [8] => [oai] => [9] => [is_good] => [10] => [object_type] => [11] => 0 [has_content] => 0 [12] => [oai_cs_optimisticky] => ) Array ( [0] => '''Algoritmus''' je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmus 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í jazyk|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. Zpravidla však na algoritmy klademe určitá omezení. [1] => [2] => == Vlastnosti algoritmů == [3] => V užším smyslu se slovem algoritmus označují takové postupy, které splňují některé silnější požadavky: [4] => ; ''Elementárnost'' : Algoritmus se skládá z konečného počtu jednoduchých (elementárních) kroků. [5] => ; ''Konečnost'' (finitnost): Každý algoritmus musí skončit v ''konečném'' počtu kroků. Tento počet kroků může být libovolně velký (podle rozsahu a hodnot vstupních údajů), ale pro každý jednotlivý vstup musí být konečný. Postupy, které tuto podmínku nesplňují, se mohou nazývat ''výpočetní metody''. Speciálním příkladem nekonečné výpočetní metody je ''reaktivní proces'', který průběžně reaguje s okolním prostředím. Někteří autoři však mezi algoritmy zahrnují i takovéto postupy. [6] => ; ''Obecnost (hromadnost, masovost, univerzálnost)'' : Algoritmus neřeší jeden konkrétní problém (např. „jak spočítat 3×7“), ale obecnou třídu obdobných problémů (např. „jak spočítat součin dvou celých čísel“), má širokou množinu možných vstupů. [7] => ; ''Determinovanost'': Algoritmus je determinovaný, pokud za stejných podmínek (pro stejné vstupy) poskytuje stejný výstup. Tato vlastnost je požadována u velké části úloh; existují však úlohy, kdy je naopak vyžadována náhodnost (například simulace [[Hrací kostka|vrhu kostkou]], [[Karetní hra|míchání karet]], generování [[Heslo|hesel]] a [[Klíč (kryptografie)|šifrovacích klíčů]]); na standardních počítačích je dosažení náhodnosti [[Hardwarový generátor náhodných čísel|obtížné]]. Pravděpodobnostní algoritmy v sobě mají zahrnutu náhodu a nemusí být determinované. [8] => ; ''Determinismus'':Každý krok algoritmu musí být ''jednoznačně'' a ''přesně'' definován; v každé situaci musí být naprosto zřejmé, co a jak se má provést, jak má provádění algoritmu pokračovat. Protože [[Jazyk (lingvistika)|přirozené jazyky]] neposkytují naprostou přesnost a jednoznačnost vyjadřování, byly pro zápis algoritmů navrženy [[programovací jazyk]]y, ve kterých má každý příkaz jasně definovaný význam. Vyjádření výpočetní metody v programovacím jazyce se nazývá [[počítačový program|program]]. Některé algoritmy jsou sice determinované, ale nejsou deterministické (například řadící algoritmus [[rychlé řazení]] s náhodnou volbou pivota). [9] => ; ''Výstup'' : Algoritmus má alespoň jeden ''výstup'', veličinu, která je v požadovaném vztahu k zadaným vstupům, a tím tvoří odpověď na problém, který algoritmus řeší (algoritmus vede od zpracování hodnot k výstupu) [10] => [11] => V praxi jsou proto předmětem zájmu hlavně takové algoritmy, které jsou v nějakém smyslu ''kvalitní''. Takové algoritmy splňují různá kritéria, měřená např. počtem kroků potřebných pro běh algoritmu, jednoduchost, efektivitu či eleganci. Problematikou efektivity algoritmů, tzn. metodami, jak z několika známých algoritmů řešících konkrétní problém vybrat ten vhodný, se zabývají odvětví [[Informatika|informatiky]] nazývané algoritmická analýza a [[teorie složitosti]]. [12] => [13] => == Metody návrhu == [14] => Algoritmus se navrhuje několika možnými způsoby: [15] => [16] => * '''Shora dolů''' – postup řešení rozkládáme na jednodušší operace, až dospějeme k elementárním krokům. [17] => * '''Zdola nahoru''' – z elementárních kroků vytváříme prostředky, které nakonec umožní zvládnout požadovaný problém. [18] => * '''Kombinace obou''' – obvyklý postup shora dolů doplníme "částečným krokem" zdola nahoru tím, že se například použijí knihovny funkcí, vyšší programovací jazyk nebo systém pro vytváření programů ([[CASE]]). [19] => [20] => == Paradigmata návrhu algoritmů == [21] => [22] => Při návrhu algoritmů se uplatňuje množství přístupů, které abstrahují od konkrétní úlohy. K nejužívanější metodám návrhu algoritmů patří: [23] => [24] => === Rozděl a panuj === [25] => {{Viz též|Rozděl a panuj (algoritmus)}} [26] => Klasický případ aplikace postupu odshora dolů. Algoritmy typu rozděl a panuj dělí problém na menší podproblémy, na něž se [[rekurze|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čí. [27] => [28] => Zpracovává se [[množina]] ''V'' složená z ''n'' údajů. Tato množina se rozdělí na ''k'' disjunktních [[podmnožina|podmnožin]], které se zpracují každá zvlášť. Získané dílčí výsledky se pak spojí a odvodí se z nich řešení pro celou množinu ''V''. [29] => [30] => Klasickým případem je [[binární vyhledávání]] nebo řadící algoritmus [[rychlé řazení]]. [31] => [32] => === Hladový algoritmus === [33] => {{Viz též|Hladový algoritmus}} [34] => Velice přímočarý přístup k řešení určité třídy [[Optimalizační úloha|optimalizačních úloh]]. [35] => [36] => 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 [[účelová funkce|úč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í''. [37] => [38] => 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. [39] => Příkladem je třeba hledání nejkratší [[Cesta (graf)|cesty grafu]]. [40] => [41] => === Dynamické programování === [42] => {{Viz též|Dynamické programování}} [43] => Dynamické programování se používá v případech kdy lze optimální řešení složit z řešení jednodušších problémů. Protože se požadavky na řešení jednodušších podproblémů mohou mnohokrát opakovat, je nutné zvolit správné pořadí jejich řešení a výsledky si zapamatovat pro opakované použití. [44] => [45] => Opírá se o ''princip optimality'': [46] => Optimální posloupnost rozhodnutí má tu vlastnost, že ať je počáteční stav a rozhodnutí jakékoliv, musí být všechna následující rozhodnutí optimální vzhledem k výsledkům rozhodnutí prvního. [47] => [48] => Typickým příkladem využití dynamického programování jsou [[Graf (teorie grafů)|grafové]] úlohy a jejich příslušné grafové algoritmy. [49] => [50] => === Použití hrubé síly === [51] => [52] => U některých úloh nezbývá než postupně probírat všechna možná řešení – tak zvaná [[Řešení hrubou silou|metoda hrubé síly]] – vygenerují se všechny možné posloupnosti a pak se vybere ta nejlepší. V některých případech lze použít metody, které vynechávají popřípadě odkládají procházení možností, které zřejmě nejsou optimální. [53] => [54] => === Hledání s návratem (backtracking) === [55] => {{Viz též|Backtracking}} [56] => Hledání s návratem založené na prohledávání [[stavový prostor|stavového prostoru]] problému. Též se nazývá metoda pokusů a oprav, metoda zpětného sledování, metoda [[prohledávání do hloubky]]. [57] => [58] => Metodu je možné použít v případě, že řešením je [[vektor]] (''x1,...,xn''), jehož jednotlivé složky vybíráme z množiny ''Si'', ''xi''∈''Si''. Zpravidla je třeba najít [[uspořádaná n-tice|n-tici]], která optimalizuje nějakou účelovou funkci ''P(x1,...,xn)''. Mohou se ale také hledat všechny n-tice, které tuto podmínku splňují. Metoda vytváří n-tice jednu složku po druhé. Přitom používá účelovou funkci (nebo nějakou vhodnou pomocnou funkci) a pro každou nově vytvořenou složku testuje, zda by taková n-tice vůbec mohla být optimální nebo splňovat dané podmínky. Jestliže pro nějaké ''xi'' žádaný vektor (''x1,...,xi'') nemůže být optimální, není třeba už žádný takový vektor testovat a vezmeme další možnou hodnotu i-té složky. Pokud jsou vyčerpány všechny hodnoty i-té složky, vrátí se metoda zpět o jeden krok a zkouší další možnou hodnotu ''xi-1''. [59] => [60] => Příkladem je třeba [[problém osmi dam]] nebo [[Jezdcova procházka|chůze koně celou šachovnicí]]. [61] => [62] => == Algoritmická složitost == [63] => [64] => Je třeba poznamenat, že abstraktní kritérium ''konečnosti'' je pro praktické použití ještě příliš slabé. V praxi je třeba zajistit, aby algoritmus skončil „v rozumném“ čase. Za rozumný čas lze v praxi považovat takový čas, který nám umožní smysluplně využít výsledek. [65] => [66] => Např. existuje jednoduchý algoritmus, který dokáže určit, zda v dané [[šachy|šachové]] pozici může hráč na tahu vynutit vítězství a zároveň dokáže určit nejlepší možný tah. Tento algoritmus se však nedá použít, protože by na svou činnost potřeboval ohromné množství času, jakkoli je toto množství konečné. Mimoto by takový algoritmus spotřeboval ohromné množství paměti, což je další praktický zřetel, který se uplatňuje při volbě algoritmu. I když průměrná počítačová paměť stále narůstá, pro některé algoritmy jí nebude nikdy dost. [67] => [68] => Pro vyčíslení [[složitost algoritmů|výpočetní složitosti algoritmů]] v závislosti na velikosti vstupních dat se používá [[asymptota|asymptotický]] zápis závislosti výpočetního času na rozsahu úlohy (typicky na počtu vstupních údajů). Například ''O(log N)'' znamená, že počet kroků algoritmu závisí logaritmicky na velikosti vstupních dat. Pokud u takového algoritmu zdvojnásobíme rozsah vstupních údajů, doba výpočtu se zvýší o jednu jednotku času, pokud bude vstupních dat čtyřikrát více, doba výpočtu se prodlouží o dvě jednotky času, a tak dále. To je třeba případ nalezení jednoho prvku o určité hodnotě v seznamu prvků seřazeném podle hodnoty (např. nalezení jména v telefonním seznamu). [69] => [70] => == Druhy algoritmů == [71] => Algoritmy můžeme klasifikovat různými způsoby. Mezi důležité druhy algoritmů patří: [72] => [73] => * [[rekurze|Rekurzivní]] algoritmy, které využívají (volají) samy sebe. [74] => [77] => * [[Pravděpodobnostní algoritmy]] (někdy též ''probabilistické'') provádějí některá rozhodnutí náhodně či [[pseudonáhodná čísla|pseudonáhodně]]. [78] => * V případě, že máme k dispozici více počítačů, 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]]. [79] => * [[Genetické algoritmy]] pracují na základě napodobování biologických [[Evoluce|evolučních]] procesů, postupným „pěstováním“ nejlepších řešení pomocí [[Mutace|mutací]] a [[křížení]]. V [[Genetické programování|genetickém programování]] se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápány jako možná řešení daného problému. [80] => * [[Heuristické algoritmy|Heuristický algoritmus]] si za cíl neklade nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používá 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). [81] => [82] => Přitom jeden algoritmus může patřit zároveň do více skupin; například může být zároveň rekurzivní a genetický. [83] => [84] => == Některé známé algoritmy == [85] => * [[Eratosthenovo síto]] [86] => * [[Euklidův algoritmus]] [87] => * [[Algoritmus de Casteljau]] [88] => * [[Dijkstrův algoritmus]] [89] => * [[Bellman-Fordův algoritmus]] [90] => [91] => == Etymologie == [92] => Slovo algoritmus pochází ze jména významného [[Persie|perského]] [[matematik]]a žijícího v první polovině [[9. století]] (cca [[780]]–[[840]]), kterým byl [[Al-Chorezmí|Abū ʻAbd Allāh Muhammad ibn Mūsā al-Chwārizmī]] ({{Cizojazyčně|ar|أبو عبد الله محمد بن موسى الخوارزمي}}) (doslova „Otec Abdulláha, Mohamed, syn Mojžíšův, pocházející z města Chwārizm (Chórézm, dnes [[Chiva]])“; tento kraj se nachází v [[Uzbekistán]]u jižně od [[Aralské moře|Aralského moře]]). Tento učenec ve svém díle prakticky vytvořil systém [[Arabské číslice|arabských číslic]] a základy algebry (konkrétně metody řešení [[Lineární rovnice|lineárních]] a [[Kvadratická rovnice|kvadratických]] [[Rovnice|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 [[Latina|latiny]] převedeno jako ''algorismus'', a původně znamenalo „provádění aritmetiky pomocí arabských číslic“; abacisté počítali pomocí [[Počítadlo|abaku]], algoristé pomocí algorismů. [93] => [94] => Postupem času se kvůli neznalosti původu slova jeho podoba měnila, záměnou arabského kořene s kořenem [[Řečtina|řeckého]] slova αριθμός (arithmos) se z algorismu stal algorithmus. (Později bylo v některých jazycích včetně češtiny ''th'' změněno na ''t'', v [[katalánština|katalánštině]] se vrátilo ''s''.) Toto slovo se používalo jako označení různých matematických postupů, např. v [[18. století]] označoval [[Latina|latinský]] termín ''algorithmus infitesimalis'' „metodu výpočtů s využitím nekonečně malých veličin, vynalezenou [[Leibniz]]em“. Slovo ''algoritmus'' v dnešním významu se používá až zhruba od [[20. století]]. [95] => [96] => == Historie: Vývoj pojmu „algoritmus“ == [97] => [98] => === Starověké Řecko === [99] => Algoritmy byly použity ve starověkém Řecku. Například Eratosthenovo síto nebo Eukleidův algoritmus. [100] => [101] => === Původ === [102] => Slovo algoritmus pochází z 9. století a je odvozeno z příjmení perského matematika [[Al-Chorezmí]]. Slovo původně odkazovalo na pravidla provádění aritmetických operací s arabskými číslicemi, ale vyvinulo se prostřednictvím překladu matematikova jména na „algoritmus“ v 18. století a zahrnuje všechny určité postupy pro řešení problémů nebo plnění úkolů. [103] => [104] => === Diskrétní a rozeznatelné symboly === [105] => '''Tally-značky''': K počítání stád, pytlů s obilím a peněz ve starověku se používaly akumulační kameny, značky vyškrábané na holích nebo záznam jednotlivých symbolů v jílu. Značky jsou obvykle v [[Jedničková soustava|jedničkové soustavě]], která se používá při kódování informací pro [[Turingův stroj|Turingovy stroje]] v [[Teorie automatů|teorii automatů]]. [106] => [107] => === Mechanická zařízení s diskrétními stavy === [108] => ''Hodiny'': Podle Boltera je vynález mechanických hodin jedním z klíčových vynálezů. Zejména pak jejich setrvačná část – [[Lihýř]]. Přesný automat vedl okamžitě k mechanickému automatu (začátek 13. století) a nakonec k výpočetním strojům – diferenční a [[analytický stroj]] ([[Charles Babbage]] a [[Ada Lovelace]]) v polovině [[19. století]]. Lovelace je připočítáno první vytvoření algoritmu, který je zpracovatelný počítačem. Babbageův analytický stroj je považován za první Turingův kompletní počítač. Charles Babbage je někdy nazýván jako historicky první programátor. [109] => [110] => ''Logické stroje 1870'' – [[William Stanley Jevons|Jevonsovo]] logické počítadlo a logický stroj: Technický problém byl zjednodušení logických rovnice, které bylo představeno v podobě podobné tomu, co je nyní známo jako [[Karnaughova mapa]]. Jevons (1880) popisuje první jednoduché počítadlo ze dřeva vybavené kolíky tak, aby jakákoli jeho třída kombinací šla vyzvednout mechanicky. Tento stroj je představen členům královské společnosti v roce 1870. [111] => [112] => ''[[Tkalcovský stav]], [[Děrný štítek|děrné štítky]], [[telegrafie]] a [[telefonie]]'' – elektromechanické relé: Bell a Newell (1971) označují, že tkalcovský stav (1801), předchůdce děrných štítků (1887) a telefonní spínací technologie vedly k vývoji prvních počítačů. V polovině 19. století telegraf, předchůdce telefonu, byl v provozu po celém světě. V roce 1910 se objevil [[dálnopis]], který využíval mezinárodní telegrafní abecedu. [113] => [114] => ''Telefonní sítě elektromechanických relé'' – George Stibitz (1937) pracoval v Bellových laboratořích a dokončil kalkulátor, který je schopen pracovat s komplexními čísly. [115] => [116] => === Matematika v průběhu 19. století až do poloviny 20. století === [117] => ''Symboly a pravidla'': V rychlém sledu za sebou matematika George Boole, [[Gottlob Frege]] a [[Giuseppe Peano]] redukovala aritmetiku do sekvence symbolů, se kterými se manipulovalo pomocí daných pravidel. Peanovo ''The principles of arithmetic, presented by a new method'' (1888) byl první pokus o axiomatizování matematiky v symbolický jazyk. [118] => [119] => Heijenoort dává Fregemu (1879) tuto slávu: Fregovo dílo je možná nejdůležitější práce, která kdy bylo v logice napsána. Tato práce byla dále zjednodušena a umocněna [[Alfred North Whitehead|Alfredem North Whiteheadem]] a [[Bertrand Russell|Bertrandem Russellem]] v jejich Principia Mathematica (1910–1913). [120] => [121] => ''Paradoxy'': Ve stejné době se objevila řada znepokojivých elementů v literatuře, zejména [[Burali-Fortiho paradox]] (1897), [[Russellův paradox]] (1902–1903) a Richardův paradox. Výsledné úvahy vedly k [[Gödelovy věty o neúplnosti|Gödelovým větám o neúplnosti]]. [122] => [123] => ''Efektivní vyčíslitelnost'': Ve snaze vyřešit [[Entscheidungsproblem]] přesně definovaným [[David Hilbert|Hilbertem]] v roce 1928 museli matematici nejprve definovat, co se rozumí pod pojmem „efektivní metoda“ nebo „efektivní výpočet“. V rychlém sledu se objevili [[Alonzo Church]], [[Stephen Cole Kleene]] a J. B. Rosser, kteří jsou známí především díky [[lambda kalkul]]u. Church pak společně s [[Alan Turing|Turingem]] ukázal, že lambda kalkul (a další výpočetní modely) má výpočetní sílu [[Turingův stroj|Turingova stroje]], což otevřelo cestu k [[Churchova–Turingova teze|Churchově–Turingově tezi]]. [124] => [125] => == Právní ustanovení == [126] => Algoritmy nejsou obvykle patentovány. Samotná manipulace s abstraktními pojmy, čísly, či dokonce signály není v USA (dle USPTO 2006) považována za proces. Jinými slovy lze říci, že algoritmy nelze patentovat (podobně jako v kauze [[Gottschalk v. Benson]]). Nicméně některá praktická využití algoritmů lze patentovat. Například v kauze [[Diamond v. Diehr]] byl patentován jednoduchý algoritmus [[Zpětná vazba|zpětné vazby]] na pomoc při vytvrzování syntetické gumy. Patentování [[Software|softwaru]] je i přes to velmi kontroverzní. Některé patentované algoritmy se potýkají s negativní kritikou, a to především algoritmy sloužící ke [[Komprese dat|kompresi dat.]] [127] => [128] => == Reference == [129] => # heslo ''Algorithmus''. [[Ottův slovník naučný]] I, p. 857 [130] => # [[Donald E. Knuth]]: ''[[The Art of Computer Programming]]'', Vol 1–3, Addison Wesley 1998. {{ISBN|0-201-48541-9}}. Klasické dílo oboru, definitivní příručka. [131] => # Gaston H. Gonnet, Ricardo Baeza-Yates: Zdrojové texty programů v [http://www.dcc.uchile.cl/~rbaeza/handbook/ ''Handbook of Algorithms and Data Structures.''] [132] => # ''[http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures]''. „Slovník algoritmů, technik, datových struktur, typických problémů a příslušných definic.“ [133] => # [[United States Patent and Trademark Office]] (2006), [http://www.uspto.gov/web/offices/pac/mpep/documents/2100_2106_02.htm ''2106.02 **>Mathematical Algorithms: 2100 Patentability''], Manual of Patent Examining Procedure (MPEP). Latest revision August 2006 [134] => [135] => == Externí odkazy == [136] => * {{commonscat}} [137] => * {{Wikicitáty|téma=Algoritmus}} [138] => * {{Wikislovník|heslo=algoritmus}} [139] => * [http://technet.idnes.cz/prvni-programatorka-ada-lovelace-dqd-/tec_technika.aspx?c=A151209_141727_tec_technika_pka První algoritmus napsala žena. Programovala dávno před prvním počítačem] [140] => {{Autoritní data}} [141] => [142] => [[Kategorie:Algoritmy| ]] [143] => [[Kategorie:Programování]] [] => )
good wiki

Algoritmus

Algoritmus je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmus 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).

More about us

About

Expert Team

Vivamus eget neque lacus. Pellentesque egauris ex.

Award winning agency

Lorem ipsum, dolor sit amet consectetur elitorceat .

10 Year Exp.

Pellen tesque eget, mauris lorem iupsum neque lacus.

You might be interested in

,'rychlé řazení','Turingův stroj','Latina','rekurze','Al-Chorezmí','Charles Babbage','Jazyk (lingvistika)','množina','křížení','Řešení hrubou silou','Optimalizační úloha','teorie složitosti'

Al-Chorezmí

Křížení

Latina

Množina

Rekurze