Algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. ledna 2022; kontroly vyžadují 10 úprav .

Algoritmus ( lat.  algorithmi  - jménem středoasijského matematika Al-Khwarizmiho [1] ) je konečný soubor přesně definovaných pravidel pro řešení určité třídy problémů nebo soubor instrukcí popisujících postup interpreta při řešení konkrétního problému. problém. Ve starém výkladu se místo slova „pořadí“ používalo slovo „sekvence“, ale s rozvojem paralelismu v práci počítačů se slovo „sekvence“ začalo nahrazovat obecnějším slovem „pořadí“. Nezávislé instrukce mohou být prováděny v libovolném pořadí, paralelně, pokud to použité vykonavatelé umožňují.

Dříve v ruštině psali „algori f m“, nyní se tento pravopis používá zřídka, ale přesto existuje výjimka ( normální Markovův algoritmus ).

Počítač často funguje jako vykonavatel, ale pojem algoritmus nemusí nutně odkazovat na počítačové programy  - například jasně popsaný recept na přípravu pokrmu je také algoritmem, v tomto případě je vykonavatelem osoba (nebo možná nějaký mechanismus, například tkací stroj nebo soustruh s číslicovým řízením ).

Je možné vyčlenit výpočetní algoritmy (dále o nich hlavně mluvíme) a řídicí . Výpočtové algoritmy ve skutečnosti transformují některá počáteční data na výstup a realizují výpočet nějaké funkce. Sémantika řídicích algoritmů se může výrazně lišit a spočívá v provádění nezbytných řídicích akcí buď v daných časech nebo jako reakce na vnější události (v tomto případě, na rozdíl od výpočetního algoritmu, může řídicí algoritmus zůstat správný pro nekonečné provádění).

Pojem algoritmus odkazuje na původní, základní, základní pojmy matematiky. Výpočetní procesy algoritmické povahy (aritmetické operace s celými čísly, hledání největšího společného dělitele dvou čísel atd.) jsou lidstvu známy již od starověku. V explicitní podobě se však pojem algoritmus zformoval až na počátku 20. století.

Částečná formalizace konceptu algoritmu začala pokusy vyřešit problém rozlišení ( německy  Entscheidungsproblem ), který zformuloval David Hilbert v roce 1928 . Následující formalizační kroky byly nutné k definování efektivního výpočtu [2] nebo „efektivní metody“ [3] ; takové formalizace zahrnují rekurzivní funkce Gödel  - Herbran -  Kleene z roku 1930 , 1934 a 1935  , λ-počet Alonza Churche z roku 1936  , Formulaci 1 Emila Posta z roku 1936 a Turingův stroj .

Historie termínu

Moderní formální definice výpočetního algoritmu byla dána ve 30-50 letech 20. století v pracích Turinga , Posta , Churche ( Church-Turingova teze ), N. Wienera , A. A. Markova .

Samotné slovo „algoritmus“ pochází ze jména perského ( Khorezm a Maverannakhr ) vědce al-Khorezmiho . Kolem roku 825 napsal dílo Kitab al-jabr wal-muqabala ("Kniha sčítání a odčítání"), z jehož původního názvu pochází slovo " algebra " (al-jabr - dokončení). V této knize poprvé popsal systém pozičních desítkových čísel vynalezený v Indii. Perský originál knihy se nedochoval. Al-Khwarizmi formuloval pravidla pro počítání v novém systému a pravděpodobně poprvé použil číslo 0 k označení chybějící pozice v zápisu čísla (Arabové přeložili jeho indický název jako as-sifr nebo jednoduše sifr , odtud slova jako "číslice" a "šifra"). Přibližně ve stejné době začali další arabští učenci používat indické číslice.

V první polovině 12. století pronikla do Evropy kniha al-Khwarizmi v latinském překladu. Překladatel, jehož jméno se k nám nedostalo, mu dal jméno Algoritmi de numero Indorum („Algoritmy o indickém účtu“) – do názvu knihy se tak dostalo latinizované jméno středoasijského vědce. Dnes se věří, že slovo „algoritmus“ přišlo do evropských jazyků právě kvůli tomuto překladu. Během několika příštích staletí se objevilo mnoho dalších děl věnovaných stejné problematice - učení umění počítání s čísly, a všechny měly v názvu slovo algoritmi nebo algorismi .

Pozdější autoři nevěděli nic o al-Khwarizmi, ale protože první překlad knihy začíná slovy: „Dixit algorizmi: ...“ („Al-Khwarizmi řekl: ...“), stále toto slovo spojovali se jménem konkrétní osoby. Verze o řeckém původu knihy byla velmi běžná. V anglo-normanském rukopisu ze 13. století , psaném ve verších, čteme:

Algorismus byl vynalezen v Řecku .

Toto je část aritmetiky . Vynalezl jej mistr jménem Algorismus, který mu dal své jméno. A protože se jmenoval Algorismus,

Svou knihu nazval Algorismus.

Kolem roku 1250 napsal anglický astronom a matematik John ze Sacrobosca Algorismus vulgaris o aritmetice , který se stal po staletí hlavní učebnicí výpočtů v desítkovém pozičním zápisu na mnoha evropských univerzitách. V úvodu Sacrobosco jmenoval moudrého muže jménem Algus jako autora nauky o počítání . A v populární středověké básni „ Romance o růži “ (1275-1280) od Jeana de Meun je „řecký filozof Algus“ postaven na roveň Platónovi , Aristotelovi , Eukleidovi a Ptolemaiovi ! Došlo také k pravopisu jména Argus ( Argus ). A ačkoliv podle starověké řecké mytologie loď Argo postavil Jason , stavba lodi byla připisována právě tomuto Argu.

„Mistr Algus“ (neboli Argus) se stal zosobněním počítání umění ve středověké literatuře. A v již zmíněném „Římanovi z růže“ a ve slavné italské básni „Květina“, kterou napsal Durante , jsou fragmenty, které říkají, že ani „mestre Argus“ nebude schopen spočítat, kolikrát se milenci pohádají a udělat mír. Anglický básník Geoffrey Chaucer v básni „ The Book of the Duchess “ ( 1369  ) píše, že ani „slavný pult Argus“ (vznešený hrabě Argu) nebude schopen spočítat monstra, která se hrdinovi zjevila v nočních můrách.

Postupem času se však matematici o taková vysvětlení zajímali stále méně a slovo algorismus (neboli algorismus ), které bylo vždy přítomno v názvech matematických prací, získalo význam způsobu, jak provádět aritmetické operace pomocí arabských číslic. je na papíře bez použití počítadla . V tomto smyslu se dostalo do mnoha evropských jazyků . Například označeno jako „zastaralé“. je přítomen v reprezentativním slovníku anglického jazyka Webster's New World Dictionary , vydaném v roce 1957.  Encyklopedický slovník Brockhause a Efrona nabízí následující výklad: algoritmus (mimochodem, před revolucí se pravopis používal algoritmus , přes fita ) se vyrábí „z arabského slova Al-Goremm, to je kořen“.

Algoritmus je umění počítání s čísly, ale slovo „číslo“ se zpočátku týkalo pouze nuly. Slavný francouzský truver Gautier de Coincy (Gautier de Coincy, 1177-1236) v jedné ze svých básní použil slova algorismus-cipher (což znamenalo číslo 0) jako metaforu pro charakterizaci absolutně zbytečného člověka. Pochopení takového obrazu samozřejmě vyžadovalo patřičnou přípravu posluchačů, což znamená, že nový číselný systém jim byl již poměrně dobře znám.

Po mnoho staletí bylo počítadlo vlastně jediným prostředkem pro praktické výpočty, používali ho obchodníci, směnárníci i vědci. Přednosti výpočtů na počítací desce vysvětlil ve svých spisech tak vynikající myslitel, jakým byl Herbert z Avrilakského (938-1003), který se roku 999 stal papežem pod jménem Silvestr II. Nové se prosazovalo s velkými obtížemi a do historie matematiky patřila zarputilá opozice mezi tábory algorismů a abacistů (někdy nazývaných herbekisté), kteří prosazovali používání počítadla místo arabských číslic pro výpočty. Zajímavostí je, že slavný francouzský matematik Nicolas Chuquet (Nicolas Chuquet, 1445-1488) byl zapsán do registru daňových poplatníků města Lyonu jako algoritmus (algoriste). Než však byla konečně zavedena nová metoda počítání, uplynulo více než jedno století, takže vývoj obecně uznávaných notací, zdokonalení a přizpůsobení výpočetních metod pro psaní na papír si vyžádalo tolik času. V západní Evropě byli učitelé aritmetiky až do 17. století nadále nazýváni „mistry počítadla“ , jako například matematik Niccolò Tartaglia (1500-1557).

Takže spisy o umění počítání se nazývaly Algoritmy . Z mnoha stovek lze vyzdvihnout takové neobvyklé, jako je pojednání Carmen de Algorismo (latinsky carmen a znamená poezie) napsané ve verších Alexandra de Villa Dei († 1240) nebo učebnice vídeňského astronoma a matematika George Purbacha ( Georg Peurbach, 1423-1461) Opus algorismi jocundissimi („Nejzábavnější esej o algoritmu“).

Postupně se význam slova rozšiřoval. Vědci jej začali aplikovat nejen na čistě výpočetní, ale i na další matematické postupy. Například kolem roku 1360 napsal francouzský filozof Nicolaus Oresme (1323/25-1382) matematické pojednání Algorismus ratioum („Výpočet proporcí“), ve kterém poprvé použil mocniny se zlomkovými exponenty a vlastně se přiblížil myšlence logaritmy. Když bylo počítadlo nahrazeno tzv. počítáním na řádcích, četné příručky k němu se začaly nazývat Algorithmus linealis , tedy pravidla pro počítání na řádcích.

Můžete věnovat pozornost skutečnosti, že po nějaké době původní forma algorismi ztratila poslední písmeno a slovo získalo vhodnější formu pro evropský algorismus výslovnosti . Později to zase prošlo zkomoleninou, nejspíše spojenou se slovem aritmetika .

V roce 1684 Gottfried Leibniz v Nova Methodvs pro maximis et minimis, itemque tangentibus... poprvé použil slovo „algoritmus“ ( Algorithmo ) v ještě širším smyslu: jako systematický způsob řešení problémů v diferenciálním počtu.

