|
Opterećenje:
|
1. komponenta
| Vrsta nastave | Ukupno |
| Predavanja |
45 |
* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)
|
|
Opis predmeta:
|
CILJ KOLEGIJA:
Upoznati studente s osnovama teorije izračunljivosti, osposobiti ih za matematičko razmišljanje o algoritmima, razviti nekoliko sustava izračunavanja i motivirati Church-Turingovu tezu, dokazati najvažnije rezultate o neodlučivosti i poluodlučivosti (kao što je Churchov teorem o neodlučivosti logike prvog reda).
NASTAVNI SADRŽAJI:
Uvodimo brojevni model izračunavanja kroz imperativno programiranje u stilu Shoenfielda. Opisujemo tehniku spljoštenja (inlining) i implementaciju funkcijskog poziva. Promatramo LOOP-strojeve u stilu Schöninga.
Prikazujemo alternativni brojevni model kroz funkcijsko programiranje u stilu Kleeneja. Konstruiramo compiler parcijalno rekurzivnih funkcija u RAM-programe.
Opisujemo kodiranje kao tehniku za rad s nebrojevnim podacima. Konstruiramo interpreter RAM-programa u funkcijskom jeziku, dokazujući Kleenejev teorem o normalnoj formi parcijalno rekurzivne funkcije.
Uvodimo jezični model izračunavanja kroz Turingove strojeve u stilu Sipsera. Virtualiziramo Turingove strojeve unutar RAM-strojeva, dokazujući ekvivalentnost brojevne i jezične izračunljivosti. Opisujemo elemente tehnike parsiranja.
Uvodimo lambda-račun u stilu Barendregta, redukcije i ekspanzije. Ostvarujemo tehnike programiranja i prikaza podataka pomoću lambda-izraza. Opisujemo programske paradigme preko redoslijeda izračunavanja, iskazujemo Church-Rosserov teorem.
Generaliziramo dobivene rezultate o ekvivalentnosti modela izračunavanja kroz Church-Turingovu tezu, dokazujemo nepostojanje algoritama za razne slavne probleme kao što je Entscheidungsproblem. Skiciramo dokaz prvog Gödelovog teorema nepotpunosti.
Dokazujemo četiri velika teorema o metaprogramiranju: teorem o parametru, teorem rekurzije, teorem o fiksnoj točki te Riceov teorem.
Formaliziramo poluodlučivost u obliku rekurzivne prebrojivosti te je karakteriziramo pomoću projekcije odlučivih relacija, čekanja na zaustavljanje izračunavanja, grafova izračunljivih funkcija, ... kako u brojevnom tako i u jezičnom modelu.
|
|
Literatura:
|
-
Komputonomikon - izračunljivost za računarce, Čačić.
-
Izračunljivost - predavanja, Vuković.
-
Recursion Theory, Shoenfield.
-
Introduction to the Theory of Computation, Sipser.
-
Interpreter za lambda-račun, Lovnički.
-
LOOP-izračunljivost, Avirović.
-
Izračunljivost na skupovima Z, Q, R i C, Posavčević.
|
|
Preduvjeti za:
|
Upis predmeta
:
Odslušan
:
Matematička logika
Odslušan
:
Modeli izračunavanja
Polaganje predmeta
:
Položen
:
Matematička logika
Položen
:
Modeli izračunavanja
|
Pristupačnost
