algoritmus - Algorithm


z Wikipedie, otevřené encyklopedie

Vývojový diagram algoritmu ( Eukleidův algoritmus ) pro výpočet největší společný dělitel (GCD) dvě čísla A a B, v místech s názvem A a B. pokračuje algoritmus postupnými odčítání ve dvou smyček: Pokud se test B ≥ Umožňuje poskytuje „Ano“ (nebo true) (přesněji číslo b v místě b je větší než nebo rovna číslo a v místě a), pak je algoritmus specifikuje b ← b - a (což znamená, že číslo b - nahrazuje starý b ). Podobně, pokud A> B, pak A ← A - B. Tento proces končí, jakmile (obsah), B je 0, čímž se získá gcd v A. (algoritmus odvozený od Scott 2009: 13; symboly a výkresového stylu z Tausworthe 1977) ,

V matematice a informatice , An algoritmus ( / æ l ɡ ə r ɪ ð əm /  ( naslouchat )O tomto zvukem ) je jednoznačná specifikace, jak řešit řadu problémů. Algoritmy mohou provádět výpočty , zpracování dat a automatického uvažování úkoly.

Jako účinná metoda , algoritmus může být vyjádřen v konečné množství času a prostoru a dobře definovaného formální jazyk pro výpočet funkce . Počínaje od počátečního stavu, a jako zdroj informací (možná prázdný ), instrukce popisují výpočet , který, když provedený , pokračuje přes konečným počtem dobře definovaných po sobě následujícími stavy, eventuálně produkovat „výstup“ a končící v konečném stavu koncovkou. Přechod z jednoho stavu do druhého, není nutně deterministický ; Některé algoritmy, známé jako randomizované algoritmy , obsahují náhodné vstup.

Pojem algoritmu existuje již celá staletí. Řečtí matematici používají algoritmy, například síto Eratosthenes pro nalezení prvočísel a algoritmus Euklidovskou pro nalezení největšího společného dělitele dvou čísel.

Slovo algoritmus sám pochází z 9. století matematik Al-Chorezmí , Latinized Algoritmi . Částečný formalizace co by se stalo moderní pojetí algoritmu začal s pokusy o vyřešení Entscheidungsproblem (rozhodnutí problém), které představuje David Hilbert v roce 1928. Pozdější formalizace byla koncipována jako pokouší definovat „ efektivní calculability “ nebo „efektivní“. Tyto formalizace zahrnovaly Gödel - Herbrandova - Kleeneho rekurzivní funkce v roce 1930, 1934 a 1935, Alonzo Church 's lambda kalkulu 1936, Emil Post ' s Formulace 1 z roku 1936, a Alan Turing je Turingův stroj z 1936-37 a 1939.

Etymologie

Slovo ‚algoritmus‘ má své kořeny v Latinizing jméno Al-Chorezmí v prvním kroku k algorismus . Al-Khwarizmi ( Peršan : خوارزمی ., C 780-850) byl perský matematik, astronom , geograf a učenec v Domě moudrosti v Bagdádu , jehož jméno znamená ‚Rodák z Khwarezm ‘, což je oblast, která byla součástí větší Írán a je nyní v Uzbekistánu .

Asi 825, al-Khwarizmi napsal arabskojazyčnou pojednání o Hindu-systém arabské číslice , která byla přeložena do latiny v 12. století pod názvem Algoritmi de numero Indorum . Tento titul znamená „Algoritmi o počtech Indiánů“, kde „Algoritmi“ byl překladatele Latinization názvu Al-Khwarizmi. Al-Khwarizmi byl nejčtenějším matematik v Evropě v pozdním středověku, a to především prostřednictvím další ze svých knih, v algebře . V pozdním středověku latiny, algorismus , anglicky ‚ Algorism ‘, korupce jeho jméno, jednoduše znamenalo „desítkovou číselnou soustavu“. V 15. století, pod vlivem řeckého slova ἀριθμός ‚číslem‘ ( srovnej ‚aritmetický‘), latinské slovo byl změněn na Algorithmus a odpovídající anglický termín ‚algoritmus‘ je nejprve doložen v 17. století; Moderní smysl byl představen v 19. století.

V angličtině, to bylo poprvé použito asi 1230 a pak Chaucer v 1391. English přijal francouzský termín, ale to nebylo až do konce 19. století, že „algoritmus“ vzal na tom smyslu, že má v moderní angličtině.

Další časný použití slova je od roku 1240, v příručce s názvem Carmen de Algorismo složil Alexandre de Villedieu . Začíná takto:

HAEC algorismus ars Praesens dicitur, v qua / Talibus Indorum fruimur bis Quinque figuris.

který se překládá jako:

Algorism je umění, kterou v současné době používáme indické obrázky, které číslo dvakrát pět.

Báseň je několik set linek dlouho a shrnuje umění výpočtu s novým stylem indických kostky nebo Talibus Indorum nebo hinduistické číslicemi.

neformální definice

Neformální definice by mohla být „soubor pravidel, která přesně definuje posloupnost operací.“ který by zahrnoval všechny počítačové programy, včetně programů, které nejsou numerických výpočtů. Obecně platí, že program je pouze algoritmus, pokud přestane nakonec.

Prototypu příkladem algoritmu je euklidovská algoritmus pro stanovení maximální společný dělitel dvou celých čísel; Příkladem (tam jsou další) je popsána v diagramu výše, a jako příklad v pozdější části.

Boolos Jeffrey & 1974, 1999 nabídka neformální smysl slova v následující citát:

Žádná lidská bytost nemůže psát dost rychle, nebo dost dlouho, nebo dost malý † († „menší a menší, bez omezení ... byste se snaží psát na molekulách, na atomy, na elektrony“) do seznamu všechny členy enumerably nekonečné nastavit napsáním jejich jména, jeden po druhém, v určitém zápisu. Ale lidé mohou dělat něco stejně užitečné, v případě některých enumerably nekonečných množin: Mohou dát jasný návod pro určení n th členem sady , pro libovolné konečné n . Tyto instrukce se mají podat zcela jasně, ve formě, ve které by mohly být následuje výpočetní zařízení , nebo o člověka, který je schopen provádět jen velmi elementární operace na symboly.

Výraz „enumerably nekonečná množina“ je ten, jehož prvky mohou být do one-to-one korespondenci s celými čísly. Tak Boolos a Jeffrey říkají, že algoritmus znamená instrukce pro proces, který „tvoří“ výstup celá čísla od nežádoucího „vstup“ celé číslo nebo celá čísla, že teoreticky, může být libovolně velký. Tak algoritmus může být algebraická rovnice, jako je y = m + n - dva libovolné „vstupní proměnné“ m a n , které vytvářejí výstupní y . Ale pokusy různých autorů definovat pojem naznačují, že slovo znamená, mnohem více, než to, co na objednávku (pro přidávání příklad):

Přesné instrukce (v jazyce, kterému porozumí „počítač“) pro rychlé a efektivní, „dobrého“ proces, který specifikuje „pohyby“ z „počítač“ (počítač nebo člověk, který je vybaven potřebnou vnitřně obsažené informace a schopnosti), aby zde , dekódovat, a pak proces jakémkoliv vstupu celá čísla / symboly m a n , symboly + a = ... a „v podstatě“ produkovat, v „rozumné“ času, výstup-celé číslo y ve stanoveném místě a ve stanoveném formátu.

Pojem algoritmu se také používá k definování pojmu rozhodnutelnosti . Tento pojem je ústřední pro vysvětlení, jak formální systémy vznikají od malého souboru axiomů a pravidel. V logice , doba, po kterou algoritmus potřebuje k dokončení nelze měřit, neboť není zřejmě souvisí s naším obvyklým fyzické dimenzi. Z těchto nejistot, které jsou charakteristické pro probíhající činnost, stonky nedostupnost definice algoritmu , který vyhovuje jak beton (v určitém smyslu) a abstraktní použití termínu.

Formalizace

Algoritmy jsou nezbytné k datům, jakým počítače procesu. Mnoho počítačové programy obsahují algoritmy, které upřesňují konkrétní pokyny počítač by měl provést následující (v určitém pořadí) provádět určené úkoly, jako je výpočet výplaty nebo potisk žáků zaměstnanců vysvědčení. Tak, algoritmus může být považován jakýkoliv sled operací, které mohou být simulovány pomocí Turing-kompletní systém. Autoři, kteří se domáhají tuto tezi patří Minsky (1967), Savage (1987) a Gurevič (2000):

Minsky: „Ale budeme také udržovat s Turing, že jakýkoli postup, který by mohl...‚Přirozeně‘se nazývá efektivní, může ve skutečnosti být realizován (jednoduché) stroje I když se to může zdát extrémní, argumenty... . v její prospěch je těžké vyvrátit“.

Gurevič: „... neformální argumentace Turing ve prospěch jeho práce odůvodňuje důraznější práce: každý algoritmus může být simulován Turing stroj ... podle Savage [1987], algoritmus je výpočetní postup definovaný Turingův stroj“ ,

Typicky, když je algoritmus spojena s zpracovávání informací, lze načítat data ze vstupního zdroje, které na výstupní zařízení a uloženy k dalšímu zpracování. Uložená data jsou považována za součást vnitřního stavu entity provádějící algoritmus. V praxi, stát je uložen v jednom nebo více datových struktur .

Z nějakého takového výpočetního procesu algoritmus musí být přesně definovány: uvedeno ve způsobu, jakým to platí ve všech možných okolností, které by mohly nastat. To znamená, že případné podmíněné kroky musí být systematicky řešit případ od případu; kritéria pro každý případ musí být jasné (a vypočitatelný).

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. Instrukce jsou obvykle předpokládá, že bude uveden výslovně, a jsou popsány jako výchozí „odshora“ a jít „až na dno“, nápad, který je popsán více formálně toku řízení .

