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

2-AIN-266 Deklaratívne programovanie

Novinky

O kurze

Tu nájdete informačný list predmetu.

Cieľ predmetu

Vybudovať matematické základy deklaratívnych programovacích jazykov. Programy sú definície rekurzívnych funkcií. Výpočtový model je založený na redukcií termov. Dátové štruktúry sa kódujú do prirodzených čísel. Problémy sa riešia na cvičeniach v programovacom jazyku CL.

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. Rekurzia so substitúciou 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. Neohraničená minimalizácia. 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

Výučba


* – aktualizované v priebehu posledných 7 dní Posledná zmena: 2019-03-04T12:49+0100