Kdy a kde:

• I/2/35, MIU/2/75 : St 15:40 v E2

Za co je zapocet:

• Zapoctovy program (v Prologu) -- tema vcetne specifikace, v niz shrnete, co ma vami vytvoreny program umet, byste mi meli oznamit do 30.11.2004. Doporucuji se inspirovat seznamem uloh na strankach RNDr. J. Hrice. Samozrejme fantazii se meze nekladou a pokud mi dodate rozumne tema zapoctaku, urcite se nejak dohodneme. Soucasti zapoctaku je dokumentace. Rady jak ji napsat (a nepsat) od RNDr R. Kryla a RNDr. J. Hrice.
• Ucast na cviceni neni povinna; na druhou stranu, pokud po me bude chtit zapocet nekdo, koho jsem na cviceni nikdy nevidel, asi bude mit problem.
• Vyreseni alespon 2*n/3 domacich ukolu, kde n je pocet domacich ukolu, ktere zadam (n bude radove 5). Ukol dodany po terminu (kterym obvykle byva pristi cviceni) se pocita za 2/3 -- tj. pokud behem semestru nebudete nic delat, nezbyva vam, nez ve zkouskovem obdobi vyresit a odevzdat vsechny ukoly. Reseni prikladu se obvykle sklada z popisu algoritmu, programu v zadanem programovacim jazyce (Prolog nebo Haskel), ktery ho implementuje, a zduvodneni spravnosti a casove slozitosti. Zduraznuji: je pozadovan popis algoritmu, nikoliv programu. Priklad:
  Spatne: Nastavim sum na 0 a pak pro i od 1 do n pricitam a[i] k sum.
  Lepe: Sectu zadane prvky (ulozene v poli a).
  Spravne: Zalezi na okolnostech. Scitat cisla v poli jen tak pro radost je vicemene k nicemu. Spise nez na detailne popisovat to, jak je secteme, je lepsi se zamerit na vysvetleni toho, proc je vlastne chceme secist.
  Zatim vypsane priklady:

  • Napiste predikat spirala(+Matice,-Seznam). Tento predikat dostane za vstup ctvercovou matici (seznam, jehoz prvky jsou seznamy, reprezentujici radky matice), a jeho vystupem je seznam prvku matice v poradi podel spiraly zacinajici v levem hornim rohu matice a koncici ve stredu matice.

  • Napiste predikat mergesort(+Seznam,-Setrideny). Tento predikat dostane za vstup seznam cisel a setridi je algoritmem mergesort.

  • Napiste predikat piskvorka(+Stav,+Hrac,-StavPoTahu), ktery hraje piskvorky (4 v rade vyhravaji). Stav je obdelnikova matice (seznam seznamu) udavajici stav hry (prvky teto matice jsou x, o, nebo p pokud je policko prazdne). Hrac je hrac, ktery je na tahu (x nebo o). StavPoTahu by mel byt stav hry po provedeni nejlepsiho tahu (urceneho standardnim minimaxem -- efektivita reseni nehraje roli, nepozaduje se, aby pro jakoukoliv vetsi matici reseni dobehlo v rozumnem case).

  • Napiste predikat porovnejStrukturu(+Term1, +Term2), ktery uspeje, pokud jsou termy Term1 a Term2 identicke az na prejmenovani volnych promennych -- tj. mel by mit stejnou semantiku jako =@= v SWI-Prologu.-- tj. mel by mit skoro stejnou semantiku jako =@= v SWI-Prologu; z nejakeho duvodu SWI-Prolog tvrdi, ze f(_X,_Y) nema stejnou strukturu jako f(_Y,_Z).

  • Mejme graf reprezentovany seznamy sousedu:

    type Vrchol = Int
    type Graf = Array Vrchol [Vrchol]
    

    Napiste funkci dfs::Graf->Vrchol->[Vrchol], ktera pro zadany graf G a jeho vrchol v vrati seznam vrcholu G v poradi podle pruchodu do hloubky z vrcholu v.

Obsah cviceni:

• (6.10.) Cviceni se nekonalo.
• (13.10.) Cvicil za me profesor Kryl, probiral jednoduche operace se seznamy a "pribuzenske vztahy".
• (20.10.) Operace se seznamy, mnoziny reprezentovane seznamy. Rozdilove seznamy.
• (27.10.) Overeni zda je matice ctvercova, prevody reprezentaci grafu, prohledavani grafu do sirky a do hloubky.
• (3.11.) AVL stromy, kostra grafu.
• (10.11.) Vstup a vystup. Tail rekurze, proc ji chtit a jak ji dosahnout. Rozklad termu -- seznam volnych promennych termu.
• (17.11.) Svatek.
• (24.11.) Pisemka. Bagof, setof, ...
• (1.12.) Lisp -- jednoduche funkce, prace se seznamy.
• (8.12.) Haskell -- jednoduche funkce.
• (15.12.) Haskell -- prace s nekonecnymi seznamy, parsovani vyrazu.
• (22.12.) Typove tridy. Trochu zmatene povidani o tom, jak psat veci typu vyhodnocovani vyrazu s promennymi ci interpretace programovaciho jazyka (jak chytre kombinovat funkce typu Promenne->(Promenne,Hodnota) odpovidajici kusum vyrazu/programu).
• (5.1.) Cvicil za mne Ondrej Bojar, prikladky na pole, opakovani -- datove a typove konstruktory, nekonecne datove struktury.