PRG005 Neprocedurální programování

Co bylo na přednáškách - paralelka Y středa 10:40 S3

1. přednáška 23.února
2. přednáška 2.března
3. přednáška 9.března
4. přednáška 16.března
5. přednáška 23.března
6. přednáška 30.března
7. přednáška 6.dubna
8. přednáška 13.dubna
9. přednáška 20.dubna
10. přednáška 27.dubna
11. přednáška 4.května
12. přednáška 11.května
18. května rektorský den
13. přednáška 25.května

1. přednáška 23.února
   • O předmětu, zkoušce a zápočtech, literatura
   • Neprocedurální programování, logické programování, funkcionální programování.
   • Příklad programu popisujícího rodinné vztahy a práce s ním: základní predikáty rodic(Kdo, Koho),muz(Kdo),zena(Kdo),manz(On,Ona)
     definování predikátů otec(Kdo,Koho), sestra(Sestra,Ci), partner(Partner1,Partner2) {genderově symetrický}
   • Dotazy, proměnné, anonymní proměnná.
     Fakta, pravidla, klausule, procedury - "nezáleží" na pořadí klauzulí.
   • Rozmyslet - probere se na cvičení
     svagr(Svagr,Ci), zet(Zet,Ci)
   • Definice seznamu, syntaktické konvence zápisu.
   • Jednoduché predikáty pro práci se seznamy.
     • prvek(Co, Ceho).
     • prvniPrvek(Co, Ceho).
     • druhyPrvek(Co, Ceho).
     • posledniPrvek(Co,Ceho)
     • predPosledniPrvek(Co,Ceho)
     • spojení seznamů conc(Prvni, Druhy, Spojeni).
       má lineární složitost v délce prvního seznamu,
       nemusí se využívat jen ke spojení, ale také třeba k rozdělení seznamu na dvě části
     • otáčení seznamů otoc(Seznam, OtocenySeznam).
       má kvadratickou složitost >
   • Rozmyslet: (může být těžké, zkuste vymyslet alespoň myšlenku, na přednášce později uděláme)
     • sestavte predikát prostredni(Co,Ceho), "Co je prostrední prvek seznamu Ceho", seznam liché délky má jeden prostřední prvek, seznam sudé délky dva
       resp půlení seznamu rozpul(Seznam, PrvniPule,DruhaPule)
       nemáme k dispozici aritmetiku
       Tři návody:
       1. dva signály, rychlý rychlostí dva, pomalý rychlostí jedna, když rychlý doazí na konec, je pomalý uprostřed
       2. odkoukání činnosti vrchního v pivnici
       3. střídavé ukousávání zepředu a ze zadu (povede na pomalý algoritmus)
     • zkuste najít ideu jak otáčet seznamy v lineárním čase
Zpět začátek
2. přednáška 2.března
   • býti seznamem
   • půlení seznamu metodou dvou signálů šířících se rychlostí jedna a dva
   • půlení seznamu metodou spočítání délky div 2 (v unární soustavě) a následného odebrání začátku zadané délky
   • rozmyslet: totéž ukousáváním střídavě ze začátku a zkonce
   • Syntaxe Prologu (proměnné, atomy, řetězce, struktury, klausule, fakty, pravidla, procedury, ... ).
   • Unifikace, příklady
   • matchování termů a algoritmus unifikace
   • Algoritmus interpretu Prologu (unifikace + backtracking).
   • vypouštění prvku ze seznamu
     • prvního výskytu, které uspěje vždy
     • prvního výskytu, které uspěje jen je-li tam
     • všech výskytů
   • prvek pomocí conc a del
   • vkládání "je totéž" jako vypouštení
   • permutace(Seznam,PermutovanySeznam)
   • otáčení seznamu v lineárním čase - reverse_append
     jako speciální příklad použití akumulátoru
Zpět začátek
3. přednáška 9.března
   • operátor středník
   matice jako seznamy řádkových seznamů
   • diag(+CtvercovaMatice, -Diagonala)
   • prazdnamatice(+Matice)
   • rozmyslet na přednášce dělat nebudeme, ale predikát spirála budeme potřebovat odkázat
     • test zda matice je obdélniková
     • test zda matice je čtvercová
     • otáčení matice o 90 stupňů
     • slupka(+Matice,-Slupka,-Pecka)
     • spirála(+Matice,-Spirala)
   používání prefixů +, - a ? u parametrů v komentářích
   Binární stromy
   prázdný strom - atom nil, neprázdný struktura - t(L,V,R), kde V je kořen, L levý a R pravý podstrom
   predikát prvekstromu(Co, Vcem)
   listy(+Strom, -SeznamListu) implementace s kontatenací a bez ní,
   měli byste být schopni v podobných případech "automaticky" přepisovat predikáty do tvaru bez použití zřetězení
   rozmyslet: průchody stromem do šírky a do hloubky
   Aritmetika, predikát is,
   aritmetické relace =:= , =/= , ‹ , › , ‹= , ›=
   Jednoduché aritmetické predikáty
   největší společný dělitel dvou čísel, delka seznamu
   maximum(+A,+B,-MaxAB), maxZeSeznamu(+Seznam,-Max)
   Algoritmus quicksortu, implementace se zřetězením a rozmyslet bez něho
   následující permutace v lexikografickém uspořádání
