Ondřej Sýkora

NPRG005 - Úterý 9:00, S8

Kontakt, konzultace

• E-mail: ondrasej (zavináč) centrum (tečka) cz
  V předmětu e-mailu uveďte kód předmětu (NPRG005), pokud potřebujete odpovědět rychle (např. máte dotaz k domácímu úkolu), napiště to do předmětu také, výrazně zvýšíte šanci, že vám opravdu rychle odpovím
• Osobní konzultace buď po cvičení, nebo po domluvě e-mailem

Podmínky pro udělení zápočtu

• Odevzdání odladěného zápočtového programu. Pozor, odevzdání neznamená jen předání zdrojového kodu a dokumentace, ale hlavně diskuzi o zvoleném řešení a jeho implementaci.
  • Zvolené téma zápočtového programu pošlete e-mailem do konce semestru, zápočtové programy, ke kterým jsem téma předem neschválil nebudu přijímat!
  • Součástí odevzdaného programu musí být také programátorská dokumentace (popis použitého algoritmu a jeho implementace) a sada testovacích příkladů.
  • Příklady možných zadání - berte spíš jako inspiraci, vaše vlastní témata uvítám; pokud vás některé z témat zajímá, ale nevíte jak na něj, není to problém
    • Matematika - symbolické integrování, chytřejší (programovatelná) kalkulačka, efektivní numerické výpočty, knihovna pro práci s maticemi (složitější maticové operace - inverze, pseudoinverze, rozklady; raději v Haskellu), lineární programování (v Haskellu)
    • Diskrétní matematika - A*, toky v sítích, komponenty souvislosti, kostry grafu a další grafové algoritmy
    • Řešení her - umělá inteligence pro piškvorky, dámu, šachové koncovky, ...
    • Řešení puzzle - rubikova kostka, Lloydova 15 (24, 35, ...), efektivní řešení Sudoku (16x16, 25x25), generátor křížovek nebo osmisměrek, ...
    • Umělá inteligence - plánovací algoritmy, automatické dokazování, strojové učení, neuronové sítě
• Aktivní účast na cvičeních / řešení domácích úkolů / písemky během cvičení
  • Termíny písemek: 20. 4. 2010 - Prolog, 18. 5. 2010 - Haskell (Pozor, změna!)
• Během semestru je třeba získat alespoň 20 bodů, body lze získat za řešení domácích úkolů a z písemek zadávaných během cvičení.
  • Domácí úkoly odevzdávejte e-mailem na adresu uvedenou výše, program pošlete v příloze jako soubor s názvem vaše-příjmení-bez-diakritiky.pl (resp. vaše-příjmení-bez-diakritiky.hs u domácích úkolů v Haskellu) pokud bude domácích úkolů víc, pošlete je v jednom souboru.
  • Odevzdaný domácí úkol musí být spustitelný program (tj. musí obsahovat všechny pomocné predikáty nutné pro běh a nesmí obsahovat syntaktické chyby). Za domácí úkoly, které nelze spustit, budu body odečítat!
  • Pokud to nevylučuje zadání úkolu, využívejte predikáty ze standardní knihovny - ušetříte si práci a znalost standard ní knihovny se vám bude hodit v písemkách.
• Aktuální počty bodů z domácích úkolů: body (2010-06-13)

Cvičení 23. 2. 2010

• Velmi stručný a neúplný úvod do Prologu - základní princip, databáze faktů a pravidel, základy odvozování, proměnné
• Příklady s rodinnými vztahy - muz(Kdo), zena(Kdo), rodic(Kdo, Koho), programovali jsme predikáty matka(Kdo, Koho), sourozenec(Kdo, Koho), prarodic(Kdo, Koho), predek(Kdo, Koho)
• Domácí úkol
  • Nainstalovat Prolog (doporučuji SWI Prolog), poslat o tom e-mailem zprávu - 1 bod
  • Potvrdit e-mailem účast na cvičení

Cvičení 2. 3. 2010

• Práce s termy, syntaktický přístup ke všem výrazům ("Prolog nepočítá, pokud nemusí!")
• Unifikace, unifikační algoritmus, role unifikace ve výpočtu
• Příklady na principy unifikace: X = sin(pi / 2), f(X + y, cos(pi / 2), Z) = f(x + A, cos(B), C), ...
• Počítání s (robinsonovými) numerály:
  • Definujeme vlastní reprezentaci čísel... 0 je reprezentována termem 0. Pokud číslo n-style: normal;"> je reprezentováno termem X, pak n + 1 je reprezentováno termem s(X).
  • Příklady: predikát inc(X, Xplus1), plus(A, B, Soucet), minus(A, B, Rozdil), krat(A, B, Soucin)
  • "Skutečná" aritmetika v prologu, operátor is, převod s(...) numerálů na klasické integery
  • Rošířená definice... Pokud číslo n je reprezentováno termem X, pak n - 1 je reprezentováno termem p(X).
  • Příklad: normalizace termu tak, aby byl ve tvaru s(s(...s(0)...)) nebo p(p(...p(0)...))
• Domácí úkoly:
  • Predikát deleno(Co, Cim, Podil, Zbytek), který provádí dělení na celých čísel (tj. na číslech složených jen z s(..), p(..) uvažovat nemusíte)
  • Dokončit term pro normalizaci tak, aby správně ošetřil všechny případy
  • Autorské řešení (688 Bytes)

Cvičení 9. 3. 2010

