From Wikipedia, the free encyclopedia
Teorija računanja je grana računarstva koja razmatra mogu li se i s kojom učinkovitošću riješiti problemi koristeći računalo. Polje je podijeljeno u dvije glavne grane: teoriju izračunljivosti i teoriju složenosti, s tim da obje grane barataju formalnim modelima računanja.
Kako bi rigorozno proučavali računanje, računalni znanstvenici barataju matematičkim apstrakcijama računala zvanim modeli računanja. Nekoliko je formulacija u uporabi, ali najčešće ispitivani je Turingov stroj. Turingov se stroj može shvatiti kao osobno računalo opremljeno memorijom beskonačnog kapaciteta, iako može memoriji pristupati u malim diskretnim dijelovima. Računalni znanstvenici proučavaju Turingov stroj jer ga je jednostavno formulirati, jer može biti analiziran i korišten u dokazivanju rezultata, i jer predstavlja ono što mnogi smatraju najmoćnijim mogućim "razumnim" modelom računanja. Iako se zahtjev za memorijom beskonačnog kapaciteta može shvatiti kao nefizikalan, za svaki stvarno riješen problem Turingovim strojem korištena memorija će uvijek biti konačna, pa svaki problem koji riješi Turingov stroj može riješiti i osobno računalo s dovoljno ugrađene memorije.
Teorija izračunljivosti se primarno bavi pitanjem je li problem uopće rješiv na računalu. Problem zaustavljanja je jedan od najvažnijih rezultata u teoriji izračunljivosti, jer predstavlja primjer konkretnog problema kojeg je i lako formulirati i nemoguće riješiti koristeći Turingov stroj. Veći je dio teorije izračunljivosti izgrađen oko rezultata problema zaustavljanja.
Teorija je izračunljivosti usko vezana s granom matematičke logike zvanom teorija rekurzije, koja otklanja ograničenje proučavanja samo modela računanja koji su bliski onim fizikalno ostvarivima. Mnogi matematičari i računski teoretičari koji proučavaju teoriju rekurzije će je naslovljavati kao teoriju izračunljivosti. Ne postoji stvarna razlika između dvaju polja osim u tome ima li sam istraživač koji se bavi poljem ured u odsjeku za računarstvo ili matematiku.
Teorija složenosti razmatra ne samo može li se problem uopće riješiti na računalu, već i koliko učinkovito može biti riješen. Dva glavna aspekta su promatrana: vremenska složenost i prostorna složenost, koji respektivno predstavljaju broj koraka potreban da se računanje obavi, te količinu memorije potrebnu za obavljanje računanja.
Kako bi analizirali koliko vremena i prostora dani algoritam zahtijeva, računalni znanstvenici izražavaju vrijeme i prostor zahtijevan za rješavanje problema kao funkciju ulaznog problema. Na primjer, pronalaženje nekog pojedinog broja u dugoj listi brojeva postaje sve teže kako ta lista raste. Ako kažemo da postoji brojeva u listi, tada, ako lista nije predsortirana ili na neki način indeksirana, moramo ispitati svaki broj kako bismo pronašli broj koji tražimo. Stoga kažemo da, kako bi riješio ovaj problem, računalo mora obaviti broj koraka koji raste linearno u veličini problema.
Kako bi pojednostavili ovaj problem, računalni su znanstvenici prihvatili veliko O notaciju, koja dozvoljava usporedbu funkcija na način koji osigurava da pojedinačni aspekti konstrukcije stroja ne moraju biti razmatrani, već samo asimptotsko ponašanje kako problemi postaju sve veći. Stoga se u prethodnom primjeru može reći da problem zahtjeva koraka za rješavanje.
Možda najvažniji od svih otvorenih problema u računarstvu jest pitanje mogu li određene široke klase problema označene kao NP biti učinkovito riješene. O ovome se više raspravlja u članku klase složenosti P i NP.
Osim Turingovog stroja, drugi istovjetni (vidi: Church-Turingova teza) modeli računanja su u uporabi.
Kao dodatak općenitim računskim modelima, neki jednostavniji računski modeli su korisni za posebne, ograničene primjene. Regularni izrazi, na primjer, se koriste za specificiranje uzoraka stringa u mnogim kontekstima, od programske podrške za uredsku produktivnost pa do programskih jezika. Drugi formalizam matematički istovjetan regularnim izrazima, konačni automati, se koristi u dizajnu elektroničkih krugova i pri rješavanju nekih problema. Kontekstno neovisne gramatike se rabe prilikom specifikacije sintakse programskih jezika. Nedeterministički potisni automati su drugi formalizam istovjetan kontekstno neovisnim gramatikama. Primitivno rekurzivne funkcije su potklasa rekurzivnih funkcija.
Različiti modeli računanja imaju sposobnost obavljanja različitih zadataka. Jedan način mjerenja moći računskog modela jest proučavanje klase formalnih jezika koje model može generirati - ovo vodi ka Chomskyjevoj hijerarhiji jezika.
Seamless Wikipedia browsing. On steroids.