Algoritmus -Algorithm

Vývojový diagram algoritmu ( Euklidův algoritmus ) pro výpočet největšího společného dělitele (gcd) dvou čísel aab v místech pojmenovaných A a B. Algoritmus postupuje postupným odečítáním ve dvou smyčkách: POKUD test B ≥ A dává „ano“ nebo "pravda" (přesněji, číslo b v místě B je větší nebo rovno číslu a v místě A) PAK algoritmus specifikuje B ← B − A (což znamená, že číslo ba nahrazuje staré b). Podobně, KDYŽ A > B, TAK A ← A − B. Proces končí, když (obsah) B je 0, čímž se získá gcd v A. (Algoritmus odvozený ze Scott 2009:13; symboly a styl kreslení z Tausworthe 1977) .
Diagram Ady Lovelace z "poznámky G", prvního publikovaného počítačového algoritmu

V matematice a informatice je algoritmus ( / ˈ æ l ɡ ə r ɪ ð əm / ( poslouchejte ) ) konečný sled přísných instrukcí, který se obvykle používá k vyřešení třídy specifických problémů nebo k provedení výpočtu . Algoritmy se používají jako specifikace pro provádění výpočtů a zpracování dat . Pokročilejší algoritmy mohou provádět automatizované dedukce (označované jako automatizované uvažování ) a používat matematické a logické testy k přesměrování provádění kódu různými cestami (označované jako automatizované rozhodování ). Používání lidských vlastností jako deskriptorů strojů v metaforických způsobech již praktikoval Alan Turing s pojmy jako „paměť“, „hledání“ a „stimul“.

Naproti tomu heuristika je přístup k řešení problémů, který nemusí být plně specifikován nebo nemusí zaručovat správné nebo optimální výsledky, zejména v problémových doménách, kde neexistuje dobře definovaný správný nebo optimální výsledek.

Jako efektivní metoda může být algoritmus vyjádřen v konečném množství prostoru a času a v dobře definovaném formálním jazyce pro výpočet funkce . Počínaje počátečním stavem a počátečním vstupem (možná prázdným ), instrukce popisují výpočet , který, když je vykonán , pokračuje přes konečný počet dobře definovaných po sobě jdoucích stavů, nakonec vytvoří „výstup“ a skončí v konečném koncovém stavu. Přechod z jednoho stavu do druhého není nutně deterministický ; některé algoritmy, známé jako randomizované algoritmy , zahrnují náhodný vstup.

Dějiny

Koncept algoritmů existuje již od starověku. Aritmetické algoritmy, jako je algoritmus dělení , používali starověcí babylonští matematici c. 2500 př.nl a egyptští matematici c. 1550 před naším letopočtem. Řečtí matematici později použili algoritmy v roce 240 př. n. l. v Eratosthenovu sítu pro nalezení prvočísel a euklidovský algoritmus pro nalezení největšího společného dělitele dvou čísel. Arabští matematici takový jako al-Kindi v 9. století používal cryptographic algoritmy pro kód-rozbití , založený na analýze frekvence .

Slovo algoritmus je odvozeno od jména perského matematika 9. století Muhammada ibn Musa al-Khwarizmiho . Al-Khwarizmi byl matematik, astronom , geograf a učenec v Domě moudrosti v Bagdádu , jehož jméno znamená „rodák z Khwarazmu “, oblasti, která byla součástí Velkého Íránu a nyní je v Uzbekistánu . Asi v roce 825 napsal al-Khwarizmi arabský jazykový pojednání o hinduisticko-arabském číselném systému , který byl přeložen do latiny během 12. století. Rukopis začíná frází Dixit Algorizmi („Tak řekl Al-Khwarizmi“), kde „Algorizmi“ byla překladatelova latinizace jména Al-Khwarizmi. Al-Khwarizmi byl nejčtenějším matematikem v Evropě pozdního středověku, především prostřednictvím další své knihy, Algebry . V pozdně středověké latině algorismus , anglicky " algorism ", zkomolenina jeho jména, znamenala " desítková číselná soustava". V 15. století, pod vlivem řeckého slova ἀριθμός ( aritmos ), „číslo“ ( srov . „aritmetika“), bylo latinské slovo změněno na algorithmus a odpovídající anglický termín „algorithm“ je poprvé doložen v 17. století; moderní smysl byl zaveden v 19. století.

Indická matematika byla převážně algoritmická. Algoritmy, které reprezentují indickou matematickou tradici, sahají od starověkých Śulbasūtrās po středověké texty Keralské školy .

V angličtině bylo slovo algoritmus poprvé použito asi v roce 1230 a poté Chaucerem v roce 1391. Angličtina převzala francouzský termín, ale až do konce 19. století „algoritmus“ získal význam, který má v moderní angličtině.

Další rané použití slova je z roku 1240 v manuálu s názvem Carmen de Algorismo , který složil Alexandre de Villedieu . Začíná to:

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

což v překladu znamená:

Algorismus je umění, kterým v současnosti používáme ty indické figury, kterých je dvakrát pět.

Báseň je dlouhá několik set řádků a shrnuje umění počítání s novými stylizovanými indickými kostkami ( Tali Indorum ), neboli hinduistickými číslicemi.

Částečná formalizace moderního konceptu algoritmu začala s pokusy vyřešit Entscheidungsproblem (rozhodovací problém) položený Davidem Hilbertem v roce 1928. Pozdější formalizace byly koncipovány jako pokusy definovat „ efektivní kalkulovatelnost “ nebo „efektivní metodu“. Tyto formalizace zahrnovaly rekurzivní funkce GödelHerbrandKleene z let 1930, 1934 a 1935, lambda kalkul Alonza Churche z roku 1936, Formulaci 1 Emila Posta z roku 1936 a Turingovy stroje Alana Turinga z let 1936–37.

Neformální definice

Neformální definice by mohla být „soubor pravidel, která přesně definují posloupnost operací“, která by zahrnovala všechny počítačové programy (včetně programů, které neprovádějí numerické výpočty) a (například) jakýkoli předepsaný byrokratický postup nebo recept z kuchařské knihy. .

Obecně platí, že program je algoritmem pouze tehdy, pokud se nakonec zastaví – i když nekonečné smyčky se někdy mohou ukázat jako žádoucí.

Typickým příkladem algoritmu je Euklidovský algoritmus , který se používá k určení maximálního společného dělitele dvou celých čísel; příklad (existují další) je popsán ve vývojovém diagramu výše a jako příklad v pozdější části.

Boolos, Jeffrey & 1974, 1999 nabízejí neformální význam slova „algoritmus“ v následující citaci:

Žádná lidská bytost nemůže psát dostatečně rychle, dostatečně dlouho nebo dostatečně malým† ( †“menší a menší bez omezení ... pokoušeli byste se psát na molekuly, na atomy, na elektrony“), aby vyjmenoval všechny členy nesčetně nekonečná množina zapsáním jejich jmen, jedno po druhém, v nějaké notaci. Ale lidé mohou udělat něco stejně užitečného v případě určitých nevyčíslitelně nekonečných množin: Mohou dát explicitní instrukce pro určení n -tého členu množiny , pro libovolné konečné n . Takové pokyny je třeba dávat zcela explicitně, ve formě, ve které by je mohl následovat počítačový stroj nebo člověk, který je schopen provádět pouze velmi elementární operace se symboly.

" Spočítatelně nekonečná množina" je taková, jejíž prvky lze dát do korespondence jedna ku jedné s celými čísly. Boolos a Jeffrey tedy říkají, že algoritmus zahrnuje instrukce pro proces, který „vytváří“ výstupní celá čísla z libovolného „vstupního“ celého čísla nebo celých čísel, která teoreticky mohou být libovolně velká. Algoritmus může být například algebraická rovnice, jako je y = m + n (tj. dvě libovolné "vstupní proměnné" ma n , které vytvářejí výstup y ), ale pokusy různých autorů definovat tento pojem naznačují, že slovo implikuje mnohem více než toto, něco v pořadí (pro příklad přidání):

Přesné instrukce (v jazyce, kterému rozumí „počítač“) pro rychlý, efektivní, „dobrý“ proces, který specifikuje „pohyby“ „počítače“ (stroje nebo člověka, vybaveného nezbytnými interně obsaženými informacemi a schopnostmi), aby najít, dekódovat a poté zpracovat libovolná vstupní celá čísla/symboly ma n , symboly + a = ... a "efektivně" vytvořit v "přiměřeném" čase výstupní celé číslo y na určeném místě a ve stanoveném formátu.

Pojem algoritmus se také používá k definování pojmu rozhoditelnosti — pojmu, který je ústředním prvkem pro vysvětlení toho, jak formální systémy vznikají, počínaje malým souborem axiomů a pravidel. V logice nelze měřit čas, který algoritmus vyžaduje k dokončení, protože zjevně nesouvisí s obvyklou fyzickou dimenzí. Z takových nejistot, které charakterizují probíhající práci, pramení nedostupnost definice algoritmu , která by vyhovovala jak konkrétnímu (v jistém smyslu), tak abstraktnímu použití tohoto termínu.

