PRM046 Co bylo na přednáškách a cvičeních

Domluvili jsme se, že i cvičení může posunovat látku kupředu, nejen procvičovat látku z přednášky. Proto zde budeme uvádět i takový obsah cvičení

1. přednáška 24.února
2. přednáška 3.března
3. přednáška 10.března
4. přednáška 17.března
5. přednáška 24.března
6. přednáška 31.března
7. přednáška 7.dubna
8. přednáška 14.dubna
9. přednáška 21.dubna
10. přednáška 28.dubna
11. přednáška 5.května
přednáška a cvičení 12.května odpadají
12. přednáška 19.května
13. přednáška 26.května

1. přednáška 24.ú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á.
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 senamy, 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ů,
     otáčení seznamu v kvadratickém čase, atd.
   • Syntaxe Prologu (proměnné, atomy, řetězce, struktury, klausule, fakty, pravidla, procedury, ... ).
   • Unifikace
   • Algoritmus interpretu Prologu (unifikace + backtracking).
   • Na rozmyšlenou:
     • Prostřední prvek seznamu (bez aritmetiky).
     • Otáčení seznamu v lepším než kvadratickém čase.
     • Starší bratr, nejstarší bratr, starší sestry, mladší bratři.
Zpět začátek
3. přednáška a cvičení 10.března
   • Při zadaných faktech typu rodina(Otec,Matka,DetiOdNejstrsihoKNejmladsimu), muz(Kdo), zena(Kdo)
     vytvorit predikaty
     nejstBratr(Kdo, Koho), starsiBratr(Kdo, Koho), sestry(Koho, SeznamSester), bratranec(Kdo, Koho), vsechnySestrenice(Koho, SeznSetrenic), atp.
   • Tři řešení půlení seznamu - jedno neefektivní
   • predikáty bytiseznamem(Co), prostySeznam(Zceho,Co), bytivybranou posloupnosti(Zceho, Vybr), zip(S1,S2,SezipS1aS2), atp
   • Reprezentace matice jako seznamu řádkovych seznamů,
     hlDiag(Matoce,HlDiag), bytiPrazdnouMatici(Matice)
   • Na rozmyšlenou:
     • Otáčení seznamu v lepším než kvadratickém čase.
     • otočení matice o 90 stupňů, slupka(Matice,Slupka,Pecka), spirala(Matice,Spirala),
4. přednáška a cvičení 17.března
   • predikát "reverse_append" - otáčení seznamu v lineárním čase pomocí akumulátoru,
     pojem akulátoru
   • několik predikátů pracujících s maticemi:
     otočení matice o 90 stupňů, slupka(Matice,Slupka,Pecka), spirala(Matice,Spirala), byti_obdelnikovou(Mat),
   • Aritmetika, predikát is,
     aritmetické relace =:= , =/= , ‹ , › , ‹= , ›=
   • Jednoduché aritmetické predikáty
     • největší společný dělitel dvou čísel
     • délka seznamu
     • maximum dvou čísel, maximum z prvků seznamu čísel
     • Maximální rostoucí začátek seznamu
   • Na rozmyšlenou:
     • Počet inverzí v seznamu čísel
     • následující permutace v lexikografickém uspořádání
     • quicksort s hlavou jako pivotem
Zpět začátek
5. přednáška a cvičení 24.března
   • Počet inverzí v seznamu
   • Následující permutace
   • Součtové seznamy
   • "Smotávání" matice ze známé spirály - použití datové struktury z anonymních proměnných
   • Rozdílové seznamy jako příklad datové struktury s s volnou proměnnou, jejich zřetězování v konstatním čase
   • Deklarativní a operační sémantika prologovské procedury
   • Deklarativně správná procedura v čisém (pure) Prologu je parciálně správná v operačním smyslu
   • Rozmyslet: chování čtyř (deklarativně ekvivalentních) variant procedury predek
   • Binární stromy - jedna možná reprezentace
   • 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
   • Rozmyslet: quicksort s hlavou jako pivotem
   • Princip možné implemenace programu Eliza (rozhovor s pacientem psychoanalitika)
