PRM046 Co bylo

Domluvili jsme se, že nebudeme důsledně rozlišovat mezi přednáškou a cvičením.

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
přednáška 6.dubna odpadá
7. přednáška 13.dubna
8. přednáška 20.dubna
9. přednáška 27.dubna
10. přednáška 4.května
11. přednáška 11.května
12. přednáška 18.května
13. přednáška 25.května

1. přednáška a cvičení 23.února
   • 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
     vypuštění a vládání prvku ze a do seznamu,
     permutace seznamu, zřetězení seznamů,
   • Unifikace
   • Na rozmyšlenou:
     • Prostřední prvek seznamu (bez aritmetiky) -lepší řešení.
     • Starší bratr, nejstarší bratr, starší sestry, mladší bratři.
2. přednáška a cvičení 3.března
   • Opakování.
   • Definice seznamu a notace pro jejich zápis.
   • Jednoduché predikáty pro práci se seznamy, např.
     prvek, první, poslední prvek seznamu
     vypuštění a vládání prvku ze a do seznamu,
     permutace seznamu, zřetězení seznamů,
   • Starší bratr, nejstarší bratr, sestry.
   • Otáčení seznamů v kvadratické čase.
   • Na rozmyšlenou:
     • Prostřední prvek seznamu, resp. rozdělení seznamu na první a druhou půlku (bez aritmetiky)
       
       návod
       • ukousávání zepředu a zezadu
       • současné ukousávání rychlostí jedna a dva
       • zjištění seznamu poloviční délky a následné zkrácení o stejnou délku
     • Otáčení seznamu v lepším než kvadratickém čase.
Zpět začátek
3. přednáška a cvičení 9.března
   • Prostřední prvek seznamu, resp. rozdělení seznamu na první a druhou půlku (bez aritmetiky)
     
     návod
     • ukousávání zepředu a zezadu
     • současné ukousávání rychlostí jedna a dva
     • zjištění seznamu poloviční délky a následné zkrácení o stejnou délku
   • Otáčení seznamu v lineárním čase pomocí predikátu revers_append/3
   • Obecné rysy procedur s akumulátorem
   • Rozdělení seznamu na dva seznamy prvků na lichých/sudých místech původního seznamu
   • Výskyt seznamu v jiném seznamu
   • Syntaxe Prologu (proměnné, atomy, řetězce, struktury, klausule, fakta, pravidla, procedury, ... ).
   • Unifikace - hledání nejobecnější substituce, po které termy "mečují"
   • Naivní rekursivní algoritmus pro unifikaci se může zacyklit - X = f(X)
   • Predikát býti seznamem
   • Reprezentace matice jako seznamu řádkovych seznamů,
     obdelnikova(Matice), ctvercova(Matice), hlDiag(Matoce,HlDiag), bytiPrazdnouMatici(Matice),
     otacení matice o 90 stupňů, spirala(Matice, Spirala)
   • Překladač SWI
     ukázka práce, consult, ladění - predikáty trace/0, notrace/0, spy/1, nospy/1
     krabičkový model výpočtu, brány CALL, EXIT, FAIL, REDO,
     standardní a grafický debugger
   • Na rozmyšlenou:
     • Rozdělení seznamu na první, druhou a třetí třetinu (bez aritmetiky)
     • Rozdělení seznamu na tři seznamy v nichž se liší počet modrých prvků nejvýše o jeden
       (bez aritmetiky, předpokládáme, že máme predikáty modry/1 a nemodry/1)
     • Predikát oloupej(Matice, Slupka, Pecka)
4. přednáška a cvičení 16.března
   • vypuštění všech výskytů daného prvku ze seznamu
     vypuštění prvního výskytu daného prvku ze seznamu (s úspěchem resp. neúspěchem,když tam prvek není)
   • Predikát oloupej(Matice, Slupka, Pecka)
   • Rozdělení seznamu na první, druhou a třetí třetinu (bez aritmetiky)
   • Rozdělení seznamu na tři seznamy v nichž se liší počet modrých prvků nejvýše o jeden
     (bez aritmetiky, předpokládáme, že máme predikáty modry/1 a nemodry/1)
   • Aritmetika - predikát is a aritmetické relační operátory
     =:= , =/= , < , > , <= , >=
   • největší společný dělitel dvou čísel
   • délka seznamu, minimum ze dvou čísel, minimum ze seznamu čísel, řešení pomocí akumulátoru
   • maximální rostoucí začátek seznamu
   • quicksort s hlavou jako pivotem
   • vektor inverzí k dané permutaci
   • Na rozmyšlenou:
     • Zkusit odstranit zřetězení seznamů z quicksortu
     • počet inversí v dané permutaci
     • predikát byti_vektorem_inversi_perm_delky_N(Vekt,N)
     • najít permutaci k danému vektoru inversí
     • Nalézt k číslům N a K K-tou permutaci délky N
