PRG005 - cvičení
skupina X35 ZS 2007/8 - středa 9:00 T5

• Docházka
• Obsah cvičení a úkoly
  1. cvičení 3.října
  2. cvičení 10.října
  3. cvičení 17.října
  4. cvičení 24.října
  5. cvičení 31.října
  6. cvičení 7.listopadu
  7. cvičení 14.listopadu
  8. cvičení 21.listopadu
  9. cvičení 28.listopadu
  cvičení 5. a 12. 12. se nekonají - nahradíme je později, až bude probrán jazyk Haskell
  Stáhněte a vytiskněte si z www.haskell.org materiál Paul Hudak, Joseph H. Fasel: A Gentle Introduction to Haskell
  10. (náhradní) cvičení 18.prosince 19:00 v S1
  11. cvičení 19.prosince
  12. (náhradní) cvičení 4.ledna 10:40 S9
  13. cvičení 29.listopadu

Obsah cvičení

1. cvičení 3.října
   • Jednoduché příklady na práci s databází o rodinných vztazích
   • Proměnná, dotaz, fakt, pravidlo, anonymní proměnná
   • Seznamy a jednoduché predikáty pro práci s nimi
2. cvičení 10.října
• Opakování seznamů
• Zřetězení seznamů, permutace seznamu, rozdělování seznamu, ...
• starsibratr(Kdo, Koho), nejstarsibratr(Kdo, Koho)
• Rozmyslet: Sestavte predikát rozpul(Seznam,Prvni, Druha), který rozdělí seznam seznam na dvě poloviny - nesmíte použít aritmetiku
• Písemný domácí úkol:
  pošlete mailem nejpozději do pondělí v poledne se subjectem "PRG005Dcv1"
  1. Sestavte predikát vypustVsechny (Co, Odkud, Zbytek),
     který uspěje vždy a platí pokud Zbytek je seznam, který vznikne vypuštením všech výskytů prvku Co ze seznamu Odkud
  2. Sestavte predikát vypustPrvni (Co, Odkud, Zbytek),
     který uspěje jen pokud je Co prvkem seznamu Odkud a v takovém případě platí pokud Zbytek je seznam, který vznikne vypuštením prvního výskytu prvku Co ze seznamu Odkud
  3. Sestavte predikát vypustPredposledni (Co, Odkud, Zbytek),
     který uspěje jen pokud se prvek Co vyskytuje v seznamu Odkud alespoň dvakrát
     a v takovém případě platí pokud Zbytek je seznam, který vznikne vypuštením předposledního výskytu prvku Co ze seznamu Odkud
3. cvičení 17.října
• komentáč k domácímu úkolu.
• Naivní otáčení s kavdartickou složitostí a otášení pomocí akumulátoru (reverse_append) v lineárním čase
• Predikát býti_seznamem/1
• Matice jako seznam řádkových seznamů
  obdelnik/1 , ctverec/1
• diagonala/2
• otoc_matici/2
• Písemný domácí úkol č.2
  pošlete mailem nejpozději do pondělí v poledne se subjectem "PRG005Dcv2"
  zdrojový text pošlete jako přílohu se jmenem "vase_prijmeni" - napr kozak.rtf, kozak.txt nebo kozak.pl
  1. Sestavte predikát spirala(+Matice, -Spirala)
  2. Sestavte predikát slupka(+Matice, -Slupka, -Pecka)
4. cvičení 24.října
   • komentář k domácímu úkolu
   • bytiprazdnoumatici/1
   • flatten/2
   • aritmetika
   • největší společný dělitel dvou čísel, seznamu čísel
   • vektor a matice anonymních proměnných zadaných rozměrů
   • "smotání" matice zadaných rozměrů ze spirály
   • Rozmyslet:
     Predikát, který k dané permutaci nalezne nejbližší větší v lexikografickém uspořádání
   • Písemný domácí úkol č.3
     pošlete mailem nejpozději do pondělí v poledne se subjectem "PRG005Dcv3"
     zdrojový text pošlete jako přílohu se jmenem "vase_prijmeni" - napr kozak.rtf, kozak.txt nebo kozak.pl
     1. Sestavte predikáty pro převody mezi reprezentacemi permutace
        jako vektoru obrazů a jako seznamu netriviálních cyklů
     2. Sestavte predikát flatten, který nepoužívá konkatenaci
