Algoritmo matematika

Algoritmas, sisteminė procedūra, kurios metu atsakymas į klausimą arba problemos sprendimas pateikiamas per tam tikrą skaičių žingsnių. Pavadinimas kilo iš 9 amžiaus musulmonų matematiko al-Khwarizmi aritmetinio traktato „Al-Khwarizmi dėl induizmo skaičiavimo meno“ lotyniškojo vertimo „Algoritmi de numero Indorum“.

informatika: algoritmai ir sudėtingumas

Algoritmas yra specifinė tiksliai apibrėžtos skaičiavimo problemos sprendimo procedūra. Esminis dalykas yra algoritmų kūrimas ir analizė

Jei turite klausimų ar problemų, susijusių tik su baigtiniu atvejų ar verčių rinkiniu, visada egzistuoja algoritmas (bent jau iš esmės); jį sudaro atsakymų reikšmių lentelė. Apskritai, tai nėra tokia nereikšminga procedūra, kaip atsakyti į klausimus ar problemas, kurių atvejais reikia įvertinti begalę atvejų ar verčių, pavyzdžiui, „Ar natūralusis skaičius (1, 2, 3 …) yra svarbiausias?“ arba „koks yra didžiausias natūraliųjų skaičių a ir b daliklis?“ Pirmasis iš šių klausimų priklauso klasei, vadinamai lemiama; algoritmas, pateikiantis „taip“ arba „ne“ atsakymą, vadinamas sprendimo procedūra. Antrasis klausimas priklauso klasei, kuri vadinama apskaičiuojamąja; algoritmas, kuris veda prie konkretaus skaičiaus atsakymo, vadinamas skaičiavimo procedūra.

Daugeliui tokių begalinių klausimų klasių yra algoritmai; Euklido elementuose, paskelbtuose apie 300 bc, buvo vienas, kad būtų galima rasti didžiausią bendrą dviejų natūraliųjų skaičių daliklį. Kiekvienas pradinių klasių moksleivis yra gręžiamas į ilgą padalijimą, o tai yra algoritmas klausimui „Padalijus natūralųjį skaičių a iš kito natūraliojo skaičiaus b, kokie yra koeficientas ir likusi dalis?“ Taikant šią skaičiavimo procedūrą, bus atsakyta į lemiamą klausimą „Ar b dalija a?“ (atsakymas yra „taip“, jei likusi dalis lygi nuliui). Pakartotinis šių algoritmų taikymas duoda atsakymą į lemiamą klausimą „Ar svarbiausias?“ (atsakymas ne, jei a dalijama iš bet kurio mažesnio natūraliojo skaičiaus, be 1).

Kartais algoritmas negali egzistuoti begalinei klasės klasei išspręsti, ypač kai priimtinam metodui daromi tam tikri apribojimai. Pavyzdžiui, dvi nuo Euklido laikų kilusias problemas, kai reikėjo naudoti tik kompasą ir tiesiaeigį (nepažymėtą liniuotę) - iškirpti kampą ir sukonstruoti kvadratą, kurio plotas lygus tam tikram apskritimui, - buvo imtasi šimtmečių, kol jie pasirodė neįmanomi.. XX amžiaus sandūroje įtakingas vokiečių matematikas Davidas Hilbertas pasiūlė 23 problemas, kurias ateinančiame amžiuje turėtų išspręsti matematikai. Antroji jo sąrašo problema paprašė ištirti aritmetikos aksiomų nuoseklumą. Daugelis matematikų mažai abejojo ​​dėl šio tikslo pasiekimo iki 1931 m., Kai austrų kilmės logikas Kurtas Gödelis pademonstravo stebinantį rezultatą, kad turi egzistuoti aritmetiniai teiginiai (arba klausimai), kurių negalima įrodyti ar paneigti. Iš esmės kiekvienas toks teiginys lemia nustatymo procedūrą, kuri niekada nesibaigia (būklė vadinama sustabdymo problema). Nesėkmingai stengdamasis išsiaiškinti, kurie teiginiai yra neišsprendžiami, anglų matematikas ir logikas Alanas Turingas griežtai apibrėžė laisvai suprantamą algoritmo sąvoką. Nors Turingas įrodė, kad turi egzistuoti nenuginčijami teiginiai, jo aprašymas apie bet kurios bendrosios paskirties algoritmo mašinos arba Tiuringo mašinos esmines savybes tapo informatikos pagrindu. Šiandien priimtinumo ir palyginamumo klausimai yra svarbiausi rengiant kompiuterio programą - specialų algoritmo tipą.