V 18. století , v jednom z německých matematických slovníků, Vollstandiges mathematisches Lexicon (vydaný v Lipsku v roce 1747  ), je termín algoritmus stále vysvětlován jako koncept čtyř aritmetických operací. Tento význam však nebyl jediný, protože terminologie matematické vědy se v té době teprve utvářela. Zejména výraz algorithmus infinitesimalis byl aplikován na způsoby provádění operací s nekonečně malými hodnotami. Slovo algoritmus také použil Leonard Euler , jehož jedna z prací se jmenuje „Using a new algorithm to solution the Pell problem“ ( De usu novi algorithmi in problemate Pellianosolvendo ). Vidíme, že Eulerovo chápání algoritmu jako synonyma pro způsob řešení problému je již velmi blízké tomu modernímu.

Trvalo však ještě téměř dvě století, než se všechny starověké významy tohoto slova přestaly používat. Tento proces lze vysledovat na příkladu pronikání slova „algoritmus“ do ruského jazyka.

Historici datují jeden ze seznamů starověké ruské učebnice aritmetiky, známé jako „Počítací moudrost“, do roku 1691 . Toto dílo je známé v mnoha verzích (nejstarší z nich jsou téměř o sto let starší) a sahá až do starověkých rukopisů 16.  století. Podle nich lze vysledovat, jak se na Rusi postupně rozšířila znalost arabských číslic a pravidel pro zacházení s nimi. Úplný název této učebnice je „Tato kniha, mluvená helénskou a řeckou aritmetikou a německým algorismem a ruskou moudrostí počítání čísel“.

Slovo „algoritmus“ tedy první ruští matematici chápali stejně jako v západní Evropě. Nebylo to však ve slavném slovníku V. I. Dahla , ani o sto let později ve Výkladovém slovníku ruského jazyka, který redigoval D. N. Ušakov (1935). Ale slovo „algoritmus“ lze nalézt v populárním předrevolučním encyklopedickém slovníku bratří Granatů a v prvním vydání Velké sovětské encyklopedie (BSE), vydané v roce 1926. Tam i tam je interpretováno ve stejném způsob: zpravidla, podle kterého ta či ona ze čtyř aritmetických operací v desítkové číselné soustavě. Nicméně začátkem 20. stol. pro matematiky slovo „algoritmus“ již znamenalo jakýkoli aritmetický nebo algebraický proces prováděný podle přesně definovaných pravidel a toto vysvětlení je také uvedeno v následujících vydáních TSB.

Algoritmy se staly předmětem stále větší pozornosti vědců a postupně tento pojem zaujal jedno z ústředních míst moderní matematiky. Pokud jde o lidi, kteří mají k matematice daleko, na začátku čtyřicátých let mohli toto slovo slyšet pouze při studiu ve škole v kombinaci „Euklidův algoritmus“. Navzdory tomu byl algoritmus stále vnímán jako čistě odborný termín, což potvrzuje i absence relevantních článků v méně objemných publikacích. Zejména to není ani v desetidílné Malé sovětské encyklopedii (1957), o jednodílných encyklopedických slovnících nemluvě. Ale o deset let později, ve třetím vydání Velké sovětské encyklopedie (1969), je algoritmus již charakterizován jako jedna z hlavních kategorií matematiky, „nemá formální definici z hlediska jednodušších pojmů a abstrahuje se přímo ze zkušenosti. " Jak vidíme, rozdíl i od výkladu prvního vydání TSB je markantní! Algoritmus se na čtyřicet let stal jedním z klíčových pojmů matematiky a slovo už nebylo zahrnuto do encyklopedií, ale do slovníků. Například v akademickém Slovníku ruského jazyka (1981) se vyskytuje právě jako termín z oblasti matematiky.

Současně s vývojem konceptu algoritmu postupně docházelo k jeho rozšiřování z čisté matematiky do dalších oblastí. A začalo to nástupem počítačů, díky nimž slovo „algoritmus“ vstoupilo v roce 1985 do všech školních učebnic informatiky a získalo nový život. Obecně lze říci, že jeho současná sláva přímo souvisí s mírou distribuce počítačů. Například ve třetím díle „Dětské encyklopedie“ (1959) se o počítačích hodně mluví, ale ještě se nestaly něčím známým a jsou vnímány spíše jako jakýsi atribut světlé, ale spíše vzdálené budoucnosti. Algoritmy proto nejsou na jeho stránkách nikdy zmíněny. Ale již na počátku 70. v minulém století, kdy počítače přestaly být exotickou kuriozitou, se slovo „algoritmus“ rychle začíná používat. Citlivě to zaznamenávají encyklopedické publikace. V „ Encyklopedii kybernetiky “ (1974) v článku „Algoritmus“ je již spojen s implementací na počítačích a v „Sovětské vojenské encyklopedii“ (1976) dokonce samostatný článek „Algoritmus pro řešení problému na počítači “ objeví se.

Za posledních jeden a půl až dvě desetiletí se počítač stal nedílnou součástí našeho života, počítačová slovní zásoba se stává stále známější. Slovo „algoritmus“ zná v dnešní době snad každý. Sebevědomě to přešlo i do hovorové řeči a dnes se často setkáváme v novinách a slyšíme v projevech politiků výrazy jako „algoritmus chování“, „algoritmus úspěchu“ nebo dokonce „algoritmus zrady“. Akademik N. N. Moiseev nazval svou knihu „Algoritmy vývoje“ a slavný lékař N. M. Amosov ji nazval  „Algoritmus zdraví“ a „Algoritmy mysli“. A to znamená, že slovo žije, obohacuje se o nové významy a sémantické odstíny.

