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 22.února
  2. přednáška 1.března
  3. přednáška 8.března
  4. přednáška 15.března
  5. přednáška 22.března
  6. přednáška 29.března
  7. přednáška 5.dubna
  8. přednáška 12.dubna
  9. přednáška 19.dubna
  10. přednáška 26.dubna
  11. přednáška 3.května
  12. přednáška 10.května odpadla
  13. přednáška 17.května
  14. přednáška 23.května
  1. přednáška 22.ú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
  2. Zpět začátek
  3. přednáška 1.března
    • 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, ... ).
    • operátor středník
    • 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 8.března
    • predikát býti seznamem
    • používání prefixů +, - a ? u parametrů v komentářích
    • 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 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
    • 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í
  6. Zpět začátek
  7. přednáška 15.března
    • pojem proměnné
    • opakování aritmetiky
    • délka 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.
    • 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
    • "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
  8. Zpět začátek
  9. přednáška 22.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
    • Standardní predikát fail a jeho "síla"
      "má ráda muže, ale ne plešaté"
    • definice negace
    • Standardní predikáty atom/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í.
  10. Zpět začátek
  11. přednáška 29.března
    pravděpodobný obsah přednášky
    • Opakování - operátor řezu, negace
    • Řešení algebrogramu
    • 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).
    • 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í.
    • Procedury realizující jednoduchý algoritmus pro zjednodušování aritmetických výrazů
    • 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
    K Prologu se ještě vrátíme
  12. Zpět začátek
  13. přednáška 5.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 12.dubna
      Ještě naskok k Prologu
    • Ř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
    • Princip možné implemenace programu Eliza (rozhovor psychoanalytika s pacientem)
    • Ovlivňování efektivity Prologovských programů.
    • Několik implemenací výpočtu Fibonnaciovy posloupnosti, iterativní výpočet.
    • Úvod do Haskellu
    • Haskell jako funkcionální jazyk s typovou kontrolou.
    • Definice funkce, typová specifikace funkce.
    • Uživatelské definice typů. Typové a datové konstruktory. Typová synonyma. Polymorfické typy. Seznamy,
    • dvě definice typu binární strom
    • Práce s fukcemi více proměnných - curryfikace
    • Lambda abstrakce.
    • funkce map, operátor skládání funkcí
  16. Zpět začátek
  17. přednáška 19.dubna
    • Haskell - opakování
    • zkratky seznamů
    • 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
    • Funkce map, fold a foldr a příklady jejich použití
    • 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"
      Příklady
    • Konstrukce let a where, dvojrozměrná syntaxe Haskellu
    • if výraz
  18. Zpět začátek
  19. přednáška 26.dubna
    • Opakování
    • "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"
      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.
    • 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, Num
    • Odvozené instance typů, deriving
    • Typ Maybe a
    • Různé implementace funkce počítající faktoriál
  20. Zpět začátek
  21. přednáška 3.května
    • 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
  22. Zpět začátek
  23. přednáška 17.května
    na přednášce pravděpodobně bude
    • 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
    • Dotazy a odpovědi
  24. Zpět začátek
  25. přednáška 24.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