Seznam přednášek a cvičení

Na této stránce jsou umístěny podrobnější informace o obsahu přednášek a cvičení k předmětu Paradigmata programování IV. K přednáškám budou průběžně zveřejňovány slajdy. Každé cvičení má podrobně vypracovaný seznam úkolů. U studentů se předpokládá, že si sami vypracují všechny příklady, které nebudou probrány na cvičení.

Seznam přednášek

1. Základy logického programování. Logický program a jeho sémantika.
Logické paradigma jako jedno z paradigmat programování. Definitní programy a jejich syntaxe. Klausule, fakta, pravidla a dotazy. Zamýšlený význam definitního programu. Deklarativní sémantika definitního programu: herbrandova struktura, herbrandův model, nejmenší herbrandův model a jeho nalezení. Sémantické vyplývání z definitních programů. Substituce, aplikace substituce, uzavřené instance klausulí, korektní odpovědi. Čisté logické programování a PROLOG.
2. Procedurální sémantika logického programu. Rekursivní datové struktury.
Konečné a nekonečné herbrandovy modely. Rekursivní pravidla a nutnost zavedení vypočtených odpovědí. Unifikace. Nedeterministická inference. Metody odstranění nedeterminismu. Nejobecnější unifikátor a jeho nalezení. Procedurální sémantika definitního programu. Vztah deklarativní a procedurální sémantiky: korektní odpovědi versus vypočtené odpovědi. Činnost zásobníku během výpočtu PROLOGu, backtracking, nalezení alternativních řešení.
3. Řezy a negace v logickém programování.
Metalogický predikát řezu. Výpočtová efektivita a řezy. Řízení výpočtu pomocí řezů. Zelené a červené řezy. Vliv řezů na sémantiku definitního programu. Činnost zásobníku během výpočtu PROLOGu obohaceného o řezy. Vytváření podmínek a cyklů pomocí vestavěných predikátů. Teoretické přístupy k negaci: předpoklad uzavřenosti světa; negace pomocí neúspěchu v konečně mnoha krocích. Problém neexistence herbrandovského modelu při použití negace. Zavedení negace pomocí řezu.
4. Zabudovaná aritmetika. Řízení databáze a modifikace programu.
Vestavěné predikáty a jejich popis pomocí boxů. Vybrané vestavěné predikáty PROLOGu. Modelování aritmemtiky pomocí termů. Zabudovaná aritmetika a její specifické vlastnosti. Přiřazování hodnot, vyhodnocování aritmetických termů, porovnávání. Modifikace definitního programu. Přidávání a odebírání definitních klausulí. Vztah programu a dat.
5. Logické programování a matematická logika.
Propojení logického programování a klasické predikátové logiky. Logický program jako teorie prvního řádu. Herbrandovské modely jako struktury prvního řádu. Princip obecné rezoluční metody a její adaptace pro definitní programy. SLD-rezoluce, její korektnost a úplnost. Role korektnosti a úplnosti v čistém logickém programování a v PROLOGu.

Seznam cvičení

1. Seznámení se s jazykem PROLOG. Databázový model PROLOGu.
Úvod do logického programování. Základy práce s interpretem PROLOGu. Logický program. Fakta, pravidla a dotazy. Syntaxe výrazů jazyka PROLOG. Vytváření databáze faktů, vytváření pravidel a cílů. Práce s malými a velkými databázemi faktů. Vytváření databází faktů podle slovního popisu. Nalezení nejmenšího herbrandovského modelu.
2. Termy a rekursivní pravidla. Práce se seznamy.
Atomy a termy. Nerekursivní a rekursivní pravidla. Rekursivní datové struktury. Modelování aritmetiky. Symbolická manipulace s výrazy, zjednodušování výrazů. Koncepce seznamu v jazyku PROLOG. Manipulace se seznamy. Kombinatorické úlohy nad seznamy. Representace uspořádaných množin.
3. Řízení výpočtu pomocí řezů. Procedurální rysy PROLOGu.
Procedurální sémantika PROLOGu, pořadí pravidel. Řízení výpočtu pomocí řezů. Zelené řezy a jejich použití. Implementace binárních vyhledávacích stromů. Červené řezy. Procedurální rysy PROLOGu. Vytváření podmínek a cyklů pomocí vestavěných predikátů. Koncová rekurse. Interaktivní programy.
4. Negace v PROLOGu. Klasifikace termů.
5. Zabudovaná aritmetika. Řízení databáze a modifikace programu.
Základní práce s aritmetikou. Reprezentace množin celých čísel pomocí uspořádaných seznamů. Kombinatorické úlohy nad seznamy využívající aritmetiku. Programy měnící databázi faktů a pravidel během výpočtu. Hledání cesty v grafu s využitím modifikace databáze.