Většina algoritmů je určena k implementaci jako počítačové programy . Algoritmy jsou však implementovány i jinými prostředky, například v biologické neuronové síti (například lidský mozek implementující aritmetiku nebo hmyz hledající potravu), v elektrickém obvodu nebo v mechanickém zařízení.

Formalizace

Algoritmy jsou nezbytné pro způsob, jakým počítače zpracovávají data. Mnoho počítačových programů obsahuje algoritmy, které podrobně popisují konkrétní pokyny, které by měl počítač provést – v určitém pořadí – k provedení určitého úkolu, jako je výpočet výplat zaměstnanců nebo tisk vysvědčení studentů. Algoritmus lze tedy považovat za jakoukoli sekvenci operací, kterou lze simulovat Turingovým úplným systémem. Mezi autory, kteří prosazují tuto tezi, patří Minsky (1967), Savage (1987) a Gurevich (2000):

Minsky: "S Turingem ale budeme také tvrdit, že jakýkoli postup, který by se dal "přirozeně" nazvat účinným, může být ve skutečnosti realizován (jednoduchým) strojem. I když se to může zdát extrémní, argumenty... . v její prospěch je těžké vyvrátit“. Gurevich: „… Turingův neformální argument ve prospěch jeho teze ospravedlňuje silnější tezi: každý algoritmus může být simulován Turingovým strojem … podle Savage [1987] je algoritmus výpočetní proces definovaný Turingovým strojem“.

Turingovy stroje mohou definovat výpočetní procesy, které nekončí. Neformální definice algoritmů obecně vyžadují, aby algoritmus vždy skončil. Tento požadavek činí v obecném případě nemožný úkol rozhodnout, zda je formální procedura algoritmem – kvůli hlavní teorému teorie vyčíslitelnosti známé jako problém zastavení .

Typicky, když je algoritmus spojen s informacemi o zpracování, data mohou být načtena ze vstupního zdroje, zapsána do výstupního zařízení a uložena pro další zpracování. Uložená data jsou považována za součást vnitřního stavu entity provádějící algoritmus. V praxi je stav uložen v jedné nebo více datových strukturách .

Pro některé z těchto výpočetních procesů musí být algoritmus přesně definován: a specifikován tak, jak se aplikuje za všech možných okolností, které by mohly nastat. To znamená, že jakékoli podmíněné kroky musí být systematicky řešeny případ od případu; kritéria pro každý případ musí být jasná (a vypočítatelná).

Protože algoritmus je přesný seznam přesných kroků, pořadí výpočtu je vždy rozhodující pro fungování algoritmu. Obvykle se předpokládá, že instrukce jsou uvedeny explicitně a jsou popsány jako začínající „shora“ a jdoucí „dolů dolů“ – myšlenka, která je popsána formálněji pomocí toku kontroly .

Doposud diskuse o formalizaci algoritmu vycházela z premis imperativního programování . Toto je nejběžnější pojetí — takové, které se pokouší popsat úkol v diskrétních, „mechanických“ prostředcích. Unikátní v této koncepci formalizovaných algoritmů je operace přiřazení , která nastavuje hodnotu proměnné. Vychází z intuice „ paměti “ jako zápisníku. Příklad takového zadání naleznete níže.

Pro některé alternativní koncepce toho, co tvoří algoritmus, viz funkční programování a logické programování .

Algoritmy vyjadřování

Algoritmy mohou být vyjádřeny v mnoha druzích zápisu, včetně přirozených jazyků , pseudokódu , vývojových diagramů , drakonových diagramů , programovacích jazyků nebo řídicích tabulek (zpracovaných interprety ). Algoritmy v přirozeném jazyce bývají upovídané a nejednoznačné a zřídka se používají pro složité nebo technické algoritmy. Pseudokód, vývojové diagramy, drakon-grafy a řídicí tabulky jsou strukturované způsoby vyjádření algoritmů, které se vyhýbají mnoha nejednoznačnostem obvyklým v příkazech založených na přirozeném jazyce. Programovací jazyky jsou primárně určeny pro vyjádření algoritmů ve formě, kterou lze provést počítačem, ale často se také používají jako způsob, jak definovat nebo dokumentovat algoritmy.

Existuje široká škála možných reprezentací a je možné vyjádřit daný program Turingova stroje jako posloupnost tabulek strojů (více viz konečný stroj , tabulka přechodů stavů a ​​řídicí tabulka ), jako vývojové diagramy a drakonovy diagramy (viz stavový diagram pro více), nebo jako forma základního strojového kódu nebo montážního kódu nazývaného „sady čtyřnásobků“ (více viz Turingův stroj ).

Reprezentace algoritmů lze rozdělit do tří přijatých úrovní popisu Turingova stroje, a to následovně:

1 Popis na vysoké úrovni
"...popsat algoritmus, ignorovat detaily implementace. Na této úrovni nemusíme zmiňovat, jak stroj spravuje svou pásku nebo hlavu."
2 Popis implementace
"...próza používaná k definování způsobu, jakým Turingův stroj používá svou hlavu a způsob, jakým ukládá data na pásku. Na této úrovni neuvádíme podrobnosti o stavech nebo přechodové funkci."
3 Formální popis
Nejpodrobnější, „nejnižší úroveň“, poskytuje „tabulku stavu“ Turingova stroje.

Příklad jednoduchého algoritmu "Add m+n" popsaného ve všech třech úrovních viz Příklady .

Design

Návrh algoritmu odkazuje na metodu nebo matematický proces pro řešení problémů a inženýrské algoritmy. Návrh algoritmů je součástí mnoha teorií řešení, jako je rozděl a panuj nebo dynamické programování v rámci operačního výzkumu . Techniky pro navrhování a implementaci návrhů algoritmů se také nazývají vzory návrhu algoritmů, přičemž příklady zahrnují vzor metody šablony a vzor dekorátoru.

Jedním z nejdůležitějších aspektů návrhu algoritmu je účinnost zdrojů (doba běhu, využití paměti); velký zápis O se používá např. k popisu růstu algoritmu za běhu, jak se zvětšuje velikost jeho vstupu.

Typické kroky ve vývoji algoritmů:

  1. Definice problému
  2. Vývoj modelu
  3. Specifikace algoritmu
  4. Navrhování algoritmu
  5. Kontrola správnosti algoritmu
  6. Analýza algoritmu
  7. Implementace algoritmu
  8. Testování programu
  9. Příprava dokumentace

Počítačové algoritmy

Logický algoritmus NAND implementovaný elektronicky v čipu 7400
Příklady vývojových diagramů kanonických Böhm-Jacopiniho struktur : SEKVENCE (obdélníky sestupně po stránce), WHILE-DO a IF-THEN-ELSE. Tyto tři struktury jsou tvořeny primitivním podmíněným GOTO ( IF test THEN GOTO step xxx, zobrazeno jako kosočtverec), nepodmíněným GOTO (obdélník), různými operátory přiřazení (obdélník) a HALT (obdélník). Vnoření těchto struktur do přiřazovacích bloků vede ke komplexním diagramům (srov. Tausworthe 1977:100, 114).

"Elegantní" (kompaktní) programy, "dobré" (rychlé) programy : Pojem "jednoduchost a elegance" se neformálně objevuje v Knuthovi a přesně v Chaitinu :

Knuth: "...chceme dobré algoritmy v nějakém volně definovaném estetickém smyslu. Jedním kritériem... je délka času potřebného k provedení algoritmu.... Dalšími kritérii jsou adaptabilita algoritmu na počítače, jeho jednoduchost a elegance atd."
Chaitin: „...program je ‚elegantní‘, tím chci říct, že je to nejmenší možný program pro produkci výstupu, který dělá“

Chaitin předkládá svou definici slovy: „Ukážu, že nemůžete dokázat, že program je ‚elegantní “ – takový důkaz by vyřešil problém zastavení (ibid).

Algoritmus versus funkce vypočítatelné algoritmem : Pro danou funkci může existovat více algoritmů. To platí i bez rozšíření dostupné instrukční sady, kterou má programátor k dispozici. Rogers poznamenává, že "to je... důležité rozlišovat mezi pojmem algoritmus , tj. procedurou a pojmem funkce vypočitatelné algoritmem , tj. mapování získané procedurou. Stejná funkce může mít několik různých algoritmů".

Bohužel může existovat kompromis mezi dobrotou (rychlostí) a elegancí (kompaktností) – elegantní program může provést více kroků k dokončení výpočtu než méně elegantní. Níže je uveden příklad, který používá Euklidův algoritmus.