Zpět začátek
4. přednáška 16.března
   • opakování aritmetiky
   • Binární vyhledávací stromy
     • náležení prvku
     • vkládání prvku - "obvyklé" vkládání prvku "do listu" nemůže posloužit pro vypouštění obecného prvku ze stromu
     • vypouštění prvku ze stromu - obvyklý algoritmus
     • vkládání prvku do kořene
     • rozmyslet: (nedeterministická) procedura vkládání do binárního vyhledávacího stromu, která může být použita i pro vypouštění
     • postav(+RostSez, +N, -T, -Zbytek) Postavení dokonale vybalancovaného binárního vyhledávacího stromu T z prvních N prvků rostoucího seznamu RostSez, Zbytek se zbytek seznamu
   • Deklarativní sémantika Prologu.
   • Různé definice predikátu býti předkem a jejich operační sémantika
   • Každá deklarativně správná procedura v čistém Prologu je parciálně správná,
     tj. odpověď na dotaz dát nemusí, ale dá-li ji, je tato odpověď správná.
   • rozmyslet: jaké jsou rozdíly v operační sémantice čtyř deklarativně ekvivalentních definicí předka
   • Predikát consult (historické reconsult)
   • 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.
   • "Smotávání" matice ze známé spirály - použití datové struktury z anonymních proměnných,
     rozmyslet:jak stejnou myšlenku použít v procedurálních jazycích
   • průchod stromem do hloubky a do šířky
Zpět začátek
5. přednáška 24.března
   • pojem proměnné v Prologu
   • "poučení z úlohy smotávání matice: mnohdy je výhodné provádět transformace na strukturách vytvořených z anonymních proměnných, pak máme inverzní transormaci "zadarmo"
   • opakování
     deklarativní sémantika prologovské procedury
     deklarativně správná procedura je parciálně správná
   • 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í
   • Třídění vkládáním
   • rozdílové seznamy jako příklad neúplně definovaných datových struktur
     konkatenace v konstatním čase
     
   • Převod mezi seznamy a rozdílovými seznamy
   • Quicksort bez konkatenace, srovnej zápis s parametrem navíc a s rozdílovými seznamy
   • Standardní predikát fail a jeho "síla"
     "má ráda muže, ale ne plešaté"
   • definice negace
   • Standardní predikáty atom/1,atomic/1, var/1, nonvar/1.
   • Rovnosti v prologu
     • = unifikace, \= její negace
     • =:= aritmetická rovnost, =\= její negace
     • == totožnost, \== její negace
   • Standardní predikáty pro analýzu a syntézu termů:
     name/2, functor/3, arg/3, =..   a příklady jejich užití.
   • 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).
Zpět začátek
6. přednáška 30.března
   Na přednášce pravděpodobně bude
   • Opakování - operátor řezu, negace
   • Definice operátorů, standardní predikát op/3.
   • Zavináčové uspořádání
   • Řešení algebrogramu
   • "Wirthův" program pro hledání všech rozestavení N nezávislých dam na šachovnici N x N
     - ne vždy pole skutečně potřebujeme
   • Predikáty bagof a setof, "existenční kvantifikátor ^ ", jednoduché příklady užití.
   • Predikáty modifikace databáze, assert, asserta, assertz, retract, retractall.
     Vhodnost resp. nevhodnost použití těchto příkazů.
   • Na co se hodí Prolog
   • Princip možné implemenace programu Eliza (rozhovor psychoanalytika s pacientem)
   • Procedury realizující jednoduchý algoritmus pro zjednodušování aritmetických výrazů
   • Ovlivňování efektivity Prologovských programů.
   • Několik implemenací výpočtu Fibonnaciovy posloupnosti, iterativní výpočet.

   K Prologu se možná ještě za několik přednášek vrátíme

   Na příští přednášce začneme probírat jazyk Scheme, vytiskněte si jeho syntaxi
Zpět začátek
7. přednáška 7.dubna
   Dialekt LISPu - SCHEME
   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
