巴基斯坦反恐取得进展 至少108名恐怖分子被打死

百度 本期简介本期简介：封面人物.CoverStory单霁翔，国家宝藏的摩登时代王刚：从前看见藏品就说钱，而今说故事总制片人说《国家宝藏》陈振裕，穿行在文物里的福尔摩斯图说世情.PhotoStory准女王范儿88岁网红奶奶世界.World政要丨金正恩文在寅，冬奥再打半岛旗梅姨，没能成为撒切尔夫人第二人物丨鲍威尔：不学经济的美联储新主席名流丨特朗普前妻，彪悍人生堪比邓文迪观美国丨全民消费情人节中国.China特别报道丨周令钊，百岁画狗票人物丨徐立平，雕刻火药的大国工匠周飞虎，真实的医界战狼赌王之子何猷君，不靠父亲靠大脑财经.Business改革四十周年丨宗庆后：我是从底层崛起的凡人商道丨叶大清：金融创新让中国弯道超车财智丨潘刚：当不好质检员的老板成不了企业家伊东重典：让产品成为表现个性的载体文史.Culture名家丨阿来，穿行在藏区与世界之间人物丨拓晓堂，为古书续命品书丨一堂对口相声式的美术课典藏丨《愚公移山》，徐悲鸿的伟大之图艺界.Artist大咖丨廖一梅：像我这么拧巴的人，也能有欢乐明星丨岳云鹏，时刻跟自己说别嘚瑟剧中人丨马戏之王的真真假假专栏.Column资治新编丨魏文侯的识人术佳人列传丨原版崔莺莺，被渣男辜负的可怜人佛陀故事丨开启说法之旅生活.Life美食丨奶酪，乡村非主流的逆袭科普丨中国克隆，拔毛变猴不是梦吐槽丨决战年终饭局名人经历丨李昌钰洗试管王源说丨挪威的雪，如履薄冰

Algoritmus je p?esny návod ?i postup, kterym lze vy?e?it dany typ úlohy. Pojem algoritmus se nej?astěji objevuje p?i programování, kdy se jím myslí teoreticky princip ?e?ení problému (oproti p?esnému zápisu v konkrétním programovacím jazyce). Obecně se ale algoritmus m??e objevit v jakémkoli jiném vědeckém odvětví. Jako jisty druh algoritmu se m??e chápat i nap?. kucha?sky recept. Zpravidla v?ak na algoritmy klademe ur?itá omezení.

Vlastnosti algoritm?

V u??ím smyslu se slovem algoritmus ozna?ují takové postupy, které splňují některé silněj?í po?adavky:

Elementárnost

Algoritmus se skládá z kone?ného po?tu jednoduchych (elementárních) krok?.

Kone?nost (finitnost)

Ka?dy algoritmus musí skon?it v kone?ném po?tu krok?. Tento po?et krok? m??e byt libovolně velky (podle rozsahu a hodnot vstupních údaj?), ale pro ka?dy jednotlivy vstup musí byt kone?ny. Postupy, které tuto podmínku nesplňují, se mohou nazyvat vypo?etní metody. Speciálním p?íkladem nekone?né vypo?etní metody je reaktivní proces, ktery pr?bě?ně reaguje s okolním prost?edím. Někte?í auto?i v?ak mezi algoritmy zahrnují i takovéto postupy.

Obecnost (hromadnost, masovost, univerzálnost)

Algoritmus ne?e?í jeden konkrétní problém (nap?. ?jak spo?ítat 3×7“), ale obecnou t?ídu obdobnych problém? (nap?. ?jak spo?ítat sou?in dvou celych ?ísel“), má ?irokou mno?inu mo?nych vstup?.

Determinovanost

Algoritmus je determinovany, pokud za stejnych podmínek (pro stejné vstupy) poskytuje stejny vystup. 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 vrhu kostkou, míchání karet, generování hesel a ?ifrovacích klí??); na standardních po?íta?ích je dosa?ení náhodnosti obtí?né. Pravděpodobnostní algoritmy v sobě mají zahrnutu náhodu a nemusí byt determinované.

Determinismus

