PRM046 Co bylo na přednáškách a cvičeních

Domluvili jsme se, že nebudeme striktně rozlišovat mezi cvičením a přednáškou, ale fomu budeme pružně přizpůsobovat potřebám probírané látky i jednotlivých studentů.
Nebudu zde uvádět výčet všech příkladů, které jsme dělali, jen témata, která jsme probrali.

Literatura k Haskellu

1. Stáhněte si: Paul Hudak, Joseph H. Fasel: A Gentle Introduction to Haskell
2. Podívejte se na:
   • Programming in Haskell
     hezká učebnice na webu slidy v Powerpointu
   • učebnice pro začátečníky - jazyk vykládán hezky, ale žádné příklady hodné toho, co už umíte
     její český překlad
   • Na stránkách Haskell.org
   můžete najít celou řadu materiálů

1. 6.října
2. 13.října
3. 20.října
4. 27.října
5. 3.listopadu
6. 10.listopadu
7. 24.listopadu
8. 1.prosince
9. 8.prosince
10. 15.prosince
11. 22.prosince
12. 7.ledna
13. 14.ledna

1. 6.října
   • Náplň kursu, podmínky pro zápočet, zkouška.
   • Neprocedurální funkcionální, logické programování.
   • Příklad jednoduchého programu v Prologu a dotazů na něj.
   • Fakt, pravidlo, proměnná, anonymní proměnná.
   • Definice seznamu a notace pro jejich zápis.
   • Jednoduché predikáty pro práci se seznamy, např.
     prvek, první, poslední, předposlední prvek seznamu
     permutace seznamu, zřetězení seznamů,
     otáčení seznamu v kvadratickém čase, atd.
   • Rozmyslet: Vytvořit predikáty nejstarší bratr, starší bratr, starší bratři, mladší bratři
2. 13.října
   • opakování jednoduchých predikátů pro práci se seznamy, další predikáty, různé variace vypuštění a vládání prvku ze a do seznamu
   • různá řešení nejstaršího a stašího bratra
   • predikát reverze_append - otáčení seznamu pomocí akumulátoru
   • rozpůlení seznamu bez aritmetiky, dvě řešení:
     dvěma signály různé rychlosti, nalezení seznamu, poloviční délky
   • domácí úkol (buď přineste ne pošlete mailem) rozpůlení seznamu umazáváním z obou konců
   • Reprezentace matice jako seznamu řádkovych seznamů,
     hlDiag(Matoce,HlDiag), bytiobdelnikovou(Mat), bytictvercovou(Matice), bytiPrazdnouMatici(Matice),otočení matice o 90 stupňů
   • Rozmyslet: několik predikátů pracujících s maticemi:
     slupka(Matice,Slupka,Pecka), spirala(Matice,Spirala), zkuste otáčení s využitím akumulátoru
   • přečtěte si skriptíčka do strany 15
3. 20.října
   • Syntaxe Prologu (proměnné, atomy, řetězce, struktury, klausule, fakty, pravidla, procedury, ... ).
   • Unifikace
   • Algoritmus interpretu Prologu (unifikace + backtracking).
   • Procedurální a deklarativní význam prologovskéhio programu
   • Deklarativně správná procedura v čisém (pure) Prologu je parciálně správná v operačním smyslu
   • Dvě varianty dekarativně správných procedur pro vyjádření vztahu predek(Kdo, Koho), z nichž jeden odpoví vždy a druhý nikdy
   • Rozmyslet: chování čtyř (deklarativně ekvivalentních) variant procedury predek
   • Binární stromy - jedna možná reprezentace
   • jednoduché predikáty pro práci se seznamy
     prvek/2, inorder průchod, výpis listů (i varianta bez konkatenace pomocí akumulátoru)
   • Aritmetika, is, aritmetické operátory
     jednoduché predikáty, nejmenší spol dělitel, délka seznamu, minimum, minimum seznamu, ...
   • vkládání do binárního vyhledávacího stromu (vkládá vždy do listu), jde tedy využít pro vypouštění z listů
     rozmyslete modifikaci této procedury tak, aby uměla i vypouštět
   • vypouštěni z binárního vyhledávacího stromu
   • vypouštění čísel mimo zadaný interval z binárního vyhledávacího stromu,
     vypouštění všech čísel s danou vlastností
   • Dvě reprezentace permutací:
     
     • p(n,Vektor_obrazů)
     • c(n,Seznam_Netriv_cyklů)
     Vytvořte predikát/y pro vzájemné převody