Doposud tato diskuse o formalizace algoritmu převzala prostor imperativním programování . Jedná se o nejběžnější pojetí a pokusí se popsat úlohu v diskrétních, „mechanické“ prostředky. Unikátní na tomto pojetí formalizovaných algoritmů je operace přiřazení , nastavení hodnoty proměnné. To pochází z intuici „ paměti “ jako zápisníku. Tam je níže uvedený příklad takového úkolu.

U některých alternativních koncepcí, co představuje algoritmus, viz funkční programování a logické programování .

vyjadřování algoritmů

Algoritmy mohou být vyjádřeny v mnoha druhů notace, včetně přirozených jazyků , pseudokódu , vývojových diagramů , DRAKON-grafy , programovacích jazyků nebo řídicích tabulek (zpracovaných tlumočníky ). Výrazů přirozeného jazyka algoritmů bývají mnohomluvný a dvojznačný, a jsou zřídka používá pro složité nebo technických algoritmů. Pseudokód, vývojové diagramy, drakon-grafy a kontrolní tabulky jsou strukturované způsobů, jak vyjádřit algoritmy, které zabrání mnoho nejasností běžné ve výkazech přirozeného jazyka. Programovací jazyky jsou primárně určeny pro vyjádření algoritmů ve formě, která mohou být provedeny na počítači, ale jsou často používán jako způsob, jak definovat nebo algoritmy dokumentů.

K dispozici je široká škála reprezentací možné a lze expresi daného Turingův stroj program, jako sled stůl stroje (viz více na konečný automat , státní přechodové tabulky a řídicí tabulce ), jako vývojových diagramů a drakon-grafy (více na stavový diagram ), nebo jako forma rudimentární strojového kódu nebo kódu shromáždění s názvem „sady čtveřicích“ (viz více na Turing stroj ).

Reprezentace algoritmů lze klasifikovat do tří uznávaných úrovní Turingův stroj popis:

Popis 1 na vysoké úrovni
„... próze popsat algoritmus, ignorování implementační detaily. Na této úrovni, nepotřebujeme o tom, jak se stroj řídí svůj pásku nebo hlavou.“
Popis 2 Provedení
„... próza slouží k definování, jak Turing stroj používá hlavu a způsob, jakým se ukládají údaje o jejím páskou. Na této úrovni, nedáme podrobnosti států nebo přechodové funkce.“
3 formální popis
Nejpodrobnější, „nejnižší úroveň“, dává Turingova stroje „státní stůl“.

Pro příklad jednoduchého algoritmu „Přidat m + n“ je popsáno ve třech úrovních, viz algoritmus # příklady .

Design

Algoritmus návrh se týká způsobu nebo matematického postupu pro řešení problémů a technické algoritmy. Návrh algoritmů je součástí mnoha řešení teorií operace výzkumu , jako je dynamické programování a rozděl a panuj . Techniky pro navrhování a realizaci návrhů algoritmů jsou také nazývány návrhové vzory algoritmů, jako je například metoda šablona vzor a dekorátor.

Jedním z nejdůležitějších aspektů návrhu algoritmů vytváří algoritmus, který má efektivní run-time, také známý jako jeho velký O .

Typické kroky ve vývoji algoritmů:

  1. Definice problému
  2. Vývoj modelu
  3. Specifikace algoritmu
  4. Navrhování algoritmu
  5. Kontrole správnosti algoritmu
  6. Analýza algoritmů
  7. Implementace algoritmu
  8. testovací program
  9. příprava dokumentace

Implementace

Logický NAND algoritmus implementován v elektronické podobě 7400 čipu

Nejvíce algoritmy mají být realizovány jako počítačové programy . Nicméně, algoritmy jsou provádět také jinými způsoby, například v biologické neuronové sítě (například, lidský mozek , kterým se provádí aritmetické nebo hmyz hledá jídlo), v elektrickém obvodu , nebo mechanickým zařízením.

počítačové algoritmy

Vývojových diagramů příklady kanonických Böhm-Jacopini struktur : posloupnost (obdélníky sestupné části stránky), a přitom-DO a IF-then-else. Tyto tři struktury jsou vyrobeny z primitivního podmíněného GOTO ( IF testu = true PAK GOTO krok xxx ) (diamant), bezpodmínečné GOTO (obdélník), různé přiřazovací operátory (obdélník) a HALT (obdélník). Hnízdění těchto struktur uvnitř přiřazení bloků vyústit v komplexní diagramů (CF Tausworthe 1977: 100,114).

V počítačových systémech , algoritmus je v podstatě instancí logiky napsán v softwaru vývojáři softwaru, aby byly účinné pro zamýšlené počítač (y) „cílové“ produkovat výstup z daného (snad null) vstup . Optimální algoritmus, i běží ve starém hardwaru, by produkovat výsledky rychleji, než je neoptimální (vyšší časová složitost algoritmu) pro stejný účel, běh na účinnější hardwaru; to je důvod, proč algoritmy, jako je počítačový hardware, jsou považovány za technologie.

„Elegantní“ (kompaktní) programů, „dobré“ (rychle) programy : pojem „jednoduchost a elegance“ objeví neformálně v Knuth a přesně Chaitin :

Knuth:..“WE chtějí dobré ...... Algoritmy v některých volně definovaném smysl pro estetiku Jedním kritériem je délka doby přijata k provedení algoritmu .. Ostatní kritéria jsou adaptabilita algoritmu k počítačům, jeho jednoduchost a eleganci , atd"
Chaitin: „.. Program je‚elegantní‘, kterou mám na mysli, že je to nejmenší možný program na výrobu výstup, který to dělá“

Chaitin předmluvy jeho definice se: „Ukážu vám nemůže dokázat, že program je‚elegantní “ -such by to důkaz vyřešit problém zastavení (tamtéž).

Algoritmus proti funkce počítačově algoritmem : Pro danou funkci, může existovat více algoritmy. To je pravda, a to i bez rozšíření dostupných instrukční sadu k dispozici programátorovi. Rogers uvádí, že „je.,. Důležité rozlišovat mezi pojmem algoritmus , tj řízení a pojmu funkce počítačově algoritmem , tj mapování výnosů z postupu. Stejná funkce může mít několik různých algoritmů“.

Bohužel, může být kompromis mezi dobrem (rychlost) a elegance (kompaktnost) -an elegantní program může podniknout další aktivní kroky k dokončení výpočtu než jeden méně elegantní. Jako příklad, který používá Eukleidův algoritmus se objeví níže.

Počítače (a computors), modely výpočtů : Počítač (nebo lidský „computor“) je omezený typ stroje, o „diskrétní deterministický mechanické zařízení“, která slepě následuje jeho pokyny. Primitivní modely Melzak je a Lambek snížen tento pojem na čtyři prvky: (i) diskrétní, rozlišitelné lokalitách , (ii) diskrétní, k nerozeznání pulty (iii) činidlo, a (iv) seznam instrukcí, které jsou účinné vzhledem ke schopnosti činidlo.

Minsky popisuje více kongeniální variaci Lambek je „počítadlo“ modelu ve svých „Velmi jednoduchý základen pro Vyčíslitelnost “. Minského stroj pokračuje postupně prostřednictvím pěti (nebo šesti, v závislosti na tom, jak se spočítá) návod, pokud jedna ze podmíněného if-then GOTO nebo nepodmíněného GOTO mění tok programu mimo pořadí. Kromě zastavit, Minského stroj obsahuje tři přiřazení (nahrazení, substituce) operace: nula (např Obsahem místa nahrazena 0: L ← 0), NÁSTUPCE (např L ← L + 1), a snížení hodnoty (např L ← L - 1 ). Zřídka musí programátor write „code“ s takovou omezenou instrukční sadou se. Ale Minsky ukazuje (jak dělat Melzak a Lambek), že jeho stroj je Turing kompletní pouze čtyři obecné typy instrukcí: podmíněného GOTO, bezpodmínečného GOTO, přiřazení / výměnu / nahrazování, a zastavit.

Simulace algoritmu: počítač (computor) Jazyk : Knuth radí čtenáře, že „.. Nejlepší způsob, jak se učit algoritmus je to zkusit hned vzít tužku a papír a pracovat pomocí příkladu“. Ale co simulaci nebo provedení skutečné věci? Programátor musí přeložit algoritmus do jazyka, že simulátor / počítač / computor může účinně vykonávat. Kámen je uveden příklad takto: při výpočtu kořenů kvadratické rovnici computor musí vědět, jak se druhá odmocnina. Pokud tomu tak není, pak je algoritmus, aby byla účinná, musí poskytnout soubor pravidel pro extrakci odmocninu.

To znamená, že programátor musí znát „jazyk“, který je efektivní vzhledem k cílové výpočetního prostředku (počítačový / computor).

Ale jaký model by měl být použit pro simulaci? Van Emde Boas podotýká, „i kdybychom založit teorii složitosti na abstraktní namísto konkrétních strojů, volnost při výběru modelu zůstává. To je v tomto bodě, že pojem simulace vstupu“. Když se měří rychlost, tím instrukční sadu otázek. Například podprogram v Eukleidova algoritmu pro výpočet zbývající by vykonat mnohem rychleji, pokud programátor měl „ modulem “ instrukce k dispozici, spíše než jen odčítání (nebo horší, jen Minského „dekrement“).

Strukturované programování, kanonické struktury : Per na Church-Turingova práce jakýkoliv algoritmus může být vypočítán pomocí modelu známo, že Turing kompletní , a za Minsky demonstrací, Turing úplnost vyžaduje pouze čtyři instrukční typy-podmíněné Goto, bezpodmínečnou GOTO, přiřazení, HALT. Kemeny a Kurtz pozorovat, že zatímco „neukázněné“ použití nepodmíněných GOTOS a podmíněný IF-THEN GOTOS může mít za následek „ špagety kódu “, programátor může psát strukturované programy využívající pouze tyto pokyny; Na druhou stranu „je také možné, a ne příliš tvrdá, psát špatně strukturované programy strukturovaným jazykem“. Tausworthe zvyšuje tři Böhm-Jacopini kanonické struktury : SEKVENCE, IF-then-else, a zatímco-DO, další dvě: do-while a případ. Další výhodou strukturovaného programu je, že se hodí do dokladů o správnosti s využitím matematické indukce .

Kanonické vývojových diagramů symboly : Grafické asistent volal vývojový diagram , nabízí způsob, jak popsat a dokumentů algoritmus (a počítačový program jednoho). Stejně jako tok programu stroje Minsky, vývojový diagram začíná vždy v horní části stránky a pokračuje dolů. Jeho primární symboly jsou pouze čtyři: režie šipkou tok programu, obdélník (sekvence, GOTO), diamant (IF-then-else), a bod (OR-tie). Tyto Böhm-Jacopini kanonické struktury jsou vyrobeny z těchto primitivních tvarů. Sub-struktury mohou „hnízdo“ v obdélníků, ale pouze tehdy, pokud jeden výstup dochází z nástavby. Symboly, a jejich použití k vytvoření kanonické struktury jsou uvedeny na obrázku.

Příklady

příkladem algoritmu

Animace na algoritmu quicksortu třídění pole náhodných hodnot. Červené pruhy označují otočný prvek; na začátku animace, prvek nejdále na pravé straně je vybrán jako čepu.

Jeden z nejjednodušších algoritmů má zjistit největší množství v seznamu čísel náhodném pořadí. Hledání řešení vyžaduje při pohledu na každé číslo v seznamu. Z toho vyplývá jednoduchý algoritmus, který může být uvedeno v popisu na vysoké úrovni v anglické próze, as:

Popis na vysoké úrovni:

  1. Pokud nejsou žádná čísla v sadě, pak není nejvyšší počet.
  2. Předpokládejme, že první číslo v sadě je největší počet v sadě.
  3. Pro každou zbývající počet v sadě: pokud je toto číslo větší než aktuální největší počet, zvažte toto číslo být největší číslo v sadě.
  4. Když zbývá v sadě k iteraci přes žádná čísla, považují současný největší počet za největší počet setu.

(Kvasisoudním) formální popis: Je napsaný v próze, ale mnohem blíže k jazyku vysoké úrovni počítačového programu, následující je více formální kódování algoritmu v pseudokódu nebo Pidgin kód :

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
  • „←“ znamená zadání . Například, „ největšípoložkou “ se rozumí, že hodnota největších změn na hodnotě předmětu .
  • Návrat “ ukončí algoritmus a vydává následující hodnoty.

Eukleidův algoritmus

Příklad-schéma Euklidova algoritmu z TL Heath (1908), s dalšími detaily přidán. Euclid nepřekračuje rámec třetí měření a neposkytuje žádné číselné příklady. Nicomachus dává příklad 49 a 21: „I odečíst méně z větší; 28 doleva, pak znovu jsem odečíst z toho stejné 21 (pro je to možné), 7 je vlevo, já odečíst to od 21, 14, je vlevo, ze které jsem se znovu odečíst 7 (pro je to možné), 7 vlevo, ale 7 nelze odečíst od 7.“ Heath poznamenává, že „Poslední věta je zvláštní, ale význam je zřejmé, nestačí, protože i významu fráze o ukončení‚na jedné a téže řady‘.“ (Heath 1908: 300).

Euclid ‚s algoritmus pro výpočet největší společný dělitel (GCD) na dvě čísla se jeví jako Proposition II v knize VII (‚Elementární teorie čísel‘) z jeho prvků . Euclid představuje problém takto: „Vzhledem k tomu, dvě čísla nejsou prime k sobě, aby si jejich největší společný míru“. Ten definuje „Řada [být] velké množství složený z jednotek“: číslo počítání, kladné celé číslo bez nuly. Pro „měření“ je umístit kratší měření délky s postupně ( q krát) podél delší délky l , dokud se zbývající část r je menší než kratší délky s . V moderních slovy, zbytek r = l - q x s , q je kvocient, nebo zbytek R je „modul“ je celé číslo, zlomková část zbude po rozdělení.

Pro Eukleidův způsob, jak uspět, délky výchozí musí splňovat dva požadavky: (i) délky nesmí být nula a (ii) odečítání musí být „správné“; tj test se musí zaručit, že menší z těchto dvou čísel se odečte od větší (střídavě, dva mohou být stejné, takže jejich odčítání výnosy nula).

Eukleidův původní doklad přidává třetí požadavek: dvě délky nesmí být prime navzájem. Euclid stanoveno to, aby se mohl postavit sporem důkaz, že společná opatření dvou čísel je ve skutečnosti největší . Zatímco Nicomachus' algoritmus je stejný jako Euclid letech, kdy čísla jsou prime k sobě navzájem, to se vzdá číslo ‚1‘ pro jejich společném opatření. Tak, abychom byli přesní, doplňuje je opravdu Nicomachus algoritmus.

Grafické vyjádření Eukleidova 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

Programovací jazyk pro Euklidova algoritmu

Jen několik instrukcí typy jsou nutné ke spuštění algoritmu-nějaké logické testy Euclidových (Conditional GOTO), nepodmíněné Goto, přiřazení (nahrazení) a odčítání.

  • Poloha je symbolizován velké písmeno (y), například S, A, atd
  • Měnící se množství (počet) na místě je zapsán malým písmenem (y) a (obvykle) spojený s názvem umístění je. Například, umístění L na začátku může obsahovat číslo l = 3009.

Nevkusný program Euklidova algoritmu

„Nevzhledné“ je překladem Knuthův verze algoritmu s odčítání bázi zbytek smyčky nahradí jeho použití dělení (nebo instrukce „modul“). Odvozen od Knuth 1973: 2-4. V závislosti na těchto dvou čísel „nevzhledné“ mohou počítat gcd v méně krocích, než „elegantní“.

Následující algoritmus je koncipován jako Knuthův čtyřstupňový verzi Eukleidova a Nicomachus', ale spíše než pomocí dělení nalézt zbytek, se používá po sobě následujících odeþítání z kratší délky je od zbývající délky r dokud r je menší než s . Popis na vysoké úrovni, zobrazeny tučným písmem, je upravena od 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: [Ujistěte se, rů .]

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 6
  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] : Do zbývající délka r v R, je menší, než je kratší délka je v S, opakovaně odečíst měřicí číslo je v S od zbývající délce 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 nula?] : (I) poslední opatření byla přesná, zbytek v R je nula, a program může zastavit, nebo (ii) algoritmus musí pokračovat: poslední opatření učinilo zbytek v R méně než měření hodnot v S.

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

E3: [Interchange s a r ] : Matice z Euklidova algoritmu. Pomocí zbytkové r k měření toho, co bylo již dříve menší počet 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

OUTPUT :

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

Dáno :

16 HALT, END, STOP.

Elegantní program Euklidova algoritmu

Následující verze Eukleidova algoritmu vyžaduje pouze šest základních pokynů k tomu, co třináct udělat pomocí „nevzhledné“ jsou požadovány; horší, „nevzhledné“ vyžaduje více typů instrukcí. Vývojový diagram na „elegantní“ lze nalézt v horní části tohoto článku. V (nestrukturované) Základní jazyk, kroky jsou čí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

Následující verze lze použít s objektově orientované jazyky:

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

Jak „elegantní“ funguje : V místě vnější „Euclid smyčku“, „elegantní“ přesouvá tam a zpět mezi dvěma „společné smyčky“, ve skupině A> B smyčka, která počítá ← A - B a B ≤ smyčce že počítá B ← B - A. Toto pracuje, protože, když se konečně menšenec M je menší než nebo se rovná menšitel s (rozdíl = menšenec - menšitel), menšenec může stát s (nová měření délky) a menšitel může stal novým r (délku, které mají být měřeny); jinými slovy „sense“ odčítání obrátí.

Testování algoritmů Euclid

Má algoritmus, co jeho autor chce, aby to udělal? Několik testovacích případů obvykle dostatečná pro potvrzení základní funkce. Jeden zdroj využívá 3009 a 884. Knuth navrhl, 40902, 24140. Další zajímavý případ je dva poměrně hlavní čísla 14157 a 5950.

Avšak ve výjimečných případech, musí být identifikovány a testovány. Bude "nevzhledné" provádět správně, když R> S, S> R, R = S? To samé platí pro "elegantní": B> A, A> B, A = B? (Ano pro všechny). Co se stane, když číslo je nula, obě čísla jsou nuly? ( „Nevzhledné“ vypočítává navždy v každém případě, „elegantní“ vypočítává navždy, když A = 0) Co se stane, když záporné se zadávají čísla? Desetinná čísla? Pokud má vstupní čísla, tedy doménu funkce vypočítané algoritmu / programu, je zahrnout pouze kladná celá čísla, včetně nuly, pak selhání v nula znamená, že algoritmus (a program, který vytvoří instanci ji) je částečná funkce a nikoliv celkové funkce . Pozoruhodný selhání v důsledku výjimek je Ariane 5 letu 501 raketa selhání (04.6.1996).

Důkazem správnosti programu pomocí matematické indukce : Knuth demonstruje použití matematické indukce na „prodloužené“ verze Eukleidova algoritmu, a navrhuje „obecnou metodu použitelnou pro prokázání platnosti jakéhokoli algoritmu“. Tausworthe navrhuje, aby míra složitosti programu je délka jeho správnost důkazu.