Definice algoritmů

Vlastnosti algoritmů

Různé definice algoritmu, explicitně nebo implicitně, obsahují následující soubor obecných požadavků:

Formální definice

Různé teoretické problémy matematiky a urychlení rozvoje fyziky a techniky kladou na pořad dne přesnou definici pojmu algoritmus.

První pokusy o objasnění pojmu algoritmus a jeho výzkum provedli v první polovině 20. století Alan Turing , Emil Post , Jacques Herbrand , Kurt Gödel , A. A. Markov , Alonzo Church . Bylo vyvinuto několik definic pojmu algoritmus, ale následně bylo zjištěno, že všechny definují stejný pojem (viz Church-Turingova teze ) [6].

Ruský matematik, zakladatel strukturální lingvistiky v Sovětském svazu V. A. Uspenskij věřil, že koncept algoritmu se poprvé objevil u Emila Borela v roce 1912 v článku o určitém integrálu. Tam psal o „výpočtech, které lze skutečně provést“, přičemž zdůrazňoval: „Záměrně ponechávám stranou víceméně praktickou činnost; podstatou zde je, že každá z těchto operací je proveditelná v konečném čase pomocí spolehlivé a jednoznačné metody“ [7] .

Turingův stroj

Základní myšlenka Turingova stroje je velmi jednoduchá. Turingův stroj je abstraktní stroj (automat), který pracuje s páskou jednotlivých buněk, do kterých jsou zapsány znaky. Stroj má také hlavu pro psaní a čtení znaků z buněk, která se může pohybovat po pásce. V každém kroku stroj přečte znak z buňky, na kterou ukazuje hlava, a na základě přečteného znaku a vnitřního stavu provede další krok. V tomto případě může stroj změnit svůj stav, zapsat do buňky další znak nebo posunout hlavu o jednu buňku doprava nebo doleva. [osm]

Na základě studia těchto strojů byla předložena Turingova teze (hlavní hypotéza algoritmů):

Nějaký algoritmus pro nalezení hodnot funkce dané v nějaké abecedě existuje tehdy a jen tehdy, když je funkce Turingově hodnotitelná, to znamená, když ji lze vypočítat na Turingově stroji.

Tato teze je axiom, postulát a nelze ji dokázat matematickými metodami, protože algoritmus není přesný matematický koncept.

Rekurzivní funkce

Každý algoritmus může být spojen s funkcí, kterou vypočítává. Vyvstává však otázka, zda je možné Turingův stroj přiřadit k libovolné funkci, a pokud ne, pro jaké funkce existuje algoritmus? Výzkum těchto otázek vedl ve 30. letech 20. století k vytvoření teorie rekurzivních funkcí [9] .

Třída vypočitatelných funkcí byla napsána v obrázku připomínajícím konstrukci nějaké axiomatické teorie založené na systému axiomů. Nejprve byly zvoleny nejjednodušší funkce, jejichž výpočet je zřejmý. Poté byla formulována pravidla (operátory) pro konstrukci nových funkcí na základě existujících. Potřebná třída funkcí se skládá ze všech funkcí, které lze získat nejjednodušší aplikací operátorů.

Podobně jako Turingova teze v teorii vyčíslitelných funkcí byla předložena domněnka, která se nazývá Churchova teze :

Numerická funkce je algoritmicky vyhodnotitelná právě tehdy, když je částečně rekurzivní.

Důkaz, že třída vypočitatelných funkcí se shoduje s Turingovými vyčíslitelnými funkcemi, probíhá ve dvou krocích: nejprve je dokázán výpočet nejjednodušších funkcí na Turingově stroji a poté výpočet funkcí získaných jako výsledek aplikace operátorů.

Algoritmus tedy lze neformálně definovat jako jasný systém instrukcí definujících diskrétní deterministický proces, který vede od počátečních dat (na vstupu) k požadovanému výsledku (na výstupu), pokud existuje, v konečném počtu kroky; pokud požadovaný výsledek neexistuje, algoritmus buď nikdy neskončí, nebo se dostane do slepé uličky.

Normální algoritmus (algoritmus) Markov

Normální algoritmus (algoritmus v autorském psaní) Markova je systém postupných aplikací substitucí, které implementují určité postupy pro získávání nových slov ze základních, sestavených ze znaků určité abecedy. Stejně jako Turingův stroj, normální algoritmy neprovádějí výpočty samy: provádějí pouze transformace slov nahrazením písmen podle daných pravidel [10] .

Normálně vyčíslitelná funkce je funkce, kterou lze implementovat normálním algoritmem. Tedy algoritmus, který převede každé slovo ze sady platných dat funkce na jeho počáteční hodnoty [11] ..

Tvůrce teorie normálních algoritmů A. A. Markov předložil hypotézu, která se nazývala Markovův normalizační princip:

Chcete-li najít hodnoty funkce dané v nějaké abecedě, pokud a pouze v případě, že existuje nějaký algoritmus, když je funkce normálně vyčíslitelná.

Stejně jako Turingovy a Churchovy teze ani Markovův normalizační princip nelze dokázat matematickými prostředky.

Stochastické algoritmy