4. 27.října
   • Opakování:
     procedurální (unifikace a backtracking) a deklarativní (formule) význam programu, jak se může chovat deklarativně správný program
   • Opakování: odstranění konkatenace seznamů z procedury pro výpis listů stromu - použití akumulátoru
     v analogických případech byste měli být schopni sami tuto ideu použít
   • rozdílové seznamy ja příklad neúplně definovaných datových struktur
     konkatenace rozdílových seznamů v konstantním čase
     převod mezi seznamy a rozfílovými seznamy uděláme později
   • standardní predikáty var/1, nonvar/1
   • "Smotávání" matice ze známé spirály - použití datové struktury z anonymních proměnných
     uvědomte si, že stejnou ideu jde (i když technicky zcela jinak) použít i v procedurálních jazycích - např. v Pascalu
   • Predikáty consult/1, halt/0,
   • Krabičkový model výpočtu odpovědi na dotaz. Princip ladění v Prologu, predikáty trace/0, notrace/0, spy/1, nospy/1.
   • Zkuste práci s kompilátoran SWI Prolog
   • Operátor řezu a jeho sémantika - červený a zelený řez, jednoduché příklady použití
   • Operátor řezu "ničí" deklaritivní sémantiku procedury, některé problémy s používáním řezu
   • Bublinkové třídění
   • Standardní predikát fail a jeho "síla"
     "má ráda muže, ale ne plešaté"
   • definice negace
   • predikát repeat
   • "Edinburgský" model vstupu a výstupu: otvírání, zavírání, zjištění aktuálního streamu, Vstup/výstup termů
     
   • Kopírování souboru
   • Příklady programování cyklů v Prologu
     ( "věčný" cyklus repeat .... fail a jeho ukončení, "repeat until" cyklus , "for" cyklus ).
   • vstup a výstup znaků, příklady
   SWI Prolog umožňuje složitější práci se soubory. Pro použití na cvičeních a při zkouškách vystačíme s touto podmnožinou (v SWI je realizována s drobnými odchylkami).
   • Přečtěte ti ze skriptíček to, co jsme již probrali:
     kapitoly 1-7, 9.2. 11., 14.1.- 14.2.
     tak, abyste se mohli zeptat na to, co Vám není jasné
   • 1. predikáty pro převod mezi dvěma reprezentacemi permutací
        p(n,Vektor_obrazů) a c(n,Seznam_Netriv_cyklů)
     2. vytvořte predikát, který najde k-tou mocninu permutace zadané pomocí netriviálních cyklů
     3. Vytvoření seznamu prvků stromu v pořadí podle jejich vzdálenosti od listů (a je-li stejná, pak odleva do prava)
     4. proceduru/y pro převody mezi seznamy a rozdílovými seznamy
     Pokud to půjde, pošlete mi řešení jako přílohu mailu s předmětem "DCV01", optimálně do úterý večer, nebo přineste na napsané na přednášku
5. 3.listopadu
   • umocňování permutací v reprezentaci pomocí cyklů - skoro jsme dodělali, pošlete do úterý mailem s s předmětem "DCV2"
   • Vytvoření seznamu prvků stromu v pořadí podle jejich vzdálenosti od listů (a je-listejná, pak odleva do prava)
   • Průchody grafem do hloubky a do šířky - skoro jsme dodělali
   • kanonická reprezentace lesa obecných stromů jako binárního stromu
     interpretace "synů v binárním stromě" - prvorozený syn a mladší bratr
   • Stáhněte si kompilátor SWI a zkuste si vytvořit a odladit několik jednoduchých predikátů
     budou-li problémy, zeptejte se příště
   • Zkuste naprogramovat:
     1. predikáty pro převod mezi dvěma reprezentacemi permutací
        p(N,Vektor_obrazů) a c(N,Seznam_Netriv_cyklů)
     2. proceduru/y pro převody mezi seznamy a rozdílovými seznamy
     3. proceduru/y pro převody mezi lesem obecných stromů a jeho kanonicku reprezentací jako binárního stromu
     4. naprogramujte proceduru vkládání do binárního vyhledávacího stromu, kterou by šlo použít i pro vypouštění