Měření a zlepšování algoritmů Euclid

Elegance (kompaktnost) oproti dobra (rychlost) : S jen šest základních pokynů, „elegantní“ je jasným vítězem, ve srovnání s „nevzhledné“ na třináct pokyny. Nicméně, „nevzhledné“ je rychlejší (dorazí zastavil méně kroků). Algoritmus analýza ukazuje, proč tomu tak je: „Elegant“ dělá dva podmíněné testy v každém odečítání smyčce, zatímco „nevzhledné“ dělá jen jeden. Vzhledem k tomu, algoritmus (zpravidla) vyžaduje mnoho loop-průchodky, na průměrnou mnoho času se promrhá dělá „B = 0?“ Test, který je potřeba pouze po zbytek je vypočítána.

Může algoritmy zlepšit? : Jakmile programátor soudce-pak autor nabízí se otázka, může to být zlepšena program „fit“ a „efektivní“ -že je to spočítá funkce určena jeho?

Kompaktnost „nevzhledné“ může být zlepšena odstraněním pěti krocích. Ale Chaitin prokázaly, že zhutněním algoritmus nemůže být automatizován pomocí zobecněného algoritmu; poněkud, to lze provést pouze heuristicky ; tedy vyčerpávající vyhledávání (příklady lze nalézt v Busy bobr ), pokus a omyl, chytrost, pohled, aplikace induktivní 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áznak, že tyto kroky, spolu s kroky 2 a 3, mohou být odstraněny. Tím se snižuje počet základních pokynů od třinácti do osmi, který dělá to „elegantnější“ než „elegantní“, v devíti krocích.

Rychlost „elegantní“ může být zlepšena pohybem „B = 0?“ Test mimo dvou odčítání smyčky. Tato změna žádá o doplnění tří instrukcí (B = 0 ?, A = 0 ?, GOTO). Nyní „elegantní“ vypočítává PŘÍKLAD čísel rychleji; zda je to vždy pro daný A, B a R, S by vyžadovalo podrobnou analýzu.

algoritmické analýzy

Často je důležité vědět, kolik z určitého zdroje (jako například čas nebo ukládání) je teoreticky potřebný pro daný algoritmus. Metody byly vyvinuty pro analýzu algoritmů pro získání takové kvantitativní odpovědi (odhady); například třídění algoritmus má výše uvedený požadavek na čase O ( n ), s použitím velké O notace s n jako délka seznamu. Po celou dobu algoritmus jen potřebuje si pamatovat dvě hodnoty: největší počet dosud nalezena, a jeho aktuální pozice v seznamu vstupu. Proto se říká, že požadavek prostoru O (1) , v případě, že prostor, potřebný pro uložení čísla vstupních se nepočítá, nebo O ( n ) v případě, že se počítá.

Různé algoritmy mohou absolvovat stejný úkol s jinou sadou instrukcí v méně nebo více času, prostoru, nebo ‚ úsilí ‘ než ostatní. Například binární vyhledávací algoritmus (s náklady O (log n)) překonává si při použití pro sekvenční vyhledávání (náklady O (n)) stolní vyhledáváními na tříděné seznamy nebo matice.

Formální proti empirické

Analýza a studie o algoritmech je disciplína počítačové vědy , a je často praktikováno abstraktně bez použití konkrétního programovacího jazyka nebo implementaci. V tomto smyslu analýzu algoritmus se podobá jiné matematické disciplíny v tom, že se zaměřuje na základní vlastnosti algoritmu a nikoli na specifika konkrétní realizaci. Obvykle pseudocode se používá pro analýzu, jak je to nejjednodušší a nejobecnější reprezentace. Nicméně, nakonec většina algoritmy jsou obvykle prováděny na konkrétní hardware / softwarové platformy a jejich algoritmické účinnost je nakonec podrobena zkoušce s použitím skutečného kódu. Pro řešení „jednorázovou“ problém, účinnost určitého algoritmu nemusí mít závažné důsledky (pokud n je extrémně velká), ale pro algoritmy určené pro rychlé interactive, obchodní nebo dlouhou životností vědecké použití to může být kritické. Změna velikosti od malých až po velké n n často vystavuje neefektivní algoritmy, které jsou jinak neškodné.

Empirické testování je užitečné, protože to může odhalit neočekávané interakce, které ovlivňují výkon. Srovnávací testy mohou být použity pro porovnání před / po případných vylepšení algoritmu po optimalizaci programu. Empirické testy nemohou nahradit formální analýzu, i když, a nejsou triviální provádět spravedlivě.

účinnost Execution

Pro ilustraci potenciální zlepšení jsou možná i dobře zavedené algoritmy, nedávná významná inovace, týkající se FFT algoritmů (používán těžce v oblasti zpracování obrazu), může snížit dobu zpracování až 1000 krát pro aplikace, jako jsou lékařské zobrazování. Obecně platí, že zlepšení rychlosti závisí na zvláštních vlastnostech tohoto problému, které jsou velmi časté v praktických aplikacích. Speedups tohoto rozsahu umožňují výpočetní zařízení, které ve velké míře využívají zpracování obrazu (jako jsou digitální fotoaparáty a zdravotnické techniky), aby se spotřebovávají méně energie.

Klasifikace

Existují různé způsoby, jak třídit algoritmy, z nichž každý má své vlastní zásluhy.

implementací

Jeden způsob, jak třídit algoritmy je o implementačních prostředků.

rekurze
Rekurzivní algoritmus je takový, který opakovaně vyvolá (odkazuje na) sám do určitého stavu (také známý jako stav ukončení) odpovídá, kterým je způsob společné funkční programování . Iterační algoritmy pouze opakující se pojmy jako smyčky a někdy i další datové struktury, jako stohy vyřešit uvedené problémy. Některé problémy jsou přirozeně vhodné pro jedno provedení nebo druhé. Například věže Hanoi je dobře známo použití rekurzivní provádění. Každý rekurzivní verze má ekvivalent (ale možná více či méně komplexní) iterativní verze, a naopak.
Logický
Algoritmus může být považována za kontrolovanou logické dedukce . Tento pojem může být vyjádřena jako: Algorithm = logiky + ovládání . Logika složka vyjadřuje axiomy, které mohou být použity pro výpočet a součástí řídící určuje způsob, ve kterém je odpočet aplikované na axiómů. To je základem pro logické programování paradigmatu. V čisté logiky programovací jazyky, řídící složka je pevná a algoritmy jsou určeny tím, že poskytují pouze logický komponent. Odvolání tohoto přístupu je elegantní sémantika : změna axiomy produkuje dobře definované změny v algoritmu.
Sériové, paralelní nebo distribuovány
Algoritmy jsou obvykle projednány s předpokladem, že počítač spustit jednu instrukci algoritmu najednou. Tyto počítače jsou někdy nazývány sériových počítačů. Algoritmus určen pro takovém prostředí se nazývá sériový algoritmus, na rozdíl od paralelní algoritmy nebo distribuovaných algoritmů . Paralelní algoritmy využít počítačových architektur, kde několik procesorů může pracovat na problém ve stejnou dobu, zatímco distribuované algoritmy využívají více počítačů spojených s počítačovou sítí . Paralelní nebo distribuované algoritmy rozdělit problém do více symetrické nebo asymetrické subproblems a sbírat výsledky zpět dohromady. Spotřeba zdrojů v takových algoritmů je nejen procesoru cykly na každý procesor, ale také komunikační režie mezi procesory. Některé třídicí algoritmy lze paralelizovat efektivně, ale jejich komunikace režie je drahé. Iterační algoritmy jsou obecně paralelizovatelné. Některé problémy nemají paralelní algoritmy a jsou nazývány neodmyslitelně sériové problémy.
Deterministický nebo non-deterministický
Deterministický algoritmus řeší problém s přesným rozhodnutím na každém kroku algoritmu, zatímco non-deterministický algoritmus řešit problémy pomocí hádání ačkoli typické odhady jsou přesnější díky použití heuristiky .
Přesný nebo přibližný
Zatímco mnoho algoritmů dostat přesné řešení, aproximační algoritmy usilovat o sbližování, která je blíže ke skutečnému řešení. Aproximace může být dosaženo buď pomocí deterministické nebo náhodné strategii. Tyto algoritmy mají praktickou hodnotu pro mnoho těžkých problémů. Jedním z příkladů přibližného algoritmu je problém batohu . Batohu problém je problém tam, kde je sada dané položky. Cílem tohoto problému je sbalit batoh získat maximální celkovou hodnotu. Každá položka má nějakou váhu a nějakou hodnotu. Celková hmotnost, že můžeme nést není nic víc než nějaký fixní počet X. Takže, musíme vzít v úvahu hmotnost předmětů, jakož i jejich hodnotu.
Quantum algoritmus
Běhají z realistického modelu kvantovém počítání . Termín se obvykle používá pro algoritmy, které se zdají neodmyslitelně quantum, nebo používají některé základní rys kvantové práce na počítači , jako jsou kvantové superpozice nebo kvantové zapletení .

Designovým paradigmatu

Další způsob, jak třídit algoritmy je jejich konstrukční metodologii nebo paradigmatu. Existuje určité množství vzorů, z nichž každý odlišný od ostatních. Kromě toho je každý z těchto kategorií zahrnuje mnoho různých typů algoritmů. Některé společné vzory jsou:

