PRG005 Neprocedurální programování

Co bylo na přednáškách - paralelka Y pátek 10:40 S3

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

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 6.října
2. přednáška 13.října
3. přednáška 20.října
4. přednáška 27.října
5. přednáška 3.listopadu
6. přednáška 10.listopadu
7. přednáška 24.listopadu
8. přednáška 1. prosince
9. přednáška 8. prosince
10. přednáška 15.prosince
11. přednáška 22.prosince
12. přednáška 5.ledna
13. přednáška 12.ledna

1. přednáška 6.ří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)
     • otáčení seznamu v kvadratickém čase
   • 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
     • zkuste napsat predikát, který otáčí seznam v lineárním čase
Zpět začátek
2. přednáška 13.října
   • 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
   • 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).
   • matice jako seznamy řádkových seznamů
     • diag(+CtvercovaMatice, -Diagonala)
     • otáčení matice o 90 stupňů
     • rozmyslet
       • test zda matice je obdélniková
       • test zda matice je čtvercová
       • spirala(+Matice,-Spirala)
       • slupka(+Matice,-Slupka,-Pecka)
Zpět začátek
3. přednáška 20.října
   • Aritmetika, predikát is,
     aritmetické relace =:= , =/= , < , > , >=, <=
   • Jednoduché aritmetické predikáty
     největší společný dělitel dvou čísel, délka seznamu, minimum ze dvou čísel,
     minimum ze seznamu (čísel)
   • 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í
     • 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
   • Prohledávání grafu do hloubky a do šířky
     analýza (jde o jeden algoritmus lišící se jen použitou datovou strukturou
     do hloubky zásobník a do šířky fronta
     rozmyslet jak naprogramovat
Zpět začátek
4. přednáška 27.října
   • seznam listů stromu bez zřetězení
   • rozmyslet: Algoritmus quicksortu bez zřetězení
   • průchod stromem do hloubky a do šířky
   • 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á.
   • Práce s kompilátorem Prologu, predikáty consult a halt (u starších komplilátorů rozdíl mezi consult a 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.
   • Standardní predikáty name/2, functor/3, arg/3, =..
   • Rovnosti v prologu
     • = unifikace, \= její negace
     • =:= aritmetická rovnost, =\= její negace
     • == totožnost, \== její negace
   • Princip možné implemenace programu Eliza (rozhovor psychoanalitika s pacientem)
   • Na co se hodí Prolog
Zpět začátek
5. přednáška 3.listopadu
   • sklidnění po poplachu
   • 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
   • Standardní predikáty atom/1, var/1, nonvar/1.
   • Příklad užití operátoru =..
   • Řešení algebrogramu
   • Hledání všech možností pozic N nezávislých dam na šachovnici N x N
   • slévání dvou uspořádaných seznamů do třetího jako příklad determnistické procedury
   • "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
     převod na běžné seznamy
Zpět začátek
6. přednáška 10.listopadu
   • Procedury realizující jednoduchý algoritmus pro zjednodušování aritmetických výrazů
   • "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
   • 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.
   • Zavináčové uspořádání
   • Predikáty bagof a setof, "existenční kvantifikátor ^ ", jednoduché příklady užití.

   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 24.listopadu
   
   Dialekt LISPu - SCHEME (Přehled základních předdefinovaných forem je v materiálu)

   • historie, literatura
   • 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.
Zpět začátek
8. přednáška 1.prosince
   • Implemenace zlomku jako příklad nutnost "inteligentních" konstruktorů a selektorů.
   • 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
   • Pro všeobecný nezájem vynechána diskuse podprogramů pro práci s mobily
   • Úvod do Haskellu, literatura
   • 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,
   • Práce s fukcemi více proměnných - curryfikace
   • Lambda abstrakce.
   • Převod infixového operátoru na binární funkci a zpět. Řezy (sections).
   • Priorita operátorů, funkce fixity.
   • 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
   • Rozdílné implementace funkce take, které se liší "mírou definivání" vzhledem prvnímu resp. druhému parametru
   • (skoro) vše zopakujeme, ale koukněte na to !!
Zpět začátek
9. přednáška 8.prosince
   • Haskell - opakování
   • 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ů
   • pojem třídy (analogie pojmu rozhaní z Javy) jako požadacek na typ, aby měl definovany některé funkce,
     použití při specifikování typu funkce
   • instance třídy, podtřída, příklad hierarchie tříd
Zpět začátek
10. přednáška 15.prosince
    pravděpodobný obsah přednášky - mimo jiné
    • 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
    • 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
    • Abstrakce v Haskelu:
Zpět začátek
11. přednáška 22.prosince
    • O zkouškových písemkácha způsobu přihlašování na zkoušky
    Ještě naskok k Prologu
    • Ovlivňování efektivity Prologoských programů.
    • Několik implemenací výpočtu Fibonnaciovy posloupnosti, iterativní výpočet.
    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ů
Zpět začátek
12. přednáška 5.ledna
    odpadla vzhledem k indispozici přednášejícího
    Zpět začátek
13. přednáška 12.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