Počítače (a počítače), modely počítání : Počítač (nebo lidský "počítač") je omezený typ stroje, "jednotlivé deterministické mechanické zařízení", které slepě následuje jeho instrukce. Melzakovy a Lambkovy primitivní modely redukovaly tento pojem na čtyři prvky: (i) diskrétní, odlišitelná umístění , (ii) diskrétní, nerozlišitelné čítače (iii) agent a (iv) seznam instrukcí, které jsou účinné vzhledem ke schopnosti činidlo.

Minsky popisuje sympatičtější variaci Lambkova modelu „počítadla“ ve svém „Very Simple Bases for Computable “. Minského stroj postupuje postupně svými pěti (nebo šesti, podle toho, jak se počítá) instrukcí, pokud buď podmíněné IF-THEN GOTO nebo nepodmíněné GOTO nezmění tok programu mimo sekvenci. Kromě HALT obsahuje Minskyho stroj tři operace přiřazení (náhrada, substituce): NULA (např. obsah lokace nahrazen 0: L ← 0), NÁSTUPNÍ (např. L ← L+1) a DECREMENT (např. L ← L − 1 ). Málokdy musí programátor napsat „kód“ s takto omezenou instrukční sadou. Ale Minsky ukazuje (stejně jako Melzak a Lambek), že jeho stroj je Turing kompletní pouze se čtyřmi obecnými typy instrukcí: podmíněné GOTO, nepodmíněné GOTO, přiřazení/náhrada/substituce a HALT. Pro Turingovu úplnost je však také vyžadováno několik různých instrukcí přiřazení (např. DECREMENT, INCREMENT a NULA/CLEAR/PRÁZDNÝ pro Minsky stroj); jejich přesná specifikace je poněkud na projektantovi. Bezpodmínečné GOTO je pohodlné; lze jej zkonstruovat inicializací vyhrazeného místa na nulu, např. instrukce " Z ← 0 "; poté je instrukce IF Z=0 THEN GOTO xxx bezpodmínečná.

Simulace algoritmu: počítačový (počítačový) jazyk : Knuth radí čtenáři, že „nejlepší způsob, jak se naučit algoritmus, je vyzkoušet si ho... okamžitě vzít tužku a papír a propracovat si příklad“. Ale co simulace nebo provedení skutečné věci? Programátor musí přeložit algoritmus do jazyka, který simulátor/počítač/počítač dokáže efektivně spustit. Stone uvádí příklad: při výpočtu kořenů kvadratické rovnice musí počítač vědět, jak vzít druhou odmocninu. Pokud tomu tak není, musí algoritmus, aby byl účinný, poskytnout sadu pravidel pro extrakci druhé odmocniny.

To znamená, že programátor musí znát "jazyk", který je účinný vzhledem k cílovému výpočetnímu agentovi (počítač/počítač).

Ale jaký model by měl být použit pro simulaci? Van Emde Boas poznamenává, že "i když založíme teorii složitosti na abstraktních namísto konkrétních strojů, zůstává libovolnost výběru modelu. Právě v tomto bodě vstupuje pojem simulace ". Při měření rychlosti záleží na instrukční sadě. Například podprogram v Euklidově algoritmu pro výpočet zbytku by se prováděl mnohem rychleji, kdyby měl programátor k dispozici instrukci „ modulu “ spíše než pouhé odčítání (nebo ještě hůř: jen Minskyho „dekrementace“).

Strukturované programování, kanonické struktury : Podle Church-Turingovy teze lze jakýkoli algoritmus vypočítat pomocí modelu známého jako Turingův úplný a podle Minského demonstrací vyžaduje Turingova úplnost pouze čtyři typy instrukcí – podmíněné GOTO, nepodmíněné GOTO, přiřazení, HALT. Kemeny a Kurtz pozorují, že zatímco „nedisciplinované“ použití nepodmíněných GOTO a podmíněných IF-THEN GOTO může vést ke „ špagetovému kódu “, programátor může psát strukturované programy pouze pomocí těchto instrukcí; na druhou stranu "je také možné, a ne příliš těžké, psát špatně strukturované programy ve strukturovaném jazyce". Tausworthe rozšiřuje tři Böhm-Jacopiniho kanonické struktury : SEQUENCE, IF-THEN-ELSE a WHILE-DO o dvě další: DO-WHILE a CASE. Další výhodou strukturovaného programu je to, že se hodí k důkazům správnosti pomocí matematické indukce .

Symboly kanonického vývojového diagramu : Grafický pomocník zvaný vývojový diagram nabízí způsob, jak popsat a zdokumentovat algoritmus (a počítačový program, který mu odpovídá). Podobně jako tok programu na stroji Minsky, vývojový diagram vždy začíná v horní části stránky a pokračuje dolů. Jeho primární symboly jsou pouze čtyři: směrovaná šipka ukazující průběh programu, obdélník (SEQUENCE, GOTO), kosočtverec (IF-THEN-ELSE) a tečka (OR-tie). Z těchto primitivních tvarů jsou vyrobeny kanonické struktury Böhm-Jacopini. Podstruktury se mohou "zahnízdit" v obdélnících, ale pouze pokud dojde k jedinému výstupu z nadstavby. Symboly a jejich použití k sestavení kanonických struktur jsou znázorněny v diagramu.

Příklady

Příklad algoritmu

Jedním z nejjednodušších algoritmů je najít největší číslo v seznamu čísel v náhodném pořadí. Nalezení řešení vyžaduje podívat se na každé číslo v seznamu. Z toho plyne jednoduchý algoritmus, který lze uvést v popisu na vysoké úrovni v anglické próze, jako:

Popis na vysoké úrovni:

  1. Pokud v množině nejsou žádná čísla, pak není žádné nejvyšší číslo.
  2. Předpokládejme, že první číslo v sadě je největší číslo v sadě.
  3. Pro každé zbývající číslo v sadě: pokud je toto číslo větší než aktuální největší číslo, považujte toto číslo za největší číslo v sadě.
  4. Pokud v sadě nezbývají žádná čísla, která by bylo možné opakovat, považujte aktuální největší číslo za největší číslo sady.

(Kvazi-)formální popis: Napsáno v próze, ale mnohem blíže k jazyku na vysoké úrovni počítačového programu, následuje formálnější kódování algoritmu v pseudokódu nebo pidgin kódu :

Algorithm LargestNumber
Input: A list of numbers L.
Output: The largest number in the list L.
if L.size = 0 return null
largestL[0]
for each item in L, do
    if item > largest, then
        largestitem
return largest
  • "←" označuje přiřazení . Například „ největšípoložka “ znamená, že hodnota největší položky se změní na hodnotu položky .
  • " return " ukončí algoritmus a vydá následující hodnotu.

Euklidův algoritmus

V matematice , Euclidean algoritmus nebo Euclidův algoritmus , je účinná metoda pro počítání největšího společného dělitele (GCD) dvou celých čísel (čísel), největší číslo, které dělí je oba beze zbytku . Je pojmenován po starověkém řeckém matematikovi Euklidovi , který jej poprvé popsal ve svých Elementech ( cca  300 př.nl ). Je to jeden z nejstarších běžně používaných algoritmů. Může být použit k redukci zlomků na jejich nejjednodušší formu a je součástí mnoha dalších číselně teoretických a kryptografických výpočtů.

Příklad-diagram Euklidova algoritmu z TL Heath (1908) s přidanými podrobnostmi. Euclid nepřesahuje třetí měření a neuvádí žádné číselné příklady. Nicomachus uvádí příklad 49 a 21: „Od většího odečítám méně; zbývá 28; pak od toho znovu odečítám stejných 21 (protože je to možné); zbývá 7; toto odečítám od 21, 14 je vlevo; od čehož znovu odečítám 7 (protože to je možné); 7 zbývá, ale 7 nelze odečíst od 7." Heath poznamenává, že „Poslední fráze je zvláštní, ale její význam je dostatečně zřejmý, stejně jako význam fráze o konci ‚na jednom a tom samém čísle‘.“ (Heath 1908:300).

Euclid položí problém takto: “Dva čísla nejsou prvočísla k sobě, najít jejich největší společnou míru”. Definuje „číslo [být] množstvím složeným z jednotek“: počítací číslo, kladné celé číslo bez nuly. "Měření" znamená umístit kratší měřicí délku s postupně ( q krát) podél delší délky l , dokud zbývající část r není menší než kratší délka s . V moderních slovech, zbytek r = l ? q × s , q být kvocient, nebo zbytek r je “modul”, celé číslo-část zlomku zbyla po rozdělení.

Aby Euklidova metoda uspěla, musí počáteční délky splňovat dva požadavky: (i) délky nesmí být nulové a (ii) odečítání musí být „správné“; tj. test musí zaručit, že se menší ze dvou čísel odečte od většího (nebo se dvě mohou rovnat, takže jejich odečtení bude nula).