Brute-force nebo vyčerpávající vyhledávání
To je naivní způsob se snaží všechny možné řešení, aby zjistili, které je nejlepší.
Rozděl a panuj
Rozděl a panuj opakovaně snižuje instanci problému na jeden nebo více menších instancí stejného problému (obvykle rekurzivně ), dokud případy jsou dostatečně malé, aby snadno vyřešit. Jedním takovým příkladem rozděl a panuj je sloučit třídění . Třídění může být provedeno v každém segmentu dat po rozdělení dat do segmentů a třídění všech dat může být získána ve fázi dobývat sloučením segmenty. Jednodušší varianta rozděl a panuj se nazývá pokles a podmanit si algoritmus , který řeší shodný podproblém a používá řešení tohoto podproblém vyřešit větší problém. Rozděl a panuj rozdělení problému do několika subproblems a tak stupeň panuj je složitější než snižují a panuj algoritmů. Příkladem poklesu a panuj algoritmu je binární vyhledávání .
Hledání a výčet
Mnoho problémů (takový jako hraní šachů ) mohou být modelovány jako problémy na grafech . Algoritmus graf průzkum určuje pravidla pro pohyb po grafu a je užitečný pro takové problémy. Tato kategorie zahrnuje také vyhledávací algoritmy , větví a mezí výčet a ústupek .
randomizované algoritmus
Takové algoritmy, aby některé volby náhodně (nebo pseudo-náhodně). Mohou být velmi užitečné při hledání přibližné řešení problémů, které se nalezení přesné řešení, může být nepraktické (viz heuristické níže). Pro některé z těchto problémů, je známo, že nejrychlejší přiblížení musí zahrnovat nějakou náhodnost . Zda randomizované algoritmy s polynomiální časovou složitostí může být nejrychlejší algoritmy pro některé problémy, je otevřená otázka známá jako P proti NP problém . Tam jsou dvě velké třídy takových algoritmů:
  1. Algoritmy Monte Carlo vrátit správnou odpověď s vysokou pravděpodobností. Např RP je podtřídy z nich, které pracují v polynomial čase .
  2. Las Vegas algoritmy vždy vrátí správnou odpověď, ale jejich hrací čas je pouze pravděpodobnostně vázána, např ZPP .
Snížení složitosti
Tato technika zahrnuje řešení složitého problému a její přeměnu ve lépe známý problém, pro které máme (snad) asymptoticky optimální algoritmy. Cílem je najít redukční algoritmus, jehož složitost není ovládán výsledné snížení algoritmu. Například jeden algoritmus volba pro nalezení mediánu v netříděného seznamu zahrnuje nejprve třídění seznamu (drahé část) a pak vytažením prostřední prvek v tříděném seznamu (levně část). Tato technika je také známá jako transformace a panuj .
Backtracking
V tomto přístupu, více řešení jsou postaveny postupně a opuštěný, když se zjistí, že nemohou vést k platného kompletního řešení.

optimalizační problémy

Pro optimalizační problémy je konkrétnější klasifikaci algoritmů; algoritmus pro takové problémy mohou spadat do jedné nebo více obecných kategorií popsaných výše, stejně jako do jedné z následujících možností:

Lineární programování
Při hledání optimálních řešení pro lineární funkce vázané na lineární rovnosti a nerovnosti omezení jsou omezení tohoto problému lze použít přímo při výrobě optimální řešení. Existují algoritmy, které lze vyřešit jakýkoliv problém v této kategorii, jako je například populární simplex algoritmu . Problémy, které mohou být řešeny pomocí lineárního programování zahrnují maximální problém toku pro orientovaných grafů. Je-li problém, navíc vyžaduje, aby jedna nebo více z neznámých musí být celé číslo , pak je zařazen do celočíselné programování . Lineární programování algoritmus může takový problém vyřešit, pokud lze prokázat, že všechna omezení pro celočíselné hodnoty jsou povrchní, tedy řešení splňují tato omezení v každém případě. V obecném případě, specializovaný algoritmus nebo algoritmus, který nalezne přibližné řešení se používá v závislosti na obtížnosti tohoto problému.
Dynamické programování
Když problém ukazuje optimální konstrukcí - to znamená optimální řešení problému, může být vyrobena z optimálních řešení subproblems - a překrývající subproblems , což znamená stejné subproblems jsou použity k řešení mnoha různých instancí problém, rychlejší přístup názvem dynamické programování zabrání přepočítání řešení, která již byly vypočteny. Například, Floyd-Warshallův algoritmus , nejkratší cestu k brance vrcholu v váženého grafu lze nalézt pomocí nejkratší cestu k cíli ze všech sousedních vrcholů. Dynamické programování a memoization jdou ruku v ruce. Hlavní rozdíl mezi dynamického programování a rozděl a panuj je, že podúlohy jsou více nebo méně nezávisle na rozděl a panuj, vzhledem k tomu, podúlohy překrývají dynamického programování. Rozdíl mezi dynamickým programováním a přímočaré rekurze je v mezipaměti nebo memoization rekurzivních volání. Když podúlohy jsou nezávislé a není opakování, memoization nepomůže; tedy dynamické programování není řešením pro všechny složitých problémů. Pomocí memoization nebo zachování tabulky z podproblémy již vyřešen, dynamické programování snižuje exponenciální charakter mnoho problémů polynomiální složitosti.
Chamtivý metoda
Chamtivý algoritmus je podobný dynamický programovací algoritmus v tom, že funguje tak, že zkoumání spodních staveb, v tomto případě nikoli problému, ale dané řešení. Takové algoritmy začít s nějakým řešení, které mohou být uvedeny, nebo byly postaveny nějakým způsobem, a vylepšit tím, že drobné úpravy. U některých problémů, které mohou najít optimální řešení, zatímco pro ostatní, že zastaví na místní optima , to znamená, že při řešení, které nemohou být zlepšeny pomocí algoritmu, ale nejsou optimální. Nejpopulárnější použití chamtivých algoritmů je pro nalezení minimální kostry, kde nalezení optimálního řešení, je možné pomocí této metody. Huffman strom , Kruskal , Prim , Sollin jsou hladové algoritmy, které mohou tento problém vyřešit optimalizaci.
Metoda heuristické
V optimalizačních problémů , heuristické algoritmy lze najít řešení v blízkosti optimální řešení v případech, kdy hledání optimálního řešení je nepraktické. Tyto algoritmy fungují tak, že stále blíž a blíž k optimální řešení, tak jak postupují. V zásadě, pokud běžet nekonečné množství času, které se najít optimální řešení. Jejich předností je, že lze nalézt řešení velmi blízko k optimálnímu řešení v relativně krátkém čase. Tyto algoritmy zahrnují místní vyhledávání , Tabu prohledávání , simulované žíhání a genetické algoritmy . Některé z nich, jako simulované žíhání, jsou non-deterministický algoritmus, zatímco jiní, jako je tabu vyhledávání, jsou deterministické. Pokud je vázán na chybou než optimální řešení je známo, je algoritmus dále rozděleny do kategorií jako algoritmus aproximace .

Podle oboru

Každý vědní obor má své vlastní problémy a potřebuje účinné algoritmy. Související problémy v jedné oblasti jsou často studovány spolu. Některé příklady třídy jsou vyhledávací algoritmy , třídění algoritmy , sloučit algoritmy , numerické algoritmy , grafové algoritmy , řetězec algoritmy , výpočetní geometrické algoritmy , kombinatorické algoritmy , lékařské algoritmy , učení stroje , šifrování , komprese dat algoritmy a rozebrat techniky .

Pole mají tendenci se vzájemně překrývají, a algoritmus pokroky v jedné oblasti se může zlepšit, ty druhé, někdy zcela nepříbuzný, pole. Například, dynamické programování byl vynalezen pro optimalizaci spotřeby zdrojů v průmyslu, ale je nyní používán při řešení širokého spektra problémů v mnoha oblastech.

podle složitosti

Algoritmy mohou být klasifikovány podle množství času, které potřebují k dokončení ve srovnání s jejich velikostí vstupu:

  • Konstantní čas: v případě, že doba potřebná pro algoritmus je stejná, bez ohledu na velikost vstupního signálu. Např přístupový do pole prvku.
  • Lineární čas: v případě, že doba je přímo úměrná velikosti vstupu. Např traverza ze seznamu.
  • Logaritmická doba: v případě, že doba je logaritmická funkcí velikosti vstupu. Např algoritmus binární vyhledávání .
  • Polynom čas: v případě, že čas je síla velikosti vstupu. Např bubble sort algoritmus má časovou složitost kvadratickou.
  • Exponenciální čas: v případě, že doba je exponenciální funkcí velikosti vstupu. Např řešení hrubou silou .

Některé problémy mohou mít více algoritmy liší složitostí, zatímco jiné problémy mohou mít žádné algoritmy ani nezná efektivní algoritmy. Jsou zde také mapování z některých problémů k jiným problémům. Vzhledem k tomu, že bylo zjištěno, že je vhodnější zařadit sami problémy namísto algoritmy do tříd rovnocennosti založených na složitosti nejlepších možných algoritmů pro ně.

spojité algoritmy

Adjektivum „kontinuální“ při aplikaci na slovo „algoritmus“ může znamenat:

  • Algoritmus pracuje na datech, která představuje kontinuální množství, přestože tato data reprezentují diskrétní aproximací, tyto algoritmy jsou studovali v numerické analýze ; nebo
  • Algoritmus ve formě diferenciální rovnice , která provozuje nepřetržitě na data, běží na analogový počítač .

Legální problémy

Algoritmy, samy o sobě nejsou obvykle patentovatelné. Ve Spojených státech, požadavek se skládá pouze z jednoduchých manipulací abstraktních pojmů, čísel nebo signálů nepředstavuje „procesy“ (USPTO 2006), a proto algoritmy nejsou patentovatelné (jako v Gottschalk v. Benson ). Nicméně praktické aplikace algoritmů jsou někdy patentovatelné. Například v Diamond v. Diehr , použití jednoduchého zpětnovazebního algoritmu na pomoc při vytvrzování syntetické gumy byl považován patentovatelné. Patentování software je vysoce kontroverzní, a tam jsou velmi kritizovaná patenty zahrnující algoritmy, a to zejména s datovou kompresí algoritmů, jako Unisys ' LZW patentu .

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