• Poučení z domácího úkolu, základní typy chyb v prologovských programech
  • syntaktické (program se nezkompiluje nebo nejde spustit kvůli syntaktickým chybám, špatným názvům predikátů, překlepům, ...)
  • logické (špatná odpověď na validní vstup, zacyklení/pád programu při neplatném vstupu)
  • chyby vycházející z nejednoznačnosti (první odpověď je správná, ale další odpovědi mohou být chybné nebo se nekonečněkrát opakují)
• Datové struktury v Prologu, seznamy, definice seznamu jako dvojice (Hlava, Tělo)
• Základní operace nad seznamy: member(Seznam, Prvek), remove(Seznam, Prvek), append(S1, S2, Spojeny), reverse(Seznam, Otoceny) - implementace pomocí append v kvadratickém čase
• Domácí úkol:
  • Predikát reverse(Seznam, Otoceny), který by pracoval v lineárním čase (1 bod)
  • Autorské řešení (133 Bytes)

Cvičení 16. 3. 2010

• Použití akumulátoru - efektivní výpočet Fibbonaciho posloupnosti pomocí akumulátoru
• Datové struktury v Prologu - avl stromy
  • avlmember(Item, Tree), avlinsert(Item, Tree, Result) bez vyvažování, predikáty pro rotaci
• Domácí úkol:
  • dokončit avlinsert(Item, Tree, Result) s vyvažováním (3 body)
  • Autorské řešení (2.03 kB)

Cvičení 23. 3. 2010

• Práce se syntaktickou strukturou aritmetických výrazů
  • kalkulačka s proměnnýma - vyčíslení aritmetického výrazu s nahrazením proměnných (reprezentovaných atomy)
  • symbolické derivování aritmetického výrazu podle proměnné
  • zjednodušení aritmetického výrazu - odstranění podtermů typu X*0, X*1 a X+1
• Domácí úkol:
  • lepší verze zjednodušování aritmetických výrazů - přidat i částečné vyčíslení, zpracování výrazů ve tvaru X - X a podporu pro mocniny (operátor **)
  • zjednodus(Vyraz, Vysledek), Vyraz i Vysledek jsou termy obsahující aritmetický výraz. Př. pro Vyraz = 3*2 + 15*(x+1)**0 je Vysledek = 21 (1 bod)
  • bonusový úkol (+1 bod) - kromě uvedených zjednodušení implementovat také vytýkání. Př. pro Vyraz = 3*x + x je Vysledek = 4*x.

Cvičení 30. 3. 2010

• Negace v Prologu, operátor řezu, definice vlastních operátorů
• Využití predikátu call(X), operátoru =.. a predikát maplist(P, From, To)
• Práce s maticemi
  • reprezentace matice jako seznam seznamů (každý "vnitřní" seznam reprezentuje jeden řádek matice)
  • transpozice matice
  • výběr podseznamu a podmatice dané velikosti
• Domácí úkol:
  • sudoku(M) - řešení základní verze Sudoku - M je matice 9x9 reprezentující zadání hlavolamu ve formátu "seznam řádků". Na známých pozicích jsou čísla 1-9, ostatní pozice obsahují volné proměnné. Výstupem výpočtu je dosazení za všechny volné proměnné tak, aby M obsahovala řešení sudoku.
  • Při řešení využijte
    1. maticové operace probírané na cvičení,
    2. "přirozený" backtracking v Prologu a
    3. predikát dif(X, Y) který zajišťuje, že proměnné X a Y obsahují různé hodnoty. Pokud X a Y již mají hodnotu, je dif(X, Y) totožné s X \=Y. Pokud některé z proměnných je volná, provede kontrolu (automaticky) ve chvíli, kdy je do proměnné dosazena hodnota. Úlohu lze vyřešit i bez tohoto predikátu pomocí "ručně provedených" kontrol po dosazení.
    4. Predikát print_matrix(M) vytiskne "formátovaně" matici M. Mohl by se vám hodit při testování vašeho řešiče:

       print_matrix(M) :- maplist(writeln, M).
       writeln(X) :- write(X), nl.
       

  • Autorské řešení (2.31 kB)

Cvičení 6. 4. 2010

• Čtení a vypisování termů v Prologu - predikáty read(T), write(T) a nl.
• Nalezení seznamu všech možných odpovědí na dotaz - predikáty bagof(Template, Query, Results) a setof(Template, Query, Results).
• Hledání vítězné strategie ve zobecněné hře Nim - nim(PocetSirek, Tahy, Strategie) - pro aktuální počet sirek PocetSirek a možné tahy ze seznamu Tahy vrátí v Strategie optimální počet odebraných sirek pro hráče, který je právě na tahu.
• Hlednání nejkratší cesty v grafu pomocí Dijkstrova algoritmu (v orientovaném grafu s konstantním ohodnocením hran) - hrany jsou uloženy přímo v databázi pomocí predikátů h(Z, Do). Cílem je vytvořit predikát dijkstra(Z, Do, Cesta), který nalezne nejkratší cestu z vrcholu Z do vrcholu Do a do Cesta uloží seznam navštívených vrcholů.
• Domácí úkol:
  • Zploštění seznamu bez omezení úrovní zanoření - všechny prvky, které nejsou seznam zachová v původním pořadí: flatten(Seznam, Zplosteny), př. pro Seznam = [[[1], 2], 3, [[]]] je výsledek Zplosteny =[1, 2, 3].
  • Autorské řešení (414 Bytes)

Cvičení 13. 4. 2010