Euklidův původní důkaz přidává třetí požadavek: dvě délky nesmí být navzájem prvočíslo. Euclid stanovil toto tak že on mohl postavit reductio inzerát absurdum důkaz, že dvě čísla je společná míra je ve skutečnosti největší . Zatímco Nicomachův algoritmus je stejný jako Euklidův, když jsou čísla navzájem prvočísla, dává pro jejich společnou míru číslo „1“. Tedy, abychom byli přesní, následující je skutečně Nicomachův algoritmus.

Grafické vyjádření Euklidova algoritmu k nalezení největšího společného dělitele pro 1599 a 650.
 1599 = 650×2 + 299
 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
 39 = 13×3 + 0

Počítačový jazyk pro Euklidův algoritmus

K provedení Euklidova algoritmu je zapotřebí pouze několik typů instrukcí – některé logické testy (podmíněné GOTO), nepodmíněné GOTO, přiřazení (náhrada) a odečítání.

  • Místo je symbolizováno velkými písmeny, např. S, A atd.
  • Proměnlivé množství (číslo) v místě se píše malými písmeny a (obvykle) je spojeno s názvem místa. Například umístění L na začátku může obsahovat číslo l = 3009.

Nevkusný program pro Euklidův algoritmus

"Neelegantní" je překladem Knuthovy verze algoritmu s odčítáním založeným na zbytku-smyčce nahrazující jeho použití dělení (nebo instrukce "modulu"). Odvozeno od Knutha 1973: 2–4. V závislosti na těchto dvou číslech může „Neelegantní“ vypočítat gcd v méně krocích než „Elegantní“.

Následující algoritmus je koncipován jako Knuthova čtyřstupňová verze Euklidova a Nicomachova algoritmu, ale namísto použití dělení k nalezení zbytku používá postupné odečítání kratší délky s od zbývající délky r , dokud r není menší než s . Popis na vysoké úrovni, zobrazený tučně, je převzat z Knuth 1973: 2–4:

VSTUP :

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
R ← L

E0: [Zajistěte rs .]

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
IF R > S THEN
the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
GOTO step 7
ELSE
swap the contents of R and S.
4 L ← R (this first step is redundant, but is useful for later discussion).
5 R ← S
6 S ← L

E1: [Najít zbytek] : Dokud nebude zbývající délka r v R menší než kratší délka s v S, opakovaně odečtěte měřicí číslo s v S od zbývající délky r v R.

7 IF S > R THEN
done measuring so
GOTO 10
ELSE
measure again,
8 R ← R − S
9 [Remainder-loop]:
GOTO 7.

E2: [Je zbytek nulový?] : BUĎ (i) poslední takt byl přesný, zbytek v R je nulový a program se může zastavit, NEBO (ii) algoritmus musí pokračovat: poslední takt zanechal zbytek v R menší než naměřené číslo v S.

10 IF R = 0 THEN
done so
GOTO step 15
ELSE
CONTINUE TO step 11,

E3: [Výměna s a r ] : Oříšek Euklidova algoritmu. Použijte zbytek r k měření toho, co bylo dříve menším číslem s ; L slouží jako dočasné umístění.

11 L ← R
12 R ← S
13 S ← L
14 [Repeat the measuring process]:
GOTO 7

VÝSTUP :

15 [Done. S contains the greatest common divisor]:
PRINT S

HOTOVO :

16 HALT, END, STOP.

Elegantní program pro Euklidův algoritmus

Následující verze Euklidova algoritmu vyžaduje pouze šest základních instrukcí, aby udělaly to, co třináct vyžaduje „Neelegantní“; horší je, že "Neelegantní" vyžaduje více typů pokynů. Vývojový diagram "Elegant" lze nalézt v horní části tohoto článku. V (nestrukturovaném) jazyce Basic jsou kroky očíslovány a instrukce je instrukce přiřazení symbolizovaná ←. LET [] = []

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A
  90 END

Jak funguje „Elegant“ : Místo vnější „Euklidovy smyčky“ se „Elegant“ posouvá tam a zpět mezi dvěma „smyčkami“, smyčkou A > B, která počítá A ← A − B, a smyčkou B ≤ A který počítá B ← B − A. Funguje to proto, že když je minuend M menší nebo roven subtrahendu S (Difference = Minuend − Subtrahend), z minuendu se může stát s (nová měřicí délka) a subtrahend může stát se novým r (délka, která má být měřena); jinými slovy "smysl" odčítání se obrátí.

Následující verze může být použita s programovacími jazyky z rodiny C :

// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B) {
     A = abs(A);
     B = abs(B);
     while (B != 0) {
          while (A > B) {
               A = A-B;
          }
          B = B-A;
     }
     return A;
}

Testování Euklidových algoritmů

Dělá algoritmus to, co po něm chce jeho autor? Několik testovacích případů obvykle dává určitou důvěru v základní funkce. Testy ale nestačí. Pro testovací případy jeden zdroj používá 3009 a 884. Knuth navrhl 40902, 24140. Dalším zajímavým případem jsou dvě relativně prvočísla 14157 a 5950.

Ale "výjimečné případy" musí být identifikovány a testovány. Bude „Neelegantní“ fungovat správně, když R > S, S > R, R = S? Totéž pro "Elegantní": B > A, A > B, A = B? (Ano pro všechny). Co se stane, když jedno číslo je nula, obě čísla jsou nula? ("Neelegantní" počítá navždy ve všech případech; "Elegant" počítá navždy, když A = 0.) Co se stane, když zadáte záporná čísla? Zlomková čísla? Pokud mají vstupní čísla, tj. definiční obor funkce vypočítané algoritmem/programem, zahrnovat pouze kladná celá čísla včetně nuly, pak chyby na nule naznačují, že algoritmus (a program, který jej vytváří ) je spíše částečnou funkcí než celkovou funkci . Pozoruhodným selháním kvůli výjimkám je selhání rakety Ariane 5 Flight 501 (4. června 1996).

Důkaz programové správnosti použitím matematické indukce : Knuth demonstruje aplikaci matematické indukce na „rozšířenou“ verzi Euklidova algoritmu a navrhuje „obecnou metodu použitelnou k prokázání platnosti jakéhokoli algoritmu“. Tausworthe navrhuje, aby měřítkem složitosti programu byla délka jeho důkazu správnosti.

Měření a zlepšování euklidovských algoritmů

Elegance (kompaktnost) versus dobrota (rychlost) : S pouhými šesti základními instrukcemi je „Elegant“ jasným vítězem ve srovnání s „Neelegantní“ se třinácti pokyny. "Neelegantní" je však rychlejší (do HALTu dorazí v méně krocích). Algoritmová analýza ukazuje, proč tomu tak je: „Elegant“ provede dva podmíněné testy v každé smyčce odčítání, zatímco „Neelegantní“ pouze jeden. Vzhledem k tomu, že algoritmus (obvykle) vyžaduje mnoho průchodů ve smyčce, v průměru se mnoho času vyplýtvá provedením "B = 0?" test, který je potřeba až po dopočítání zbytku.

Lze algoritmy zlepšit? : Jakmile programátor posoudí program „vhodný“ a „účinný“ – to znamená, že vypočítá funkci zamýšlenou jeho autorem – pak vyvstává otázka, lze jej zlepšit?

Kompaktnost „Neelegantní“ lze zlepšit eliminací pěti kroků. Chaitin však dokázal, že komprimaci algoritmu nelze automatizovat zobecněným algoritmem; spíše to lze provést pouze heuristicky ; tj. vyčerpávajícím hledáním (příklady naleznete na Busy bobr ), pokusem a omylem, chytrostí, vhledem, aplikací induktivního uvažování atd. Všimněte si, že kroky 4, 5 a 6 se opakují v krocích 11, 12 a 13. Srovnání s "Elegantní" poskytuje nápovědu, že tyto kroky spolu s kroky 2 a 3 lze eliminovat. Tím se snižuje počet základních instrukcí ze třinácti na osm, díky čemuž je „elegantnější“ než „Elegantní“, v devíti krocích.

Rychlost "Elegant" lze zlepšit posunutím "B=0?" test mimo dvě odečítací smyčky. Tato změna vyžaduje přidání tří instrukcí (B = 0?, A = 0?, GOTO). Nyní "Elegant" počítá čísla příkladů rychleji; zda je tomu tak vždy pro dané A, B a R, S, by vyžadovalo podrobnou analýzu.

Algoritmická analýza

Často je důležité vědět, kolik určitého zdroje (jako je čas nebo úložiště) je teoreticky vyžadováno pro daný algoritmus. Byly vyvinuty metody pro analýzu algoritmů pro získání takových kvantitativních odpovědí (odhadů); například algoritmus, který sčítá prvky seznamu n čísel, by měl časový požadavek O(n) s použitím velkého O zápisu . Algoritmus si vždy potřebuje pamatovat pouze dvě hodnoty: součet všech dosavadních prvků a jeho aktuální pozici ve vstupním seznamu. Proto se říká, že má prostorový požadavek O(1) , pokud není započítán prostor potřebný k uložení vstupních čísel, nebo O(n) , pokud se počítá.

