Zpět PRG005

PRG005 Neprocedurální programování

Co bylo na přednáškách - paralelka X - úterý 10:40 S3

  1. přednáška 19.února
  2. přednáška 26.února
  3. přednáška 5.března
  4. přednáška 12.března
  5. přednáška 19.března
  6. přednáška 26.března
  7. přednáška 2.dubna
  8. přednáška 9.dubna
  9. přednáška 19.dubna
  10. přednáška 23.dubna
  11. přednáška 30.dubna
  12. přednáška 7.května
  13. přednáška 14.května
  14. přednáška 21.května
  1. přednáška 19.ú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
    • 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
  2. Zpět začátek
  3. přednáška 26.února
    • 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, ... ).
    • používání prefixů +, - a ? u parametrů v komentářích
    • 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
    • permutace(Seznam,PermutovanySeznam)
    • otáčení seznamu v lineárním čase - reverse_append
      jako speciální příklad použití akumulátoru
  4. Zpět začátek
  5. přednáška 5.března
    • opakování: Algoritmus interpretu Prologu (unifikace + backtracking).
    • 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)
    • 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 konkatenací 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í
    • Aritmetika, predikát is,
      aritmetické relace =:= , =/= , ‹ , › , ‹= , ›=
    • Jednoduché aritmetické predikáty
      největší společný dělitel dvou čísel
    • délka seznamu
    • maximum(+A,+B,-MaxAB), maxZeSeznamu(+Seznam,-Max)
    • následující permutace v lexikografickém uspořádání
    • 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
    • rozmyslet: co je proměnná v Prologu
  6. Zpět začátek
  7. přednáška 12.března
    • pojem proměnné
    • opakování aritmetiky
    • Algoritmus quicksortu, implementace se zřetězením a rozmyslet bez něho
    • vkládání prvku do kořene binárního vyhledávacího stromu
    • (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í
    • 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
    • "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
    • "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"
    • rozmyslet:
      "nejde zvolit jiný model seznamů, jejichž konkatenace by byla v konstantním čase?"
      návod: zkuste použít anonymních proměnných a inspirujte se tím, jak vypadá quicksort bez konkatenace
  8. Zpět začátek
  9. přednáška 19.března
    • operátor středník
    • opakování
      deklarativní sémantika prologovské procedury
      deklarativně správná procedura je parciálně správná
    • rozdílové seznamy jako příklad neúplně definovaných datových struktur
      konkatenace v konstatním čase
    • porovnání kódu quicksortu be konkatenace a qicksortu rozdílových seznamů - tu ideu jsme vlastně už znali
    • Standardní predikáty pro analýzu a syntézu termů:
      name/2, functor/3, arg/3, =..   a příklady jejich užití.
    • Standardní predikáty atom/1, var/1, nonvar/1, ......
    • 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.
    • 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í
    • Převod mezi seznamy a rozdílovými seznamy
    • Standardní predikát fail a jeho "síla"
      "má ráda muže, ale ne plešaté"
    • definice negace
    • Řešení algebrogramu
  10. Zpět začátek
  11. přednáška 26.března
    pravděpodobný obsah přednášky
    • Rovnosti v prologu
      • = unifikace, \= její negace
      • =:= aritmetická rovnost, =\= její negace
      • == totožnost, \== její negace
    • "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át consult (historické reconsult)
    • predikát repeat
    • Příklady programování cyklů v Prologu
      ( "věčný" cyklus repeat .... fail a jeho ukončení, "repeat until" cyklus , "for" cyklus ).
    • "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
    • 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).
    • Definice operátorů, standardní predikát op/3.
    • Zavináčové uspořádání
    • Predikáty bagof a setof, "existenční kvantifikátor ^ ", jednoduché příklady užití.
    • Modifikace obsahu databáze - assert, retract, retractall
      pomocí těchto predikátů můžeme modelovat globální proměnné
      tyto prostředky zpomalují výpočet tím podstatněji, čím je překladač"lepší"
    • Na co se hodí Prolog
    K Prologu se 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
  12. Zpět začátek
  13. přednáška 2.dubna
    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
  14. Zpět začátek
  15. přednáška 9.dubna
    Ještě naskok k Prologu
    • O zkouškách a zápočtech
    • Princip možné implemenace programu Eliza (rozhovor psychoanalytika s pacientem)
    • Procedury realizující jednoduchý algoritmus pro zjednodušování aritmetických výrazů
    • Na co se hodí Prolog
    • Ovlivňování efektivity Prologovských programů.
    • Několik implemenací výpočtu Fibonnaciovy posloupnosti, iterativní výpočet.
    • for cyklus jako ukázka, jak raději v Prologu neprogramovat
    Příště začneme s Haskellem
  16. Zpět začátek
  17. přednáška 16.dubna
      Můžete si přečíst: Miran Lipovača: Learn You Haskel
      Jako zdroj detailních informací můžete používat: Haskell 2010 - Language report
    • Co jsme se již o neprocedurálním programování naučili
    • Předběžné informace o zkouškách
    • Haskell jako funkcionální jazyk s typovou kontrolou.
    • Definice funkce, typová specifikace funkce, typové konstruktory: seznamy, funkce, ntice.
    • Práce s funkcemi více proměnných - curryfikace
    • Seznamy a jednoduché funkce pro práci se seznamy
    • Operátory jak funkce, např. (++) a funkce se dvěma parametry jako operátory
    • Lambda abstrakce.
    • Řezy funkcí, např. (x+),(+x)
    • Uživatelské definice typů. Typové a datové konstruktory. Polymorfické typy.
    • Definice typu binární strom
    • Jednoduché funkce pro práci se stromy
    • funkce map
    • zkratky seznamů
  18. Zpět začátek
  19. přednáška 23.dubna
    • Haskell - opakování
      • Typy: standardní typové konstruktory: seznamy, funkce, ntice,
        uživatelské definice typů, typový konstruktor, datové konstruktory, polymorfické typy,
        třídy jako analog javovských interfaců (zatím jenom standardní)
      • definice funkcí pomocí "definičních rovností", typová specifikace funkce,
        curryfikace - funkce n proměnných jsou standardně chápány jako funkce jedné proměnné vracející fukci (n-1) proměnných
        lambda abstrakce
        binární operátory jako funkce, funkce dvou proměnných jako oprerátory
        řezy funkcí
      • Seznamy, jejich definice pomocí generátorů a stráží, zkratky za seznamy
    • Definování seznamů pomocí generátorů a stráží. Výrazy pro aritmetické posloupnosti.
      Podrobný výklad sémantiky výrazů tvaru [ e | q1 , q2 , ... ,qr ],
      jednoduché příklady použití.
    • Dvě implementace generování seznamu všech permutací daného seznamu
    • Standardní typy Int, Bool, Char, String, Double
    • Typová synonyma - type
    • Funkce v Haskellu nejsou striktní.
      Objekt boot. Líné (lazy, by need) vyhodnocování funkcí.
    • 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" od verze 10 již není dovoleno
      Příklady
    • lazy patterns, příklady
    • 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.
  20. Zpět začátek
  21. přednáška 30.dubna
    • opakování
    • if výraz
    • Konstrukce let a where, dvojrozměrná syntaxe Haskellu
    • Funkce map, foldl a foldr a příklady jejich použití
    • 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, pythagorejské trojice.
    • 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ů
    • 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
    • Odvozené instance typů, deriving
    • Typ Maybe a
    • Různé implementace funkce počítající faktoriál
  22. Zpět začátek
  23. přednáška 7.května
    na přednášce pravděpodobně bude
    • Třídy, podtřídy, vícenásobná dědičnost, použití při typové specifikaci funkcí
    • Třídy Eq, Ord
    • Odvozené instance typů, deriving
    • Typ Maybe a
    • moduly, import, export,
    • abstraktní datové typy - implementace zásobníku, množiny,
      detailní reprezentace množiny (jako rostoucího seznamu prvků)
    • několik jednoduchých funkcí se seznamy, curry, uncurry, ....
    • Abstrakce v Haskellu
    • Pole v Haskellu
    • Jednoduché I/O operace
    • 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
    • O zkouškových písemkách a způsobu přihlašování na zkoušky
  24. Zpět začátek
  25. přednáška 14.května
    Dokončení Haskellu
    otázky a odpovědi
  26. přednáška 21.května
    Logika za Prologem - letem světem