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

přednáška 24.února

O zodpovědném přístupu rozvrhové komise, která nerozvrhla obě paralelky s tím, že živých studentů je maximálně 120
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.
Dotazy, proměnné, anonymní proměnná.
Fakta, pravidla, klausule
Definice seznamu, syntaktické konvence zápisu.
Jednoduché predikáty pro práci se seznamy.
- prvek(Co, Ceho).
- prvníPrvek(Co, Ceho).
- posledniPrvek(Co,Ceho)
- slévání dvou seznamů do jednoho rozdel(Co,Liche,Sude)/li>
Rozmyslet:
- 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
  nemáme k dispozici aritmetiku

Přednášku jsem omylem ukončil cca o 20 minut dřív. Pokud by se něco podobného ještě někdy stalo, upozorněte mne na to.
Na oplátku se pokusím respektovat i případná upozornění na přetažení času.

Zpět začátek

přednáška 3.března

Nejnovější zprávy z rozvrhového bojiště
Syntaxe Prologu (proměnné, atomy, řetězce, struktury, klausule, fakty, pravidla, procedury, ... ).
operátor středník
Unifikace, příklady
býti seznamem
vypouštění prvku ze seznamu
spojování seznamu conc(Zacatek,Konec,Spojeni)
prvek pomocí conc a del
permutace(Seznam,PermutovanySeznam)
Hledání prostředního prvku:
- ukousáváním zpředu a ze zadu - jen idea zkuste sami
- hledání seznamu poloviční délky a následné umazaní vhodného počtu prvků - jen idea zkuste sami
- rozdělení seznamu na prvním a druhou polovinu pomocí současného ukousávaní dvou a jednoho prvku ze dvou exemplářů původního seznamu
otáčení seznamu v kvadratickém čase
zkuste udělat v lineárním
další jednoduché příklady na seznamy

Zpět začátek

přednáška 10.března

Algoritmus interpretu Prologu (unifikace + backtracking).
reverse-append otáčení v lineárním čase - idea akumulátoru
používání prefixů +, - a ? u parametrů v komentářích
matice jako seznamy řádkových seznamů
- diag(+CtvercovaMatice, -Diagonala)
- prazdnamatice(+Matice)
- rozmyslet
  - 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)
rozdílové seznamy jako příklad neúplně definovaných datových struktur
konkatenace v konstatním čase
myšlenka převodu na běžné seznamy - ještě se k tomu vrátíme
součtové seznamy jako příklad jiné reprezentace seznamů
rozmyslet základní operace s nimi
Aritmetika, predikát is,
aritmetické relace =:= , =/= , ‹ , › , ‹= , ›=
Jednoduché aritmetické predikáty
největší společný dělitel dvou čísel, délka 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í

Zpět začátek

přednáška 17.března

Quicksort bez konkatenace, srovnej zápis s parametrem navíc a s rozdílovými seznamy
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í 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)
zviditelnění stromu pomocí indentace
listy(+Strom, -SeznamListu) implementace s kontatenací, rozmyslet bez ní
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
- (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í
"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
průchod stromem do hloubky a do šířky

Zpět začátek

přednáška 24.března

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
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
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.
Řešení algebrogramu
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ů
ještě se k tomu vrátíme
Kopírování souboru

Zpět začátek

přednáška 31.března

Opakování - operátor řezu, negace
Příklady programování cyklů v Prologu
( "věčný" cyklus repeat .... fail a jeho ukončení, "repeat until" cyklus , "for" cyklus ).
opakování Edinburgského modelu vstupu a výstupu
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 ralizována s drobnými odchylkami).

Na co se hodí Prolog
Princip možné implemenace programu Eliza (rozhovor psychoanalitika s pacientem)
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í.
Predikáty modifikace databáze, assert, asserta, assertz, retract, retractall.
Vhodnost resp. nevhodnost použití těchto příkazů.
Procedury realizující jednoduchý algoritmus pro zjednodušování aritmetických výrazů

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 7.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
Rozmyslet: Datová reprezentace mobilu, testy na vyváženost a bezpečnost.

Zpět začátek

přednáška 14.dubna

Na přednášce pravděpodobně bude

Ú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í
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
Převod infixového operátoru na binární funkci a zpět. Řezy (sections).
fixity deklarace

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

Zpět začátek

přednáška 21.dubna

dost se mi nepovedla

Ještě naskok k Prologu

"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
Ovlivňování efektivity Prologovských programů.
Několik implemenací výpočtu Fibonnaciovy posloupnosti, iterativní výpočet.
Haskell - opakování
if výraz
Konstrukce let a where, dvojrozměrná syntaxe Haskellu
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
ještě se k tomu vrátíme

Zpět začátek

přednáška 28.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
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 patterns, příklady
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 petenciá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 a n-tá derivace mocninné řady
Prvočísla pomocí Erathostenova síta.
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ů
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ů

Zpět začátek

přednáška 5.května

Na přednášce pravděpodobně bude

poznámka k preludu
Abstrakce v Haskellu
Pole v Haskellu
Násobení matic
Různé implementace funkce počítající faktoriál
......

Zpět začátek

přednáška 12.května

bude suplována a věnována příkladům v Haskellu

Zpět začátek

přednáška 9.ledna

na základě dohody se obsah může změnit

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

Zpět začátek

PRG005 Neprocedurální programování

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