Různé algoritmy mohou dokončit stejný úkol s jinou sadou instrukcí za méně nebo více času, prostoru nebo „ úsilí “ než jiné. Například binární vyhledávací algoritmus (s cenou O(log n) ) překonává sekvenční vyhledávání (cena O(n) ), když se používá pro vyhledávání v tabulkách v seřazených seznamech nebo polích.

Formální versus empirické

Analýza a studium algoritmů je disciplína informatiky a často se praktikuje abstraktně bez použití specifického programovacího jazyka nebo implementace. V tomto smyslu se analýza algoritmů podobá jiným matematickým disciplínám v tom, že se zaměřuje na základní vlastnosti algoritmu a ne na specifika nějaké konkrétní implementace. Obvykle se pro analýzu používá pseudokód , protože je to nejjednodušší a nejobecnější reprezentace. V konečném důsledku je však většina algoritmů obvykle implementována na konkrétních hardwarových/softwarových platformách a jejich algoritmická efektivita je nakonec testována pomocí reálného kódu. Pro řešení „jednorázového“ problému nemusí mít účinnost konkrétního algoritmu významné důsledky (pokud n není extrémně velké), ale pro algoritmy navržené pro rychlé interaktivní, komerční nebo vědecké použití s ​​dlouhou životností to může být kritické. Změna měřítka od malého n po velké n často odhaluje neefektivní algoritmy, které jsou jinak neškodné.

Empirické testování je užitečné, protože může odhalit neočekávané interakce, které ovlivňují výkon. Benchmarky lze použít k porovnání před/po potenciálních vylepšeních algoritmu po optimalizaci programu. Empirické testy však nemohou nahradit formální analýzu a jejich provedení spravedlivým způsobem není triviální.

Efektivita provedení

Abychom ilustrovali potenciální zlepšení možná i v dobře zavedených algoritmech, nedávná významná inovace týkající se algoritmů FFT (používaných ve velké míře v oblasti zpracování obrazu) může u aplikací, jako je lékařské zobrazování, zkrátit dobu zpracování až 1000krát. Obecně platí, že zlepšení rychlosti závisí na speciálních vlastnostech problému, které jsou v praktických aplikacích velmi běžné. Zrychlení tohoto rozsahu umožňuje výpočetním zařízením, která široce využívají zpracování obrazu (jako jsou digitální fotoaparáty a lékařské vybavení), spotřebovávat méně energie.

Klasifikace

Existuje několik způsobů klasifikace algoritmů, z nichž každý má své vlastní výhody.

Realizací

Jedním ze způsobů klasifikace algoritmů je implementace.

int gcd(int A, int B) {
    if (B == 0)
        return A;
    else if (A > B)
        return gcd(A-B,B);
    else
        return gcd(A,B-A);
}
Rekurzivní C implementace Euklidova algoritmu z výše uvedeného vývojového diagramu
Rekurze
Rekurzivní algoritmus je takový, který se opakovaně vyvolává (odkazuje na sebe), dokud určitá podmínka (také známá jako podmínka ukončení) neodpovídá, což je metoda společná pro funkční programování . Iterativní algoritmy používají k řešení daných problémů opakující se konstrukce, jako jsou smyčky , a někdy další datové struktury, jako jsou zásobníky . Některé problémy jsou přirozeně vhodné pro jednu nebo druhou implementaci. Například věže Hanoje jsou dobře pochopeny pomocí rekurzivní implementace. Každá rekurzivní verze má ekvivalentní (ale možná více či méně komplexní) iterativní verzi a naopak.
Logický
Algoritmus může být viděn jako řízená logická dedukce . Tento pojem lze vyjádřit jako: Algoritmus = logika + řízení . Logická složka vyjadřuje axiomy, které lze při výpočtu použít, a řídicí složka určuje způsob, jakým je na axiomy aplikována dedukce. To je základ pro paradigma logického programování . V čistě logických programovacích jazycích je řídicí komponenta pevná a algoritmy jsou specifikovány dodáním pouze logické komponenty. Přitažlivost tohoto přístupu je elegantní sémantika : změna v axiomech vytváří dobře definovanou změnu v algoritmu.
Sériové, paralelní nebo distribuované
Algoritmy jsou obvykle diskutovány s předpokladem, že počítače provádějí vždy jednu instrukci algoritmu. Tyto počítače se někdy nazývají sériové počítače. Algoritmus navržený pro takové prostředí se nazývá sériový algoritmus, na rozdíl od paralelních algoritmů nebo distribuovaných algoritmů . Paralelní algoritmy využívají počítačové architektury, kde může na problému pracovat několik procesorů současně, zatímco distribuované algoritmy využívají více strojů připojených k počítačové síti . Paralelní nebo distribuované algoritmy rozdělují problém na více symetrické nebo asymetrické podproblémy a shromažďují výsledky zpět dohromady. Spotřeba prostředků v takových algoritmech není pouze cykly procesoru na každém procesoru, ale také režie komunikace mezi procesory. Některé třídicí algoritmy lze efektivně paralelizovat, ale jejich komunikační režie je drahá. Iterační algoritmy jsou obecně paralelizovatelné. Některé problémy nemají paralelní algoritmy a nazývají se neodmyslitelně sériové problémy.
Deterministické nebo nedeterministické
Deterministické algoritmy řeší problém přesným rozhodnutím v každém kroku algoritmu, zatímco nedeterministické algoritmy řeší problémy pomocí hádání, ačkoli typické odhady jsou přesnější pomocí heuristiky .
Přesné nebo přibližné
Zatímco mnoho algoritmů dosahuje přesného řešení, aproximační algoritmy hledají aproximaci, která je blíže skutečnému řešení. Aproximace může být dosažena buď pomocí deterministické nebo náhodné strategie. Takové algoritmy mají praktickou hodnotu pro mnoho těžkých problémů. Jedním z příkladů přibližného algoritmu je Knapsack problem , kde existuje množina daných položek. Jeho cílem je sbalit batoh tak, aby získal maximální celkovou hodnotu. Každá položka má nějakou váhu a nějakou hodnotu. Celková hmotnost, kterou lze přepravovat, není větší než nějaké pevné číslo X. Řešení tedy musí vzít v úvahu hmotnosti položek i jejich hodnotu.
Kvantový algoritmus
Běží na realistickém modelu kvantového počítání . Termín se obvykle používá pro ty algoritmy, které se zdají neodmyslitelně kvantové, nebo používají nějaký základní rys kvantového počítání , jako je kvantová superpozice nebo kvantové zapletení .

Podle paradigmatu designu

Dalším způsobem klasifikace algoritmů je jejich návrhová metodologie nebo paradigma . Existuje určitý počet paradigmat, každé odlišné od druhého. Kromě toho každá z těchto kategorií zahrnuje mnoho různých typů algoritmů. Některá běžná paradigmata jsou:

Brute-force nebo vyčerpávající hledání
Toto je naivní metoda zkoušení všech možných řešení, abyste zjistili, které je nejlepší.
Rozděl a panuj
Algoritmus rozděl a panuj opakovaně redukuje instanci problému na jednu nebo více menších instancí stejného problému (obvykle rekurzivně ), dokud nejsou instance dostatečně malé, aby je bylo možné snadno vyřešit. Jedním z takových příkladů rozdělení a panování je slučovací třídění . Třídění lze provést na každém segmentu dat po rozdělení dat do segmentů a třídění celých dat lze získat ve fázi dobytí sloučením segmentů. Jednodušší varianta rozděl a panuj se nazývá algoritmus poklesu a panování , který řeší identický dílčí problém a řešení tohoto dílčího problému využívá k řešení většího problému. Rozděl a panuj rozděluje problém na několik dílčích problémů, takže fáze dobývání je složitější než algoritmy snižování a dobývání. Příkladem algoritmu poklesu a dobytí je binární vyhledávací algoritmus .
Vyhledávání a výčet
Mnoho problémů (například hraní šachů ) lze modelovat jako problémy v grafech . Algoritmus zkoumání grafů specifikuje pravidla pro pohyb po grafu a je užitečný pro takové problémy. Tato kategorie také zahrnuje vyhledávací algoritmy , větvený a vázaný výčet a zpětné sledování .
Randomizovaný algoritmus
Takové algoritmy provádějí některé volby náhodně (nebo pseudonáhodně). Mohou být velmi užitečné při hledání přibližných řešení problémů, kde může být hledání přesných řešení nepraktické (viz heuristická metoda níže). U některých z těchto problémů je známo, že nejrychlejší aproximace musí zahrnovat určitou náhodnost . Zda randomizované algoritmy s polynomiální časovou složitostí mohou být nejrychlejšími algoritmy pro některé problémy, je otevřená otázka známá jako problém P versus NP . Existují dvě velké třídy takových algoritmů:
  1. Algoritmy Monte Carlo vrátí správnou odpověď s vysokou pravděpodobností. Např . RP je podtřída těch, které běží v polynomiálním čase .
  2. Algoritmy Las Vegas vždy vrátí správnou odpověď, ale jejich doba běhu je vázána pouze pravděpodobnostně, např . ZPP .
