Cvičení se koná každý čtvrtek od 9:00 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í 12.10.2006
Pro získání zápočtu je vyžadována aktivní účast na cvičení, napsání zápočtové písemky a vytvoření zápočtového programu opatřeného testovacími daty a dokumentací.

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ů. Většina cvičení byla věnována unární aritmetice, probíraly se predikáty realizující sčítání, násobení a "opatrné" odčítání (zatím pouze tak, že volná proměnná odpovídá výsledku operace).

Cvičení 19.10.2006
Na cvičení se probíraly rozdíly mezi dotazy plus(+,+,+), plus(+,+,-), plus(+,-,-) a plus(-,-,-) v unární aritmetice, kde + značí zadaný parametr a - značí volný parametr. Podrobně se rozebíral průběh unifikací při zodpovídání uvedených dotazů. Na rozmyšlenou byl nechán průběh unifikací pro predikát krát v unární aritmetice (opět případy krát(+,+,+), krát(+,+,-), krát(+,-,-) a krát(-,-,-)).

Procvičovaly se seznamy na základních operacích - member(+Seznam, +Prvek), append(+Seznam, +Prvek, -Výsledek), sjednoceni(+Seznam1, +Seznam2, -Výsledek), sudé_liché(+Seznam, -Sudé, -Liché). Na rozmyšlenou do příště zbyl predikát pro permutaci (permutace(+Seznam, +Permutovaný) a permutace(+Seznam, -Permutovaný)), transpozice matice ([[1,2,3], [a,b,c]] přejde na [[1,a], [2,b], [3,c]]) a náhrada seznamu pomocí jiné struktury.

Cvičení 26.10.2006
Část cvičení byla věnována ulohám, které byly zadány na rozmyšlenou na minulém cvičení. Pokračovalo se v práci se seznamy - reverse(+Seznam, -Obrácený_seznam) bez akumulátoru a s akumulátorem (význam akumulátoru pro výslednou složitost), reprezentace slov pomocí seznamu - například [a,h,o,j], hledání slov, která se čtou pozpátku stejně jako odpředu - palindrom(+Slovo). Dále se procvičovala reprezentace binárního (vyhledávacího) stromu a základní operace - member(+Strom, +Prvek), insert(+Strom, +Prvek, -Nový_strom) a delete(+Strom, +Prvek, -Nový_strom).

Cvičení 2.11.2006
Příští cvičení (tj. 9.11.2006) se bude psát písemka. Obsahem písemky budou varianty úloh probíraných na cvičení.

Procvičovala se aritmetika v Prologu - výpočet Fibonacciho čísla, faktoriál, největší společný dělitel, délka seznamu a počet transpozic v seznamu čísel. Dále se procvičovala reprezentacu grafů (varianty: orientovaný, neorientovaný, ohodnocené hrany, ohodnocené vrcholy) a základní grafové algoritmy - nejkratší cesta, minimální kostra, barvení vrcholů. Dále jsme se zabývali úlohami na prohledávání stavového prostoru - proskákání šachovnice koněm, N královen, přelévání vody a vlk-koza-zelí. Složitější úlohy zbyly na příště.

Cvičení 9.11.2006
Písemka se skutečně psala. Na následujícím odkazu je její zadání.

Několik informací k zápočtovým programům v Prologu: Téma zápočtového programu lze získat na internetových stránkách dalších vyučujících předmětu Neprocedurální programování. Vybrané téma je potom nutné si nechat schválit (stačí mi poslat email s popisem tématu či s odkazem na zdroj). Hotové dílo pro odevzdání by mělo obsahovat smotný program, dokumentaci (uživatelskou, algoritmickou - popis použitých algoritmů, programovou) a testovací data. Pro ladění programu je nevhodnější použít nějký Prolog dostupný v počítačové laboratoři (třeba SWI Prolog).

Cvičení 16.11.2006
Probíraly se úlohy na prohledávání stavového prostoru - přelévání vody, proskákání šachovnice koněm, N neohrožujících se královen. Na rozmyšlenou zůstalo barvení grafu a základní grafové algoritmy - minimální kostra, nejkratší cesta. Procvičovaly se rozdílové seznamy na predikátu pro spojení dvou seznamů - průběh unifikace, různé varianty dotazů.

Cvičení 23.11.2006
Na cvičení byla (hlavně zpočátku) malá účast. Příliš mnoho absencí (více než 3) bude kompenzováno domácím úkolem navíc (lehčí zápočtový program).

Probíraly se technické aspekty Prologu. Definice nových operátorů - operátor pro sjednocení (\_/), průnik (/-\) a vyhodnocní těchto operací (is_set). Přidávání a odebírání klauzulí v databázi (assert, retract). Sbírání všech možných řešení (setof, bagof, findall). Řez, k čemu je, jak funguje. Na ilustračním příkladu jsme zkoumali paradoxní chování řezu. Začal se procvičovat Scheme - výpočet n-tého Fibonacciho čísla, výpočet třetí odmocniny.

Cvičení 30.11.2006
Nejprve se opakovaly úlohy z minulého cvičení - tj. Fibonacciho čísla a třetí odmocnina ve Schemu. Přitom se procvičily základní syntaktické konstrukce jazyka Scheme (define, if, cond, let, lambda). Dále jsme se věnovali základním obratům funkcionálního programování - konstrukce map (každý prvek struktury je zpracován unární operací) a konstrukce fold (všechny prvky struktury jsou zpracovány binární operací). Konstrukce jsme naprogramovali pro seznam, na rozmyšlenou zůstalo, jak totéž realizovat pro strom.

Cvičení 7.12.2006
Oznámení: příští cvičení (tj. 14.12.2006) odpadá, po-příští cvičení (tj. 21.12.2006) ale neodpadá a navíc začíná v 7:30.

Cvičil se Haskell. Jednoduché příklady na procvičení syntaxe a vestavěných typů - n-tý prvek seznamu, délka seznamu, faktoriál atd. Dále jsme procvičovali konstrukci zip (dvě struktury, prvky na stejných místech ve strukturách jsou zpracovány pomocí binární operace a výsledek je uložen do výsledné struktury na odpovídající místo) na seznamech a na stromech. Zkoušeli jsme různé varianty funkcionálních paramtrů konstrukce zip. Na rozmyšlenou zůstaly konstrukce map a fold pro strom (aplikace na výpočet výsky stromu).

Cvičení 21.12.2006
Cvičení se konalo od 7:30 do 10:30. Opět se cvičil Haskell. Počet prvků stromu, výška stromu - normálně, s využitím map, fold, zip. Kartezský součin seznamů, stromů. Nekonečné datové struktury. Seznam všech přirozených čísel, seznam všech prvočísel - Eratosthenovo síto. Zobecněné barvení grafu, vrcholy mají přiřazeny seznamy barev, hrany jsou ohodnoceny podmínkami větší, menší, rovno, nerovno,... Úkolem je odstranit barvy, které nemohou úlohu řešit (hranová konzistence).

Příští cvičení (tj. 4.1.2007) se bude psát druhá zápočtová písemka.

Cvičení 4.1.2007
Psala se druhá zápočtová písemka. Na následujícím odkazu je její zadání.

Cvičení 11.1.2007
Programovali jsme merge-sort v Haskellu. Nakonec se téměř podařilo napsat verzi s časovou složitostí O(log₂N). Na rozmyšlenou zůstala implementace maticových operací pomocí polí a barvení grafu (obecnější verze s různými relacemi na hranách). Nakonec bylo rozdáno několik zápočtů.

Zápočtové povinnosti