Výše uvedená formální definice algoritmu však může být v některých případech příliš přísná. Někdy je potřeba použít náhodné proměnné [12] . Algoritmus, jehož činnost je určována nejen počátečními daty, ale také hodnotami získanými z generátoru náhodných čísel, se nazývá stochastický (nebo randomizovaný, z anglického  randomized algorithm ) [13] . Stochastické algoritmy jsou často efektivnější než deterministické a v některých případech jsou jediným způsobem, jak vyřešit problém [12] .

V praxi se místo generátoru náhodných čísel používá generátor pseudonáhodných čísel .

Je však třeba rozlišovat mezi stochastickými algoritmy a metodami, které poskytují správný výsledek s vysokou pravděpodobností. Na rozdíl od metody dává algoritmus správné výsledky i po dlouhém běhu.

Někteří výzkumníci připouštějí možnost, že stochastický algoritmus poskytne nesprávný výsledek s určitou předem stanovenou pravděpodobností. Potom lze stochastické algoritmy rozdělit na dva typy [14] :

Další formalizace

U některých úkolů mohou výše uvedené formalizace ztížit hledání řešení a provádění výzkumu. K překonání překážek byly vyvinuty obě modifikace „klasických“ schémat a byly vytvořeny nové modely algoritmu. Zejména lze jmenovat:

Typy algoritmů

Typy algoritmů jako logické a matematické prostředky odrážejí naznačené složky lidské činnosti a trendy i samotné algoritmy v závislosti na cíli, výchozích podmínkách problému a způsobech jeho řešení. Je třeba zdůraznit zásadní rozdíl mezi algoritmy výpočtového charakteru, které převádějí některá vstupní data na výstupní data (jejich formalizací probíhají výše zmíněné Turingovy, Post, PAM stroje, normální Markovovy algoritmy a rekurzivní funkce) a interaktivními algoritmy (Turing již má C-machine, z angličtiny  choice  - volba, která čeká na vnější vliv, na rozdíl od klasického A-machine, kde jsou všechna počáteční data uvedena před začátkem výpočtu a výstupní data nejsou k dispozici do konce r. výpočet). Ty jsou určeny k interakci s nějakým řídicím objektem a jsou navrženy tak, aby zajistily správné vydávání řídicích akcí v závislosti na aktuální situaci, odrážené signály přicházejícími z řídicího objektu [15] [16] . Řídící algoritmus v některých případech vůbec nepočítá s dokončením práce (např. udržuje nekonečný cyklus čekání na události, na které je vydána příslušná reakce), přestože je zcela správný.

Algoritmy lze také rozlišit:

  • Mechanické algoritmy nebo jinak deterministické , rigidní (například algoritmus pro provoz stroje, motoru atd.) - nastavují určité akce a označují je v jediné a spolehlivé sekvenci, čímž poskytují jednoznačný požadovaný nebo požadovaný výsledek, pokud tyto podmínky procesu jsou splněny úkoly, pro které je algoritmus vyvinut.
  • Flexibilní algoritmy , jako jsou stochastické, tj. pravděpodobnostní a heuristické.
  • Pravděpodobnostní (stochastický) algoritmus poskytuje program pro řešení problému několika způsoby nebo způsoby, které vedou k pravděpodobnému dosažení výsledku.
  • Heuristický algoritmus (z řeckého slova „ heureka “) – algoritmus, který využívá různé rozumné úvahy bez striktního odůvodnění [17] .
  • Lineární algoritmus  je soubor příkazů (instrukcí), které se provádějí postupně v čase jeden po druhém.
  • Algoritmus větvení  je algoritmus, který obsahuje alespoň jednu podmínku, v jejímž důsledku lze provést rozdělení algoritmu do několika alternativních větví.
  • Cyklický algoritmus  je algoritmus, který zahrnuje opakované opakování stejné akce (stejné operace). Většina výpočtových metod a výčtu možností je redukována na cyklické algoritmy. Programový cyklus je posloupnost příkazů (série, tělo cyklu), které lze provést vícekrát.
  • Pomocný ( podřízený ) algoritmus ( procedura ) je algoritmus dříve vyvinutý a zcela používaný při algoritmizaci konkrétního problému. V některých případech, pokud existují identické sekvence instrukcí (příkazů) pro různá data, rozlišuje se také pomocný algoritmus pro zkrácení záznamu. Ve všech fázích přípravy na algoritmizaci problému je široce používána strukturní reprezentace algoritmu.
  • Strukturální blokový diagram , grafový diagram algoritmu  - grafické znázornění algoritmu ve formě diagramu bloků propojených šipkami (přechodovými čarami) - grafickými symboly, z nichž každý odpovídá jednomu kroku algoritmu. Uvnitř bloku je uveden popis odpovídající akce. Grafické znázornění algoritmu je široce používáno před programováním úlohy kvůli své přehlednosti, protože vizuální vjem obvykle usnadňuje proces psaní programu, jeho opravy v případě možných chyb a pochopení procesu zpracování informací. Můžete se dokonce setkat s takovým tvrzením: „Algoritmus je navenek schéma - sada obdélníků a dalších symbolů, uvnitř kterých se píše, co se počítá, co se zadává do stroje a co se vydává k tisku a další způsob zobrazování informací."

Číslování algoritmů

Při jejich studiu a analýze hraje důležitou roli číslování algoritmů [18] . Protože jakýkoli algoritmus může být specifikován jako konečné slovo (reprezentované jako konečná posloupnost symbolů nějaké abecedy) a množina všech konečných slov v konečné abecedě je spočetná , pak je spočetná také množina všech algoritmů. To znamená existenci mapování jedna ku jedné mezi množinou přirozených čísel a množinou algoritmů, tedy možnost přiřadit každému algoritmu číslo.

Číslování algoritmů je zároveň číslováním všech algoritmicky počítaných funkcí a každá funkce může mít nekonečný počet čísel.

Existence číslování umožňuje pracovat s algoritmy stejně jako s čísly. Číslování je užitečné zejména při studiu algoritmů, které pracují s jinými algoritmy.

Algoritmicky neřešitelné problémy

Formalizace konceptu algoritmu umožnila prozkoumat existenci problémů, pro které neexistují žádné algoritmy pro hledání řešení. Následně byla prokázána nemožnost algoritmického výpočtu řešení řady problémů, což znemožňuje jejich řešení na libovolném výpočetním zařízení. Funkce se nazývá vyčíslitelná , pokud existuje Turingův stroj , který vypočítá hodnotu pro všechny prvky množiny definic funkcí. Pokud takový stroj neexistuje, říká se, že funkce je nevypočitatelná. Funkce bude považována za nevyčíslitelnou, i když existují Turingovy stroje schopné vypočítat hodnotu pro podmnožinu celé sady vstupů [19] .  

Případ, kdy je výsledkem vyhodnocení funkce logický výraz „pravda“ nebo „nepravda“ (nebo množina {0, 1}), se nazývá problém, který může být řešitelný nebo neřešitelný v závislosti na vyčíslitelnosti funkce. [19] .

Je důležité přesně specifikovat povolenou sadu vstupních dat, protože problém může být pro jednu sadu řešitelný a pro jinou neřešitelný.

Jedním z prvních problémů, u kterých byla prokázána neřešitelnost, je problém zastavení . Je formulován následovně:

Daný popis programu pro Turingův stroj, to je vyžadováno určit zda program skončí v konečném čase nebo běží neurčitě daný nějaký vstup. [dvacet]

Důkaz neřešitelnosti problému zastavení je důležitý, protože na něj lze redukovat další problémy. Například jednoduchý problém zastavení lze redukovat na problém zastavení na prázdném řádku (když potřebujete pro daný Turingův stroj určit, zda se zastaví, když je spuštěn na prázdném řádku), čímž se prokáže nerozhodnutelnost tohoto stroje. [19] .

Analýza algoritmů

Spolu s rozšířením informačních technologií se zvýšilo riziko selhání softwaru. Jednou z cest, jak se vyhnout chybám v algoritmech a jejich implementacích, je dokázat správnost systémů matematickými prostředky.

Použití matematického aparátu pro analýzu algoritmů a jejich implementací se nazývá formální metody. Formální metody zahrnují použití formálních specifikací a obvykle sady nástrojů pro analýzu a dokazování vlastností specifikací. Abstrakce od implementačních detailů umožňuje nastavit vlastnosti systému nezávisle na jeho implementaci. Přesnost a jedinečnost matematických tvrzení navíc umožňuje vyhnout se nejednoznačnosti a nepřesnosti přirozených jazyků [21] .

Podle hypotézy Richarda Macea je „vyhýbání se chybám lepší než eliminace chyb“ [22] . Podle Hoareho dohadu „důkaz programů řeší problém správnosti, dokumentace a kompatibility“ [23] . Průkaz správnosti programů nám umožňuje odhalit jejich vlastnosti ve vztahu k celému rozsahu vstupních dat. Za tímto účelem byl koncept správnosti rozdělen do dvou typů:

  • Částečně správně  - program dává správný výsledek pro ty případy, kdy se ukončí.
  • Úplná správnost  - program se ukončí a vytvoří správný výsledek pro všechny prvky z rozsahu vstupních dat.

Při ověřování správnosti je text programu porovnáván se specifikací požadovaného poměru vstupních a výstupních dat. U důkazů typu Hoare má specifikace formu příkazů, které se nazývají předběžné a postpodmínky. Spolu se samotným programem se jim také říká Hoare triple . Tato prohlášení jsou psána jako

{P}O{S}

kde P  jsou předběžné podmínky, které musí být splněny před spuštěním programu Q , a S jsou dodatečné podmínky, které jsou pravdivé po ukončení programu.

Formální metody byly úspěšně aplikovány na širokou škálu problémů, zejména: vývoj elektronických obvodů, umělá inteligence, automatické systémy na železnici, verifikace mikroprocesorů , specifikace norem a specifikace a verifikace programů [24] .

Otevírací doba

Společným kritériem pro vyhodnocování algoritmů je doba běhu a pořadí, ve kterém doba běhu roste v závislosti na množství vstupních dat. [25]

Pro každý konkrétní úkol tvoří určité číslo, které se nazývá jeho velikost. Například velikost úlohy výpočtu součinu matic může být největší velikostí maticových faktorů, u úloh na grafech může být velikostí počet hran grafu.

Čas, který algoritmus stráví jako funkce velikosti úlohy, se nazývá časová složitost tohoto algoritmu T ( n ). Asymptotika chování této funkce s rostoucí velikostí problému se nazývá asymptotická časová složitost a pro její označení se používá označení „O“ velké . Pokud například algoritmus zpracovává vstupní data v čase cn² , kde c  je nějaká konstanta , pak se o časové složitosti takového algoritmu říká, že je O ( n² ).

Asymptotická složitost je důležitá, protože je charakteristickým znakem algoritmu, nikoli jeho konkrétní implementace: „optimalizací“ operací lze beze změny algoritmu změnit pouze multiplikativní koeficient c , ale ne asymptotiku. Zpravidla je to asymptotická složitost, která je hlavním faktorem, který určuje velikost úloh, které je algoritmus schopen zpracovat.

Často se při vývoji algoritmu snaží snížit asymptotickou časovou složitost pro nejhorší případy. V praxi existují případy, kdy stačí algoritmus, který „obvykle“ běží rychle.

Zhruba řečeno, analýzu průměrné asymptotické časové složitosti lze rozdělit na dva typy: analytickou a statistickou. Analytická metoda poskytuje přesnější výsledky, ale v praxi je obtížně použitelná. Statistická metoda však umožňuje rychle analyzovat složité problémy [26] .

V následující tabulce jsou uvedeny běžné asymptotické složitosti s komentáři [27] .

Složitost Komentář Příklady
O (1) Udržitelná doba provozu nezávisí na velikosti úlohy Očekávaná doba vyhledávání v hašovací tabulce
O ( přihlášení ) Velmi pomalý růst požadovaného času Očekávaná doba trvání interpolačního hledání n prvků
O ( přihlášení ) Logaritmický růst – Zdvojnásobení velikosti úlohy zvyšuje dobu běhu o konstantní hodnotu Výpočet x n ; Binární vyhledávání v poli n prvků
O ( n ) Lineární růst – zdvojnásobení velikosti úkolu zdvojnásobí potřebný čas Sčítání/odčítání čísel od n číslic; Lineární vyhledávání v poli n prvků
O ( n log n ) Lineární růst – Zdvojnásobení velikosti úlohy o něco více než zdvojnásobí požadovaný čas Řadit podle sloučení nebo shluku n prvků; seřadit dolní mez podle odpovídajících n prvků
O ( n² ) Kvadratický růst – Zdvojnásobení velikosti úkolu zčtyřnásobí potřebný čas Elementární třídicí algoritmy
O ( n³ ) Krychlový růst – Zdvojnásobení velikosti úkolu prodlouží požadovaný čas osmkrát Obyčejné maticové násobení
O ( c n ) Exponenciální růst - zvýšení velikosti úlohy o 1 vede k c -násobnému nárůstu v požadovaném čase; zdvojnásobení čtverců velikosti úkolu požadovaný čas Některé problémy s cestujícím prodejcem , vyhledávací algoritmy hrubou silou

Přítomnost počátečních dat a některých výsledků

Algoritmus je přesně definovaná instrukce, její postupnou aplikací na počáteční data můžete získat řešení problému. Pro každý algoritmus existuje určitá množina objektů, které lze použít jako vstupní data. Například v algoritmu pro dělení reálných čísel může být dividenda jakákoliv a dělitel nemůže být roven nule.

Algoritmus slouží zpravidla k řešení ne jednoho konkrétního problému, ale určité třídy problémů. Algoritmus sčítání je tedy použitelný pro jakoukoli dvojici přirozených čísel. To vyjadřuje jeho hmotnostní vlastnost, tedy schopnost opakovaně aplikovat stejný algoritmus pro jakýkoli úkol stejné třídy.

Pro vývoj algoritmů a programů se používá algoritmizace  - proces systematického sestavování algoritmů pro řešení aplikovaných problémů. Algoritmizace je považována za povinnou fázi v procesu vývoje programů a řešení problémů na počítači. Právě pro aplikované algoritmy a programy jsou zásadně důležité determinismus, efektivita a masový charakter a také správnost výsledků řešení zadaných úloh.

Algoritmus je jasný a přesný pokyn pro umělce, aby provedl sekvenci akcí zaměřených na dosažení cíle.

Reprezentace algoritmů

Formy zápisu algoritmu:

Algoritmus je obvykle nejprve (na úrovni nápadu) popsán slovy, ale jak se blíží k implementaci, dostává stále více formálních obrysů a formulací v jazyce srozumitelném pro interpreta (například strojový kód ).

Efektivita algoritmů

Přestože definice algoritmu vyžaduje pouze konečný počet kroků potřebných k dosažení výsledku, v praxi vede realizace velkého množství kroků k dlouhodobému provádění programů a obvykle existují další omezení (velikost programu, na povolené akce). V tomto ohledu jsou představeny takové pojmy, jako je složitost algoritmu ( čas , velikost programu, výpočetní a další).

Pro každý úkol může existovat mnoho algoritmů, které vedou k cíli. Zvyšování efektivity algoritmů je jedním z problémů informatiky , od 40. let 20. století byla v souvislosti s tím vybudována řada asymptoticky výkonnějších algoritmů pro tradiční problémy (např. algoritmy rychlého násobení , Chudnovského algoritmus pro výpočet čísla ).

Příklad

Euklidův algoritmus  je efektivní metoda pro výpočet největšího společného dělitele (gcd). Pojmenován po řeckém matematikovi Euklidovi; jeden z nejstarších stále používaných algoritmů [28] .

Popsáno v "Počátcích" Euklida (asi 300 př.nl), jmenovitě v knihách VII a X. V sedmé knize je popsán algoritmus pro celá čísla a v desáté - pro délky segmentů.

Existuje několik variant algoritmu, níže je rekurzivní verze napsaná v pseudokódu :

funkce node(a, b) pokud b = 0 vrátí a jinak vrátí node(b, a mod b)

GCD čísel 1599 a 650:

Krok 1 1599 = 650*2 + 299
Krok 2 650 = 299*2 + 52
Krok 3 299 = 52*5 + 39
Krok 4 52 = 39*1 + 13
Krok 5 39 = 13*3 + 0

Viz také

Poznámky

  1. ↑ ALGORITHM Semenov A. L. . Velká ruská encyklopedie. Elektronická verze (2016). Získáno 29. října 2018. Archivováno z originálu 30. října 2018.
  2. ↑ Kleene 1943 v Davisu 1965: 274
  3. ↑ Rosser 1939 v Davisu 1965: 225
  4. ↑ Knuth, 2006 , 1.1. Algoritmy.
  5. ↑ Robert Andrew Wilson, Frank C. Keil. The MIT Encyclopedia of the Cognitive Sciences . - MIT Press, 2001. - S. 11. - 1106 s. — ISBN 9780262731447 . Archivováno 17. listopadu 2021 na Wayback Machine
  6. ↑ (Igošin, str. 317)
  7. ↑ V. A. Uspenskij: „Matematika je humanitní věda“  // Trinity Variant. - 2014. - 28. ledna ( č. 2 (146) ). - str. 4-6 . Archivováno z originálu 27. listopadu 2018.
  8. ↑ Základy: Turingův stroj (s tlumočníkem!) . Dobrá matematika, špatná matematika (9. února 2007). Archivováno z originálu 2. února 2012.
  9. ↑ (Igoshin, část 33)
  10. ↑ Encyklopedie kybernetiky , díl 2 , str. 90-91.
  11. ↑ (Igoshin, část 34)
  12. ↑ 1 2 "Pravděpodobnostní algoritmy by se neměly zaměňovat s metodami (které odmítám nazývat algoritmy), které dávají výsledek, který má vysokou pravděpodobnost, že bude správný. Je nezbytné, aby algoritmus produkoval správné výsledky (s vyloučením lidských nebo počítačových chyb), i když k tomu dojde po velmi dlouhé době.“ Henri Cohen. Kurz výpočetní algebraické teorie čísel  . - Springer-Verlag , 1996. - S.  2 . — ISBN 3-540-55640-0 .
  13. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives't, Clifford Stein. Úvod do  algoritmů . - 2. - MIT Press , 2001. - S. 531. - ISBN 0-262-03293-7 .
  14. ↑ (Oddíl 12, str. 12–22 v Atallah, 2010)
  15. ↑ Dina Goldin, Peter Wegner. The origins of the Turing Thesis Myth , CS-04-14, říjen 2004
  16. ↑ Interaktivní výpočet je výkonnější než neinteraktivní Archivováno 19. listopadu 2015 na Wayback Machine , c2.com
  17. ↑ M. Gary, D. Johnson, Výpočetní stroje a obtížné problémy, M.: Mir, 1982, C. 155.
  18. ↑ (Igoshin, část 36)
  19. ↑ 1 2 3 Peter Linz. Úvod do formálních jazyků a automatů  . — Jones and Bartlett Publishers, 2000. - ISBN 0-7637-1422-4 .
  20. ↑ vyčíslitelnost a složitost, Encyklopedie počítačové vědy a technologie , Facts On File, 2009, ISBN 978-0-8160-6382-6 . 
  21. ↑ (O'Regan, část 4.5)
  22. ↑ (část 5.3.6 v Enders, 2003)
  23. ↑ (část 5.3.7 v Enders, 2003)
  24. ↑ (O'Regan, str. 119)
  25. ↑ A. Aho , J. Hopcroft , J. Ullman . Konstrukce a analýza výpočetních algoritmů = The Design and Analysis of Computer Algorithms . - M .: "Mir", 1979.
  26. ↑ (část 11 v Atallah, 2010)
  27. ↑ (část 1 v Atallah, 2010)
  28. ↑ Knuth D. The Art of Computer Programming , Volume 2 : Seminumerical Algorithms  . — 3. — Addison–Wesley , 1997. — ISBN 0201896842 .

Literatura

  • Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmy: Konstrukce a analýza = Úvod do algoritmů, třetí vydání. - 3. - M. : "Williams" , 2013. - 1328 s. - ISBN 978-5-8459-1794-2 .
  • Donald Knuth . The Art of Computer Programming = The Art of Computer Programming, sv. 1. Základní algoritmy. - 3. vyd. - M. : "Williams" , 2006. - V. 1. Základní algoritmy. - S. 720. - ISBN 0-201-89683-4 .
  • Thomas H. Cormen. Algoritmy: Úvodní kurz = Algoritmy odemčeny. - M. : "Williams" , 2014. - 208 s. — ISBN 978-5-8459-1868-0 .
  • Igoshin VI Matematická logika a teorie algoritmů. - 2. vyd., vymazáno .. - M . : Informační centrum "Akademie", 2008. - 448 s. — ISBN 5-7695-1363-2 .

Odkazy

  • " Slovo "algoritmus": původ a vývoj ", V. V. Shilov, Potenciální časopis  - zdroj historických informací.
  • O algoritmu  (nepřístupný odkaz od 22-05-2013 [3452 dní] - historie ,  kopie ) v encyklopedii "Round the World"
  Přejděte na položku Wikidata  Slovníky a encyklopedie