Snížení složitosti
Tato technika zahrnuje řešení obtížného problému jeho transformací na známější problém, pro který máme (doufejme) asymptoticky optimální algoritmy. Cílem je najít redukční algoritmus, jehož složitost nebude dominovat výsledným redukovaným algoritmům. Například jeden výběrový algoritmus pro nalezení mediánu v neseřazeném seznamu zahrnuje nejprve seřazení seznamu (drahá část) a poté vytažení prostředního prvku v seřazeném seznamu (levná část). Tato technika je také známá jako transformovat a dobýt .
Sledování zpět
V tomto přístupu se postupně vytváří více řešení a opouští se, když se zjistí, že nemohou vést k platnému úplnému řešení.

Problémy s optimalizací

Pro optimalizační problémy existuje specifičtější klasifikace algoritmů; Algoritmus pro takové problémy může spadat do jedné nebo více obecných kategorií popsaných výše a také do jedné z následujících:

Lineární programování
Při hledání optimálních řešení lineární funkce vázané na omezení lineární rovnosti a nerovnosti lze omezení problému použít přímo při vytváření optimálních řešení. Existují algoritmy, které dokážou vyřešit jakýkoli problém v této kategorii, jako je například populární simplexní algoritmus . Problémy, které lze vyřešit lineárním programováním, zahrnují problém maximálního průtoku pro orientované grafy. Pokud problém navíc vyžaduje, aby jedna nebo více neznámých bylo celé číslo , pak je klasifikován v celočíselném programování . Algoritmus lineárního programování může takový problém vyřešit, pokud lze prokázat, že všechna omezení pro celočíselné hodnoty jsou povrchní, tj. řešení tato omezení stejně splňují. V obecném případě se používá specializovaný algoritmus nebo algoritmus, který najde přibližná řešení v závislosti na obtížnosti problému.
Dynamické programování
Když problém vykazuje optimální podstruktury – což znamená, že optimální řešení problému lze konstruovat z optimálních řešení podproblémů – a překrývající se podproblémy , což znamená, že stejné podproblémy se používají k řešení mnoha různých instancí problémů, rychlejší přístup nazývaný dynamické programování se vyhýbá přepočítávání řešení, která již byly spočítány. Například Floyd-Warshall algoritmus , nejkratší cestu k cíli z vrcholu ve váženém grafu lze najít pomocí nejkratší cesty k cíli ze všech sousedních vrcholů. Dynamické programování a zapamatování jdou dohromady. Hlavní rozdíl mezi dynamickým programováním a rozděl a panuj je v tom, že podproblémy jsou v rozděl a panuj víceméně nezávislé, zatímco v dynamickém programování se podproblémy překrývají. Rozdíl mezi dynamickým programováním a přímou rekurzí je v ukládání do mezipaměti nebo zapamatování rekurzivních volání. Když jsou dílčí problémy nezávislé a nedochází k jejich opakování, memorování nepomáhá; dynamické programování tedy není řešením pro všechny složité problémy. Použitím memoizace nebo udržováním tabulky již vyřešených dílčích problémů snižuje dynamické programování exponenciální povahu mnoha problémů na polynomiální složitost.
Zištná metoda
Chamtivý algoritmus je podobný dynamickému programovacímu algoritmu v tom, že funguje na základě zkoumání podstruktur, v tomto případě nikoli problému, ale daného řešení. Takové algoritmy začínají nějakým řešením, které může být dáno nebo bylo nějakým způsobem zkonstruováno, a vylepšují ho malými úpravami. U některých problémů dokážou najít optimální řešení, u jiných se zastaví u lokálního optima , tedy u řešení, která nelze algoritmem zlepšit, ale nejsou optimální. Nejoblíbenější použití chamtivých algoritmů je pro nalezení minimální kostry, kde je pomocí této metody možné najít optimální řešení. Huffman Tree , Kruskal , Prim , Sollin jsou chamtivé algoritmy, které dokážou vyřešit tento optimalizační problém.
Heuristická metoda
V optimalizačních problémech lze použít heuristické algoritmy k nalezení řešení blízkého optimálnímu řešení v případech, kdy je nalezení optimálního řešení nepraktické. Tyto algoritmy fungují tak, že se postupem času přibližují k optimálnímu řešení. V zásadě platí, že pokud běží nekonečně dlouho, najdou optimální řešení. Jejich zásluhou je, že dokážou v relativně krátké době najít řešení velmi blízké optimálnímu řešení. Takové algoritmy zahrnují lokální vyhledávání , tabu vyhledávání , simulované žíhání a genetické algoritmy . Některé z nich, jako je simulované žíhání, jsou nedeterministické algoritmy, zatímco jiné, jako je vyhledávání tabu, jsou deterministické. Když je známa hranice chyby neoptimálního řešení, je algoritmus dále kategorizován jako aproximační algoritmus .

Podle studijního oboru

Každá vědní oblast má své vlastní problémy a potřebuje účinné algoritmy. Související problémy v jednom oboru se často studují společně. Některé příklady tříd jsou vyhledávací algoritmy , třídicí algoritmy , slučovací algoritmy , numerické algoritmy , grafové algoritmy , řetězcové algoritmy , výpočetní geometrické algoritmy , kombinatorické algoritmy , lékařské algoritmy komprese dat a šifrovací techniky parování dat ,

Pole mají tendenci se navzájem překrývat a pokroky algoritmů v jednom poli mohou zlepšit pole jiných, někdy zcela nesouvisejících polí. Například dynamické programování bylo vynalezeno pro optimalizaci spotřeby zdrojů v průmyslu, ale nyní se používá při řešení široké škály problémů v mnoha oblastech.

Podle složitosti

Algoritmy lze klasifikovat podle doby, kterou potřebují k dokončení, v porovnání s velikostí vstupu:

  • Konstantní čas: pokud je čas potřebný pro algoritmus stejný, bez ohledu na velikost vstupu. Např. přístup k prvku pole .
  • Logaritmický čas: pokud je čas logaritmickou funkcí velikosti vstupu. Např . binární vyhledávací algoritmus .
  • Lineární čas: pokud je čas úměrný velikosti vstupu. Např. procházení seznamu.
  • Polynomiální čas: je-li čas mocninou vstupní velikosti. Např. algoritmus pro třídění bublin má kvadratickou časovou složitost.
  • Exponenciální čas: pokud je čas exponenciální funkcí vstupní velikosti. Např . vyhledávání hrubou silou .

Některé problémy mohou mít více algoritmů různé složitosti, zatímco jiné problémy nemusí mít žádné algoritmy nebo žádné známé účinné algoritmy. Existují také mapování z některých problémů na jiné problémy. Díky tomu se ukázalo jako vhodnější klasifikovat problémy samotné místo algoritmů do tříd ekvivalence na základě složitosti pro ně nejlepších možných algoritmů.

Spojité algoritmy

Přídavné jméno „kontinuální“ při použití slova „algoritmus“ může znamenat:

  • Algoritmus pracující na datech, která představují spojité veličiny, i když jsou tato data reprezentována diskrétními aproximacemi – takové algoritmy jsou studovány v numerické analýze ; nebo
  • Algoritmus ve formě diferenciální rovnice , který nepřetržitě pracuje na datech, běží na analogovém počítači .

Legální problémy

Algoritmy samy o sobě obvykle nejsou patentovatelné. Ve Spojených státech tvrzení sestávající pouze z jednoduchých manipulací s abstraktními pojmy, čísly nebo signály nepředstavuje „procesy“ (USPTO 2006), a proto algoritmy nejsou patentovatelné (jako v Gottschalk v. Benson ). Praktické aplikace algoritmů jsou však někdy patentovatelné. Například ve věci Diamond v. Diehr bylo použití jednoduchého zpětnovazebního algoritmu na pomoc při vytvrzování syntetického kaučuku považováno za patentovatelné. Patentování softwaru je vysoce kontroverzní a existují vysoce kritizované patenty zahrnující algoritmy, zejména algoritmy komprese dat, jako je patent Unisys LZW .

Navíc některé kryptografické algoritmy mají exportní omezení (viz export kryptografie ).

Historie: Vývoj pojmu "algoritmus"

Starověký Blízký východ