6. přednáška a cvičení 31.března
   • Vytvoření seznamu listů daného stromu - verze bez konkatenace
   • Vytvoření seznamu prvků stromu v pořadí podle jejich vzdálenosti od listů (a je-listejná, pak odleva do prava)
   • Quicksort
   • Predikáty consult/1, reconsult/1, halt/0,
   • 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.
   • Na rozmyšlenou: Mečování seznamů obsahujících písmena a "žolíky ? a *"
Zpět začátek
7. cvičení a přednáška 7.dubna
   • Qiucksort bez konkatenace
   • Predikát flatten
   • Mečování seznamů obsahujících písmena a "žolíky ? a *
   • Průchody stromem do hloubky a do šířky
   • Standardní predikáty var/1, nonvar/1, atom/1, atomic/1, number/1, a pod.
   • Standardní predikáty pro analýzu a syntézu termů:
     name/2, functor/3, arg/3, =..   a příklady jejich užití.
   • Rovnosti a nerovnosti v Prologu (==, /==, =, /=, =:=, =/= )
   • Operátor řezu
   • Třídění seznamu vkládáním
   • Třídění seznamu výběrem
   • Negace
   • Použití negace a řezu
   • Řez ničí deklarativní sémantiku
   • Jednoduchá procedura řešící algebrogram
   • fail, repeat, cyklus repeat .... fail
   • "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).
   • Příklady jednoduchého vstupu a výstupu.
   • Větvení výpočtu pomocí středníku a explicitního použití operátoru = na pravé straně klauzule.
   • Kopírování souboru
   • Prezence
   • Na rozmyšlenou:
     1. Průchody grafem do hloubky a do šířky
     2. Hledání všech pozic N nezávislých dam na šachovnici N x N
Zpět začátek
8. cvičení a přednáška 14.dubna
   • Průchod grafem do hloubky a a do šířky
   • Práce s permutacemi
     • Různé reprezentace: vektor obrazů, seznam netriviálních cyklů, vektor inverzí
     • převody mezi reprezentacemi - pomocný formát zobrazení jako seznam dvojic
     • umocňování permutací
     • Rozmyslet další predikáty
   • for cyklus
   • jednoduchý příklad na zjednodušování výrazů - součet absolutních členů
   • příklad na zjednodušování výrazů - součet členů typu +-K*A, kde K je číslo
   • definování operátorů, predikát op/3, asociativita a priorita operátorů
     příklady použití
   • predikáty ovlivňující databázi: assert/1, retract/1, retractall/1
     a jejich vliv na efektivitu programu
   • modelování "globálních" proměnných pomocí assert a retract
9. cvičení a přednáška 21.dubna
   • Implementace Dijkstrova algoritmu v Prologu
   • Predikáty bagof a setof, "existenční kvantifikátor ^ ", jednoduché příklady užití.

   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í, 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.
10. cvičení a přednáška 28.dubna
    • Implementace Dijkstrova algoritmu v Prologu
    Lisp
    • Forma quote.
    • Datová struktura = konstruktory + selektory (+metody).
    • Implemenace zlomku jako příklad nutnost "inteligentních" konstruktorů a selektorů.
    • Jednoduché příklady na práci se seznamy
    • Datobvá struktura strom
    • Rozmyslet:
      Dodělat příklady z předášky.
      Konstrukce dokonale vybalancovaného binárního vyhledávacího stromu z ze začátku (zadané dély) rostoucího seznamu.
11. cvičení a přednáška 5.května
    • Příklady v Lispu
    • Několik verzí procedury počítající Fibonnaciho čísla, iterační verze
    • Rekapitulace technik, které má programátor v Prologu k dispozici k (pozitivnímu) ovlivňování složitosti programů.
12. přednáška 19.května
13. přednáška 26.května