Umiestnenie: Výučba* | CL Homepage | KAI | FMFI UKBratislave


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

O kurze

Tu nájdete informačný list predmetu.

Cieľ predmetu

Úvod do teórie rekurzívnych funkcií a teórie vypočítateľnosti. Ukážeme, že rekurzívne funkcie sú matematickým základom pre teóriu deklaratívnych programovacích jazykov. Teoretické témy prednášok sú prakticky precvičené za počítačom.

Stručná osnova predmetu

Induktívne definované triedy funkcií. Explicitne a rekurzívne definície funkcií a predikátov. Primitívne rekurzívne funkcie. Rekurzívne funkcie a ich efektívny výpočet. Kleeneho vety o normálnej forme a o rekurzii. μ-rekurzívne funkcie. Turingove stroje. Ekvivalentnosť Turingových strojov a rekurzívnosti. Turing-Churchova téza a vypočitateľné funkcie.

Rozhodnuteľné a nerozhodnuteľné problémy. Polorozhodnuteľné problémy. Aritmetická hierarchia. Nerozhodnuteľné problémy v iných oblastiach matematiky. Nerozhodnutelnosť predikátového počtu. Goedelova veta o neúplnosti.

Literatúra

Výučba


* – aktualizované v priebehu posledných 7 dní Posledná zmena: 2008-09-17T17:47+0200