Zpět PRG005
PRG005 Programování II - pondělí 12:20 M1
Co bylo na přednášce
- přednáška 14.října
- Náplň kursu, podmínky pro zápočet, zkouška.
- Neprocedurální 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.
- Jednoduhé predikáty pro práci seznamy, např. :
- member(?Co,?Kde)
- prvni_prvek(?Co,?Ceho)
- posledni_prvek(?Co,?Ceho)
- zřetězeni seznamů conc(?L1,?L2,?L3)
- obracení seznamů obrat(?L,?ObrL) v kvadratickém čase
- Problémy k rozmyšlení
- zřetězení seznamů v lineární čase
- prostřední prvek seznamu
zpět na začátek
přednáška 21.října
- Nalezení prostředního prvku seznamu.
- Lineární obracení seznamu (reverse_append) pomocí akumulátoru.
- Syntaxe Prologu (proměnné, atomy, řetězce, struktury, klausule, fakty, pravidla, procedury, ... ).
- Unifikace.
- Algoritmus interpretu Prologu (unifikace + backtracking).
- Deklarativní a procedurální význam programu v Prologu. Deklarativně správná procedura je procedurálně parciálně správná (může se zacyklit a nedat správnou odpověď, ale nemůže dát špatnou odpověď).
- Procedura predek a její modifikace vzniklé permutací klausulí a cílů v jejich tělech (rozmyslet).
- Aritmetika v Prologu.
- Největší společný dělitel, délka seznamu, generování seznamu obsahujícího aritmetickou posloupnost.
zpět na začátek
přednáška 4.listopadu
- Opakování aritmetiky a algoritmu zodpovídání Prologovského dotazu.
- Quicksort. Rozmyslet implementaci bez (explicitního volání) zřetězování seznamu.
- Slévání dvou uspořádaných seznamů do jednoho. Co je deterministická procedura (deterministický predikát).
- Nalezení následující permutace v lexikografickém uspořádání.
- Reprezentace binárního stromu - buď atom nil jako reprezentace prázdného stromu
nebo term t(Levy,Koren,Pravy), který konstruuje neprázdný strom z Korene, Leveho a Praveho podstromu.
- Tisk binárního stromu pomocí indentace.
- Test zda je daný term prvkem stromu.
- Průchod stromem do hloubky a do šířky.
- Vkládání do binárního vyhledávacího stromu (obvyklý algoritmus vkládající do listu) a proč nemůže být použito obecně pro vypouštění.
- Vypouštění z binárního vyhledávacího stromu (obvyklý algoritmus záměny kořene např. nejmenším z větších).
- Vkládání do kořene a jeho použití pro konstrukci vkládání, které je schopno také vypouštět.
- Krabičkový model. Brány CALL, EXIT, FAIL, REDO.
- Princip ladění. Predikáty trace/0, notrace/0, spy/1, nospy/1. Ukázka možného výstupu při ladění.
zpět na začátek
přednáška 11.listopadu
- consult a reconsult.
- Předdefinované predikáty var/1, nonvar/1, number/1, atom/1, atomic/1.
- Předdefinované predikáty pro "rozebírání a skládání" prologovských termů:
name/2, functor/3, arg/3, =.. a příklady jejich užití.
- Quicksort - varianta bez explicitního zřetězení.
- Rozdílové seznamy jako příklad neúplně definovaných datový struktur.
Zřetězení rozdílových seznamů.
Převody mezi kanonickou reprezentací seznamů a rozdílovými seznamy.
Quicksort na rozdílových seznamech.
- Různé implementace "rozvinutí" seznamu - rozvin/2.
?- rozvin([a,[b,[ c,[1,[yy,j],e],5,],8],89,aa] , X ).
X = [a,b,c,1,yy,j,e,5,8,89,aa].
- Operátor řezu. Jednoduché příklady použití.
- Příklady predikátů pro třídění seznamů (bublinkové třídění, třídění výběrem, zatřiďování).
- Operátor řezu zničil deklarativní sématiku čistého (pure) Prologu.
- Negace.
- Vstup a výstup z/do streamu (souboru nebo konzole).
Otvírání, zavírání, zjištění aktuálního streamu.
Vstup/výstup termů resp. znaků.
procedura pro kopírování jednoho streamu do druhého.
- "Věčný" cyklus repeat .... fail a jeho ukončení.
zpět na začátek
přednáška 18.listopadu
- Rovnosti a nerovnosti v Prologu:
unifikace
|
= , \=
|
identita
|
== , \==
|
aritmetika
|
=:= , =\=
|
- Operátory. Příkaz op/3, asociativita, priorita operátoru. Jednoduché příklady použití operátorů.
- Ukázky programů v Prologu:
- 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ů. bagof pomocí assert a retract.
- Úvod do LISPu.
zpět na začátek
přednáška 25.listopadu
Probírá se dialekt Scheme jazyka LISP. 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: faktoriál rekursivně a iterativně, efektivní umocňování, odmocnina newtonovou metodou.
- Funkce jako parametry.
- Formy lambda a let, lokalita ve formě let.
- Dvojice : formy cons, car, cdr. Implementace, alternativní konstrukce dvojic.
- Seznamy, forma list, příklady jednoduchých funkcí pro práci se seznamy.
- Forma quote.
- Datová struktura = konstruktory + selektory (+metody).
- Implemenace zlomku jako příklad nutnost "inteligentních" konstruktorů a selektorů.
- Binární strom:
- konstruktory Nulltree, Tree(L,V,R)
- test nulltree?
- selektory Root, Left, Right
- Výpis listů stromu do seznamu (bez nutnosti zřetězovat seznamy).
zpět na začátek
přednáška 2.prosince
Výklad jazyka Haskell na této přednášce poměrně těsně sledoval výklad v publikaci
"A Gentle Introduction to Haskell 98".
Probrali jsme přibližně látku obsaženou na stránkách 1 - 18 tohoto materiálu.
- Haskell jako funkcionální jazyk s typovou kontrolou.
- Definice funkce, typová specifikace funkce.
- Uživatelské definice typů. Typové a datové kostruktory.
Typová synonyma.
- Polymorfické typy. Seznamy, (n)tice - tuples.
- Definování seznamů pomocí generátorů a stráží. Výrazy pro aritmetické posloupnosti.
- Lambda abstrakce.
- Převod infixového operátoru na binární funkci a zpět. Řezy (sections). Deklarace fixity.
- Funkce v Haskellu nejsou striktní.
Objekt boot. Líné (lazy, by need) vyhodnocování funkcí.
- Nekonečné datové struktury. Příklad fibonacciovy posloupnosti.
- Error funkce.
- "Mečování" parametrů, speciální vzorky: as-pattern, žolík.
- Case výraz a způsob pořadí "mečování parametrů" (a jeho případný vliv na definovanou funkci).
zpět na začátek
přednáška 9.prosince
- Lazy pattern ~p a příklady jeho použití.
- Výraz let a konstrukce where.
- "Dvojrozměrná" syntaxe Haskellu.
- Jednoduché příklady definic funkcí.
- Abstrakce v Haskelu
- pomocí výrazu let a konstrukce where
- pomocí definicí funkcí
- pomocí datové abstrakce
- pomocí funkcí vyšších řádů
(např. funkce map a fold)
- pomocí líného (lazy) vyhodnocování
zpět na začátek
přednáška 16.prosince
přednáška 8.ledna
Zpět PRG005