Tímové zadanie v jazyku Prolog

Cieľom projektu je navrhnúť a implementovať riešenie vybraného problému pomocou logického programovania v jazyku Prolog a vysvetliť použité princípy.

Projekt má preukázať schopnosť:

modelovať problém pomocou logických pravidiel,
implementovať riešenie v Prologu,
analyzovať a demonštrovať jeho správanie na príkladoch.

Maximálny počet bodov: 15

Body za projekt sú súčasťou výslednej známky zo skúšky.
Najlepší projekt bude odmenený ziskom plného počtu bodov zo skúšky.

Organizácia tímu

Projekt vypracuje tím 4-5 študentov.
Každý tím si vyberie jednu tému.
Každú tému môže riešiť iba jeden tím.

Jednotlivé tímy sa zapíšu do tabulky, ktorá bude zverejnená v systéme Moodle v kurze LPI. Spolu s témou projektu uvedú mená členov tímu a kontaktné informácie (emaily).

Výstupy projektu

Projekt obsahuje tri časti:

1. Implementácia

Program v jazyku Prolog riešiaci zvolený problém. Program musí obsahovať:

reprezentáciu znalostí,
inferenčné pravidlá,
aspoň 3 demonštračné príklady.

Projekt bude hodnotený predovšetkým podľa kvality modelovania problému a návrhu logických pravidiel v programe v jazyku Prolog, nie podľa rozsahu textovej časti.

2. Elaborát

Rozsah: 6–10 strán

Obsah:

Motivácia problému
Aktuálny stav v oblasti
Teoretické východiská
Popis riešenia
Ukážky použitia
Diskusia výsledkov
Rozdelenie práce v tíme
Použitá literatúra

Zdrojový kód sa odovzdáva ako príloha elaborátu.

Šablóna pre vypracovanie elaborátu.

3. Prezentácia

dĺžka: 10–12 minút
diskusia: 3 minúty

Každý člen tímu musí byť schopný vysvetliť svoju časť projektu.

Prezentácie budú prebiehať počas skúškového obdobia (presný termín bude upresnený).

Projekt sa odovzdáva prostredníctvom systému Moodle v kurze LPI.

Odovzdaný archív projekt.zip musí obsahovať nasledujúcu štruktúru:

projekt.zip
 ├── report.pdf
 ├── program.pl
 ├── examples.pl
 ├── README.md
 └── src/
     ├── report.tex
     ├── bibliography.bib
     └── ...

Výsledné hodnotenie projektu bude založené na nasledujúcich kritériách:

Kritérium	Body
modelovanie problému	4
implementácia	5
príklady	2
elaborát	2
prezentácia	2

Nasledujúci zoznam obsahuje príklady vhodných tém projektov. Tímy si môžu zvoliť aj vlastnú tému (po konzultácii s vyučujúcim), pokiaľ ide o problém vhodný na riešenie pomocou logického programovania.

Pri implementácii je možné použiť aj dostupné rozšírenia jazyka Prolog (napr. SWI-Prolog knižnice, jednoduché GUI, alebo webové rozhranie), pokiaľ jadrom riešenia zostáva logický program.

Logické hry a puzzle

1. Riešenie šachových problémov

Implementácia systému na riešenie vybraných šachových problémov (napr. mate in N, generovanie legálnych ťahov, riešenie koncoviek).

Program môže analyzovať pozície a hľadať riešenia pomocou logických pravidiel.

2. Problém N-Queens

Generovanie všetkých riešení + vizualizácia + optimalizácia + varianty (N rooks, N knights).

porovnanie viacerých algoritmov (backtracking, CLP(FD), heuristiky),
vizualizácia riešení (ASCII, HTML, GUI),
generovanie optimalizovaných riešení (napr. minimalizácia symetrií),
riešenie príbuzných problémov: N‑rooks, N‑knights, N‑bishops,
benchmarking výkonu pre rôzne N.

3. Sudoku solver

Generátor sudoku s garantovanou jednoznačnosťou riešenia,

klasifikácia obtiažnosti (na základe použitých techník),
implementácia logických techník riešenia (X‑Wing, Swordfish, Hidden Singles…),
riešenie variantov:
- Killer Sudoku
- Samurai Sudoku
- Hyper Sudoku
porovnanie CLP(FD) vs. vlastný solver bez constraints.

Dedukcia a logické systémy

4. Emulácia dedukčného kalkulu

Implementácia jednoduchého dedukčného systému pre výrokovú alebo predikátovú logiku (napr. natural deduction alebo sequent calculus).

5. Automatický dôkazový systém pre výrokovú logiku

Program, ktorý dokáže overiť platnosť logických formúl pomocou rezolúcie alebo iných inferenčných pravidiel.

6. Systém na manipuláciu s logickými formulami

Implementácia nástroja na transformáciu logických formúl (napr. konverzia do CNF alebo DNF, Tseitinova transformácia a podobne).

7. Jednoduchý logický inferenčný mechanizmus

Program implementujúci mechanizmus odvodenia nových faktov zo znalostnej bázy.

podpora negácie, default reasoning,
vysvetľovanie odvodení (explainable inference),
viacero stratégií inferencie (depth-first, breadth-first, iterative deepening),
detekcia cyklov a nekonzistencií,
modulárna znalostná báza + editor pravidiel.

Reprezentácia znalostí

8. Expertný diagnostický systém

Systém, ktorý na základe príznakov dedukuje možné príčiny (napr. diagnostika porúch počítača alebo jednoduchých zdravotných problémov).

9. Odporúčací systém

Program, ktorý odporúča napr. filmy, knihy alebo technológie na základe definovaných pravidiel.

Plánovanie a constraint problémy

10. Generovanie rozvrhu

Program generujúci rozvrh predmetov s ohľadom na rôzne obmedzenia (miestnosti, čas, učitelia).

11. Plánovanie pohybu robota v mriežke

Modelovanie prostredia a hľadanie cesty robota medzi prekážkami.

12. Plánovanie úloh (task scheduling)

Program plánujúci vykonanie úloh s rôznymi obmedzeniami.

Jazyk a symbolická manipulácia

13. Parser jednoduchého jazyka

Implementácia analyzátora jednoduchých viet pomocou DCG (Definite Clause Grammars).

parser pre mini‑programovací jazyk (výrazy, priradenia, cykly),
interpret jazyka (vykonávanie AST),
typový systém,
generovanie AST + vizualizácia,
detekcia syntaktických chýb.

14. Systém na logickú interpretáciu viet

Program, ktorý transformuje jednoduché prirodzené vety na logickú reprezentáciu.

podpora rôznych typov viet (kvantifikátory, negácia, viacnásobné vzťahy),
generovanie predikátovej logiky z DCG,
spätná transformácia logiky → prirodzený jazyk,
inferencia nad interpretovanými vetami,
malý „chatbot“ založený na logike.

Poznámka

Tímy môžu implementovať aj jednoduché používateľské rozhranie (napr. GUI alebo webové rozhranie) pre demonštráciu programu. Hlavná logika riešenia však musí byť implementovaná v jazyku Prolog.

Existujú rôzne knižnice a nástroje v SWI-Prolog, ktoré môžu pomôcť s vizualizáciou alebo interaktívnym rozhraním, ale jadrom projektu musí zostať logické programovanie. (V prípade otázok ohľadom použitia konkrétnych knižníc alebo technológií sa neváhajte obrátiť na vyučujúceho.)