Cvičení z Neprocedurálního programování
Obecné informace
Pro zápočet požaduji:
- zápočtový program v Prologu nebo Haskellu
- alespoň polovinu všech bodů za domácí úlohy a zároveň alespoň polovinu všech bodů za úlohy v jazyce ve kterém nepíšete zápočtový program (nebo individuální dohoda, raději předem)
- nepožaduji účast; zadání domácích úkolů budou zde, řešení posílejte e-mailem
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.
- 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.
- Domácí úkol: doporučuji začít přemýšlet o zápočtovém programu.
- 23.4.
- 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
- doporučovaný interpret je SWI prolog, lze také použít třeba GNU prolog nebo SICStus prolog (všechny jsou v labu, prof. Barták poskytuje licence na SICStus)
- SWI prolog obsahuje dobrou dokumentaci, kterou lze vyvolat dotazem
?- help(něco). - neprocedurální techniky, přehled některých vlastností Prologu
- odkazy jinam (En): exercises, Barták’s guide, tutorial to create an adventure
Haskell
- odkazovník http://haskell.org pro vše okolo Haskellu
- online přístupné knihy:
- učebnice Learn You a Haskell, i s českou verzí Naučte se Haskell!
- praktický přístup - Real World Haskell, je i v MS knihovně
- neprocedurální techniky, přehled syntaxe Haskellu a něco o knihovnách
Zápočtové programy
- témata domlouvejte se mnou e-mailem
- s programem odevzdáváte také vhodná testovací data. Program by měl umět je načíst ze zadaného souboru, ale záleží na konkrétním tématu. Počítejte s tím, že budu zkoušet i jiné vstupy.
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ů:
- 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)