Seminář z Neprocedurálního programování pátek 9:00 S1

• Pravidla pro zasílání domácích cvičení mailem
• Zápočtové úlohy
• Náplň jednotlivých cvičení

Náplň jednotlivých cvičení

1. cvičení 7.října
   • Jednoducké predikáty o rodinných vztazích:
     otec/2, bratr/2, partner/2, švagr/2, dedazmatcinystrany/2,
   • Opakování seznamů
   • Jednoduché predikáty pro práci se seznamy
     bytiSeznamem/1, prvek/2, prvniPrvek/2, posledniPrvek/2, predposledniPrvek/2, zretezSeznamy/3, zip/3, otoc/2, perm/2, vypustPrvek/3, vlozPrvek/3, atd.
   • Domácí cvičení:
     Uvažujte elementární predikáty:
     rodina(Otec, Matka, Deti) - Deti je seznam dětí v rodině od nejstaršího k nejmladšímu
     muz(Kdo), zena(Kdo)
     Vytvořte predikáty
     • nejstarsiBratr(Kdo, Koho)
     • starsiBratr(Kdo, Koho)
     • sestry(Ci, Sestry)
2. cvičení 15.října
   • Predikaty nejstarsiBratr/2, starsiBratr/2, sestry/2
   • Jednoduché predikaty pro práci se seznamy:
     zip/3, rozde/2, del/3, delall/3
   • revers_append a otáčení v linearnim čase, technika akumulatoru
   • Matice jako seznamy řádkových seznamů
   • hlavni_diagonala(+Matice,-Diagonala)
   • otocMaticio90(+matice,-OtocenaMatice)
   • Domácí cvičení:
     • obdelnik/1, ctverec/1,
     • spirala(+Matice, -Spirala)
     • slupka(+Matice, - Slupka, -Pecka
3. cvičení 21.října
   • otocMaticio90(+matice,-OtocenaMatice)
   • Písemné domácí cvičení:slupka(+Matice, - Slupka, -Pecka)
   • obdelnik/1, ctverec/1,
   • Aritmetika - jednoduché příklady
   • Délka seznamu
   • Reprezentace binárního stromu
   • Binární vyhledávací stromy
     • prvek/2
     • vloz(co,Kam,Vysl), jde použít na obecné vypouštění prvků ze stromu ?
     • D.cv.: Vypuštění z binárního vyhledávací stromu
   • D.cv.: Vzájemné převody různých reprezentací permutací
     vektor obrazů,
     seznam netriviálních cyklů,
     seznam dvojic
     vektor inversí


4. cvičení 4. listopadu
   • "inversní spirála" pomocí vytvoření matice z anonymních proměnných
   • vytvoření seznamu uzlů stromu uspořádaného podle vzdáleností od kořenů
   • Domácí cvičení
     Rozmyslet:
     • Převody mezi různými reprezentacemi permutací
     Napsat:
     • převody p2v a inverzní v2p mezi reprezentacemi permutace jako vektoru obrazů a vektoru inverzí
5. cvičení 11. listopadu
   • Koncepce programu Eliza
   • Postavení dokonale vybalancovaného stromu z prvních N prvků rostoucího seznamu
   • Následující permutace v lexikografickém uspořádání
   • Průchody grafem do šířky a do hloubky
   • Domácí cvičení
     • Projít si a rozmyslet vše, co z Prologu na přednáškách bylo, zformulovat případné dotazy
     • Povinně: Topologické třídění
     • Dobrovolně: Průchody grafem do hloubky a šířky
6. cvičení 18. listopadu
   • První nabídka témat na zápočtové úlohy
   • Rozdílové seznamy
   • operátory
     dom. cvičení: Definujte operátory pro obvyklé spojky výrokové logiky a vytvořte proceduru, která pro zadanou formuli výrokového počtu zjistí, zda je to tautologie a pokud není vrátí ohodnocení elementárních formulí, při kterém nabývá tato formule pravdivostní hodnoty false
   • predikáty bagof, setof
   • Funkce pro změnu databáze assert, retract, retractall
7. cvičení 25. listopadu
   • Písemka:
     1. Součtovým seznamem nazveme datovou strukturu tvaru A + B , kde A a B jsou seznamy. Označíme-li OB otočený seznam B, pak součtový seznam A + B reprezentuje seznam, který vznikne konkatenací seznamu OB za seznam A.
        Sestavte predikáty, které realizují
        a) Přidání prvku na konec součtového seznamu
        b) Odebrání posledního prvku součtového seznamu
        c) Přidání prvku na začátek součtového seznamu
        d) Odebrání prvního prvku součtového seznamu
        e) Konkatenaci součtových seznamů
     2. Naprogramujte součin řídkých polynomů reprezentovaných jako (vhodně uspořádaný) seznam dvojic prv(Koef, Exp) , kde Koef je nenulový koeficient u exponentu Exp. Definujte si nějak vhodně reprezentaci nulového polynomu.
 
8. cvičení 2. prosince
   Scheme
   • Konkatenace seznamů, reverseappend.
   • Definice datové struktury binární strom- konstruktory a selektory
     Funkce v této reprezentaci:
     • Seznam listů stromu
     • verze bez konkatenace
     • Z rostoucího seznamu L a čísla N vyrobit dvojici
       dokonale vybalancovaný binární vyhledávací strom z prvních N prvků seznamu L
       a nezpracovaný zbytek sezamu L
   • Div a mod
   • Součet prvků seznamu, součin prvků seznamu, zobecnění s binární funkcí jako argumentem
   • Rozmyslet: Definovat datovou strukturu graf a naprogramovat průchod do hloubky a do šířky
9. cvičení 9. prosince
   suplování Scheme
   • Reprezentace grafu, průchody do hloubky a do šířky
   • lambda forma
   • foldr, foldl a jejich použití
10. cvičení 16. prosince
    Haskel
    • Specifikace typu funkce
    • Seznamy
    • Řídké polynomy - reprezentace
      sčítání a násobení řídkých polynomů
    • Skalární součin, s funkcionálními parametry
    • Reprezentace binárního stromu
      seznam listů, verze bez zřetězení seznamů
    • Rozmyslet:
      • rozdělení seznamu na rosoucí začátek a zbytek
      • Závěsné mobily, reprezentace, vyváženost a bezpečnost

Pravidla pro zasílání domácích cvičení mailem

Domácí cvičení umístěte do textového souboru, který jde přečíst běžným textovým editorem (nikoli world).
Na jeho první řádce souboru napište
  svoje jméno, identikaci cvičení: pátek 9:00
Na jeho druhé řádce napište
  název úlohy.
Soubor pošlete jako přílohu mailu, jehož předmět bude mít tvar
 DCV NP900 vase_jmeno nazev_ulohy
Mail pošlete na moji adresu kryl@ksvi.mff.cuni.cz
tak, aby došel do čtvrtka 8 hodin ráno.

Zápočtové úlohy

Na dotazy jak podrobná specifikace má odpovídám takto: