Algoritmus je konstrukční a výrobní pravidla a techniky, které jsou zapojeny do vymezení a návrhu algoritmů , to znamená, systematický proces řešení problému přesně popsat kroky vyřešit algoritmické problémy .
Slovo „algoritmus“ pochází z názvu matematik Al-Khwarizmi (Latinized do středověku v Algoritmi ), který v té IX th století napsal první systematickou práci poskytující řešení lineárních rovnic a kvadratické . Tiché h, které není odůvodněno etymologií, pochází z deformace ve srovnání s řeckým ἀριθμός (arithmós). „Algoritmus“ dal „algoritmický“. Synonymum „algoritmus“, staré slovo, které použil například Wronski v roce 1811, se stále někdy používá.
První algoritmy, které byly nalezeny popisy sahají do Babyloňané , do III th tisíciletí před naším letopočtem. AD . Na příkladech popisují metody výpočtu a řešení rovnic .
Slavný algoritmus je nalezen v jedné knize 7 z Prvky Euclid , a zavolal Euclidův algoritmus . Najde největšího společného dělitele neboli GCD dvou čísel. Obzvláště pozoruhodný bod je, že výslovně obsahuje iteraci a že propozice 1 a 2 prokazují její správnost .
Byl to Archimedes, kdo jako první navrhl algoritmus pro výpočet π .
Prvním, kdo systematizoval algoritmy, je perský matematik Al-Khwârizmî , aktivní mezi 813 a 833. Ve své práci Abrégé du computation pomocí restaurování a srovnání studuje všechny kvadratické rovnice a dává jejich rozlišení pomocí generálů algoritmů. Používá podobné metody jako Babyloňané , ale liší se systematickým vysvětlením, kde Babylóňané uvedli pouze příklady.
Andaluský učenec Averroès ( 1126 - 1198 ) evokuje metodu uvažování, kde je práce iteračně zdokonalována krok za krokem, dokud nedojde k určité konvergenci a to v souladu s pokrokem algoritmu. Ve stejné době, v XII -tého století , mnich Adelard Bath představil termín latina pro Algorismus , pod názvem Al Khwarizmi. Toto slovo dává algoritmus ve francouzštině v roce 1554 .
V XVII th století , některé narážka mohl spatřit algoritmický způsob k René Descartes v obecném přístupu navržené Pojednání o metodě ( 1637 ), zejména tehdy, když v jeho druhé části, francouzský matematik navrhuje „rozdělit každý obtíže, které bych zkoumat, v co největším počtu částí a podle potřeby, aby je bylo možné lépe vyřešit. „ Bez výslovného vyvolání iterace nebo dichotomie pojmů smyčky je Descartův přístup předurčen k logice pojmu pojmu program , slovo se rodí ve francouzštině v roce 1677 .
V roce 1843 provedla matematička a průkopnice výpočetní techniky Ada Lovelace , dcera lorda Byrona a asistenta Charlese Babbage , první implementaci algoritmu ve formě programu (výpočet Bernoulliho čísel ).
Desátý Hilbert problémem , který je součástí seznamu 23 problémů , které představuje David Hilbert v roce 1900 v Paříži je jednoznačně algoritmické problém. V tomto případě odpověď zní, že neexistuje žádný algoritmus reagující na daný problém.
Algoritmická XX th a XXI tého století na matematickém základě formalismu, například to Turing stroje , které umožňují přesně definovat, co se rozumí pod pojmem „kroků“ „specifický“ a „jednoznačné“, a které poskytují vědecký rámec pro studium vlastnosti algoritmů. Podle zvoleného formalismu však člověk získá různé algoritmické přístupy k řešení stejného problému. Například , rekurzivní algoritmizace, paralelní Algoritmika nebo kvantová výpočetní vzniknou na prezentaci algoritmů, které jsou odlišné od těch, iteračních algoritmizace.
Algoritmika vyvinula především v druhé polovině XX -tého století, jako koncepční podporu programování v oblasti rozvoje informačních technologií v tomto období. Donald Knuth , autor pojednání The Art of Computer Programming, které popisuje velké množství algoritmů, pomohl spolu s dalšími položit matematické základy jejich analýzy.
Podstatné jméno algoritmické označuje všechny metody použité k vytvoření algoritmů. Termín je také používán jako adjektivum.
Algoritmus uvádí řešením problému v podobě řetězce operací, které mají být provedeny .
Počítačoví vědci často používají implementační anglicismus k označení implementace algoritmu v programovacím jazyce . Tato implementace provádí přepis základních operací algoritmu a určuje způsob, jakým jsou tyto operace vyvolány. Toto psaní v počítačovém jazyce je také často označováno výrazem „ kódování “. Mluvíme o „ zdrojovém kódu “ k označení textu, který tvoří program a provádí algoritmus. Kód je více či méně podrobně v závislosti na úrovni abstrakce použitého jazyka, stejně jako vaření recept musí být více či méně podrobně na základě zkušeností z kuchaře.
Bylo vyvinuto mnoho formálních nebo teoretických nástrojů, které popisují algoritmy, studují je, vyjadřují jejich kvality a umí je porovnávat:
Konceptů implementovaných v algoritmu, například podle přístupu N. Wirtha pro nejrozšířenější jazyky (Pascal, C atd. ), Je málo. Patří do dvou tříd:
Toto rozdělení je někdy obtížné vnímat pro určité jazyky ( Lisp , Prolog …) více založené na pojmu rekurze, kde jsou určité řídicí struktury implicitní, a proto se zdá, že mizí.
Tyto tři pojmy „oprava“, „úplnost“, „ukončení“ spolu souvisejí a předpokládejme, že je k vyřešení problému napsán algoritmus.
Zakončení je jistota, že na koncích algoritmus v konečném čase. Důkazy ukončení obvykle zahrnují striktně klesající kladné celé číslo v každém „kroku“ algoritmu.
Vzhledem k záruce, že algoritmus dokončí, musí důkaz správnosti poskytnout záruku, že pokud algoritmus skončí poskytnutím výsledku, pak je tento výsledek skutečně řešením vzniklého problému. Důkazy o správnosti obvykle zahrnují logickou specifikaci, kterou je třeba ověřit řešením problému. Důkaz správnosti tedy spočívá v prokázání, že výsledky algoritmu splňují tuto specifikaci.
Důkaz úplnosti zaručuje, že pro daný problémový prostor poskytne algoritmus, pokud je dokončen, sadu řešení problémového prostoru. Důkazy úplnosti vyžadují identifikaci problémového prostoru a prostoru řešení, aby se ukázalo, že algoritmus skutečně produkuje druhý z prvního.
Hlavní matematické pojmy ve výpočtu nákladů přesného algoritmu jsou pojmy dominance (označenou O (f (n)) , „velký O“), kde f je matematická funkce z n , proměnná určuje množství informací (v bitech , počtu záznamů atd. ) použitých v algoritmu. V algoritmech často nacházíme složitosti typu:
Hodnocení | Typ složitosti |
---|---|
konstantní složitost (nezávislá na velikosti dat) | |
logaritmická složitost | |
lineární složitost | |
kvazilineární složitost | |
kvadratická složitost | |
kubická složitost | |
polynomiální složitost | |
kvazi-polynomiální složitost | |
exponenciální složitost | |
složitost faktorů |
Aniž bychom zacházeli do matematických detailů, výpočet účinnosti algoritmu (jeho algoritmické složitosti ) spočívá v nalezení dvou důležitých veličin. První kvantitou je vývoj počtu základních instrukcí podle množství zpracovávaných dat (například u třídicího algoritmu se jedná o počet dat, která mají být tříděna), který bude upřednostňován na měřeném čase provádění v sekundách (protože druhý závisí na stroji, na kterém je algoritmus spuštěn). Druhým odhadovaným množstvím je množství paměti potřebné k provedení výpočtů. Založení výpočtu složitosti algoritmu na čase nebo efektivní velikosti paměti, kterou konkrétní počítač potřebuje k provedení uvedeného algoritmu, nebere v úvahu vnitřní strukturu algoritmu ani zvláštnost algoritmu. Počítač: podle jeho pracovní vytížení, rychlost jeho procesoru, rychlost přístupu k datům, provedení algoritmu (který může zahrnovat i náhodu) nebo jeho organizace paměti, doba provedení a velikost paměti nebudou stejné.
Výkon se často zkoumá „v nejhorším případě“, to znamená, že v konfiguracích, jako je běh nebo paměť, je největší. Existuje také další aspekt hodnocení účinnosti algoritmu: „průměrný“ výkon. To předpokládá existenci modelu statistického rozdělení dat algoritmu, zatímco implementace analytických technik předpokládá poměrně jemné metody kombinatoriky a asymptotického vyhodnocení , využívající zejména generující řady a pokročilé metody komplexní analýzy . Všechny tyto metody jsou seskupeny pod názvem analytická kombinatorika .
Další hodnocení složitosti, která obecně přesahují výše navržené hodnoty a která třídí algoritmické problémy (spíše než algoritmy) do tříd složitosti, lze najít v článku o teorii složitosti algoritmů .
Některé údaje o účinnosti algoritmů a jejich zkresleníAlgoritmická účinnost je často známa pouze asymptoticky, to znamená pro velké hodnoty parametru n . Když je tento parametr dostatečně malý, může být v praxi efektivnější algoritmus s větší asymptotickou složitostí. Pro třídění pole 30 řádků (jedná se o malý parametr) je tedy zbytečné používat pokročilý algoritmus, jako je rychlé řazení (v průměru jeden z asymptoticky nejúčinnějších třídicích algoritmů): l Nejjednodušší algoritmus řazení, který se bude psát, bude být dostatečně efektivní.
Mezi dvěma počítačovými algoritmy stejné složitosti použijeme algoritmus s menším obsazením paměti. Analýzu algoritmické složitosti lze také použít k vyhodnocení obsazení paměti algoritmu. Nakonec je nutné zvolit spíše algoritmus než jiný podle údajů, od nichž se očekává, že budou poskytnuty jako vstup. To znamená, že quicksort , když zvolíme první prvek ve formě čepu, chová katastrofálně kdybychom to platí pro již seřazený seznam hodnot. Není proto rozumné jej používat, pokud se očekává, že program bude přijímat jako vstupní seznamy, které jsou již téměř seřazeny, nebo budete muset náhodně vybrat otočný čep.
Mezi další parametry, které je třeba vzít v úvahu, patří:
Algoritmus vyvinul několik strategií k řešení problémů:
Pro některé problémy jsou algoritmy příliš složité, než aby bylo možné získat výsledek v rozumném čase, i kdyby bylo možné použít fenomenální výpočetní výkon. Jsme proto vedeni k tomu, abychom hledali řešení nesystematickým způsobem ( algoritmus Las Vegas ) nebo abychom byli spokojeni s řešením co nejblíže optimálnímu řešení postupnými testy ( algoritmus Monte-Carlo ). Vzhledem k tomu, že nelze vyzkoušet všechny kombinace, je třeba provést některá strategická rozhodnutí. Tyto volby, obecně velmi závislé na řešeném problému, představují to, co se nazývá heuristika . Cílem heuristiky proto není zkoušet všechny možné kombinace, ale najít řešení v rozumném čase a jinými prostředky, například náhodným losováním. Řešení může být přesné (Las Vegas) nebo přibližné (Monte-Carlo). Tyto algoritmy Atlantic City , na druhou stranu, pravděpodobně účinně dát pravděpodobně správnou odpověď (řekněme s jedním ze sta milionů šance, že budou špatně) na otázku, zeptal se.
Takto šachové nebo go herní programy (abychom jmenovali alespoň některé) velmi často používají heuristiku, která modeluje zážitek hráče. Některý antivirový software také spoléhá na heuristiku při rozpoznávání počítačových virů, které nejsou uvedeny v jejich databázi, a spoléhá na podobnosti se známými viry, jedná se o příklad algoritmu Atlantic City. Podobně SAT problém, který je archetypem NP-úplného problému, a proto je velmi obtížný, je praktickým a efektivním způsobem vyřešen rozvojem heuristiky .
Existuje řada klasických algoritmů, které se používají k řešení problémů nebo snadněji k ilustraci programovacích metod. Další podrobnosti najdete v následujících článcích (viz také seznam algoritmů ):