Zpět začátek
8. přednáška 13.dubna
   Úvod do Haskellu
   • Haskell jako funkcionální jazyk s typovou kontrolou.
   • Definice funkce, typová specifikace funkce.
   • Uživatelské definice typů. Typové a datové konstruktory. Polymorfické typy. Seznamy,
   • dvě definice typu binárnístrom
   • Práce s funkcemi více proměnných - curryfikace
   • Lambda abstrakce.
   • funkce map, operátor skládání funkcí, fold, foldr a příklady použití
   • zkratky seznamů
   • Definování seznamů pomocí generátorů a stráží. Výrazy pro aritmetické posloupnosti.
     Podrobný výklad sémantiky výrazů tvaru [ e | q₁ , q₂ , ... ,q_r ],
     jednoduché příklady použití.
   • Dvě implementace generování seznamu všech permutací daného seznamu
   • Převod infixového operátoru na binární funkci a zpět. Řezy (sections).
   • Funkce v Haskellu nejsou striktní.
     Objekt boot. Líné (lazy, by need) vyhodnocování funkcí.
   • Stráže v definicích funkcí

   Stáhněte si: A Gentle Introduction to Haskell
Zpět začátek
9. přednáška 20.dubna
   • Haskell - opakování
   • Zápis definice funkce pomocí case výrazu, Stráže v definicích funkcí
   • "Mečování" parametrů. Pořadí - odleva doprava a z vněšku dovniř,
     Výsledkem mečování může být úspěch, selhání nebo divergence.
     Formální parametry jako "vzorky" - patterns:
     • proměnné
     • As-patterns - '@'
     • žolík - '_'
     • datový konstruktor
     • "aritmetický parametr" - "n+k"
     • lazy parametr
     Příklady
   • Konstrukce let a where, dvojrozměrná syntaxe Haskellu
   • if výraz
   • lazy vyhodnocování - vyhodnocuj až když musíš
     otvírá možnost definování nekonečných termů (jako zápisů algoritmů produkujících nekonečnou posloupnost výsledků, z nichž však v každém konkrétním výpočtu potřebuji - a tedy budu počítat - jen konečně mnoho)
     srovnej aktuální a potenciální nekonečno v matematice
   • Nekonečné datové struktury. Příklad fibonacciovy posloupnosti, syntaxe pro nekonečné seznamy.
   • Mocninné řady jako příklad nekonečných termů, derivace
   • Prvočísla pomocí Erathostenova síta.
   • Na rozmyšlenou:
     • Operace s mocninnými řadami
       • První a n-tá derivace mocninné řady
       • Aritmetické operace s mocninnými řadami (sčítání, odčítání, násobení )
       • Výpočet hodnoty součtu prvních N čísel mocninné řady R v bodě X
       • Totéž pro K tou derivaci
       • Typové specifikace těchto funkcí
     • Porovnejte s obdobnými funkcemi pro různé reprezentace polynomů
Zpět začátek
10. přednáška 27.dubna
    • průzkum zájmu o termíny zkoušky
    • Dvě definice funkce , která vrací zadaný počet prvků ze začátku seznamu, které se liší mírou tolerance k chybě v prvním a druhém parametru.
    • fixity deklarace
    • motivační příklad pro zavedení tříd
    • Třídy, podtřídy, vícenásobná dědičnost, použití při typové specifikaci funkcí
    • Třídy Eq, Ord, Visible
    • instance typů, deriving
    • Typ Maybe a
    • moduly, import, export,
    • abstraktní datové typy - implementace zásobníku,
      detailní reprezentace množiny (jako rostoucího seznamu prvků)
    • několik jednoduchých funkcí se seznamy, curry, uncurry
    • Různé implementace funkce počítající faktoriál
Zpět začátek
11. přednáška 4.května
    • O zkouškových písemkách a způsobu přihlašování na zkoušky
    • Abstrakce v Haskellu
    • definování typu s explicitním uvedením jmen selektorů
    • striktní konstruktory typů
    • Pole v Haskellu, příklady
    • Jednoduché I/O operace
    • Monáda IO (k tomu se ještě vrátíme)
Zpět začátek
12. přednáška 11.května
    Haskell
    -
    Na přednášce pravděpodobně bude
    • O zkouškových písemkách a způsobu přihlašování na zkoušky
    • Monáda IO
    • Obecné vlastnosti monád
    • konstrukce do
    • Monády L a I
    • Příklad praktické použití monád - abstrakce imperativních výpočtů
    • komentář k začátku modulu prelude
    • Dotazy a odpovědi
Zpět začátek
13. přednáška 25.května
    Logika za Prologem - letem světem
    • Predikátový a výrokový počet
    • Interpretace, logicky pravdivé formule, splnitelnost
    • Klauzulární tvar formule, Skolemova věta
    • Herbrandovo universum, Herbrandova věta
    • Základní resoluční metoda, unifikační algoritmus, Robinsonova věta
    • Hornovy klausule a Prolog
Zpět začátek