Teorija računanja
Sa Wikipedije, slobodne enciklopedije
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 kompleksnosti, 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.
[uredi] Teorija računjivosti
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.
[uredi] Teorija kompleksnosti
Teorija kompleksnosti 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: kompleksnost vremena i kompleksnost 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.
