Izračunljivost

Bodovi iz zadaće

objavio 10. sij 2018. 15:10 Vedran Čačić

... su objavljeni.

Test

objavio 5. sij 2018. 06:49 Vedran Čačić   [ ažurirano 11. sij 2018. 22:49 ]

... će biti 18. siječnja u 10:15 sati. Piše se 60 minuta. Prije i poslije imamo normalno nastavu. Bit će 4 zadatka:

1. Kodiranje formula i veza problema logičke posljedice s RAM-izračunavanjem (2 boda)
2. Primjena teorema rekurzije (2 boda)
3. Primjena Riceovog teorema (3 boda)
4. Rekurzivno prebrojivi skupovi, veza s grafovima i slikama (3 boda)

O predaji zadaće

objavio 3. sij 2018. 05:00 Vedran Čačić

Bit ću na fakultetu u petak u 12h (uobičajeni termin konzultacija), ako želite predati zadaću u papirnatom obliku, ili imate kakvih pitanja. Za digitalnu predaju deadline ostaje sutra u 23:59.

Dvije greške koje sam uočio u dosad predanim zadaćama:

* ako se želite pozvati na činjenicu da funkcija zadovoljava totalne jednakosti (=) za dokaz da je totalna, onda trebate _dokazati_ da ih doista zadovoljava. Teorem rekurzije vam to ne daje, samo daje parcijalne jednakosti. Drugim riječima, trebate još provući neku indukciju da biste vidjeli da su sve vrijednosti definirane, i/ili da su sve totalne jednakosti zadovoljene (što dođe na isto). Pogledajte Z5.1.5, odlomak koji počinje s "Četvrto,". (Razlog zašto dosta vas radi tu grešku je vjerojatno što ste gledali rješenje Z5.1.1, ali u tom zadatku eksplicitno piše da se smije bez dokaza pretpostaviti da je definicija dobra, odnosno da su jednakosti totalne. U većini drugih zadataka to ne piše.)

* ako primjenjujete neki od "izvedenih operatora" (sumiranje, ograničenu minimizaciju, povijest,...) na funkcije koje ste namjestili za zadatak, pripazite da se doista radi o brojevnim funkcijama: dakle funkcijama čija domena je podskup od nekog N^k, a slika podskup od N. Recimo, funkcija sqrt sigurno ne pripada među takve, pa ne možete primijeniti minimizaciju na neki izraz koji uključuje sqrt i zaključiti da ste dobili parcijalno rekurzivnu funkciju. I ne, zapis pow(x,0.5) ne pomaže :-] (jer biste onda za eksplicitni zapis trebali imati konstantu C_{0.5}^1, koja naravno nije brojevna funkcija jer joj slika {0.5} nije podskup od N). Pogledajte Z5.1.3, funkcija fld _jest_ brojevna funkcija (iako log2 to nije), i dalje se radi s njom.

Nove verzije

objavio 20. pro 2017. 02:14 Vedran Čačić   [ ažurirano 4. sij 2018. 10:24 ]

... zbirke i slideova su u prilogu.

Domaća zadaća: (2 boda) riješite bar dva (neriješena u zbirci) zadatka iz zbirke (prvenstveno poglavlja 5 i 6, možete i 7). [a), b)... podzadatci smatraju se zasebnim zadatcima.] Za tehnike, pogledajte riješene zadatke. Ako mislite da se neki od zadataka iz poglavlja 5 i 6 ne može riješiti prikazanim tehnikama, pošaljite mail. Za bonus bodove možete i smišljati zadatke za zbirku, te tražiti greške u zbirci ili slajdovima. :-)

Slajdovi u prilogu su finalizirani za ovu akademsku godinu. Cijenio bih (iako za to neću davati bodove:) da mi napišete koji slajd ili skupinu slajdova ste smatrali posebno nerazumljivima - tako ćete pomoći narednoj generaciji.

Rok za predaju zadaće je 4. siječnja 2018. Test pišemo 11. ili 18. siječnja (možete glasovati za termin prilikom predaje zadaće:). Predaja može biti mailom ili papirnato (4. ili 5. siječnja sam sigurno na fakultetu.)

Zbirka

objavio 14. pro 2017. 03:10 Vedran Čačić   [ ažurirano 15. pro 2017. 05:24 ]

(vrlo rani draft) i nova verzija slajdova nalaze se u prilogu.

P.S. Samo ću napomenuti da mi je jako drago da smo napokon počeli komunicirati u oba smjera. :-) Nadam se da će uroditi nečim korisnim.

Rezultati prvog kolokvija

objavio 3. pro 2017. 09:22 Vedran Čačić

... su objavljeni. Kao što sam već rekao, uvidi su sutra u 11h.

Pojašnjenje "overflow" bodova: "minimalističko rješenje" iz prošlog posta dobilo je bonus 1 bod na 5. zadatku. Na 6. zadatku dobili su bonus svi kojima RAM-program (pored ostalih vrijednosti) ispravno računa Lh3(0)=0 - poslije sam shvatio da usprkos primjeru, "duljina ternarnog zapisa" sama po sebi nije najjasnija, pa nisam htio skidati bod rješenjima koja računaju Lh3(0)=1, ali sam ipak htio nagraditi ona koja korektno računaju Lh3 po definiciji iz slajdova.

Rješenja kolokvija i obavijest o rezultatima

objavio 1. pro 2017. 09:43 Vedran Čačić   [ ažurirano 1. pro 2017. 21:44 ]

Službena rješenja kolokvija nalaze se u prilogu.

Kolokviji bi trebali biti ispravljeni do nedjelje navečer, a uvidi u ponedjeljak u 11h.

Također je u prilogu nova verzija slajdova.

P.S. Na ovom linku nalazi se jedno nekonvencionalno i minimalističko rješenje 5. zadatka.

Prvi kolokvij

objavio 19. stu 2017. 15:13 Vedran Čačić   [ ažurirano 20. stu 2017. 07:22 ]

... piše se 29. studenoga 2017. u 12 sati.

Naslovna stranica kolokvija je u prilogu. Možda ju je dobro proučiti ranije. :-)

Objavljen je i raspored za kolokvij. Ako niste na popisu, javite se što prije!

Slika Turingovog stroja za \upsilon(I_2^4)

objavio 16. stu 2017. 01:04 Vedran Čačić

Na kolokviju će biti jednostavniji zadatak. :-)

LOOP-izračunljivost

objavio 14. stu 2017. 08:31 Vedran Čačić   [ ažurirano 15. stu 2017. 02:33 ]

Mislim da imam programski jezik koji će se svidjeti studentima koji više vole imperativni pristup: vrti se na registrima RAM-stroja, a računa točno primitivno rekurzivne funkcije. Detalji u prilogu.

In other news... nekoliko URLova za Turingov stroj:
(primjer koji smo obradili na nastavi) raspolavljanje riječi
Kompajlirajte, zadajte neki primjer i promatrajte kako radi.

1-10 of 39