Nejčasnější důkazy o algoritmech se nacházejí v babylonské matematice starověké Mezopotámie (moderní Irák). Sumerská hliněná tabulka nalezená v Shuruppak poblíž Bagdádu a datovaná do doby kolem roku 2500 př. n. l. popsala nejčasnější algoritmus dělení . Během dynastie Hammurabi, přibližně 1800-1600 př.nl, babylonské hliněné tabulky popisovaly algoritmy pro výpočet vzorců . Algoritmy byly také použity v babylonské astronomii . Babylonské hliněné tabulky popisují a používají algoritmické postupy pro výpočet času a místa významných astronomických událostí.

Algoritmy pro aritmetiku lze nalézt také ve starověké egyptské matematice , pocházející z Rhindova matematického papyru kolem roku 1550 př.nl. Algoritmy byly později použity ve starověké helénistické matematice . Dva příklady jsou Eratosthenesovo síto , které bylo popsáno v Úvodu do aritmetiky Nicomachem , a euklidovský algoritmus , který byl poprvé popsán v Euklidových prvcích ( c.  300 př.nl ).

Samostatné a rozlišitelné symboly

Sčítací značky: Aby mohli sledovat svá stáda, pytle obilí a peníze, starověcí lidé používali počítání: shromažďování kamenů nebo značek poškrábaných na tyčích nebo vytváření samostatných symbolů v hlíně. Prostřednictvím babylonského a egyptského používání značek a symbolů se nakonec vyvinuly římské číslice a počítadlo (Dilson, s. 16–41). Sčítací značky se objevují prominentně v aritmetice jednočlenné číselné soustavy používané ve výpočtech Turingova stroje a Post-Turingova stroje .

Manipulace se symboly jako "zástupci" pro čísla: algebra

Muhammad ibn Mūsā al-Khwārizmī , perský matematik , napsal Al-jabr v 9. století. Termíny „ algorismus “ a „algoritmus“ jsou odvozeny ze jména al-Khwārizmī, zatímco termín „ algebra “ je odvozen z knihy Al-jabr . V Evropě se slovo „algoritmus“ původně používalo k označení souborů pravidel a technik používaných Al-Khwarizmi k řešení algebraických rovnic, než se později zobecnilo na jakýkoli soubor pravidel nebo technik. To nakonec vyvrcholilo Leibnizovou představou kalkulu ratiocinator ( cca  1680 ):

Dobré století a půl před svou dobou navrhl Leibniz algebru logiky, algebru, která by specifikovala pravidla pro manipulaci s logickými pojmy způsobem, jakým obyčejná algebra specifikuje pravidla pro manipulaci s čísly.

Kryptografické algoritmy

První kryptografický algoritmus pro dešifrování zašifrovaného kódu vyvinul Al-Kindi , arabský matematik 9. století , v knize A Manuscript On Deciphering Cryptographic Messages . Podal první popis kryptoanalýzy frekvenční analýzou , nejčasnějším algoritmem pro rozbití kódu .

Mechanické zařízení s diskrétními stavy

Hodiny : Bolter připisuje vynález hodin poháněných váhou jako „klíčový vynález [Evropy ve středověku]“, zejména krajní únik , který nám poskytuje tikání a tahy mechanických hodin. „Přesný automatický stroj“ okamžitě vedl k „mechanickým automatům “ počínaje 13. stoletím a nakonec k „počítačovým strojům“ – rozdílovému motoru a analytickým strojům Charlese Babbage a hraběnky Ady Lovelace z poloviny 19. století. Lovelace je připisován prvnímu vytvoření algoritmu určeného pro zpracování na počítači – Babbageův analytický stroj, první zařízení považované za skutečný Turingův kompletní počítač namísto pouhého kalkulátoru – a v důsledku toho je někdy nazýván „prvním programátorem historie“. ačkoli úplná implementace Babbageova druhého zařízení by byla realizována až desítky let po jejím životě.

Logické stroje 1870 – „logické počítadlo“ a „logický stroj“ Stanleyho Jevonse : Technickým problémem bylo redukovat booleovské rovnice , když byly prezentovány ve formě podobné tomu, co je nyní známé jako Karnaughovy mapy . Jevons (1880) popisuje nejprve jednoduché „počítadlo“ „pryžů dřeva opatřených kolíky, vymyšlené tak, aby bylo možné mechanicky vybrat jakoukoli část nebo třídu [logických] kombinací... V poslední době jsem však zredukoval systém do zcela mechanické formy, a ztělesňují tak celý nepřímý proces vyvozování v tom, co lze nazvat logickým strojem . Jeho stroj byl vybaven "určitými pohyblivými dřevěnými tyčemi" a "u paty je 21 kláves podobných těm klavír [atd.] ...“. S tímto strojem mohl analyzovat " sylogismus nebo jakýkoli jiný jednoduchý logický argument".

Tento stroj předvedl v roce 1870 před členy Královské společnosti. Jiný logik John Venn však ve své Symbolické logice z roku 1881 k tomuto úsilí obrátil zažloutlé oko: „Sám nemám žádný velký odhad zájmu nebo důležitosti toho, čemu se někdy říká logické stroje... nezdá se mi, že by jakýkoli vynález, který je v současnosti známý nebo pravděpodobně objeven, si skutečně zaslouží jméno logické stroje“; více viz Charakterizace algoritmů . Aby však nebyl opomenut, také předložil „plán poněkud analogický, jak se domnívám, k počítadlu prof. Jevona ... [A] [a]zisk, odpovídající logickému stroji prof. abych to nazval pouze strojem s logickými diagramy... ale předpokládám, že by mohl dělat úplně všechno, co lze racionálně očekávat od jakéhokoli logického stroje."

Žakárový tkalcovský stav, děrné štítky Hollerith, telegrafie a telefonie – elektromechanické relé : Bell a Newell (1971) naznačují, že kořeny byly žakárový tkalcovský stav (1801), předchůdce karet Hollerith (děrné štítky, 1887) a „technologie přepínání telefonů“. stromu vedoucího k vývoji prvních počítačů. V polovině 19. století se telegraf , předchůdce telefonu, používal po celém světě, jeho diskrétní a rozlišitelné kódování písmen jako „tečky a čárky“ byl běžným zvukem. Koncem 19. století se používala páska ( cca  70. léta 19. století ), stejně jako použití karet Hollerith při sčítání lidu v USA v roce 1890. Pak přišel dálnopis ( cca  1910 ) s použitím Baudotova kódu na pásce pomocí děrovaného papíru.

Za prací George Stibitze (1937), vynálezce digitálního sčítacího zařízení, stály telefonní přepínací sítě elektromechanických relé (vynalezeno 1835). Když pracoval v Bellových laboratořích, pozoroval "obtížné" používání mechanických kalkulátorů s ozubenými koly. "Jednoho večera v roce 1937 se vrátil domů s úmyslem otestovat svůj nápad... Když skončilo kutilství, Stibitz zkonstruoval binární sčítací zařízení." .

Matematik Martin Davis si všímá zvláštní důležitosti elektromechanického relé (s jeho dvěma „binárními stavy“ otevřeným a uzavřeným ):

Teprve s vývojem elektromechanických kalkulátorů využívajících elektrická relé, počínaje 30. lety 20. století, byly postaveny stroje s rozsahem, jaký si Babbage představoval."

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

Symboly a pravidla : V rychlém sledu matematika George Boolea (1847, 1854), Gottloba Frege (1879) a Giuseppe Peana (1888–1889) redukovala aritmetiku na posloupnost symbolů manipulovaných pravidly. Peanova Principy aritmetiky, prezentované novou metodou (1888), byly „prvním pokusem o axiomatizaci matematiky v symbolickém jazyce “.

Ale Heijenoort dává Fregovi (1879) tuto chválu: Fregeho je „možná nejdůležitější samostatné dílo, jaké kdy bylo napsáno v logice... ve kterém vidíme jazyk vzorců“, to je lingua characterica , jazyk psaný speciálními symboly. , „pro čisté myšlení“, tedy bez rétorických příkras ... vytvořených ze specifických symbolů, se kterými se manipuluje podle určitých pravidel.“ Fregeovo dílo dále zjednodušili a umocnili Alfred North Whitehead a Bertrand Russell ve svém Principia Mathematica (1910–1913).

Paradoxy : Současně se v literatuře objevila řada znepokojivých paradoxů, zejména Burali-Fortiho paradox (1897), Russellův paradox (1902–03) a Richard Paradox . Výsledné úvahy vedly k článku Kurta Gödela (1931) — konkrétně cituje paradox lháře —, který zcela redukuje pravidla rekurze na čísla.

