Seminář z Neprocedurálního programování pátek 10:40 S7

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

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 10:40
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 NP1040 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.

Náplň jednotlivých cvičení

1. cvičení 8.ří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
   • puleni seznamu
   • revers_append a otáčení v linearnim čase, technika akumulatoru
   • Matice jako seznamy řádkových seznamů
   • hlavni_diagonala(+Matice,-Diagonala)
   • otocMaticio90(+matice,-OtocenaMatice)
   • obdelnik/1, ctverec/1,
   • spirala(+Matice, -Spirala)
   • Domácí cvičení:
     • slupka(+Matice, - Slupka, -Pecka)
     • rozdelNatretiny(Seznam, Prvnitretina, DruhaTretina, treriTretina)
3. cvičení 21.října
• slupka(+Matice, - Slupka, -Pecka)
• Písemné domácí cvičení: rozdelNatretiny(Seznam, Prvnitretina, DruhaTretina, treriTretina)
• Aritmetika - jednoduché příklady
• Délka seznamu
• Největší společný dělitel
• lookup
• Reprezentace binárního stromu
• listyStromu(+Strom,-SeznamListuOdLeva), verze bez zřetězení
• Binární vyhledávací stromy
  • prvek/2
  • vloz(co,Kam,Vysl), ten obvyklý nejde 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ů
   • postavení dokonale vybalancovaného stromu z prvních N prvků rostoucího seznamu
   • Domácí cvičení
     Rozmyslet:
     • Převody mezi různými reprezentacemi permutací
     • Následující permutace v lexikografickém uspořádání
     Napsat:
     • převody p2v a inverzní v2p mezi reprezentacemi permutace jako vektoru obrazů a vektoru inverzí
5. cvičení 11. listopadu
   • Koncepce programu Eliza
   • Rozdílové seznamy
   • Převod p2c
   • 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
     • Topologické třídění
6. cvičení 18. listopadu
   • První nabídka témat na zápočtové úlohy
   • 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
   • Matching vzorů dvou vzorů složených z { *, ?, terminál } (v každím nejvýše jedna hvězdička) - rozmyslet a odladit
7. cvičení 25. listopadu
   • Písemka:
   1. Součin permutací P1 a P2 je permutace P3, která vznikne složením zobrazení P1 P2 , tj. P3(x)=P1(P2(x)). Sestavte predikáty, které realizují násobení a umocňování permutací reprezentovaných pomocí cyklů.
   2. Sestavte predikát
      soucin( +Scit1,+Scit2, -Soucin) ,
      který realizuje násobení libovolně dlouhých čísel zapsaných ve dvojkové soustavě. Argumenty jsou seznamy čísel 0 a 1 reprezentující cifry čísel od nejvíce k nejméně platné. Např.
      soucin( [1,0,0,1,1], [1,0,1], [1,0,1,1,1,1,1] )
 
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
   • Soucet 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
   • Písemný domácí úkol:Následující permutace v lexikografickém uspořádání
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ů
    • rozdělení seznamu na rosoucí začátek a zbytek
    • Rozmyslet:
      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 10:40
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 NP1040 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: