Teorija računanja
 | Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
Teorija računanja je dio računarske nauke koja se bavi načinima na koji se efektivno mogu riješiti problemi koristeći računar. Polje je podijeljeno u dva glavna dijela: teorija računjivosti i teorija složenosti, ali oba dijela se bave formalnim modelima računanja.
Da bi napravili studiju računanja, kompjuterski znanstvenici rade sa matematičkom apstrakcijom kompjutera zvanom model računanja. Postoji nekoliko formulacija koje se koriste, ali ona koja je najviše prihvaćena i koja se najviše istražuje je Turingova mašina. Kompjuterski znanstvenici je istražuju jer je jednostavna za formulisanje i može biti analizirana i korištena da opravda rezultate.
Teorija računjivosti
[uredi | uredi izvor]Teorija računjivosti se primarno bavi pitanjem da li je neki problem moguće riješiti na kompjuteru. Halting problem je jedan od najvažnijih razultata u teoriji računjivosti i on je primjer konkretnog problema koji je i jednostavan za formulisati i nemoguće riješiti koristeći Turingovu mašinu.
Teorija računjivosti je blisko povezana sa dijelom matematičke logike zvanim rekurzivna tehnika, koja uklanja ograničenja promatranja samo modela računanja koji su bliski stvarnom svijetu.
Teorija složenosti
[uredi | uredi izvor]Teorija složenosti razmatra ne samo da li je neki problem moguće riješiti koristeći kompjuter, nego kako efektno se problem može riješiti. Dva glavna aspekta se razmatraju: složenost vremena i složenost prostora, odnosno, koliko koraka je potrebno izvršiti da bi se riješio problem i koliko memorije je potrebno da bi se izvelo to računanje.
