M-INBP-004 Teória vypočítateľnosti pre programátorov ZS 2006/07

Prednášky: štvrtok 16:30-18:00, m. I
Cvičenia: štvrtok 18:10-19:40, m. H6
Konzultácie: štvrtok 13:00-14:00, m. I15
Učiteľ: Ján Komara, m. I15, tel. 60295 727

Novinky

• 17.12.2006. Termíny na skúšku nájdete tu.

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

O kurze

Tu nájdete základné informácie: M-INBP-004 Teória vypočítateľnosti pre programátorov

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. MFF UK. Bratislava. 1983.

Cvičenia

• 1. cvičenie (výsledky)
• zobraz modul Ex01 - niektoré efektívne operácie
• 2. cvičenie (výsledky)
• zobraz modul Ex02a - primitívne rekurzívne odvodenia
• zobraz modul Ex02b - explicitné definície, primitívne rekurzívne definície, ohraničené kvantifikátory, ohraničená minimalizácia
• zobraz modul Ex02c - Cantorova párovacia funkcia
• 3. cvičenie (výsledky)
• zobraz modul Ex03a - 'course of values recursion'
• zobraz modul Ex03b - univerzálna funkcia pre p.r. funkcie (poznámky)
• 4. cvičenie (výsledky)
• zobraz modul Ex04 - efektívne operácie na p.r. indexoch
• 5. cvičenie (výsledky)
• zobraz modul Ex05 - aritmetizácia výpočtového modelu pre obecne rekurzívne funkcie
• 7. cvičenie (výsledky)
• zobraz modul Ex07 - Kleeneho veta o normálnej forme
• 8. cvičenie (výsledky)
• zobraz modul Ex08 - efektívne operácie na rekurzívnych indexoch
• 9. cvičenie (výsledky)
• zobraz modul Ex09 - μ-rekurzívne funkcie
• 11. cvičenie (výsledky)
• zobraz modul Ex11 - nerozhodnuteľné problémy
• 12. cvičenie (výsledky)
• zobraz modul Ex12 - polorozhodnuteľné problémy
• 13. cvičenie (výsledky)
• zobraz modul Ex13 - rozhodnuteľné a nerozhodnuteľné problémy

Testy

• test z 30.11.2006 (zadanie) (riešenia) (výsledky)

Skúška

Termíny na skúšku:

• utorok 9.1.2007
  • 13:00 - Mirko Zibolen
  • 15:00 - Marián Dudek
  • 17:00 - Michal Malý
• štvrtok 18.1.2007
  • 11:00 - Ján Kollárik
  • 15:00 - Róbert Durkaj
  • 17:00 - Tomáš Malovič
• štvrtok 25.1.2007
  • 13:00 - Roman Pauer
• štvrtok 1.2.2007
  • 09:00 - Roman Pauer
  • 11:00 - Ján Kollárik
  • 13:00 - Juraj Sloboda
  • 15:00 - Tomáš Sako
  • 17:00 - Tomáš Malovič
• štvrtok 8.2.2007 (1. opravný termín)
• 13:00 - Tomáš Sako
• 15:00 - Juraj Sloboda

Hodnotenie

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

Staršie správy

• 8.1.2007. Opravte si znenie prvej vety v 13. cvičení. Malo byť:

  For an infinite predicate R, the predicate is computable iff it is recursively enumerable in increasing order.

  Súbor 13. cvičenie túto zmenu už obsahuje.

• 18.12.2006. Dole nájdete 13. cvičenie. Treba ho odovzdať do štvrtka 11.1.2007. Konzultácie sú v utorok 9.1.2007 (poobede, počas skúšky).

• 11.12.2006. Test je opravený.

• 24.11.2006. V zadaní posledného cvičenia, ktoré sa nachádza v module Ex09, chýba táto veta:

  • Theorem. μ-recursive functions are closed under definitions of functions with regular minimalization of bounded formulas.

  Táto veta by sa mala nachádzať hneď za tvrdením:

  • Theorem. μ-recursive functions are closed under definitions of functions with bounded minimalization.

To znamená, že pri dôkaze toho, že sčítanie je μ-rekurzívne, môžete použiť regulárnu minimalizáciu ohraničenej formuly.

• 12.11.2006. Test bude vo štvrtok 30.11 na cvičení.

• 20.10.2006. Konzultácie: každý štvrtok o 13:00-14:00, m. I15

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

• 29.9.2006. Od dnešného dňa by mal fungovať prenos súborov do adresárov

  /data/vyuka/inf/cl/M-INBP-004-vyp/prenos/ex/ex<ord>/<user>/ Všimnite si, že tieto adresáre sa líšia od tých, ktoré boli uvedené na cvičeniach: /data/vyuka/inf/cl/M-INBP-004/prenos/ex/ex<ord>/<user>/