2-INF-121 Teória vypočítateľnosti ZS 2008/09

Prednášky: štvrtok 15:40-17:10, m. M-IV
Cvičenia: štvrtok 17:20-18:50, m. F1-248
Konzultácie: utorok 18:10-19:40, m. F1-248
Učiteľ: Ján Komara, m. I16, tel. 60295 727

Novinky

12.12.2008 priebežne aktualizované. Termíny na skúšku.

... tu nájdete ostatné správy.

O kurze

Tu nájdete všeobecné informácie o kurze 2-INF-121 Teória vypočítateľnosti.

Literatúra

J. Komara and P. J. Voda. Lecture Notes in Theory of Computability. 2001. (PostScript) (Adobe Acrobat Document)
P. J. Voda. Theory of Recursive Functions & Computability. 2000. (PostScript)
I. Korec. Úvod do teórie algoritmov. Skriptá MFF UK, 1981
V. Švejdar. Logika: neúplnost, složitost a nutnost. Academia Praha, 2002. (Adobe Acrobat Document)

Prednášky

Tu nájdete študijné materiály k prednáškam. Sú priebežne dopĺňané.

Cvičenia

1. cvičenie (výsledky)

zobraz modul Ex01a - začíname s CL
zobraz modul Ex01b - induktívne definované triedy funkcií

2. cvičenie (výsledky)

zobraz modul Ex02a - primitívne (p.r.) rekurzívne funkcie
zobraz modul Ex02b - ohraničená minimalizácia, p.r. predikáty
zobraz modul Ex02c - Cantorova párovacia funkcia a aritmetizácia

3. cvičenie (výsledky)

zobraz modul Ex03a - Catalanova párovacia funkcia
zobraz modul Ex03b - 'course of values recursion'
zobraz modul Ex03c - klauzálny jazyk

4. cvičenie (výsledky)

zobraz modul Ex04a - Ackermann-Péterovej funkcia
zobraz modul Ex04b - univerzálna funkcia pre primitívne rekurzívne funkcie

5. cvičenie (výsledky)

zobraz modul Ex05 - μ-rekurzívne funkcie: vyjadrenie primitívnej rekurzie pomocou regulárnej minimalizácie

6. cvičenie (výsledky)

zobraz modul Mtm - Turingove stroje: formalizácia
zobraz modul Ex06a - Turingove stroje: príklady, 1. časť
zobraz modul Ex06b - Turingove stroje: príklady, 2. časť
zobraz modul Ex06c - Turingove stroje: príklady, 3. časť

7. cvičenie (výsledky)

zobraz modul Ex07 - aritmetizácia Turingových strojov, Kleeneho veta o normálnej forme

8. cvičenie (výsledky)

zobraz modul Ex08 - efektívne operácie na indexoch

9. cvičenie (výsledky)

zobraz modul Ex09 - rozhodnuteľné a nerozhodnuteľné problémy

10. cvičenie je test
11. cvičenie (výsledky)

zobraz modul Ex11 - polorozhodnuteľné problémy a čiastočne vypočítateľné predikáty

12. cvičenie je prednáška

Testy

test zo 4.12.2008 (zadanie) (riešenia) (výsledky)

Prémiové úlohy

Skúška

Tu nájdete súbor obsahujúci termíny na skúšku. Je priebežne aktualizovaný.

Hodnotenie

Tu sa nachádza súhrn vašich výsledkov (celkové hodnotenie).

Spôsob hodnotenia a ukončenia štúdia predmetu je 40/60. Toto je len základný rámec, spresnenie na 1. prednáške.

Erráta

Tu nájdete erráta ku kurzu. Sú priebežne dopĺňané.

Staršie správy

5.12.2008 Test zo 4.12 je opravený.

20.11.2008 Test bude vo štvrtok 4.12.

17.10.2008 Prvú časť 4. cvičenia (modul Ex04a) a prémiovú úlohu v druhej časti (pozri modul Ex04b) stačí odovzdať o týždeň neskôr.

15.10.2007 Pridaný súbor obsahujúci vaše celkové hodnotenie .

10.10.2008 Konzultácie sú v utorok o 18:10-19:40, m. F1-248.

3.10.2008 Záverečnú časť 2. cvičenia, t.j. modul Ex02c, stačí odovzdať o týždeň neskôr.

* – aktualizované v priebehu posledných 7 dní

Posledná zmena: 2008-12-28T10:12+0100