Cvičení z Neprocedurálního programování

Obecné informace

Pro zápočet požaduji:

Co bylo/bude na cvičeních

19.2.

Rodinné vztahy a peanova aritmetika.

Domácí úkol: dělení v peanově aritmetice.
26.2.

Více o strukturách v Prologu: stromy, seznamy.

Domácí úkol: konstrukce stromu.
5.3.

Akumulátory, stručný přehled aritmetiky v prologu.

12.3.

Rozdílové seznamy.

Domácí úkol: rychlá fronta.
19.3.

Prohledávání prostorů: problém N dam.

Domácí úkol: podstromy.
26.3.
Zrušeno pro nemoc.
2.4.

Pokračování prohledávání možností.

Domácí úkol: regulární výrazy.
9.4.

Návrat ke způsobu vyhodnocování – řez, apod. (konec Prologu)

Domácí úkol: překračování mostu (poslední v Prologu).
16.4.

Úvod do Haskellu.

Domácí úkol: doporučuji začít přemýšlet o zápočtovém programu.
23.4.

Práce se seznamy.

Domácí úkol: seznam čísel.
30.4.

Plán: znova seznamy.

Domácí úkol: segment.
7.5.

Definice (datových) typů, case, apod.: binární vyhledávací stromy.

Domácí úkol: mobily.
14.5.
Odkázání na některé debugovací možnosti: ladící výpisy, “krokování” v ghci (jde i “krokovat zpět”, přehled příkazů pomocí :help). Typové třídy. Odkázání na užitečné knihovny pro pole a kontejnery.
21.5.

Plán: monády, vstup a výstup, apod.

Domácí úkol: unix-like sort, posílejte do konce května.

Počet bodů z domácích úkolů potřebných pro zápočet už se nebude měnit, ale v případě zájmu přidám ještě nějaký bonusový úkol (který tuto hranici neposune).

Prolog

Haskell

Zápočtové programy

Témata obecně

  • defaultní jazyk je Prolog (protože se probere s dostatečným předstihem), ale Haskell vůbec nevadí
  • minimální obtížnost tématu odpovídá zhruba 100 řádkům kódu (+navíc komentáře, prázdné řádky, apod.)
  • pro Prolog jsou například vhodná témata využívající backtracking a/nebo unifikaci, především z oblasti umělé inteligence. Kromě hloupého prohledávání je potřeba použít alespoň nějaké jednoduché heruristiky.

    Můžete ale přijít s libovolným tématem přiměřené obtížnosti, například v Haskellu se dají programovat různé utilitky, zvláště s využitím knihoven kterých je dostupné velké množství. Nejužitečnější knihovny se distribuují přímo v rámci Haskell Platform.
  • požaduji dobře čitelný kód: každá netriviální procedura/funkce je okomentovaná (takže je každému zřejmé co má dělat), identifikátory jsou rozumně pojmenované, kód je hezky indentovaný, apod.

Příklady témat

  • můžete se inspirovat třeba u jiných cvičících, třeba Hric a Barták
  • příklady minulých témat pro inspiraci:
    • zjednodušování symbolických výrazů nebo symbolická integrace
    • těžké problémy: splnitelnost CNF, obchodní cestující (aproximačně, evolučně, …)
    • řešení různých rébusů:
      • sudoku: standardní, Killer, greater-than
      • zebra, griddlers, mastermind, přelévání vody
      • generování akordového doprovodu :-)
      • generování rébusů, například křížovek
    • různé hry, například řešení šachových koncovek, piškvorky, Quatro
    • Eliza
    • různé algoritmy a struktury, hlavně z předmětů ADS
    • utility v Haskellu, například generování webových stránek (generují i tyto stránky)