PRG005 Neprocedurální programování

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

Hromadná konzultace k předmětu PRG005 se koná v úterý 16.ledna 2007 od 8:15 v posluchárně S9.

pokud alespoň trochu můžete, choďte raději na přednášku v pátek,
v úterý nebylo dost míst ani ke stání

Cvičení začínají druhý týden výuky

Věnujte pozornosti vyhlášce o rozdělení studentů do skupin na semináře

1. přednáška 3.října
2. přednáška 10.října
3. přednáška 17.října
4. přednáška 24.října
5. přednáška 31.října
6. přednáška 7.listopadu
7. přednáška 14.listopadu
8. přednáška 21.listopadu
9. přednáška 28.listopadu
10. přednáška 5.prosince
11. přednáška 12.prosince
12. přednáška 19.prosince
13. přednáška 9.ledna

1. přednáška 3.října
   • 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)
     • spojování seznamu conc(Zacatek,Konec,Spojeni)
     • prvek pomocí conc
     • permutace(Seznam,PermutovanySeznam)
   • 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
Zpět začátek
2. přednáška 10.října
   • Syntaxe Prologu (proměnné, atomy, řetězce, struktury, klausule, fakty, pravidla, procedury, ... ).
   • operátor středník
   • Unifikace, příklady
   • Algoritmus interpretu Prologu (unifikace + backtracking).
   • 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ů
     • 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
   • reverse-append otáčení v lineárním čase - idea akumulátoru
   • matice jako seznamy řádkových seznamů
     • diag(+CtvercovaMatice, -Diagonala)
     • rozmyslet
       • test zda matice je obdélniková
       • test zda matice je čtvercová
       • otáčení matice o 90 stupňů
Zpět začátek
3. přednáška 17.října
   • permutace(Seznam,PermutovanySeznam)
   • Aritmetika, predikát is,
     aritmetické relace =:= , =/= , ‹ , › , ‹= , ›=
   • Jednoduché aritmetické predikáty
     největší společný dělitel dvou čísel, délka seznamu
   • následující permutace v lexikografickém uspořádání
   • 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í
   • Algoritmus quicksortu, implementace se zřetězením a rozmyslet bez něho
   • 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á.
     Ještě se k tomu vrátíme
Zpět začátek
4. přednáška 24.října
   • opakování
     deklarativní sémantika prologovské procedury
     deklarativně správná procedura je parciálně správná
   • 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.
   • průchod stromem do hloubky a do šířky
   • 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,
     jak stejnou myšlenku použít v procedurálních jazycích
   • 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
   • Princip možné implemenace programu Eliza (rozhovor psychoanalitika s pacientem)
   • Na co se hodí Prolog
Zpět začátek
5. přednáška 31.října
   • 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é"
   • Standardní predikáty atom/1, var/1, nonvar/1.
   • Řešení algebrogramu
   • Hledání všech možností pozic N nezávislých dam na šachovnici N x N
   • 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í.
   • "Edinburgský" 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).
   • Kopírování souboru
Zpět začátek
6. přednáška 7.listopadu
   • Opakování vstupy a výstupy
   • Vstup a výstup znaků
   • Příklady programování cyklů v Prologu
     ( "věčný" cyklus repeat .... fail a jeho ukončení, "repeat until" cyklus , "for" cyklus ).
   • negace
   • Definice operátorů, standardní predikát op/3.
   • Procedury realizující jednoduchý algoritmus pro zjednodušování aritmetických výrazů
   • 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ů.

   Na příští přednášce začneme probírat jazyk Scheme, vytiskněte si jeho syntaxi
Zpět začátek
7. přednáška 14.listopadu
   K Prologu se ještě vrátíme, vzhledem k potřebám cvičení přejdeme k Lispu

   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.
   • 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).
   • Příklad struktury Binární strom:
     • konstruktory Nulltree, Tree(L,V,R),
     • test nulltree?
     • selektory Root, Left, Right
   • Rozmyslet: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.
   • prezence
Zpět začátek
8. přednáška 21.listopadu
   • Implemenace zlomku jako příklad nutnost "inteligentních" konstruktorů a selektorů.
   • Jednoduché příklady funkcí v Lispu nad datovou strukturou binární strom:
     • Výpis listů stromu do seznamu (bez nutnosti zřetězovat seznamy).
     • výška stromu
   • Komentář k úlohám o mobilu
   Ještě naskok k Prologu
   • Ovlivňování efektivity Prologoský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é kostruktory. Typová synonyma. Polymorfické typy. Seznamy,
Zpět začátek
9. přednáška 28.listopadu
   • Haskell - opakování
   • 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
     opravte chybu, která byla na slidu !!
   • Lambda abstrakce.
   • Práce s fukcemi více proměnných - curryfikace
   • Převod infixového operátoru na binární funkci a zpět. Řezy (sections).
   • 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í prametry jako "vzorky" - patterns:
     • proměnné
     • As-patterns - '@'
     • žolík - '_'
     • datový konstruktor
     • "aritmetický parametr" - "n+k"
     Příklady
   • Jednoduché příklady na práci se seznamy
Zpět začátek
10. přednáška 5.prosince
    • Opakování
    • fixity deklarace
    • 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.
    • if výraz
    • Konstrukce let a where, dvojrozměrná syntaxe Haskellu
    • Funkce map, fold a foldr a příklady jejich použití
    • Mocninné řady jako příklad nekonečných termů, derivace a n-tá derivace mocninné řady
    • První a n-tá derivace mocninné řady
    • Prvočísla pomocí Erathostenova síta.
    • 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í a dělení)
        • 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ů
    • motivační příklad pro zavedení tříd
Zpět začátek
11. přednáška 12.prosince
    • 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ů
    • Různé implementace funkce počítající faktoriál
    • Pole v Haslellu
    • Násobení matic
Zpět začátek
12. přednáška 19.prosince
    velmi se nepovedla
    • O zkouškových písemkácha způsobu přihlašování na zkoušky
    Co je ještě v Haskellu
    • Abstraktní datové typy - moduly.
    • třídy a jejich instance
    • v typu jde definovat identifikátory složek a pak je používat obvyklým způsobem
    • striktní konstruktory dat - !
    • programování vstupů a výstupů
    • imperativní programování v Haskellu
    • komentář k začátku modulu prelude
    • prohra s hardwarem a předčasný konec
Zpět začátek
13. přednáška 9.ledna
    Logika za Prologem - letem světem
    • Predikátový a výrokový počet
    • Interpretace, logicky pravdivé formule, splnitelnost
    • Kluzulární tvar formule, Skolemova věta
    • Herbrandovo universum, Herbrandova věta
    • Základní resoluční metoda, unifikační algoritmus, Robonsonova věta
    • Hornovy klausule a Prolog
Zpět začátek