Algoritmus , systematický postup, ktorý v konečnom počte krokov poskytne odpoveď na otázku alebo riešenie problému. Názov je odvodený z latinského prekladu, Algoritmi počet Indov , moslimského matematika z 9. storočia al-Khwarizmi Aritmetika pojednanie Al-Khwarizmi týkajúce sa hinduistického zúčtovania.
Pre otázky alebo problémy s iba konečným súborom prípadov alebo hodnôt an algoritmus vždy existuje (aspoň v zásade); skladá sa z tabuľky s hodnotami odpovedí. Všeobecne to nie je taký banálny postup na zodpovedanie otázok alebo problémov, ktoré majú nekonečný počet prípadov alebo hodnôt, ktoré sa majú zohľadniť, napríklad Je prirodzené číslo (1, 2, 3, ...) do hlavný ? alebo Aký je najväčší spoločný deliteľ prirodzených čísel do a b ? Prvá z týchto otázok patrí do triedy s názvom decidable; algoritmus, ktorý vytvára odpoveď áno alebo nie, sa nazýva rozhodovací postup. Druhá otázka patrí do triedy s názvom computable; algoritmus, ktorý vedie k odpovedi na konkrétne číslo, sa nazýva postup výpočtu.
Algoritmy existuje veľa takýchto nekonečných tried otázok; Euklidov Prvky , publikované asi 300bce, obsahoval 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 delení, čo je algoritmus pre otázku Pri delení prirodzeného čísla do 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 b rozdeliť do ? (odpoveď je áno, ak je zvyšok nulový). Opakovaná aplikácia týchto algoritmov nakoniec prinesie odpoveď na rozhodujúcu otázku Is do hlavný? (odpoveď je nie, ak do je deliteľné akýmkoľvek menším prirodzeným číslom okrem 1).
Algoritmus niekedy nemôže existovať na riešenie nekonečnej triedy problémov, zvlášť keď sa pri prijatej metóde urobí ďalšie obmedzenie. Napríklad dva problémy z Euklidovej doby, ktoré vyžadovali použitie iba kompasu a pravítka (neoznačené pravítko) - pretínanie uhla a zostrojenie štvorca s plochou rovnou danému kruhu - sa sledovali po celé storočia, kým sa ukázalo, že je nemožné . Na prelome 20. storočia vplyvný nemecký matematik David Hilbert navrhol 23 úloh, ktoré majú matematici vyriešiť v nasledujúcom storočí. Druhý problém na jeho zozname si vyžiadal preskúmanie konzistencie axiómov aritmetiky. Väčšina matematikov nepochybovala o konečnom dosiahnutí tohto cieľa až do roku 1931, keď rakúsky logik Kurt Gödel preukázal prekvapivý výsledok, že musia existovať aritmetické návrhy (alebo otázky), ktoré nemožno dokázať ani vyvrátiť. Každý takýto návrh v podstate vedie k postupu určovania, ktorý nikdy nekončí (stav známy ako problém zastavenia). V neúspešnom úsilí zistiť prinajmenšom ktoré návrhy sú neriešiteľné, anglický matematik a logik Alan Turing dôsledne definoval voľne pochopený koncept algoritmu. Aj keď Turing nakoniec dokázal, že musia existovať nerozhodnuteľné návrhy, jeho popis základných vlastností každého univerzálneho algoritmického stroja alebo Turingovho stroja sa stal základom počítačová veda . V súčasnosti sú otázky rozhodovateľnosti a vypočítateľnosti ústrednou súčasťou návrhu počítačového programu - špeciálneho typu algoritmu.
Copyright © Všetky Práva Vyhradené | asayamind.com