Efektivní kalkulovatelnost : Ve snaze vyřešit problém Entscheidungs , který přesně definoval Hilbert v roce 1928, se matematici nejprve pustili do definování toho, co se rozumí „efektivní metodou“ nebo „efektivní kalkulací“ nebo „efektivní kalkulovatelností“ (tj. kalkulací, která by uspěla). ). V rychlém sledu se objevily následující: Alonzo Church , Stephen Kleene a JB Rosserův λ -kalkul , jemně vybroušená definice „obecné rekurze“ z díla Gödela jednajícího na základě návrhů Jacquese Herbranda (srov. Gödelovy přednášky z Princetonu z roku 1934) a následná zjednodušení od Kleene. Churchův důkaz, že problém Entscheidungs ​​byl neřešitelný, definice efektivní vypočítavosti Emila Posta jako pracovníka bezmyšlenkovitě se řídí seznamem instrukcí, aby se pohyboval doleva nebo doprava po řadě místností a zatímco tam buď označoval nebo vymazával papír, nebo sledoval papír a dělal rozhodnutí ano-ne o dalším pokynu. Důkaz Alana Turinga, že problém Entscheidungs ​​byl neřešitelný použitím jeho „[automatického] stroje“ – ve skutečnosti téměř identický s Postovou „formulací“, definicí „účinné metody“ J. Barkley Rossera v termínech „a stroj". Kleeneův návrh předchůdce „ Církevní teze “, kterou nazval „Teze I“, a o několik let později Kleeneovo přejmenování své teze na „Církevní tezi“ a navrhování „Turingovy teze“.

Emil Post (1936) a Alan Turing (1936-37, 1939)

Emil Post (1936) popsal jednání „počítače“ (člověka) takto:

„...zahrnuje dva koncepty: prostor symbolů, v němž má být vykonávána práce vedoucí od problému k odpovědi, a pevný neměnný soubor směrů .

Prostor jeho symbolu by byl

"obousměrná nekonečná posloupnost prostorů nebo krabic... Řešitelem problému nebo pracovníkem je pohybovat se a pracovat v tomto prostoru symbolů, být schopen být uvnitř a pracovat v jednom boxu po druhém... je připustit pouze dvě možné podmínky, tj. být prázdný nebo neoznačený a mít v něm jedinou značku, řekněme svislý tah.
"Je třeba vyčlenit jeden rámeček a nazvat jej výchozím bodem. ...konkrétní problém má být dán v symbolické formě tím, že konečný počet rámečků [tj. INPUT] je označen čárkou. Stejně tak odpověď [tj. , VÝSTUP] má být dán v symbolické podobě takovouto konfigurací označených políček...
"Soubor směrů použitelných na obecný problém vytváří deterministický proces, když je aplikován na každý konkrétní problém. Tento proces končí pouze tehdy, když dojde ke směru typu (C ) [tj. STOP]". Více viz Post-Turing machine
Socha Alana Turinga v Bletchley Parku

Práce Alana Turinga předcházela práci Stibitze (1937); není známo, zda Stibitz věděl o Turingově díle. Turingův životopisec se domníval, že Turingovo použití modelu podobného psacímu stroji pochází ze zájmu mládí: „Alan snil o tom, že vynalezne psací stroje, jako chlapec; paní Turingová měla psací stroj a on mohl začít tím, že se sám sebe zeptal, co znamená volání "mechanický " psací stroj . Vzhledem k tomu, že v té době převládala Morseova abeceda, telegrafie, páskové stroje a dálnopisy, je docela možné, že to vše ovlivnilo Turinga během jeho mládí.

Turing – jeho model výpočtu se nyní nazývá Turingův stroj – začíná, stejně jako Post, analýzou lidského počítače, kterou omezuje na jednoduchý soubor základních pohybů a „stavů mysli“. Pokračuje však o krok dále a vytváří stroj jako model výpočtu čísel.

"Výpočet se běžně provádí tak, že se na papír zapisují určité symboly. Můžeme předpokládat, že tento papír je rozdělen na čtverce jako dětská aritmetická kniha... Předpokládám tedy, že výpočet probíhá na jednorozměrném papíru, tj. na pásce rozdělené do čtverců. Také budu předpokládat, že počet symbolů, které lze vytisknout, je konečný...
"Chování počítače v každém okamžiku je určeno symboly, které sleduje, a jeho "stavem mysli" v daném okamžiku. Můžeme předpokládat, že existuje vazba B na počet symbolů nebo čtverců, které počítač dokáže pozorovat v jeden okamžik. Pokud chce pozorovat více, musí použít postupná pozorování. Budeme také předpokládat, že počet stavů mysli, které je třeba vzít v úvahu, je konečný...
"Představme si, že operace prováděné počítačem je třeba rozdělit na "jednoduché operace", které jsou tak elementární, že není snadné si je představit dále rozdělit."

Turingova redukce dává následující:

"Jednoduché operace proto musí zahrnovat:
"(a) Změny symbolu na jednom z pozorovaných čtverců
"(b) Změny jednoho z pozorovaných čtverců na jiný čtverec v rámci L čtverců jednoho z dříve pozorovaných čtverců.

"Je možné, že některé z těchto změn nutně vyvolají změnu stavu mysli. Nejobecnější jednotlivou operaci je proto třeba považovat za jednu z následujících:

"(A) Možná změna (a) symbolu spolu s možnou změnou stavu mysli.
"(B) Možná změna (b) pozorovaných čtverců spolu s možnou změnou stavu mysli"
"Nyní můžeme postavit stroj, který bude vykonávat práci tohoto počítače."

O několik let později Turing rozšířil svou analýzu (tezi, definici) o toto silné vyjádření:

"O funkci se říká, že je "efektivně vypočítatelná", pokud lze její hodnoty nalézt nějakým čistě mechanickým procesem. I když je poměrně snadné tuto myšlenku intuitivně pochopit, je nicméně žádoucí mít nějakou konkrétnější, matematicky vyjádřitelnou definici. ... [diskutuje o historii definice v podstatě tak, jak je uvedeno výše s ohledem na Gödela, Herbranda, Kleenea, Churche, Turinga a Posta] ... Toto tvrzení můžeme brát doslovně, rozumíme-li čistě mechanickým procesem, který by mohly být prováděny strojem. Je možné podat matematický popis, v určité normální formě, struktury těchto strojů. Vývoj těchto myšlenek vede k autorově definici vyčíslitelné funkce a k identifikaci vyčíslitelnost † s efektivní vyčíslitelností...
"† Výraz "vypočitatelná funkce" budeme používat ve významu funkce vypočítatelné strojem a "efektivně vypočítatelné" budeme odkazovat na intuitivní myšlenku bez zvláštního ztotožnění se s některou z těchto definic".

JB Rosser (1939) a SC Kleene (1943)

J. Barkley Rosser definoval „efektivní [matematickou] metodu“ následujícím způsobem (přidáno kurzívou):

Efektivní metoda“ se zde používá v poněkud zvláštním smyslu metody, jejíž každý krok je přesně určen a která jistě poskytne odpověď v konečném počtu kroků. S tímto zvláštním významem byly dány tři různé přesné definice k dnešnímu dni. [jeho poznámka pod čarou č. 5; viz diskuse bezprostředně níže]. Nejjednodušší z nich (kvůli Postovi a Turingovi) v podstatě říká, že existuje účinná metoda řešení určitých souborů problémů, pokud lze postavit stroj, který pak vyřešit jakýkoli problém množiny bez lidského zásahu kromě vložení otázky a (později) přečtení odpovědi . Všechny tři definice jsou ekvivalentní, takže nezáleží na tom, která z nich se použije. Navíc skutečnost, že všechny tři jsou ekvivalentní, je velmi silný argument pro správnost kohokoli." (Rosser 1939: 225–226)

Rosserova poznámka pod čarou č. 5 odkazuje na práci (1) Churche a Kleenea a jejich definici λ-definibility, zejména na její použití Churchem ve své knize An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand a Gödel a jejich použití rekurze, zejména Gödelovo použití v jeho slavném článku On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931); a (3) Post (1936) a Turing (1936–37) ve svých mechanizmech-modelech výpočtu.

Stephen C. Kleene definoval jako svou nyní slavnou „tezi I“ známou jako Church-Turingova teze . Ale udělal to v následujícím kontextu (v originále tučně):

"12. Algoritmické teorie ... Při sestavování úplné algoritmické teorie popíšeme proceduru, proveditelnou pro každou sadu hodnot nezávislých proměnných, která nutně končí, a to takovým způsobem, že z výsledku můžeme přečtěte si jednoznačnou odpověď „ano“ nebo „ne“ na otázku „je hodnota predikátu pravdivá?“ (Kleene 1943:273)

Historie po roce 1950

Řada snah byla zaměřena na další zpřesnění definice „algoritmu“ a činnost pokračuje kvůli problémům spojeným zejména se základy matematiky (zejména Church-Turingova teze ) a filozofie mysli (zejména argumenty ). o umělé inteligenci ). Další informace naleznete v části Charakterizace algoritmů .

Viz také

Poznámky

Bibliografie

Další čtení

externí odkazy

Algoritmová úložiště