Zpět začátek
5. přednáška a cvičení 23.března
   • následující permutace k dané permutaci (v lexikografickém uspořádání)
   • Kolikátá je daná permutace v lexikografickém uspořádání
   • Binární stromy - jedna možná reprezentace
   • Seznam listů k danému stromu - verze s konkatenací a bez ní
   • Vyhledávání, vkládání a vypuštění prvku z binárního vyhledávacího stromu.
   • Vkládání prvku do kořene binárního vyhledávacího stromu
   • Vypuštění prvků zadaného intervalu z binárního vyhledávacího stromu.
   • Na rozmyšlenou:
     • Zkusit odstranit zřetězení seznamů z quicksortu
     • predikát byti_vektorem_inversi_perm_delky_N(Vekt,N)
     • najít permutaci k danému vektoru inversí
     • Nalézt k číslům N a K K-tou permutaci délky N
     • Vkládání do binárního stromu, které může být použito i pro vypuštění
Zpět začátek
6. přednáška a cvičení 30.března
   • nalezení permutace k danému vektoru inversí
   • Nalezení k číslům N a K K-té permutace délky N
   • vkládání do kořene binárního vyhledávacího stromu
   • Vkládání do binárního stromu, které může být použito i pro vypuštění
   • Vytváření dokonale vybalancovaného binárního vyhledávací stromu z prvních N prvků rostoucího seznamu
   • "Smotávání" matice ze známé spirály - použití datové struktury z anonymních proměnných,
     jak stejnou myšlenku použít v procedurálních jazycích
   • Deklarativní a operační sémantika prologovské procedury
   • Deklarativně správná procedura v čistém (pure) Prologu je parciálně správná v operačním smyslu
   • Rozmyslet: chování čtyř (deklarativně ekvivalentních) variant procedury predek
   • standardní predikáty var/1 a nonvar/1
   • rozdílové seznamy jako příklad neúplně definované datové struktury
     zřetězení rozdílových seznamů v konstatním čase
   • operátor řezu = typické použití
   • predikát bubblesort/2
   • řez "ničí" deklarativní sémantiku programu
   • negace
   • není vhodné programovat podmínku pomocí negace
   • "Edinbugrský" model vstupu a výstupu: otvírání, zavírání, zjištění aktuálního streamu, Vstup/výstup termů resp. znaků.
     
     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 ralizována s drobnými odchylkami).
   • Na rozmyšlenou:
     • Zkusit odstranit zřetězení seznamů z quicksortu
     • Vkládání do binárního stromu, které může být použito i pro vypuštění
     • převod seznamů na rozdílové a zpět
     • Vytvoření seznamu prvků stromu v pořadí podle jejich vzdálenosti od listů (a je-li stejná, pak odleva do prava)
Zpět začátek
7. přednáška a cvičení 13.dubna
   • Opakování: rozdílové seznamy,
     převod seznamů na rozdílové a zpět
   • Vytvoření seznamu prvků stromu v pořadí podle jejich vzdálenosti od listů (a je-li stejná, pak odleva do prava)
   • Opakování řez a negace
   • koncepce programu Eliza
   • Zjednodušování výrazů - ukázkový příklad
   • Opakování vstup a výstup jednoduché příklady
   • predikát repeat a jeho použití pro programování cyklů
   • prezence
   • Na rozmyšlenou:
     Zůstává:
     • Odstranění zřetězení seznamů z quicksortu - uvědomte si souvislost s rozdílovými seznamy
     • Vkládání do binárního stromu, které může být použito i pro vypuštění
     Vyberte si problém podle vlastního výběru
   • prezence

   Vytiskněte si materiál o předdefinovaných formách jazyka SCHEME
Zpět začátek
8. přednáška a cvičení 20.dubna
   • Součtové seznamy
   Dialekt LISPu - SCHEME (k Prologu se ještě vrátíme)
   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.
   • Lokální define v Scheme - není přiš obvyklé.
   • 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) .
   • Příklad struktury Binární strom:
     • konstruktory Nulltree, Tree(L,V,R),
     • test nulltree?
     • selektory Root, Left, Right
   • Výpis listů stromu do seznamu
   • Vytvoření dvojice
     
     • dokonale vybalancovaný strom z prvních N prvků rostoucího seznamu
     • zbytek seznamu
   • Nutnost definovat "inteligentní" konstruktory resp. selektory
   • Rozmyslet:Příklady funkcí v Lispu
     • Výpis listů stromu do seznamu (bez nutnosti zřetězovat seznamy).
     • výška stromu
     • Dělení čísel reprezentovaných jako seznam binárních cifer
       zkuste i v Prologu