Ka?dy krok algoritmu musí byt jednozna?ně a p?esně definován; v ka?dé situaci musí byt naprosto z?ejmé, co a jak se má provést, jak má provádění algoritmu pokra?ovat. Proto?e p?irozené jazyky neposkytují naprostou p?esnost a jednozna?nost vyjad?ování, byly pro zápis algoritm? navr?eny programovací jazyky, ve kterych má ka?dy p?íkaz jasně definovany vyznam. Vyjád?ení vypo?etní metody v programovacím jazyce se nazyvá program. Některé algoritmy jsou sice determinované, ale nejsou deterministické (nap?íklad ?adící algoritmus rychlé ?azení s náhodnou volbou pivota).

Vystup

Algoritmus má alespoň jeden vystup, veli?inu, která je v po?adovaném vztahu k zadanym vstup?m, a tím tvo?í odpově? na problém, ktery algoritmus ?e?í (algoritmus vede od zpracování hodnot k vystupu)

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?ebnych pro běh algoritmu, jednoduchost, efektivitu ?i eleganci. Problematikou efektivity algoritm?, tzn. metodami, jak z několika známych algoritm? ?e?ících konkrétní problém vybrat ten vhodny, se zabyvají odvětví informatiky nazyvané algoritmická analyza a teorie slo?itosti.

Metody návrhu

Algoritmus se navrhuje několika mo?nymi zp?soby:

• Shora dol? – postup ?e?ení rozkládáme na jednodu??í operace, a? dospějeme k elementárním krok?m.
• Zdola nahoru – z elementárních krok? vytvá?íme prost?edky, které nakonec umo?ní zvládnout po?adovany problém.
• Kombinace obou – obvykly postup shora dol? doplníme "?áste?nym krokem" zdola nahoru tím, ?e se nap?íklad pou?ijí knihovny funkcí, vy??í programovací jazyk nebo systém pro vytvá?ení program? (CASE).

Paradigmata návrhu algoritm?

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?í:

Rozděl a panuj

Související informace naleznete také v ?lánku Rozděl a panuj (algoritmus).

Klasicky p?ípad aplikace postupu odshora dol?. 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í vhodnym zp?sobem slou?í.

Zpracovává se mno?ina V slo?ená z n údaj?. Tato mno?ina se rozdělí na k disjunktních podmno?in, které se zpracují ka?dá zvlá??. Získané díl?í vysledky se pak spojí a odvodí se z nich ?e?ení pro celou mno?inu V.

Klasickym p?ípadem je binární vyhledávání nebo ?adící algoritmus rychlé ?azení.

Hladovy algoritmus

Související informace naleznete také v ?lánku Hladovy algoritmus.

Velice p?ímo?ary p?ístup k ?e?ení ur?ité t?ídy optimaliza?ních úloh.

Zpracovává se mno?ina V slo?ená z n údaj?. úkolem je najít podmno?inu W mno?iny V, která vyhovuje ur?itym podmínkám a p?itom optimalizuje p?edepsanou ú?elovou funkci. Jakákoliv mno?ina W, vyhovující danym podmínkám, se nazyvá p?ípustné ?e?ení. P?ípustné ?e?ení, pro které nabyvá ú?elová funkce optimální hodnoty, se nazyvá optimální ?e?ení.

Hladovy algoritmus se skládá z krok?, které budou procházet jednotlivé prvky z V, a v ka?dém kroku rozhodne, zda se dany prvek hodí do optimálního ?e?ení. Prvky V bude vybírat v po?adí ur?eném jistou vyběrovou procedurou. Vyběrová procedura bude zalo?ená na nějaké optimaliza?ní mí?e – funkci, která m??e byt 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. P?íkladem je t?eba hledání nejkrat?í cesty grafu.

Dynamické programování

Související informace naleznete také v ?lánku Dynamické programování.

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 vysledky si zapamatovat pro opakované pou?ití.

Opírá se o princip optimality: Optimální posloupnost rozhodnutí má tu vlastnost, ?e a? je po?áte?ní stav a rozhodnutí jakékoliv, musí byt v?echna následující rozhodnutí optimální vzhledem k vysledk?m rozhodnutí prvního.

Typickym p?íkladem vyu?ití dynamického programování jsou grafové úlohy a jejich p?íslu?né grafové algoritmy.

Pou?ití hrubé síly

U některych úloh nezbyvá ne? postupně probírat v?echna mo?ná ?e?ení – tak zvaná metoda hrubé síly – vygenerují se v?echny mo?né posloupnosti a pak se vybere ta nejlep?í. V některych p?ípadech lze pou?ít metody, které vynechávají pop?ípadě odkládají procházení mo?ností, které z?ejmě nejsou optimální.

Hledání s návratem (backtracking)

