Teorija računanja

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

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]

Glavna stranica: 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.

Teorija složenosti[uredi | uredi izvor]

Glavna stranica: Teorija složenosti

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.

Također pogledajte[uredi | uredi izvor]