Historie: Vývoj pojmu „algoritmus“

Starověký Blízký východ

Algoritmy byly použity ve starověkém Řecku. Dva příklady jsou na eratosthenovo síto , které bylo popsáno v úvodu, aby aritmetický podle Nicomachus , a Euklidova algoritmu , který byl poprvé popsán v Euclidových elementů (c. 300 BC). Babylonské hliněné cihly popsat a zaměstnat algoritmické postupy počítat čas a místo konání významných astronomických událostí.

Diskrétní a rozeznatelné symboly

Tally-značky : Chcete-li mít přehled o svých stád, jejich pytle s obilím a jejich peněz ve starověku použitého sčítání hlasů: hromadit kameny nebo značky poškrábané na hole nebo dělat jednotlivé symboly v jílu. Skrze babylonského a egyptské užívání ochranných známek a symbolů, případně římskými číslicemi a počítadla vyvíjel (Dilson, str. 16-41). Tally známky se objeví prominentně v jedničková soustava aritmetiky používané v Turingova stroje a Post-Turingův stroj výpočty.

Manipulace symbolů jako „place držáky“ na číslech: algebra

Práce starověkých řeckých geometry ( Euclidean algoritmus ) je indický matematik Brahmagupta a perský matematik Al-Khwarizmi (z jehož jméno pojmy „ Algorism “ a „algoritmus“ jsou odvozeny) a západní Evropy matematici vyvrcholila Leibniz ‚s ponětí o ratiocinator (ca 1680):

Dobrý a půl století dopředu jeho času, Leibniz navrhl algebru logiky, algebru, která by určit pravidla pro manipulaci logické pojmy způsobem, že obyčejní algebra určuje pravidla pro manipulaci s čísly.

Mechanické contrivances s jednotlivými státy

Hodiny : Bolter připočítá vynález hmotnosti řízené hodiny jako „klíč vynálezu [Evropy ve středověku]“, zejména lihýř který nám poskytuje klíštěte a tock mechanický hodiny. „Přesný automat“ vedlo okamžitě k „mechanické automaty “, který začíná v 13. století, a nakonec na „výpočetní technika“ -The rozdíl motoru a analytický stroj s Charles Babbage a hraběnka Ada Lovelace , v polovině 19. století. Lovelace je připočítán s prvním vytvořením algoritmu určeného ke zpracování na počítači - analytické motoru Babbage, první zařízení považována za skutečný Turing-kompletní počítač namísto pouhého kalkulačky - a je někdy nazýván „první programátor historie je“ jako výsledek, i když je úplné provedení druhého zařízení Babbageova by neměl být realizován až po desetiletích svého života.

Logické stroje 1870- Stanley Jevon- sovo ' ‚logické počitadlo‘ a ‚logické stroj‘ : Technickým problémem bylo snížení logické rovnice , když představila v podobě podobné tomu, co je nyní známý jako Karnaughových mapy . Jevons (1880) popisuje první jednoduché „počítadlo“ z „kousky dřeva vybavených kolíky, vykonstruované tak, že každá část, nebo třídu [logických] kombinací lze vyzvednout mechanicky... V poslední době se však, jsem snížila systém zcela mechanické podobě, a mají tak ztělesňuje celý nepřímého procesu závěru v tom, co může být nazýváno Logical Machine „Jeho stroj přišel vybavený s‚určitými pohyblivými dřevěných tyčí‘a“ na úpatí jsou 21 kláves, jako ty piano [atd]... ". S tímto strojem se mohl analyzovat „ úsudek nebo jiný jednoduchý logický argument“.

Tento stroj se zobrazí v roce 1870 před Fellows královské společnosti. Další logik John Venn , nicméně, v jeho 1881 symbolickou logiku , otočil záštiplnou oko k tomuto úsilí: „Já jsem žádné vysoké odhadnout sám o zájmu a významu toho, co se někdy nazývá logické automaty ... se nezdá se mi, že jakékoliv contrivances v současné době známé nebo mohou být zjištěny opravdu zaslouží název logických strojů "; viz více na Algoritmus charakterizace . Ale ne, aby nezůstal pozadu i on představil „plán poněkud podobný, vnímám, Prof. Jevon je počítadlo ... [A] [a] zisk, což odpovídá logickému stroji profesora Jevons, může být následující contrivance popsáno. Raději nazývat to jen z logického schéma stroj ... ale myslím, že to mohl udělat velmi úplně vše, co lze rozumně očekávat jakékoliv logické stroj“.

Jacquard tkalcovský stav, Hollerith děrné štítky, telegrafie a telefonie-elektromechanické relé : Bell a Newell (1971) ukazují, že Jacquard tkalcovský stav (1801), předchůdce Hollerith karet (děrné štítky, 1887), a „telefonní technologie přepínání“ byl ke kořenům stromu vést k vývoji prvních počítačů. V polovině 19. století telegrafní , předchůdce telefonu, byl v provozu po celém světě, jeho diskrétní a odlišnou kódování písmen jako „teček a čárek“ společný zvuk. Do konce 19. století telegraf páska (cca 1870) byl v použití, stejně jako použití Hollerith karet v 1890 americkém sčítání lidu. Pak přišla dálnopis (cca 1910) s jeho děrných papírových použití Baudot kódu na pásce.

Telefonní přepínání sítí elektromechanických relé (vynalezený 1835) byl za práci George Stibitz (1937), vynálezce digitálního přidání zařízení. Jak on pracoval v Bellových laboratořích, on pozoroval „zatěžující‘ využití mechanických kalkulátorů s převody. ‚Šel domů jeden večer v roce 1937 v úmyslu vyzkoušet jeho myšlenku ... Když se šťourat skončila, Stibitz zkonstruoval binární přidání zařízení‘ ,

Davis (2000) sleduje zvláštní význam elektromechanického relé (se svými dvěma „binární stavy“ otevřené a uzavřené ):

To bylo jen s vývojem, počínaje v roce 1930, z elektromechanických kalkulačky používání elektrických relé, že stroje byly postaveny mající rozsah Babbage představil si.“

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

Symboly a pravidla : v rychlém sledu, matematika George Boole (1847, 1854), Frege (1879), a Giuseppe Peano (1888-1889) redukuje na aritmetickou řadou znaků manipulovat pravidly. Peanova Zásady aritmetiky, představovaný novou metodou (1888) byl „první pokus o axiomatization matematiky v symbolickém jazyce“.

Ale Heijenoort dává Frege (1879) tato sláva: Fregeho je „možná nejdůležitějším práce kdy byla napsána v logice ..., ve kterém vidíme.“ ‚Vzorec jazyk‘, který je lingua characterica , jazyk psaný se speciálními znaky „pro čisté myšlenky“, to znamená, že bez rétorických ozdob ... konstruována z určitých symbolů, které jsou manipulovány podle určitých pravidel“. práce Frege byl dále zjednodušena a umocněna Alfred North Whitehead a Bertrand Russell ve své Principia Mathematica (1910-1913).

Paradoxy : Zároveň se objevila celá řada rušivých paradoxů v literatuře, zejména burali-fortiho paradox (1897), přičemž Russell paradox (1902-1903), a Richard paradox . Výsledné úvahy vedly k Kurt Gödel papír ‚s (1931) -Je výslovně uvádí paradox lháře-, které zcela snižuje pravidla rekurze na čísla.

Efektivní calculability : Ve snaze řešit Entscheidungsproblem definovanou právě tím, Hilbert v roce 1928, matematici nejprve nastavit o definovat, co se rozumí pod pojmem „efektivní metoda“ nebo „účinné výpočtu“ nebo „účinné calculability“ (tj, výpočet, který by uspět ). V rychlém sledu objevily následující: Alonzo Church , Stephen Kleene a JB Rosserova ‚s lambda-kalkul vybroušené definici‚obecného rekurze‘z práce Gödel působící na návrhy Jacques Herbrandova (srov Gödel Princeton přednášky 1934) a následné zjednodušení podle Kleene. Církevní důkazem toho, že Entscheidungsproblem byl neřešitelný, Emil Post definice je efektivní calculability jako pracovník tupě následující seznam instrukcí pro pohyb doleva nebo doprava přes sled místností a zároveň tam buď označit, nebo vymazat papír nebo pozorovat papír a učinit ano-ne rozhodnutí o dalším pokynu. Alan Turing je důkazem této Entscheidungsproblem byla neřešitelná pomocí jeho „a- [automatic-] stroj“ -v efekt téměř totožný s Post „formulace“, J. Barkley Rosser definice ‚ze dne‚účinným způsobem‘ve smyslu„a stroj". SC Kleene ‚s návrhem předzvěst‚ Church práce ‘, který nazval‚práce I‘, a pár let později Kleenova přejmenování jeho práce‚církevní práci‘a navrhuje‚Turing práce‘.

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

Zde je pozoruhodná shoda dva muži nevědí, navzájem však popisuje proces mužů-as-počítače pracují na výpočtech, a dávají prakticky shodné definice.

Emil Post (1936) popsal akce na „počítač“ (člověk) takto:

“... dva pojmy jsou zapojeny: jako u symbolu prostoru , ve kterém se práce vedoucí z problému, který má odpovědět, je třeba provést, a pevnou nezměnitelné množiny směrů .

Jeho symbol prostor by

