V této lekci se podíváme na to, co je to algoritmus, jeho historii, původ a použití v programování.
Перегляд файлу
VÝVOJ POJMU „algoritmus“
STAROVĚKÉ ŘECKO
Algoritmy byly použity ve starověkém Řecku.
Například Eratosthenovo síto nebo Eukleidův algoritmus.
ETYMOLOGIE(1/2)
•
Slovo algoritmus pochází ze jména významného perského matematika žijícího v první polovině 9. století (cca 780–840), kterým 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)“. Dneska se tento kraj nachází v Uzbekistánu jižně od Aralského moře).
•
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).
ETYMOLOGIE(1/2)
•
Jeho jméno bylo do latiny převedeno jako algorismus, a původně znamenalo „provádění aritmetiky pomocí arabských čí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.
•
Toto slovo se používalo jako označení různých matematických postupů, např. v 18. století označoval latinský termín algorithmus infitesimalis„metodu výpočtů s využitím nekonečně malých veličin, vynalezenou Leibnizem“.
•
Slovo algoritmus v dnešním významu se používá až zhruba od 20. století.
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 jednotlivých 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ů.
Jedničková soustava (též unární soustava) je nepoziční číselná soustava, která umožňuje zápis pouze kladných celých čísel. Čísla se zapisují jediným znakem ve významu jedna, zpravidla rovná čára,
nejběžněji svislá, ve strojním zpracování pak „1“. Další počty a čísla se zapisují opakováním tohoto znaku tolikrát, až je počet naplněn, např. 3 je jedničkově „111“ a deset je „1111111111“.
MECHANICKÉ ZAŘÍZENÍ S DISKRÉTNÍMI STAVY
Hodiny:Vynález mechanických hodin považuji tento za jedním z klíčových vynálezů. Zejména pak jejich setrvačná části.
•
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.
MECHANICKÉ ZAŘÍZENÍ S DISKRÉTNÍMI STAVY
Logické stroje 1870– 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.
MECHANICKÉ ZAŘÍZENÍ S DISKRÉTNÍMI STAVY
Tkalcovský stav, 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.
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.
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 kterými se manipulovalo pomocí daných pravidel.
PRÁVNÍ STANOVY
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é vazby na pomoc při vytvrzování syntetické gumy.
Patentování 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 kompresi dat.