Pavel Surynek's Academic Page | Neprocedurální programování (PRG005 - Informatici)

Neprocedurální programování (PRG005 - Informatici)


Cvičení se koná každý pátek od 10:40 v učebně S10 (Malá Strana). Na této stánce budou postupně uveřejňovány informace týkající se průběhu cvičení.


Cvičení 5.10.2007
Pro získání zápočtu je vyžadována aktivní účast na cvičení, napsání zápočtových písemek a vytvoření zápočtového programu opatřeného dokumentací a testovacími daty (zápočtový program bude upřesněn později podle požadavků přednášejícího).

Probírala se unifikace jako způsob předávání parametrů. Dále se probíraly jednoduché predikáty na odpovídání, zda platí daný příbuzenský vztah za předpokladu, že platí fakta uvedená v databázi faktů. Průběh vyhodnocování dotazů pro příbuzenské vztahy - backtracking. Reprezentace stromu rekurzivní strukturou t(levy_podstrom, hodnota, pravy_podstrom), predikát na zodpovězení, zda se zadaná hodnota nachází v zadaném stromu. Testování správně formované struktury strom. Unární reprezentace přirozených čísel (a nuly) pomocí struktury následník (např. číslo 3 je reprezentováno pomocí struktury s(s(s(0)))). Testování správně formovaného čísla, aritmetické operace nad unární reprezentací čísel.


Cvičení 12.10.2007
Aritmetika nad unární reprezentací přirozených čísel (a nuly) - operace sčítání, opatrné odčítání a násobení. Různé varianty dotazů pro aritmetické operace - plus(+,+,-) (známe sčítance, neznáme výsledek operace), plus(-,-,+) (neznáme sčítance, známe výsledek operace), plus(-,+,+) (neznáme prvního sčítance, známe druhého sčítance a výsledek operace). Základy práce se seznamy, unifikace konstrukce [X|Y]. Připojení seznamu na konec jiného seznamu - append, generování všech permutací seznamu, transpozice matice reprezentované jako seznam seznamů.


Cvičení 19.10.2007
Aritmetická operace plus pro módy plus(-,-,+). Generování všech permutací seznamu. Transpozice matice. Základní operace se seznamy. Sjednocení seznamů. Průnik seznamů. Palindrom (seznam čtený popředu i pozpátku stejně), otočení seznamu. Akumulátor na zeefektivnění operace otáčení seznamu. Slévání seznamu seznamů do jednoho seznamu. Rozdělení seznamu na sudé a liché prvky (podle pozic). Mailové domácí úkoly (na cv. se nebude předvádět): variace, kombinace seznamu, bez opakování a s opakováním. Klasický domácí úkol (bude se předvádět na cv.): binární vyhledávací strom - member, insert, delete (klasický dcv. lze i mailově).


Cvičení 26.10.2007
První zápočtová písemka se bude psát 9.11.2007. Náplní písemky budou podobné úlohy, jako se probírají na cvičení. Rozhas písemky bude vše, co bylo až do termínu písemky probráno (na cvičení i přednášce).

Transpozice matice. Binární vyhledávací strom - insert, member, delete. Aritmetické operace. Výpočet faktoriálu, Fibonacciho čísla, největšího společného dělitele, počet transpozic v seznamu čísel. Reprezentace 2-regulární haldy - operace vložení prvku a odebrání minimálního prvku. Reprezentace grafu s ohodnocenými vrcholy. Barvení grafu.


Cvičení 2.11.2007
Úlohy na prohledávání stavového prostoru. Barvení grafu. Přelévání vody - dáno několik nádob celočíselných objemů, úkolem je odměřit zadaný objem. Vlk, koza, zelí, převozník, převážení na druhý břeh. Obecné barvení grafu (hrany nejsou jen nerovnosti, ale také další relace na uspořádání). Proskákání šachovnice koněm, N neohrožujících se královen na šachovnici velikosti NxN.


Cvičení 9.11.2007
Slibovaná zápočtová písemka se skutečně psala. Na následujícím odkazu je její zadání.

  • První (zápočtová) písemka - zadání  (pdf formát)
  • Cvičení 16.11.2007
    Další úlohy na prohledávání stavového prostoru. Vyhodnocování a splňování Booleovských formulí v CNF formě. Dále se procvičovalo použití řezu. Ukázka paradoxního chvání vyhodnocování dotazů pro různá umístění řezu v programu. Za domácí úkol zbyla úloha o hledání pozic pro N neohrožujících se královen na šachovnici velikosti NxN.


    Cvičení 23.11.2007
    Procvičování definic operátorů. Množinové oprátory. Řešení těžkých úloh (z hlediska výpočetní složitosti) v Prologu - součet podmnožiny, Lloydova osmička (patnáctka). Plánování ve světě kostek - klasické STRIPS plánování, kde akce je trojice množin atomů (předpoklad, pozitivní efekt, negativní efekt).


    Cvičení 30.11.2007
    Ještě jsme se chvíli zabývali plánováním. Pak jsme začali Scheme, jednoduché úlohy - faktoriál, Fibonacciho číslo, kombinační číslo. Seznamy ve Schemu - délka seznamu.


    Cvičení 7.12.2007
    Procvičoval se Scheme. Numerické úlohy ve Schemu - numerické počítání derivace, numerické integrování, numerické hledání nulových bodů funkce (Newtonova metoda). Základní funkcionální techniky - zpracování struktury pomocí unární operace (map), pomocí binární operace (fold). Domácí úkol: filrace signálu, transpozice matice a vyhledávání ve stromu.


    Cvičení 14.12.2007
    Další úlohy ve Schemu. Transpozice matice, filtrace signálu, vyhledávání ve stromu. Začal se procvičovat Haskell. Základní úlohy - Fibonacciho číslo, faktoriál, maticové násobení, transpozice matice.

    První cvičení po Vánocích (tj. 4.1.2008) se bude psát další zápočtová písemka.


    Cvičení 4.1.2008
    Psala se druhá zápočtová písemka. Zadání písemky bude zveřejněno později.



    Zápočtové povinnosti

  • Tabulka zápočtových povinností