„Obousměrná nekonečný sled mezer nebo krabic ... Problém řešitel nebo pracovník pro pohyb a práce v této symbolu prostoru, který je schopen být v, a působí v jedné krabici, ale v době .... krabice je přiznat but dvou možných podmínek, tedy je prázdná nebo neoznačený, a má jediný značku v tom, řekněme vertikální zdvih.
„Jeden kolonka se vybral a nazývá počáteční bod. ... zvláštní problém musí být uvedeny v symbolické formě konečného počtu krabic [tj INPUT] se označí zdvihu. Stejně tak je odpověď [tj , OUTPUT] má být uveden v symbolické formě takovou konfigurací označených boxů ...
„Sada směrů použitelných pro obecný problém nastaví deterministický proces, když je aplikován na každý konkrétní problém. Tento proces je ukončen pouze tehdy, pokud jde o směr typu (C) [tj STOP]“. Více na Post-Turingova stroje
Alan Turing socha v Bletchley Parku

Alan Turing je práce předchází tomu Stibitz (1937); není známo, zda Stibitz věděl o práci Turing. Turing životopisec věřil, že Turing použití modelu psacího stroje, jako odvozený z mladické zájmu: „Alan snil o vynalézat psací stroje jako kluk, paní Turing měl na psacím stroji, a mohl dobře začali tím, ptal se sám sebe, co se rozumí pod pojmem voláním psací stroj ‚mechanický‘“. S ohledem na výskyt Morseovy abecedy a telegrafii, burzovní páskové stroje a teletypewriters můžeme se domnívají, že všichni byli vlivy.

Turing-jeho model výpočtu je nyní volala Turingův stroj -begins, stejně jako Post, s analýzou lidského počítače, který se whittles až do jednoduchého souboru základních pohybů a „stavy mysli“. Ale pokračuje ještě o krok dále a vytváří stroj jako model výpočtu čísel.

„Výpočetní technika se zpravidla provádí písemně určité symboly na papíře. Lze předpokládat, tato kniha je rozdělena do čtverců, jako je dětská aritmetický knihy ... Domnívám se pak, že výpočet se provádí na jednorozměrné papíru, tedy na kazetě rozdělené do čtverce. budu také předpokládat, že počet symbolů, které mohou být vytištěny je konečný ...
„Chování počítače v každém okamžiku je určen symbolů, které se pozoruje, a jeho‚stavu mysli‘V tom okamžiku. Můžeme předpokládat, že je vázán B počtu symbolů nebo čtverců které může počítač pozorovat v jednom okamžiku. Pokud chce sledovat více, musí používat po sobě jdoucích vyjádření. Budeme také předpokládat, že počet stavů mysli, které je nutno vzít v úvahu, je konečný ...
„Pojďme si představit, že operace prováděné v počítači, které mají být rozděleny na‚jednoduché operace‘, které jsou tak základní, že to není snadné, aby je dále rozdělena představit.“

Turing redukce se získá následující:

„Tyto jednoduché operace proto musí zahrnovat:
„(A) Změny symbolu na jednom z pozorovaných čtverců
„(B) změny jedno z polí pozorovaných na jiné pole v L čtverců jednoho z dříve pozorovaných čtverců.

„Je možné, že některé z těchto změn nutně vyvolat změnu stavu mysli Nejobecnější jediné operace proto musí být pokládán za jednu z následujících možností.:

„(A) možná změna (a) symbolem spolu s možnou změnu stavu mysli.
„(B) lze změnit (b) pozorovaných čtverců, spolu s případnou změnu stavu mysli“
„Nyní můžeme sestrojit stroj dělat práci tohoto počítače.“

O několik let později, Turing rozšířila svou analýzu (práce, rozlišení) s tímto mocným výrazem toho:

„Funkce se říká, že‚účinně vypočítat‘, pokud jeho hodnoty lze nalézt nějakou čistě mechanickým způsobem. Ačkoli to je docela snadné se dostat intuitivní pochopení této myšlenky je však žádoucí mít nějaké konkrétnější, matematické exprimovatelný definice ... [on diskutuje o historii definice do značné míry, jak je uvedeno výše v souvislosti s Gödel, Herbrandova, Kleene, Church, Turing a Post]... můžeme mít toto prohlášení doslova porozumění čistě mechanickým proces ten, který by mohlo být provedeno pomocí počítače. je možné dát matematický popis v určitém normálním tvaru, struktur těchto strojů. vývoj těchto nápadů vede k definici autorově v počítačově funkce, a na identifikaci vyčíslitelnost † s účinným calculability....
„† budeme používat výraz‚vypočitatelnou funkci‘se rozumí funkce vypočítatelné strojem a necháme‚efektivně kalkulovat‘odkazují na intuitivní myšlence bez konkrétního určení některého z těchto definic“.

JB Rosser (1939) a SC Kleene (1943)

J. Barkley Rosser definoval "metody efektivní [matematické] následujícím způsobem (italicization přidáno):

