Cvičení z Neprocedurálního programování

skupina X33 - středa 10:40 S1

1. cvičení 11.října
   • jedoduché predikáty o rodinných vztacích
     bratranec(Kdo,Ci), svagr(Kdo,Ci), prababickazOtcovyStrany(Kdo,Ci)
   • vypuštění prvku ze seznamu -prvního výskytu (amatér/profesionál), všech výskytů
   • rozdělení seznamu na seznamy prvků na lichých a sudých místech
   • další jednoduché predikáty pro práci seznamy
   • Matice jako seznam řádkových seznamů a predikáty pro práci s nimi
     obdelnikova(Mat), ctvercova(Matice), hlDiag(+Matice,-HlDiagonala),
     otoc(Matice, OtocenaMatice) - vice zpusobů
     prazdna(Mat), spirala(+Matice,-Spirala)
   • Domácí úkol:
     1. Vytvorte predikat slupka(+Matice,-Slupka,-Pecka)
     2. Předpokládejte, že v databázi jsou fakta typu
        rodina(Otec,Matka,Deti) % Deti je seznam dětí od nejstaršího k nejmladšímu
        muz(Kdo) a zena (Kdo)
        Vtvořte predikáty:
        • nejstarsiBratr(Kdo, Koho)
        • starsiBratr(Kdo, Koho)
        • mladsiSestry(MlSestry,Koho) % MlSestry jsou seznam sester Koho (od nejstarší k nejml.)
        • sestry(Sestry,Koho)
        • starsiSestry(StSestry,Koho) % StSestry jsou seznam sester Koho (od nejstarší k nejml.)
2. cvičení 18.října
   • nejstarsiBratr(Kdo, Koho)
   • starsiBratr(Kdo, Koho)
   • sestry(Sestry,Koho)
   • bytiSeznamem(S)
   • prvnivyskyt(Ceho,Kde,Zacatek, Konec)
   • lezipred(Co,PredCim,Kde,Zac,Prostredek,Konec)
   • natretiny(+Seznam,-Prvni,-Druha,-Treti)
   • flatten(Seznam,PlochySeznam) se zřetězením
   • Součtové seznamy, predikat s2n(+ Souctseznam, -Seznam)
   • rozmyslet:
     1. Vytvorte predikat slupka(+Matice,-Slupka,-Pecka)
     2. flatten(+Seznam,-PlochySeznam) bez zřetězení
     3. natretinyModr(+S,-S1,-S2,-S3) rozdeleni seznamu na tri casti obsahující
        "stejný" počet modrých prvků
        (můžete předpokládat, že máte predikáty modry/1, nemodry/1
     4. predikáty pro práci se součtovými seznamy (přidávání na konec, na začátek, ubírání z konce a ze začátku, zřetězení a pod.


3. cvičení 25.října
   • predikat slupka(+Matice,-Slupka,-Pecka)
     rozmyslet elegantní variantu
   • flatten(+Seznam,-PlochySeznam) bez zřetězení
   • natretinyModr(+S,-S1,-S2,-S3) rozdeleni seznamu na tri casti obsahující
     "stejný" počet modrých prvků
   • listy(+Strom,-Listy) bez zřetězení
   • reprezentace permutace jako vektoru obrazů a jako seznam netriviálních cyklů
     rozmyslet převody mezi nimi
   • vektor inverzí permutace
     • převod vektoru inverzí na permutaci
     • rozmyslet spočtení vektoru inverzí
   • Písemný domácí úkol:
     1. quicksort bez zřetězení
     2. případně elegantní slupka
     buď přineste napsané na cvičení nebo pošlete emailem s předmětem "DcvNerpPrg" tak, aby mi došlo do ponděli večer
4. cvičení 1.listopadu
   • elegantní slupka
   • vyrobit seznam uzlů stromu v pořadí podle vzdálenosti od listů
   • vektor permutací
   • rozmyslet:
     1. topologické třídění
     2. umocňování permutace zadané pomocí seznamu netriviálních cyklů
     3. převody mezi reprezentacemi permutace jako vektoru obrazů a jako seznamu netriviálních cyklů
        zůstává
   • Písemný domácí úkol:
     
     1. kanonická reprzentace obecného stromu pomocí binárního stromu
     2. průchod do šířky obecným stromem zadaným pomocí své kanonické reprezentace
     3. průchod do hloubky obecným stromem zadaným pomocí své kanonické reprezentace
     buď přineste napsané na cvičení nebo pošlete emailem s předmětem "DcvNerpPrg" tak, aby mi došlo do ponděli večer
5. cvičení 8.listopadu
   • Písemka
6. cvičení 15.listopadu
   Jednoduché příklady v jazyce Scheme
   • obracení seznamu s konkatenací a bez ní
   • funkce mod a div
   • největší společný dělitel seznamu čísel
   • flatten pro seznamy
   • datová struktura binární strom (konstruktory a selektory - viz přednáška)
     • seznam listů stromu
     • rozmyslet: (napište si)
       funkce, která z rostoucího seznamu S a čísla N "vrátí"
       dokonale vybalancovaný binární vyhledávací strom postavený z prvních N prvků S
       a zbytek tohoto seznamu
   • rozmyslet: mobil a jeho reprezentace
     funkce zjišťující vyváženost a bezpečnost
7. cvičení 22.listopadu
   • predikát list?
   • funkce, která z rostoucího seznamu S a čísla N "vrátí"
     dokonale vybalancovaný binární vyhledávací strom postavený z prvních N prvků S
     a zbytek tohoto seznamu
   • vyváženost mobilu
   • rozmyslet: bezpečnost mobilu
   Tím jsme na cvičení ukončili práci s jazykem Scheme
   • první povídání o zápočtech
8. cvičení 29.listopadu
   • povídání o zápočtech
     
     Každý do příštího cvičení buď přijde s vlastním tématem zápočťáku nebo si vybere některé téma z nabídky. Kdo si nevybere, bude mu téma přiděleno.
     Do 15. prosince pošle každý specifikaci dohodnutého zápočťáku
   • kolektivní vytváření programů - dijkstrův algoritmus
     každá ze tří skupin dodá své dílo mailem nejpozději do úterý 5.12.2006 do 18:00


9. cvičení 6.prosince
   Haskell
   • slévání dvou upořádaných seznamů
   • násobení polynomů
   • skládání permutací
   • předvádění kolektivních programů
   • začneme s jazykem Haskell,
     podívejte se na přednášky (i tu z 5. prosince) resp. literaturu
   
   
10. cvičení 13.prosince suplováno


11. cvičení 20.prosince
    • Klouzavé průměry
    • Domácí úkol:
      více klouzavých průměrů najednou - délky intervalů jsou zadány v rostoucím seznamu
    • vypuštění prvků ležících v zadaném intervalu z binárního vyhledávacího stromu