Algoritmus, systematický postup, ktorý v konečnom počte krokov vytvára odpoveď na otázku alebo riešenie problému. Názov je odvodený z latinského prekladu Algoritmi de numero Indorum z aritmetického pojednávania aritmetiky moslimského matematika al-Khwarizmi z 9. storočia „Al-Khwarizmi o hindskom umení v Reckoningu“.
počítačová veda: Algoritmy a zložitosť
Algoritmus je špecifický postup riešenia dobre definovaného výpočtového problému. Vývoj a analýza algoritmov je zásadná
V prípade otázok alebo problémov s obmedzeným súborom prípadov alebo hodnôt vždy existuje algoritmus (aspoň v zásade); pozostáva z tabuľky hodnôt odpovedí. Vo všeobecnosti to nie je také triviálne konanie, ktoré by zodpovedalo na otázky alebo problémy, ktoré majú nekonečný počet prípadov alebo hodnôt, napríklad „Je prirodzené číslo (1, 2, 3, …) prvoradé?“ alebo „Aký je najväčší spoločný deliteľ prírodných čísel aab?“ Prvá z týchto otázok patrí do triedy nazývanej rozhodné; algoritmus, ktorý vytvára odpoveď áno alebo nie, sa nazýva rozhodovací postup. Druhá otázka patrí do triedy s názvom compible; algoritmus, ktorý vedie k odpovedi na konkrétne číslo, sa nazýva výpočtový postup.
Algoritmy existujú pre mnoho takýchto nekonečných tried otázok; Euclidove prvky, publikované asi 300 bc, obsahovali jeden na nájdenie najväčšieho spoločného deliteľa dvoch prirodzených čísel. Každý žiak základnej školy je cvičený v dlhom členení, čo je algoritmus pre otázku „Po rozdelení prirodzeného čísla a iným prirodzeným číslom b, aký je kvocient a zvyšok?“ Použitie tohto výpočtového postupu vedie k odpovedi na rozhodujúcu otázku „Rozdeľuje sa b a?“. (odpoveď je áno, ak je zvyšok nula). Opakované použitie týchto algoritmov nakoniec poskytne odpoveď na rozhodujúcu otázku „Je to prvotriedne?“ (odpoveď znie nie, ak a je deliteľné akýmkoľvek menším prirodzeným číslom okrem 1).
Niekedy nemôže existovať algoritmus na riešenie nekonečnej triedy problémov, najmä keď sa na akceptovanú metódu urobia nejaké ďalšie obmedzenia. Napríklad dva problémy z Euklidovho času, ktoré vyžadovali použitie iba kompasu a priamky (neoznačeného pravítka) - zisťovanie uhla a vytvorenie štvorca s plochou rovnajúcou sa danému kruhu - sa sledovali celé storočia predtým, ako sa ukázalo, že sú nemožné., Na prelome 20. a 20. storočia navrhol vplyvný nemecký matematik David Hilbert pre matematikov v nasledujúcom storočí 23 problémov. Druhý problém na jeho zozname si vyžadoval preskúmanie dôslednosti axiómov aritmetiky. Väčšina matematikov nepochybovala o dosiahnutí tohto cieľa až do roku 1931, keď rakúsky logik Kurt Gödel preukázal prekvapivý výsledok, že musia existovať aritmetické tvrdenia (alebo otázky), ktoré nemožno dokázať alebo vyvrátiť. Takýto návrh v podstate vedie k rozhodovaciemu postupu, ktorý sa nikdy nekončí (stav známy ako problém zastavenia). Anglický matematik a logik Alan Turing sa v neúspešnom úsilí zistiť, ktoré výroky sú neriešiteľné, presne definoval voľne chápaný pojem algoritmu. Aj keď Turing nakoniec dokázal, že musia existovať nerozhodnuteľné výroky, jeho opis podstatných vlastností akéhokoľvek stroja na všeobecné použitie algoritmov alebo Turingovho stroja sa stal základom počítačovej vedy. Dnes sú otázky rozhodnuteľnosti a vypočítateľnosti ústredným bodom pri návrhu počítačového programu - špeciálneho typu algoritmu.
