Teorija računanja: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
+iw |
gotov prijevod sa en wiki |
||
Redak 1:
'''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: [[teorija izračunljivosti (računarstvo)|teoriju izračunljivosti]] i [[računska teorija složenosti|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 [[model računanja|modeli računanja]]. Nekoliko je formulacija u uporabi, ali najčešće
== Teorija izračunljivosti ==
{{main|Teorija izračunljivosti (računarstvo)}}
[[Teorija izračunljivosti (računarstvo)|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 sa granom [[matematička logika|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 [[matematika|matematiku]].
== Teorija složenosti ==
{{main|Računska teorija složenosti}}
[[Računska teorija složenosti|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 <math>n</math> brojeva u listi, tada, ukoliko 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 [[Velika O notacija|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 zahtijeva <math>O(n)</math> 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 (složenost)|NP]] biti učinkovito riješene. O ovome se više raspravlja u članku [[klase složenosti P i NP]].
== Druge formalne definicije računanja ==
Osim [[Turingov stroj|Turingovog stroja]], drugi istovjetni (vidi: [[Church-Turingova teza]]) modeli računanja su u uporabi.
;[[lambda račun]]: Računanje je početni lambda izraz (ili dva ako se želi odvojiti funkcija od njenog ulaza) plus konačni slijed lambda termina, od kojih je svaki deduciran iz prethodnog aplikacijom [[beta redukcija|beta redukcije]].
;[[kombinatorna logika]]
:je koncept koji ima mnogo sličnosti sa <math>\lambda</math>-računom, ali postoje i važne razlike (npr. kombinator fiksne točke '''Y''' u kombinatornoj logici ima normalnu formu, ali ne i u <math>\lambda</math>-računu). Kombinatorna je logika razvijena sa velikim ambicijama: razumijevanje prirode paradoksa, činjenja osnovna matematike ekonomičnijima (konceptualno), te eliminiranje notacije varijabli (te tako osvjetljavajući njihovu ulogu u matematici).
;[[μ-rekurzivna funkcija|μ-rekurzivne funkcije]]: računanje je μ-rekurzivna funkcija, tj. njen definirajući slijed, bilo koja ulazna vrijednost/vrijednosti te slijed rekurzivnih funkcija koje se pojavljuju u definirajućem slijedu sa ulazima i izlazima. Stoga, ako se u definirajućem slijedu rekurzivne funkcije <math>f(x)</math> pojavljuju <math>g(x)</math> i <math>h(x,y)</math>, tada se mogu pojaviti termini oblika 'g(5)=7' ili 'h(3,2)=10'. Svaki unos u ovom slijedu treba biti aplikacija osnovne funkcije ili slijediti iz gornjih unosa koristeći [[kompozicija funkcija (računarstvo)|kompoziciju funkcija]], [[primitivna rekurzija|primitivnu rekurziju]] ili [[μ-rekurzivna funkcija|μ-rekurziju]]. Na primjer, ako je <math>f(x)=h(x,g(x))</math>, tada da bi se pojavio 'f(5)=3', gore se moraju pojaviti termini poput 'g(5)=6' i 'h(3,6)=3'. Računanje terminira samo ako konačni termin daje vrijednost rekurzivne funkcije primjenjene na ulaze.
;[[Markovljev algoritam]]: [[prepisivanje stringa|sustav za prepisivanje stringa]] koji koristi pravila slična [[gramatika|gramatičkim]] kako bi djelovao nad [[string (računarstvo)|stringovima]] simbola.
;[[Registarski stroj]]
:je teoretski zanimljiva idealizacija računala. Postoji više varijanti. U većini od njih, svaki registar može sadržavati prirodni broj (neograničene veličine), dok su same instrukcije jednostavne (obično tek nekolicina njih), pa npr. postoje samo dekrementiranje (kombinirano sa uvjetnim skokom) i inkrementiranje (i zaustavljanje). Nedostatak beskonačne (ili dinamički rastuće) vanjske memorije (poput one u Turingovim strojevima) se može shvatiti kao zamjena njene uloge tehnikama [[Gödelovo obrojčavanje|Gödelovog obrojčavanja]]: činjenica da svaki registar sadrži prirodni broj dopušta mogućnost predstavljanja složenih konstrukata (npr. niza, matrice itd.) odgovarajuće velikim prirodnim brojem - nejednoznačnost i predstavljanja i interpretiranja može biti uspostavljena na osnovama ovih tehnika zasnovanih na [[teorija brojeva|teoriji brojeva]].
;[[P′′]]
:Poput Turingovih strojeva, [[P′′]] koristi beskonačnu traku simbola (bez slučajnog pristupa) i poprilično minimalistički skup instrukcija. Ali ove su instrukcije vrlo različite, te stoga, za razliku od Turingovih strojeva, P′′ me treba održavati različito stanje, jer svu funkcionalnost "sličnu memoriji" može pružiti samo traka. Umjesto prepisivanja trenutnog simbola, može obaviti inkrementiranje [[modularna aritmetika|modularnom aritmetikom]] nad njim. P′′ također posjeduje par instrukcija za ciklus, ispitujući simbol praznine. Unatoč svojoj minimalističkoj prirodi, postao je roditeljski formalni jezik ostvarenog i (za zabavu) korištenog programskog jezika zvanog [[Brainfuck]].
Kao dodatak općenitim računskim modelima, neki jednostavniji računski modeli su korisni za posebne, ograničene primjene. [[Regularni izraz]]i, na primjer, se koriste za specificiranje uzoraka stringa u mnogim kontekstima, od programske podrške za uredsku produktivnost pa do [[programski jezik|programskih jezika]]. Drugi formalizam matematički istovjetan regularnim izrazima, [[konačni automat|konačni automati]], se koristi u dizajnu elektroničkih krugova i pri rješavanju nekih problema. [[Kontekstno neovisna gramatika|Kontekstno neovisne gramatike]] se rabe prilikom specifikacije sintakse programskih jezika. Nedeterministički [[potisni automat|potisni automati]] su drugi formalizam istovjetan kontekstno neovisnim gramatikama. [[Primitivno rekurzivna funkcija|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 [[formalni jezik|formalnih jezika]] koje model može generirati - ovo vodi ka[[Chomskyjeva hijerarhija|Chomskyjevoj hijerarhiji]] jezika.
== Daljnje čitanje ==
* {{cite book
| author = [[Michael Sipser]]
| year = 2006
| title = Introduction to the Theory of Computation 2ed
| publisher = PWS Publishing
| id = ISBN 0-534-94728-X
}} Drugi dio: ''Computability Theory'', poglavlja 3–6, str. 123–222.
* {{cite book
| author = [[Eitan Gurari]]
| year = 1989
| title = An Introduction to the Theory of Computation
| publisher = Computer Science Press
| id = ISBN 0-7167-8182-4
}} Besplatna je verzija također dostupna na: http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html
* Hein, James L: ''Theory of Computation.'' Sudbury, MA: Jones & Bartlett, 1996. ISBN 978-0867204971 Nježni uvod u polje, prikladno za studente računarstva druge godine.
* Hopcroft, John E., and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation. 3rd ed'' Reading, MA: Addison-Wesley, 2006. ISBN 978-0321455369 Jedna od standardnih referenci u polju.
* Taylor, R. Gregory: ''Models of Computation.'' New York: Oxford University Press, 1998. Neobično čitljiv udžbenik, prikladan za studente viših godina ili postdiplomske studente.
*[[Hartley Rogers, Jr]], ''Theory of Recursive Functions and Effective Computability'', MIT Press, 1987, ISBN 0-262-68052-1
*[http://www.cis.upenn.edu/~giorgi/cl.html Logika izračunljivost]: Teorija interaktivnog računanja. Glavi izvor na webu o ovoj temi.
*[http://www.cs.uky.edu/~lewis/texts/theory/title.pdf] Dobar udžbenik u PDF formatu Forbesa D. Lewisa, koji pokriva teme formalnih jezika, automata i gramatika. Naglasak je više na predstavljanju pregleda rezultata i njihovim primjenama, radije nego na pružanju dokaza.
[[Kategorija: Teorija računanja]]
| |||