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

2-INF-264 Teória deklaratívneho programovania

Novinky

O kurze

Tu nájdete informačný list predmetu.

Cieľ predmetu

Študent sa zoznámi s matematickými základmi deklaratívnych programovacích jazykov.

Stručná osnova predmetu

Primitívne rekurzívne funkcie. Základné funkcie a operácie (kompozícia funkcií, primitívna rekurzia). Explicitné definície. Ohraničená minimalizácia. Párovacia funkcia a aritmetizácia. Spätná rekurzia. Substitúcia v parametri. Vnorená jednoduchá rekurzia. Rekurzia s mierou. Regulárne rekurzívne definície.

Obecne rekurzívne funkcie. Poza primitívnu rekurziu: Ackermann-Péterovej funkcia, univerzálna funkcia pre primitívne rekurzívne funkcie. Primitívne rekurzívne indexy. Transfinitná rekurzia. Obecne rekurzívne funkcie. Regulárna minimalizácia. µ-Rekurzívne funkcie.

Čiastočne rekurzívne funkcie. Prvá veta o rekurzii (veta o pevnom bode). Výpočtový model. Ekvivalentnosť operačnej a denotačnej sémantiky. Čiastočne rekurzívne funkcie. Operátor minimalizácie. Aritmetizácia výpočtového modelu. Kleeneho veta o normálnej forme. Univerzálna funkcia. Rekurzívne indexy. Veta o enumerácií. Čiastočne µ-rekurzívne funkcie. Rekurzívne rozhodnuteľné, polorozhodnuteľné a nerozhodnuteľné problémy. Churchova téza.

Literatúra

Podmieňujúce predmety

Doporučené:

Nadväzujúce predmety

Výučba


* – aktualizované v priebehu posledných 7 dní Posledná zmena: 2017-03-01T12:32+0100