Zpět PRG005

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
  13. 18. května rektorský den
  14. 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
  2. Zpět začátek
  3. 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
  4. Zpět začátek
  5. 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í
  6. Zpět začátek
  7. 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
  8. Zpět začátek
  9. 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).
  10. Zpět začátek
  11. 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
  12. Zpět začátek
  13. přednáška 7.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 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 | q1 , q2 , ... ,qr ],
      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í
  16. Zpět začátek
  17. 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ů
  18. Zpět začátek
  19. 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
  20. Zpět začátek
  21. 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)
  22. Zpět začátek
  23. 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
  24. Zpět začátek
  25. 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
  26. Zpět začátek