Algoritem matematika

Algoritem, sistematičen postopek, ki v končnem številu korakov ustvari odgovor na vprašanje ali rešitev problema. Ime izhaja iz latinskega prevoda, Algoritmi de numero Indorum, iz aritmetičnega traktata o muslimanskem matematiku al-Khwarizmija iz 9. stoletja "Al-Khwarizmi o hindujski umetnosti priznavanja."

računalništvo: Algoritmi in kompleksnost

Algoritem je poseben postopek za reševanje natančno opredeljene računske težave. Razvoj in analiza algoritmov je temeljna

Za vprašanja ali težave z le končnim naborom primerov ali vrednosti algoritem vedno obstaja (vsaj načeloma); je sestavljena iz tabele vrednosti odgovorov. Na splošno ni tako nepomemben postopek odgovarjanja na vprašanja ali težave, ki bi jih bilo treba upoštevati v neskončnem številu primerov ali vrednosti, na primer "Ali je naravno število (1, 2, 3, …) glavno?" ali "Kateri je največji delitelj naravnih števil a in b?" Prvo od teh vprašanj spada v razred, imenovan decidable; algoritem, ki ustvari odgovor da ali ne, se imenuje postopek odločanja. Drugo vprašanje spada v razred, imenovan računsko; algoritem, ki vodi do odgovora na določeno številko, se imenuje postopek računanja.

Algoritmi obstajajo za številne take neskončne razrede vprašanj; Elementi Euclid's, objavljeni približno 300 bc, so vsebovali enega za iskanje največjega skupnega deljenika dveh naravnih števil. Vsak osnovnošolec se vrti v dolgi delitvi, kar je algoritem za vprašanje "Ko ločimo naravno število a z drugim naravnim številom b, kakšen je količnik in preostanek?" Uporaba tega računskega postopka vodi k odgovoru na odločljivo vprašanje "Ali b deli a?" (če je preostanek nič, je odgovor pritrdilen). Večkratna uporaba teh algoritmov sčasoma ustvari odgovor na odločljivo vprašanje "Je primeren?" (odgovor je ne, če je a delljivo s katerim koli manjšim naravnim številom poleg 1).

Včasih algoritem ne more obstajati za reševanje neskončnega razreda težav, še posebej, če je sprejeta metoda še nadaljnja omejitev. Na primer, dve težavi iz Euklidovega časa, ki sta zahtevali uporabo samo kompasa in ravnala (neoznačeni ravnilo) - preizkus kota in konstruiranje kvadrata s površino, ki je enako določenemu krogu - sta se lotili stoletja, preden se je pokazalo, da je nemogoče. Na prehodu v 20. stoletje je vplivni nemški matematik David Hilbert predlagal 23 problemov, ki naj bi jih matematiki rešili v prihodnjem stoletju. Drugi problem na njegovem seznamu je zahteval preiskavo skladnosti aritmetike aksiomov. Večina matematikov je malo dvomila o morebitnem doseganju tega cilja do leta 1931, ko je avstrijski logik Kurt Gödel pokazal presenetljiv rezultat, da morajo obstajati aritmetične trditve (ali vprašanja), ki jih ni mogoče dokazati ali ovrgniti. V bistvu vsak tak predlog vodi v postopek določanja, ki se nikoli ne konča (pogoj, znan kot problem zaustavitve). Angleški matematik in logik Alan Turing je v neuspešnem prizadevanju, da bi ugotovil vsaj, katere trditve so nerešljive, strogo opredelil ohlapno razumljen koncept algoritma. Čeprav je Turing na koncu dokazal, da morajo obstajati nesporne trditve, je njegov opis bistvenih značilnosti katerega koli splošnega algoritemskega stroja ali Turingovega stroja postal temelj računalništva. Danes so vprašanja odločljivosti in računanja ključnega pomena pri oblikovanju računalniškega programa - posebne vrste algoritma.