„Je zde použit‚efektivní metoda‘v poněkud zvláštní smyslu způsobu každý krok, který je přesně určeno, a které je jisté, že produkci odpověď v konečném počtu kroků. S tímto speciálním smyslu, byly uvedeny tři různé přesné definice k dnešnímu dni [jeho poznámky pod čarou # 5, viz diskusi okamžitě níže]. nejjednodušší z nich do stavu (v důsledku Post a Turing) říká, v podstatě to. účinný způsob řešení určité sady problémů existuje, pokud je možné postavit stroj, který pak bude vyřešit jakýkoliv problém sady bez zásahu člověka za vložení otázku a (později) čtení odpověď . Všechny tři definice jsou rovnocenné, takže nezáleží na tom, který z nich je používán. Navíc skutečnost, že všichni tři jsou rovnocenné se velmi silný argument pro správnost některého.“ (Rosserova 1939: 225-6)

Rosserova své poznámky pod čarou č 5 odkazuje na dílo (1) Církev a Kleene a jejich definice Á-Definovatelnost, zejména církevní využití něj v jeho neřešitelný problém elementární teorie čísel (1936); (2) Herbrand a Gödel a jejich použití rekurze při použití konkrétního Gödel ve svém slavném papíru On formálně undecidable Principia Mathematica a příbuzné systémy I (1931); a (3) Post (1936) a Turing (1936-1937) ve svých mechanismus modelů výpočtů.

Stephen C. Kleene definován jako jeho nyní-slavný „práce I“ známý jako Church-Turingova teze . Ale on to udělal v následujícím kontextu (tučně v originále):

„12. algoritmické teorie ... V nastavení kompletní algoritmické teorii, co děláme, je popsat postup, splnitelný pro každou sadu hodnot nezávislých proměnných, který postup nutně končí a takovým způsobem, že z výsledku můžeme číst definitivní odpověď „ano“ nebo „ne“ na otázku, „je hodnota predikát pravda?““(Kleene 1943: 273)

Historie po roce 1950

Mnoho úsilí bylo zaměřeno dalšího zpřesnění definice „algoritmus“, a činnost probíhající kvůli problémům s kolem, zejména základy matematiky (zejména Church-Turing práce ) a filozofii mysli (zejména argumenty o umělé inteligence ). Pro více informací viz algoritmus charakterizace .

viz též

Poznámky

Bibliografie

  • AXT, P (1959). „Na Subrecursive hierarchie a primitivně rekurzivní stupňů“. Transakce na americkém matematické společnosti . 92 : 85-105. doi : 10,2307 / 1993169 . JSTOR  1993169 .
  • Bell, C. Gordon a Newell, Allen (1971), počítačové Structures: Čtení a příklady , McGraw-Hill Book Company, New York. ISBN  0-07-004357-4 .
  • Blass, Andreas ; Gurevič, Yuri (2003). „Algoritmy: pátrání po absolutní Definice“ (PDF) . Bulletin Evropské asociace pro teoretické informatiky . 81 . Zahrnuje vynikající bibliografii 56 referencí.
  • Prosévačky, David J. (1984). Turingova Man: Západní kultura ve věku počítačů (1984 ed.). Univerzita Severní Karolíny Press, Chapel Hill NC. ISBN  0-8078-1564-0 ., ISBN  0-8078-4108-0 pbk.
  • Boolos, George ; Jeffrey, Richard (1999) [1974]. Vyčíslitelnost a logické (4th ed.). Cambridge University Press, London. ISBN  0-521-20402-X .: Cf. Kapitola 3 Turingovy stroje , kde se diskutují „určité spočetné množiny nejsou efektivně (mechanicky) enumerable“.
  • Burgin, Mark (2004). Super-rekurzivních algoritmů . Springer. ISBN  978-0-387-95569-8 .
  • Campagnolo, ML, Moore, C. , a Costa, JF (2000) Analogové charakterizace subrecursive funkcí. V Proc. ze 4. konference o reálných čísel a počítače , Odense University, str. 91-109
  • Kostel, Alonzo (1936a). „Neřešitelný problém elementárních teorie čísel“. The American Journal of matematiky . 58 (2): 345-363. doi : 10,2307 / 2371045 . JSTOR  2371045 .Dotisknutý v The nerozhodnutelná , s. 89ff. První výraz „práce církve“. Viz zejména strana 100 ( nerozhodnutelné ), kde se definuje pojem „efektivní calculability“ ve smyslu „algoritmus“, a on používá slovo „se ukončí“ atd
  • Kostel, Alonzo (1936b). „Poznámka k Entscheidungsproblem“. The Journal of Symbolic Logic . 1 (1): 40-41. doi : 10,2307 / 2269326 . JSTOR  2269326 .Kostel, Alonzo (1936). „Oprava k Poznámka k Entscheidungsproblem“. The Journal of Symbolic Logic . 1 (3): 101-102. doi : 10,2307 / 2269030 . JSTOR  2269030 .Dotisknutý v The nerozhodnutelná , s. 110ff. Církev ukazuje, že Entscheidungsproblem je neřešitelný v cca 3 stran textu a 3 stránek poznámky pod čarou.
  • Daffa‘, Ali Abdullah al-(1977). Muslimská příspěvek k matematice . London: Croom Helm. ISBN  0-85664-464-1 .
  • Davis, Martin (1965). Nerozhodnutelné: Základní dokumenty o undecidable, neřešitelné problémy a vyčíslitelných funkcí . New York: Raven Press. ISBN  0-486-43228-9 .Davis dává komentář před každým článkem. Papíry Gödel , Alonzo Church , Turing , Rosser , Kleene a Emil Post jsou zahrnuty; ty, citované v tomto článku jsou zde uvedeny podle jména autora.
  • Davis, Martin (2000). Motory logiky: Matematici a Původ počítače . New York: WW Nortion. ISBN  0-393-32229-7 .Davis nabízí stručné životopisy Leibniz , Boole , Frege , Cantor , Hilbert , Gödel a Turing s von Neumann jako show-krást darebák. Velmi krátké bios Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken a další
  •  Tento článek včlení materiál public domain  z  NIST dokumentu:  Black, Paul E. "algoritmus" . Slovník algoritmů a datových struktur .
  • Dean, Tim (2012). „Evoluce a morální různorodost“. Baltic International Yearbook poznání, logiky a komunikace . 7 .
  • Dennett, Daniel (1995). Darwinova Dangerous Idea . New York: Touchstone / Simon & Schuster. ISBN  0-684-80290-2 .
  • Dilson, Jesse (2007). Počítadlo ((1968,1994), ed.). Svatomartinská Press, NY. ISBN  0-312-10409-X ., ISBN  0-312-10409-X (PBK).
  • Yuri Gurevič , Sekvenční Abstraktní stavových automatů Zachyťte sekvenční algoritmy , ACM Transactions on Computational Logic, Vol 1, No 1 (červenec 2000), strany 77-111. Zahrnuje bibliografii 33 zdrojů.
  • van Heijenoort, Jean (2001). Od Frege k Gödel, Kniha zdroje v matematické logiky, 1879-1931 ((1967), ed.). Harvard University Press, Cambridge, MA. ISBN  0-674-32449-8 ., 3rd edition 1976 [?], ISBN  0-674-32449-8 (PBK).
  • Hodges, Andrew (1983). Alan Turing: Hádanka . New York: Simon a Schuster . ISBN  0-671-49207-1 ., ISBN  0-671-49207-1 . Srov Kapitola „Duch pravdy“ o historii vedoucí k, a diskuse o jeho důkaz.
  • Kleene, Stephen C. (1936). „General rekurzivní funkce přirozených čísel“ . Mathematische Annalen . 112 (5): 727-742. doi : 10,1007 / BF01565439 .Prezentovány na Americké matematické společnosti, září 1935. dotisknutý v The nerozhodnutelné , str. 237ff. Definice Kleenova z „obecného rekurze“ (známý nyní jako mu-rekurze) byl používán kostela v jeho 1935 papíru neřešitelný problém základní teorie čísel , která ukázala jen „rozhodnutí o problému“ být „undecidable“ (tj negativní výsledek).
  • Kleene, Stephen C. (1943). „Rekurzivní predikáty a Kvantifikátory“. Američtí Transakce Mathematical Society . 54 (1): 41 až 73. doi : 10,2307 / 1990131 . JSTOR  1990131 .Dotisknutý v The nerozhodnutelná , s. 255ff. Kleene rafinované svou definici „obecného rekurze“ a pokračoval ve své kapitole „12. algoritmické teorií“ postulovat „práci I“ (str 274).; on by později opakovat tuto práci (v Kleene 1952: 300) a název "církevní práci" (Kleeneho 1952: 317) (tj Church práce ).
  • Kleene, Stephen C. (1991) [1952]. Úvod do metamathematics (desátá ed.). North-Holland Publishing Company. ISBN  0-7204-2103-9 . Výborná přístupný, čitelné-reference zdrojem pro matematické „základy“.
  • Knuth, Donald (1997). Základní algoritmy, třetí vydání . Reading, Massachusetts: Addison-Wesley. ISBN  0-201-89683-4 .
  • Knuth, Donald (1969). Volume 2 / Seminumerical algoritmy, Umění programování prvního vydání . Reading, Massachusetts: Addison-Wesley.
  • Kosovsky, NK prvky matematické logiky a jeho aplikace na teorii Subrecursive algoritmů , LSU Publ., Leningrad, 1981
  • Kowalski, Robert (1979). "Algoritmus = Logic + Control". Komunikace ACM . 22 (7): 424-436. doi : 10,1145 / 359.131,359136 .
  • AA Markov (1954) Teorie algoritmů . [Přeloženo Jacques J. Schorr-Kon a zaměstnanci PST] Imprint Moskvě, Akademie věd SSSR, 1954 [tj, Jeruzalém, Izrael Program pro vědecké Překlady, 1961; k dispozici od Úřadu technických služeb, US Dept. of Commerce, Washington] Popis 444 str. 28 cm. Přidán tp v ruštině Překlad děl Matematického ústavu Akademie věd SSSR, v 42. Originální název:. Teoriya algerifmov. [Knihovna QA248.M2943 Dartmouth College. US Dept. of Commerce, Úřad technických služeb, počet OTS 60-51085.]
  • Minsky, Marvin (1967). Výpočet: Konečné a nekonečné stroje (první ed.). Prentice Hall, Englewood Cliffs, NJ. ISBN  0-13-165449-7 .Minsky rozšiřuje svou „... myšlenku algoritmu-efektivním způsobem ...“ v kapitole 5.1 Vyčíslitelnost, účinné postupy a algoritmy. Nekonečné stroje.
  • Post, Emil (1936). "Konečné Kombinatorické Processes, formulace I". The Journal of Symbolic Logic . 1 (3): 103-105. doi : 10,2307 / 2269031 . JSTOR  2269031 .Dotisknutý v The nerozhodnutelná , s. 289ff. Post definuje jednoduchý algoritmické podobný proces člověka psaní známky nebo odstraněním značek a vede z pole na pole a nakonec se zastavit, když následuje seznam jednoduchých instrukcí. To je citován Kleene jako jeden ze zdrojů jeho „I práce“, tzv Church-Turingova teze .
  • Rogers, Jr, Hartley (1987). Teorie rekurzivní funkce a efektivní Vyčíslitelnost . MIT Press. ISBN  0-262-68052-1 .
  • Rosserova, JB (1939). „Neformální Expozice dokladů o Gödel teorém a církevní věty“. Journal of Symbolic Logic . 4 (2): 53-60. doi : 10,2307 / 2269059 . JSTOR  2269059 .Dotisknutý v The nerozhodnutelná , s. 223ff. Zde je Rosserova slavná definice „účinným způsobem“:“... metoda každý krok, který je přesně předem určena a která je jistě vyvolají odpověď v konečném počtu kroků ... stroje, který pak bude řešit jakýkoliv problém sada bez zásahu člověka za vložení otázku a (později) přečtení odpovědi“(str. 225-226, nerozhodnutelné )
  • Santos-Lang, Christopher (2014). „Morální Ecology Přístupy do strojového etiky“. V van Rysewyk, Simon; Pontier, Matthijs. Stroj Lékařská etika (PDF) . Švýcarsko: Springer. str. 111-127. doi : 10,1007 / 978-3-319-08108-3_8 .
  • Scott, Michael L. (2009). Programovací jazyk pragmatika (3. ed.). Morgan Kaufmann Publishers / Elsevier. ISBN  978-0-12-374514-9 .
  • Sipser, Michael (2006). Úvod do teorie počítání . PWS Publishing Company. ISBN  0-534-94728-X .
  • Střízlivý, Elliott; Wilson, David Sloan (1998). Unto Ostatní: Evoluce a psychologie nesobecké chování . Cambridge: Harvard University Press.
  • Kámen, Harold S. (1972). Úvod do informatiky organizaci a datových struktur (1972 ed.). McGraw-Hill, New York. ISBN  0-07-061726-0 .Srov zejména první kapitola s názvem: Algoritmy, Turingovy stroje a programy . Jeho krátký neformální definice: „... jakýkoli sled instrukcí, které mohou být poslouchán pomocí robotu, se nazývá algoritmus “ (str. 4).
  • Tausworthe, Robert C (1977). Standardizovaná Vývoj počítačového softwaru Část 1: Metody . Englewood Cliffs: Prentice-Hall, Inc. ISBN  0-13-842195-1 .
  • Turing, Alan M. (1936 - 1937). „On vypočitatelných číslech, s žádostí o Entscheidungsproblem“. Proceedings of the London matematické společnosti . Série 2. 42 : 230-265. doi : 10,1112 / PLMS / s2-42.1.230 ., Opravy, tamtéž, sv. 43 (1937), str. 544-546. Dotisknutý v The nerozhodnutelná , s. 116ff. Turing slavný papír dokončena magisterského práce, zatímco na královské vysoké škole Cambridge UK.
  • Turing, Alan M. (1939). „Na řadové systémy Logic Based“. Proceedings of the London matematické společnosti . 45 : 161-228. doi : 10,1112 / PLMS / s2-45.1.161 .Dotisknutý v The nerozhodnutelná , s. 155ff. Turing papír, který definoval „orákulum“ byla jeho disertační práce, zatímco na Princeton v USA.
  • Spojené státy americké patenty a ochranné známky Office (2006), 2106,02 **> matematické algoritmy: 2100 Patentovatelnost , Manuál Patent Zkoumání řízení (MPEP). Poslední revize 08. 2006

Další čtení

externí odkazy

algoritmus úložiště
Poznámky k výuce