Algoritms, sistemātiska procedūra, kas - ar ierobežotu soļu skaitu - rada atbildi uz jautājumu vai problēmas risinājumu. Nosaukums cēlies no 9. gadsimta musulmaņu matemātiķa al-Khwarizmi aritmētiskā traktāta “Al-Khwarizmi par hindu aprēķināšanas mākslu” latīņu valodas tulkojuma Algoritmi de numero Indorum.
datorzinātne: algoritmi un sarežģītība
Algoritms ir īpaša procedūra precīzi definētas skaitļošanas problēmas risināšanai. Algoritmu izstrāde un analīze ir būtiska
Jautājumiem vai problēmām ar tikai ierobežotu gadījumu vai vērtību kopumu vienmēr pastāv algoritms (vismaz principā); tas sastāv no atbilžu vērtību tabulas. Parasti tā nav tik niecīga procedūra, lai atbildētu uz jautājumiem vai problēmām, kurās jāņem vērā bezgalīgs gadījumu skaits vai vērtības, piemēram, “Vai naturālais skaitlis (1, 2, 3 …) ir galvenais?” vai “Kāds ir lielākais dabisko skaitļu a un b dalītājs?” Pirmais no šiem jautājumiem pieder klasei, kuru sauc par pieņemamu; algoritmu, kas rada “jā” vai “nē” atbildi, sauc par lēmumu pieņemšanas procedūru. Otrais jautājums pieder klasei, ko sauc par aprēķināmu; algoritmu, kas noved pie noteiktas skaitļa atbildes, sauc par aprēķināšanas procedūru.
Daudzām šādām bezgalīgām jautājumu klasēm pastāv algoritmi; Eiklida Elementi, kas publicēti aptuveni 300 BC, saturēja vienu, lai atrastu lielāko dabisko skaitļu kopējo dalītāju. Katrs pamatskolas skolēns tiek trenēts garā dalījumā, kas ir algoritms jautājumam “Sadalot naturālo skaitli a ar citu naturālo skaitli b, kādi ir koeficienti un atlikušie?” Šīs aprēķināšanas procedūras izmantošana dod atbildi uz izlemjamo jautājumu “Vai b dalās a?” (atbilde ir "jā", ja atlikums ir nulle). Šo algoritmu atkārtota piemērošana galu galā dod atbildi uz izlemjamo jautājumu “Vai galvenā loma?” (atbilde ir nē, ja a ir dalāms ar mazāku dabisko skaitli, izņemot 1).
Dažreiz algoritms nevar pastāvēt bezgalīgas problēmu klases risināšanai, it īpaši, ja pieņemtajai metodei ir vēl daži ierobežojumi. Piemēram, divas Eiklida laika problēmas, kurās bija nepieciešams izmantot tikai kompasu un taisnstūri (bez marķējuma) - novirzīt leņķi un uzbūvēt kvadrātu ar laukumu, kas vienāds ar doto apli - tika risinātas gadsimtiem ilgi, pirms tās izrādījās neiespējamas.. 20. gadsimta mijā ietekmīgais vācu matemātiķis Deivids Hilberts ierosināja 23 problēmas matemātiķiem nākamajā gadsimtā atrisināt. Otra problēma viņa sarakstā lūdza izpētīt aritmētikas aksiomu konsekvenci. Lielākajai daļai matemātiķu bija maz šaubu par šī mērķa sasniegšanu līdz 1931. gadam, kad Austrijā dzimušais žurnālists Kurts Gēdels demonstrēja pārsteidzošo rezultātu, ka jābūt aritmētiskiem priekšlikumiem (vai jautājumiem), kurus nevar pierādīt vai atspēkot. Būtībā katrs šāds piedāvājums noved pie noteikšanas procedūras, kas nekad nebeidzas (stāvoklis, ko sauc par apturēšanas problēmu). Neveiksmīgi cenšoties noskaidrot vismaz to, kuri apgalvojumi nav atrisināmi, angļu matemātiķis un loģiķis Alans Tjūrings stingri definēja algoritma brīvi saprotamo jēdzienu. Lai gan Tērings galu galā pierādīja, ka ir jābūt nenoliedzamiem piedāvājumiem, viņa aprakstīts jebkuras vispārējas nozīmes algoritma aparāta jeb Tjūringa aparāta būtiskās iezīmes kļuva par datorzinātnes pamatu. Mūsdienās datorprogrammas, kas ir īpaša veida algoritms, projektēšanā galvenā nozīme ir izlemjamībai un aprēķinamībai.