5. cvičení 31.října
   • Dohodli jsme si konzultaci o práci s překladačem na čtvrtek 1.listopadu v 8:00 v laboratoři v rotundě
   • Predikát, který k dané permutaci nalezne nejbližší větší v lexikografickém uspořádání
   • Binární stromy, seznam listů bez konkatenace
   • Vytvoření dokonale vybalancovaného binárního vyhledávacího stromu zadané velikosti ze začátku rostoucího seznamu
   • Zopakujte si vše, co bylo na přednáškách a cvičeních, pro neúnosně mnoho zúčastněných je to "japonský film s čínskými titulky".
   • Rozmyslet:
     Predikát, který k danému stromu vydá seznam vrchlolů seřazených podle vzdálenosti od listů (a uvnitř stejné vzdálenosti "odleva doprava"
   • Zůstává písemný domácí úkol č.3 - pokud budete posílat znovu, pošlete celé a do subjectu mailu napište navíc slovo znovu
   • Písemný domácí úkol č.4
     pošlete mailem nejpozději do pondělí v poledne se subjectem "PRG005Dcv4"
     zdrojový text pošlete jako přílohu se jmenem "vase_prijmeni" - napr kozak.rtf, kozak.txt nebo kozak.pl
     1. Sestavte predikáty pro vkládání čísla do binárního vyhledávacího stromu,
        který uspěje i když tam dané číslo již je
     2. Sestavte predikát pro vypuštění čísla zo binárního vyhledávacího stromu,
        který uspěje i když tam dané číslo nebylo
6. cvičení 7.listopadu
   • Predikát, který k danému stromu vydá seznam vrchlolů seřazených podle vzdálenosti od listů (a uvnitř stejné vzdálenosti "odleva doprava"
   • topologické třídění
   • Rozmyslet:
     Predikát, který realizuje algoritmus topologického třídění takový, že
     uspěje na každém grafu a výsledkem je dvojice:
     jejiž první složka vyjadřuje, zda existuje topologické uspořádání nebo ne
     a druhou je buď topologické uspořádání nebo nějaký cyklus v grafu
   • Písemný domácí úkol č.5
     pošlete mailem nejpozději do pondělí v poledne se subjectem "PRG005Dcv5"
     zdrojový text pošlete jako přílohu se jmenem "vase_prijmeni" - napr kozak.rtf, kozak.txt nebo kozak.pl
     Sestavte predikáty pro průchod obecným stromem do šířky a do hloubky
7. cvičení 14.listopadu
   • Komentář k domácím úkolům
   • První návrh témat zápočtových programů
     dohoda: každý přijde s tématem a po tom, co se na něm dohodneme, mi nejpozději do Mikuláše pošle přesnější specifikaci zápočtové úlohy
   • Predikáty bagof a setof - význam a typické použití
   • negace a řez
   • bubblesort
   • Písemný domácí úkol č.6
     pošlete mailem nejpozději do pondělí v poledne se subjectem "PRG005Dcv6"
     zdrojový text pošlete jako přílohu se jmenem "vase_prijmeni" - napr kozak.rtf, kozak.txt nebo kozak.pl
     Sestavte predikáty zjišťování zda zadaná formule výrokového počtu je či není tautologie
     definujte operátory pro výrokové spojky, abyste mohli formule psát obvyklejším způsobem.
8. cvičení 21.listopadu
   • komentář k domácím úkolům
   • Mobily
     1. vyváženost - dvě řešení
     2. bezpečnost - písemka
        pokud víte, že nemáte dobře pošlete mailem nejpozději do pondělí v poledne se subjectem "PRG005Dcv7"
        zdrojový text pošlete jako přílohu se jmenem "vase_prijmeni" - napr kozak.rtf, kozak.txt nebo kozak.pl
9. cvičení 28.listopadu
   cvičení 5. a 12. 12. se nekonají - nahradíme je později, až bude na přednášce probrán jazyk Haskell,
   termíny pro zadání zápočtových úloh trvají - když tak využijte telefon k domluvě
   Zápočtovou písemku (z Prologu) navrhuji v prvním týdnu v lednu - buď na náhradním cvičení nebo ve speciálním čase
   SCHEME
   • délka seznamu
   • konkttenace seznamů
   • otáčení seznamů s akumulátorem
   • funkce div a mod
   • binární stromy
     • interface - konstruktory a selektory
     • vkládání do binárního vyhledávacího stromu
     • postavení dokonale vybalancovaného binárního vyhledávacího stromu ze začátku zadané délky rostoucího seznamu
10. (náhradní) cvičení úterý 18.prosince 19:00 v S1
    • Typový systém v Haskelu, curryfikace, typová specifikace funkcí
    • seznamy
    • mečování parametrů
    • Mocninné řady - derivace, k-tá derivace, součet mocniných řad, hodnota součtu prvních k čleů v bodě x
      rozmyslet součin
    • definice polymorfických typů - strom
      výpis listů, vkládání do binárního stromu
    • moticace pro zavedení tříd
    • generátor seznamů
11. cvičení 19.prosince
12. (náhradní) cvičení 4.ledna 10:40 v S9
13. cvičení 9.ledna