Co bylo PRG005 Neprocedurální programování X

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

Zpět začátek

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

Zpět začátek

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í

Zpět začátek

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

Zpět začátek

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í.

Zpět začátek

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

Zpět začátek

přednáška 5.dubna

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í, 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

Zpět začátek

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í

Stáhněte si: A Gentle Introduction to Haskell

Zpět začátek

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 | q₁ , q₂ , ... ,q_r ],
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

Zpět začátek

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

Zpět začátek

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

Zpět začátek

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

Zpět začátek

přednáška 24.května

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

PRG005 Neprocedurální programování

Co bylo na přednáškách - paralelka X - úterý 10:40 S3