Kdy a kde:

• I/2-X/36 : St 10:40 v S11

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.2005. Doporucuji se inspirovat seznamem uloh na strankach RNDr. J. Hrice. Samozrejme fantazii se meze nekladou a pokud mi navrhnete 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 jsem zadal (n=4). 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: Pouziji vyraz foldl 0 (+) (elems a).
  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:
  • (Do 18.10.) Napiste predikat rec_conc(+Seznamy,-Spojene), ktery do Spojene vlozi seznam vsech atomu, ktere jsou prvky seznamu Seznamy, nebo prvky prvku seznamu Seznamy, nebo prvky prvku prvku, atd. Tj. napriklad ?-rec_conc ([a,[b,[c,d],e,[f]],g], X). vrati X=[a,b,c,d,e,f,g]. Pro reseni muzete vyuzit standardni predikat atom(+X), ktery je splnen pro atomy (mimo jine take pro prazdny seznam), ale ne pro neprazdne seznamy.
  • (Do 25.10.) Pracujeme s polynomy v promenne x, reprezentovanymi seznamem jejich clenu s nenulovymi koeficienty setridenych podle exponentu, tj. napriklad 1 + x + 5x⁴ - 7x¹⁰ je reprezentovano jako [x(1,0), x(1,1), x(5,4), x(-7, 10)]. Napiste predikat deleni, ktery vydeli dva polynomy v teto reprezentaci se zbytekem, napriklad deleni([x(2,0),x(1,2)],[x(-1,0),x(1,1)],[x(1,0),x(1,1)],[x(3,0)]), jelikoz x² + 2 = (x - 1)(x+1) + 3. Presneji, deleni(P1,P2,R,Zb) pokud P1 = P2 * R + Zb a stupen Zb je mensi nez stupen P2.
  • (Do 8.11.) Mame orientovany graf zadany poctem vrcholu n a seznamem hran (ve formatu [h(1,2),h(2,3),h(1,4)]). Prevedte ho na matici sousednosti, reprezentovanou jako term m s n argumenty, z nichz kazdy odpovida radku matice. Kazdy radek je term r s n argumenty, odpovidajicimi prvkum. Tj. i-tem radku a j-te pozici je 1, pokud ij je hrana, 0 jinak. Napriklad, prevod(4,[h(1,2),h(2,3),h(1,4)], m(r(0,1,0,1),r(0,0,1,0),r(0,0,0,0),r(0,0,0,0))).
  • (Do 20.12.) Mejme nasledujici typ pro parser: Parser a = String->Maybe (a, String), tedy parser pro typ a nacte ze zadaneho retezce pocatecni usek, ktery lze interpretovat jako hodnotu typu a, a vrati ji spolu se zbytkem retezce. V pripade, ze takovy pocatecni usek neexistuje, vrati Nothing. Napiste parseInt::Parser Int.

Obsah cviceni:

• (4.10.) Cviceni se konat nemelo, ale par lidi prislo. Zakladni priklady v Prologu (pribuzenske vztahy, seznamy -- member, append, reverse; vliv poradi klauzuli a poradi predikatu v telech klauzuli na vysledek).
• (11.10.) Prace se seznamy (deleni, trideni, ...)
• (18.10.) Diskuse rec_conc (efektivita, reversibilita), stromy (vkladani, vypis, konstrukce perfektniho vyvazeneho stromu/vsech stromu se zadanym vypisem), tail rekurze.
• (25.10.) Datove struktury -- fronta (rozdilove seznamy, 2 zasobniky), halda.
• (1.11.) Grafy -- reprezentace, prohledavani do sirky, barveni. Rozklad termu -- seznam volnych promennych v termu.
• (8.11.) Map, fold, setof (bez assert), bagof (pomoci assert), interpret Prologu v Prologu.
• (15.11.) Vstup a vystup v prologu, LISP -- prace se seznamy.
• (22.11.) Improvizace na LISP -- vyvazenost mobilu, implementace objektu, odstraneni rekurze pouzitim operatoru pevneho bodu.
• (29.11.) Cvicil za me Santiago, uvod do Haskellu.
• (6.12.) Odpadlo.
• (13.12.) Haskell -- transpozice a nasobeni matic, prace se seznamy, typ Maybe.
• (20.12.) Parsovani, monady.
• (3.1.) Vypsani a vyhodnocovani vyrazu (s osetrenim chyb, menenim hodnot promennych).
• (10.1.) Pole, stromy.