6. 10.listopadu
   • proceduru/y pro převody mezi lesem obecných stromů a jeho kanonicku reprezentací jako binárního stromu
   • proceduru/y pro převody mezi seznamy a rozdílovými seznamy
   • proměnná v Prologu je jen označení místa pro substituci
   • ukázka procedury, která řeší jednoduché algebrogamy
   • jednoduché zjednodušování výrazů
   • ukázky práce s překladačem a debugerem
   • vkládání prvku do kořene binárního vyhledávacího stromu
   • návody pro
     • hledání následující permutace v lexikografickém zobrazení
     • hledání pořadového čísla permutace - rozmyslete do příště
     • hledání permutace s daným pořadovacím číslem - rozmyslete do příště
   • definování operátorů, predikát op/3, asociativita a priorita operátorů
   • Domácí úkoly:
     pošlete do pondělí 21.listopadu mailem se subjektem "DCV3" - v souborech napište své jméno a nezapomeńte na komentáře
     
     • predikáty pro převod mezi dvěma reprezentacemi permutací
       p(N,Vektor_obrazů) a c(N,Seznam_Netriv_cyklů)
     • naprogramujte proceduru vkládání do binárního vyhledávacího stromu, kterou by šlo použít i pro vypouštění
     • umocňování permutací v reprezentaci pomocí cyklů
     • hledání následující permutace v lexikografickém zobrazení
7. 24.listopadu
   • opakováni - definování operátorů
   • zavináčové uspořádání
   • identita == a její negace \==
   • "Wirthův" program pro generování nezávislých pozic N dam na šachovnivi NxN - není třeba pole
   • Standardní predikáty pro analýzu a syntézu termů:
     name/2, functor/3, arg/3, =..   a příklady jejich užití.
   • Predikáty bagof a setof, "existenční kvantifikátor ^ ", jednoduché příklady užití.
   • Princip možné implemenace programu Eliza (rozhovor s pacientem psychoanalitika)
   • predikáty ovlivňující databázi: assert/1, retract/1, retractall/1
     a jejich vliv na efektivitu programu
   • modelování "globálních" proměnných pomocí assert a retract
   • jazyk XSCHEMe vytiskněte si na příště: seznam standardních forem
   • pokud jste mi neposlali domácí úkol, udělejte to, odpovím Vám, že jsem ho dostal
   • jednoduchá písemka
     1. Množina (čísel) je reprezentována jako rostoucí seznam jejich prvků.
        Funkce je reprezentována jako seznam dvojic f(Vzor,Obraz) seřazený vzestupně podle Vzoru.
        Sestavte procedury, které k dané množně M a funkci F najdou obraz F(M) a vzor F^-1(M)
     2. Řídká matice je je reprentována jako trojice (počet_řádek, počet_sloupců, seznam_nenulovýxch_prvků), kde v seznamu jsou trojice (i,j,a_i,j), seznam je uspořádán podle i a pro stejná i podle j
        návod: udělejte predikát transponující matici
     pokud se Vám nepovedlo, pošlete mi mailem do středy ráno
8. 1.prosince
   Přehled základních předdefinovaných forem je v materiálu
   • Výrazy v LISPu - prefixový způsob zápisu, vyhodnocování expanzí a redukcí.
   • Forma define
   • Podmínky: formy cond a if, nil jako false.
   • Příklady: efektivní umocňování, faktoriál, odmocnina Newtonovou metodou.
   • Funkce jako parametry - motivační příklad.
   • Formy lambda a let, lokalita ve formě let.
   • Dvojice : formy cons, car, cdr.
   • "Alternativní" implementace forem cons, car a cdr "pomocí funkcí"
   • Seznamy, forma list, příklady jednoduchých funkcí pro práci se seznamy.
   • Forma quote.
   • Datová struktura = konstruktory + selektory (+metody).
     Výhody takového styly programování (platí obecně nikoli jen v nějakém konkrétním jazyku).
   • Implemenace zlomku jako příklad nutnosti "inteligentních" konstruktorů a selektorů.
   • Příklad struktury Binární strom:
     • konstruktory Nulltree, Tree(L,V,R),
     • test nulltree?
     • selektory Root, Left, Right
   • Příklady funkcí v Lispu nad touto datovou strukturou:
     • Výpis listů stromu do seznamu (bez nutnosti zřetězovat seznamy).
     • výška stromu
     • dodělejte: postavení dokonale vybalancivaného binárního vyhledávacího stromu ze začátku rostoucí posloupnosti zadané délky.
   • Rekapitulace technik, které má programátor v Prologu k dispozici k (pozitivnímu) ovlivňování složitosti programů.
   • Několik verzí procedury počítající Fibonnaciho čísla, iterační verze
   • odkaz na obrázky od Eshera
Zpět začátek