9. přednáška a cvičení 27.dubna
   • výška stromu v SCHEME
   • mobil - datová reprezentace
     funkce kontrolující vyváženost (nemá-li být nepřijatelně neefektivní musí vracet dvojici (vyváženost a váha)
     rozmyslet bezpečnost mobilu
   Zpět k Prologu
   • predikátu name a =.., jejich použití
   • predikáty bagof a setof, použití ^ jako !existenčního kvantoru"
   • predikáty assert, retract, retractall
     namodelování globální proměnné, vliv na efektivitu programu
   • "Wirthův" program pro osm dam
   • řešení algebrogramu hrubou silou
   • quicksort bez konkatenace a quicksort na rozdílových seznamech "jedno jsou"
   Haskell
   • Haskell - literatura a překladač na adrese
   • Doporučeno ke stažení: A Gentle Introduction to Haskell
   • Haskell jako funkcionální jazyk s typovou kontrolou.
   • Definice funkce, typová specifikace funkce.
   • Uživatelské definice typů. Typové a datové kostruktory - příklady.
     Typová synonyma.
     Polymorfické typy. Seznamy, (n)tice - tuples.
   • Lambda abstrakce.
   • Převod infixového operátoru na binární funkci a zpět. Řezy (sections).
   • několik jednoduchých příkladů
   • Funkce map, funkce skládání fukncí
10. cvičení a přednáška 4.května
    • Haskell - opakování
    • Převod infixového operátoru na binární funkci a zpět. Řezy (sections). Deklarace fixity.
    • Zápis definice funkce pomocí case výrazu, Stráže v definicích funkcí
    • if výraz
    • Konstrukce let a where, dvojrozměrná syntaxe
    • Sémantika výrazů tvaru [ e | q₁ , q₂ , ... ,q_r ],
      jednoduché příklady použití.
    • Jednoduché příklady se seznamy
    • Funkce v Haskellu nejsou striktní.
      Objekt boot. Líné (lazy, by need) vyhodnocování 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í prametry jako "vzorky" - patterns:
      • proměnné
      • As-patterns - '@'
      • žolík - '_'
      • datový konstruktor
      • "aritmetický parametr" - "n+k"
      Příklady
    • Příklady nekonečných termů
      Fibonnaciova posloupnost, aritmetická posloupnost, Pythagorejská čísla
    • Několik poznámek o samoreflexi, Alhambře, Esherovi a jeho obrazech, roli nekonečna v matematice a pod.
    • Rozmyslet: Mocninné řady jako příklad nekonečných termů
      
      • Součet a součin mocninných řad
      • derivace a n-tá derivace mocninné řady
    • O zkouškách
11. přednáška a cvičení 11.května
    • Mocninné řady jako příklad nekonečných termů
      Součet a součin mocninných řad, derivace a n-tá derivace mocninné řady
    • další příklady
    • Binární stromy - definice typu
      • seznam listů s konkatenací a bez ní
      • kopie stromů, který má v uzlech navíc počet prvků příslušného podstromu
      • vypouštění z binárného vyhledávacího stromu
      • konstrukce funkce, která vypustí z binárného vyhledávacího stromu všechny prvky zadané predikátem, jako parametr
    • Třídy v Haskelu jako analogie pojmu rozhraní z Javy,
      použití ve specifikaci typu funkce
    • Dědičnost (i vícenásobná)
    • Příklady standardních tříd Eq a Ord
12. přednáška a cvičení 11.května
    • Opakování: třídy v Haskellu, mečování parametrů
    • lazy parametry
    • pole v Haskellu
    • Ovlivňování efektivity prologovských programů - přehled technik
    • Dva příklady - zkuste vyřešit a poslat mi řešení mailem - do středy
      1. Vytvořte program, který realizuje šifrování a dešifrování šifrou "nový hrabě monte Christo"
      2. Najděte program, který ke dvěma vstupním číslům
         M počet misionářů, K počet kanibalů
         najde nejkratší cestu, jak se mohou pomocí loďky pro dva bezpečně přepravit na druhý břeh
         (případně to nemusí jít - pokud by na některém z břehů v některém okamžiku bylo více kanibalů než misionářů, kanibalové by misionáře snědli).
13. přednáška a cvičení 25.května
    • Abstrakce v Haskellu
    • Různé implementace funkce počítající faktoriál
    • Logika za Prologem:
      logická pravdivost, splnitelnost, klausulární tvar formule, Skolemizace, ke každé formuli existuje fomule v klausuralním tvaru, která je splnitelná právě když je splnitelná původní formule,
      Herbandovo universum, Herbrandova věta, základní rezoluční metoda, algoritmus unifikace, obecná rezoluční metoda,
      Hornovy klausule a Prolog,