Související informace naleznete také v ?lánku Backtracking.

Hledání s návratem zalo?ené na prohledávání stavového prostoru problému. Té? se nazyvá metoda pokus? a oprav, metoda zpětného sledování, metoda prohledávání do hloubky.

Metodu je mo?né pou?ít v p?ípadě, ?e ?e?ením je vektor (x₁,...,x_n), jeho? jednotlivé slo?ky vybíráme z mno?iny S_i, x_i∈S_i. Zpravidla je t?eba najít n-tici, která optimalizuje nějakou ú?elovou funkci P(x₁,...,x_n). 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 byt optimální nebo splňovat dané podmínky. Jestli?e pro nějaké x_i ?ádany vektor (x₁,...,x_i) nem??e byt optimální, není t?eba u? ?ádny takovy 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 x_i-1.

P?íkladem je t?eba problém osmi dam nebo ch?ze koně celou ?achovnicí.

Algoritmická slo?itost

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 rozumny ?as lze v praxi pova?ovat takovy ?as, ktery nám umo?ní smysluplně vyu?ít vysledek.

Nap?. existuje jednoduchy algoritmus, ktery doká?e ur?it, zda v dané ?achové pozici m??e hrá? na tahu vynutit vítězství a zároveň doká?e ur?it nejlep?í mo?ny 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 takovy algoritmus spot?eboval ohromné mno?ství paměti, co? je dal?í prakticky z?etel, ktery 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.

Pro vy?íslení vypo?etní slo?itosti algoritm? v závislosti na velikosti vstupních dat se pou?ívá asymptoticky zápis závislosti vypo?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 vypo?tu se zvy?í o jednu jednotku ?asu, pokud bude vstupních dat ?ty?ikrát více, doba vypo?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).

Druhy algoritm?

Algoritmy m??eme klasifikovat r?znymi zp?soby. Mezi d?le?ité druhy algoritm? pat?í:

• Rekurzivní algoritmy, které vyu?ívají (volají) samy sebe.
• Pravděpodobnostní algoritmus (někdy té? probabilistické) provádí některá rozhodnutí náhodně ?i pseudonáhodně.
• 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.
• Geneticky algoritmus pracuje na základě napodobování biologickych evolu?ních proces?, postupnym ?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ápány jako mo?ná ?e?ení daného problému.
• Heuristicky 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).

P?itom jeden algoritmus m??e pat?it zároveň do více skupin; nap?íklad m??e byt zároveň rekurzivní a geneticky.

Některé známé algoritmy

• Eratosthenovo síto
• Euklid?v algoritmus
• Algoritmus de Casteljau
• Dijkstr?v algoritmus
• Bellman?v–Ford?v algoritmus

Etymologie

