Záznamy prednášok (slajdy) pre kurz 1-INF-450 Logika pre informatikov ZS 2013/14

Prednášky

• 1. prednáška - primitívne rekurzívne funkcie.
• 2. prednáška - poza primitívnu rekurziu: univerzálna funkcia pre primitívne rekurzívne funkcie.
• 3. prednáška - explicitné definície, primitívne rekurzívne definície.
• 4. prednáška - primitívne rekurzívne predikáty a ohraničená minimalizácia, spätná rekurzia.
• 5. prednáška - párovacia funkcia, aritmetizácia dátových štruktúr, 'course-of-values' rekurzia.
• 6. prednáška - rekurzia so substitúciou v parametri, vnorená jednoduchá rekurzia.
• 7. prednáška - rekurzia s mierou, poza primitívnu rekurziu: Ackermannova funkcia.
• 8. prednáška - poza primitívnu rekurziu: Ackermannova funkcia a univerzálna funkcia pre primitívne rekurzívne funkcie, obecne rekurzívne funkcie, μ-rekurzívne funkcie.
• 9. prednáška - deklaratívne programovanie, efektívne operácie na primitívne rekurzívnych indexoch.
• 10. prednáška - Kleeneho prvá veta o rekurzii (veta o pevnom bode), rekurzívne definície, ekvivalentnosť výpočtovej a definičnej sémantiky.
• 11. prednáška - čiastočne rekurzívne funkcie, aritmetizácia výpočtového modelu pre čiastočne rekurzívne funkcie.
• 12. prednáška - neohraničená minimalizácia, Kleeneho veta o normálnej forme pre čiastočne rekurzívne funkcie, enumerácia čiastočne rekurzívnych funkcií, efektívne operácie na rekurzívnych indexoch.
• 13. prednáška - čiastočne μ-rekurzívne funkcie, Church-Turingova téza, rekurzívne rozhodnuteľné, polorozhodnuteľné a nerozhodnuteľné problémy, Turingova úplnosť a totálne funkcionálne programovanie.