Slovo algoritmus pochází ze jména vyznamného perského matematika ?ijícího v první polovině 9. století (cca 780–840), kterym byl Abū ?Abd Allāh Muhammad ibn Mūsā al-Chwārizmī (??? ??? ???? ???? ?? ???? ??????????) (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ánu ji?ně od Aralského jezera). Tento u?enec ve svém díle prakticky vytvo?il systém arabskych ?íslic a základy algebry (konkrétně metody ?e?ení lineárních a kvadratickych 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í arabskych ?íslic“; abacisté po?ítali pomocí abaku, algoristé pomocí algorism?.

Postupem ?asu se kv?li neznalosti p?vodu slova jeho podoba měnila, záměnou arabského ko?ene s ko?enem ?eckého slova αριθμ?? (arithmos) se z algorismu stal algorithmus. (Později bylo v některych jazycích v?etně ?e?tiny th změněno na t, v katalán?tině se vrátilo s.) Toto slovo se pou?ívalo jako ozna?ení r?znych matematickych postup?, nap?. v 18. století ozna?oval latinsky termín algorithmus infitesimalis ?metodu vypo?t? s vyu?itím nekone?ně malych veli?in, vynalezenou německym matematikem Leibnizem“. Slovo algoritmus v dne?ním vyznamu se pou?ívá a? zhruba od 20. století.

Historie: Vyvoj pojmu ?algoritmus“

Starověké ?ecko

Algoritmy byly pou?ity ve starověkém ?ecku. Nap?íklad Eratosthenovo síto nebo Eukleid?v algoritmus.

P?vod

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í aritmetickych operací s arabskymi ?í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?.

Diskrétní a rozeznatelné symboly

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 jednotlivych symbol? v jílu. Zna?ky jsou obvykle v jedni?kové soustavě, která se pou?ívá p?i kódování informací pro Turingovy stroje v teorii automat?.

Mechanická za?ízení s diskrétními stavy

Hodiny: Podle Boltera je vynález mechanickych hodin jedním z klí?ovych vynález?. Zejména pak jejich setrva?ná ?ást – Lihy?. P?esny automat vedl okam?itě k mechanickému automatu (za?átek 13. století) a nakonec k vypo?etním stroj?m – diferen?ní a analyticky stroj (Charles Babbage a Ada Lovelace) v polovině 19. století. Lovelace je p?ipo?ítáno první vytvo?ení algoritmu, ktery je zpracovatelny po?íta?em. Babbage?v analyticky stroj je pova?ován za první Turing?v kompletní po?íta?. Charles Babbage je někdy nazyván jako historicky první programátor.

Logické stroje 1870 – Jevonsovo logické po?ítadlo a logicky stroj: Technicky problém byl zjednodu?ení logickych 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.

Tkalcovsky stav, děrné ?títky, telegrafie a telefonie – elektromechanické relé: Bell a Newell (1971) ozna?ují, ?e tkalcovsky stav (1801), p?edch?dce děrnych ?títk? (1887) a telefonní spínací technologie vedly k vyvoji 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, ktery vyu?íval mezinárodní telegrafní abecedu.

Telefonní sítě elektromechanickych relé – George Stibitz (1937) pracoval v Bellovych laborato?ích a dokon?il kalkulátor, ktery je schopen pracovat s komplexními ?ísly.

Matematika v pr?běhu 19. století a? do poloviny 20. století

Symboly a pravidla: V rychlém sledu za sebou matematika George Boole, Gottlob Frege a Giuseppe Peano redukovala aritmetiku do sekvence symbol?, se kterymi se manipulovalo pomocí danych pravidel. Peanovo The principles of arithmetic, presented by a new method (1888) byl první pokus o axiomatizování matematiky v symbolicky jazyk.

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 Alfredem North Whiteheadem a Bertrandem Russellem v jejich Principia Mathematica (1910–1913).

Paradoxy: Ve stejné době se objevila ?ada znepokojivych element? v literatu?e, zejména Burali-Fortiho paradox (1897), Russell?v paradox (1902–1903) a Richard?v paradox. Vysledné úvahy vedly k G?delovym větám o neúplnosti.

Efektivní vy?íslitelnost: Ve snaze vy?e?it Entscheidungsproblem p?esně definovanym Hilbertem v roce 1928 museli matematici nejprve definovat, co se rozumí pod pojmem ?efektivní metoda“ nebo ?efektivní vypo?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 kalkulu. Church pak spole?ně s Turingem ukázal, ?e lambda kalkul (a dal?í vypo?etní modely) má vypo?etní sílu Turingova stroje, co? otev?elo cestu k Churchově–Turingově tezi.

Právní ustanovení

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. Jinymi 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 jednoduchy algoritmus zpětné vazby na pomoc p?i vytvrzování syntetické gumy. Patentování softwaru je i p?es to velmi kontroverzní. Některé patentované algoritmy se potykají s negativní kritikou, a to p?edev?ím algoritmy slou?ící ke kompresi dat.

Reference

1. heslo Algorithmus. Ott?v slovník nau?ny I, p. 857
2. Donald Ervin 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.
3. Gaston H. Gonnet, Ricardo Baeza-Yates: Zdrojové texty program? v Handbook of Algorithms and Data Structures.
4. Dictionary of Algorithms and Data Structures. ?Slovník algoritm?, technik, datovych struktur, typickych problém? a p?íslu?nych definic.“
5. United States Patent and Trademark Office (2006), 2106.02 **>Mathematical Algorithms: 2100 Patentability, Manual of Patent Examining Procedure (MPEP). Latest revision August 2006

Externí odkazy

• Obrázky, zvuky ?i videa k tématu algoritmus na Wikimedia Commons
• Téma Algoritmus ve Wikicitátech
• Slovníkové heslo algoritmus ve Wikislovníku
• První algoritmus napsala ?ena. Programovala dávno p?ed prvním po?íta?em

Autoritní data	NKC: ph114026 BNE: XX527980 BNF: cb119358199 (data) GND: 4001183-5 LCCN: sh85003487 LNB: 000052282 NDL: 00560337 NLI: 987007293927505171