Seminář Programování II - úterý 14:00 K3

1. seminář 20.února 2007
   • O zápočtech - nejpozději do 10.3. je potřeba přijít ukázat první verzi zápočtového programu a dokumentace k němu
     dokumentace by měla být již k definitivní verzi programu
   • Textové soubory - souhrnné opakování
   • Analýza úlohy kódování a dekódování morzeovky, návrh dattových struktur
     pro kódování :pole stringů indexované intervalem typu char
     pro dekódování buď hašování nebo rozhodovací - rozmyslet
   • Rozmyslet:
     Řekneme, že posloupnost je k-rostoucí jesliže se vynecháním nejvýše k prvků stane rostoucí.
 
2. seminář 27.února 2007
   • Hledání tříd ekvivalence na množině vrcholů orientovaného grafu příslušných ekvivalenci
     v je ekvivalentní w, pokud je buď v=w nebo existují cesty z v do w i z w do v
   • Hledání komponent souvislosti v neorientovaném grafu
   • k-tá mocnina orientovaného grafu G je graf se stejnou množnou vrcholů jako G, ve kterém vede hrana z v do w právě když v původním grafu G existuje sled délku k, který vede z v do w
     Vytořte k danému grafi a číslu k k-tou mocninu grafu G
 
3. seminář 3.března 2007
   • Dynamicky alokované proměnné, ukazatele, new, dispose
   • Destruktivní a nedestruktivní vytváření uspořádaného seznamu obsahujícího stejné prvky jako zadaný seznam
     D.cv.: dodělat
   • Vypouštění intervalu hodnot z neklesajícího dvousměrného seznamu
     D.cv.: dodělat
   • D.cv. - technický příklad s pánskou resp. dámskou volenkou
 
4. seminář 13.března 2006
   • Opakování - předávání parametrů hodnotou a referencí
   • Práce se seznamy - technická úloha volenka
   • Domácí úkol: skladiště
     pošlete mailem s předmětem "PRM045 - skladiste"
     stačí poslat text, není nutné ladit na počítači.
   • Rozmyslet resp. dodělat:
     • Volenka bez pomocných hlav
     • destruktivní (nesmí se volat new - jen přepojujeme ukazatele)
       a nedestruktivní (musí být ba "vstupní" seznamy zachovány - vytváříme zcela nový)
       varianty spojení dvou rostoucích seznamů do jednoho rostoucího seznamu
 
5. seminář 20.března 2006
   • Technická úloha: Vyřazení konzervy ze skladiště
   • seznam listů stromu
   • Domácí úkol:
     Množnina je reprezentována jako binární vyhledávací strom,
     vytvořte podprogramy, které realizují
     • destruktivní resp. nedestruktivní sjednocení
     • destruktivní resp. nedestruktivní průnik
 
6. seminář 27.března 2006
   • Dohoda o odevzdávání zbývajících zápočtových programů
   • Písemná práce
     • Množina je realizována jako rostoucí jednosměrný seznam ukončený nilem.
       Vytvořte podprogram, který realizuje nedestruktivní (nesmíte použít proceduru new) průnik dvou množin
     • Vytvořte podprogram, který k danému binárnímu stromu vytvoří seznam prvků, v něm obsažených, v pořadí "po hladinách od leva do prava"
   • Domácí úkol:
     z minulého cvičení
 
7. seminář 3.dubna 2007
   • Komentář k písemkám - pro většinu studentů je nutné se spojovými strukturami zabývat více,
     případně přijít se svými pokusy na konzultaci
   • Průchod binárního stromu do šířky
   • Povinný domácí úkol: - pošlete mailem s předmětem DCVPRM
     Vytvořte podprogram, který vypíše do výstupního souboru čísla uložená ve vrcholech binárního stromu v pořadí
     podle vzdálenosti vrchlu od listů - a vrcholy ve stejné vzdálenosti odleva doprava.
 
8. seminář 10.dubna 2007
   Tři větší úlohy "a la zkoušková písemka"
   • Volba "prezidenta" napodobující vícekolový systém při jednom hlasování
     návrh komunikace mezi volebními místy, okresy, kraji a centrem, algoritmus zpravování výsledků
   • Povinný domácí úkol: Je dána posloupnost oáz, ležících na trase karavany (oáza je zadána vzdáleností od počátku cesty a cenou za přenocování). Karavana se může pohybovat pouze ve dne, v noci musí přespat v některé oáze. Za den je schopna urazit maximálně M kilometrů.
     Najděte efektivní algoritmus, který najde nejlacinější cestu karavany ze startu do cíle.
   • Nepovinný domácí úkol: Předpokládejme hru typu NIM (není příliš podstatné), ve které hráč na tahu prohrál, pokud již nemůže provést žádný tah. Máme k dispozici unitu, která ve své části interface exportuje datový typy POZICE (reprezentuje pozici hry) a datový typ TAH (reprezentuje tah) a dva podprogramy:
     podprogram TAHY, který k dané pozici vrátí seznam tahů, které jsou v dané pozici možné (může být prázdný)
     podprogram NovaPozice, který k pozici a k tahu vrátí novou pozici, která vznikne z původní provedením daného tahu.
     Naprogramujte podprogram, který pro danou pozici rozhodne, zda je pro hráče na tahu vyhraná nebo prohraná.
 
9. seminář 17.dubna 2007
   • První nabídka témat zápočtových úloh,
     Nejpozději do 27.dubna by každý měl být dohodnut o tématu zápočtové úlohy,
     Nejpozději do 17.května by měl mít schválenu specifikaci
   • Analýza tvorby programu realizující algoritmus vnitřního třídění s n páskámi založený na slévaní (n-1) pásek na n-tou volnou- cíl přiblížit se polyfázovému třídění s optimální rozdělením počtu běhů na jednotlivé běhy (prostředek - fiktivní běhy)
     Kolektivní domácí úkol - poslat e-mailem do 3.května
   • Povinný domácí úkol: podívat se před příštím cvičením na objektové programování z přednášky
 
10. seminář 24.dubna 2007
    • Zápočtové úlohy.
    • Opakování objektového programování v Pascalu
    • Analýza objektové typové hierarchie realizující abstraktní typ tabulka
      a několik jeho realizací (podtříd) pomocí pole, seznamu/ů a binárního vyhledávacího stromu
      domácí úkol: napište deklarace příslušných tříd včetně naprogramování metod
      
    • Analýza návrhu třídy pro provádění cenzury "a la Yosarian"
      domácí úkol:Napište příslušnou třídu a alespoň dva programy používající její podtřídy pro konkrétní cenzurní algoritmy (např.
      cenzurní podmnínka: "slovo obsahuje lichý výskyt znaku 'o' (počítáno od začátku souboru)
      "některé z následujících N slov končí na 'ová' "
      cenzurní akce: "zahvězdičkování slova", "nahrazení všech písmen ve náhodně generovanými znaky")
    • Podívejte se na dynamické programování z přednášky
    Domácí úkoly pošlete e-mailem do 11. května
 
11. seminář 15.května 2007
    • O zápočtech
    • Konstrukce optimálního binárního vyhledávacího stromu k zadaným četnostem úspěšných dotazů
      včetně upravy efektivity na složitost O(n²),
      rozmyslete jednoduchou modifikaci, když jsou zadány i četnosti jednotlivých neúspěšných dotazů
    • Opakování úlohy o optimálním uzávorkování součinu matic
    • Floyd-Warshallův algoritmus pro hledání nejkratší cesty v grafu
    • Obecně o dynamickém programování
    • Domácí úkol: (pošlete elektronicky do 23.5. v poledne)
      napište deklarace tříd včetně naprogramování některých metod v objektové hierarchii probírané 24.dubna, která implementuje abstraktvní třídu tabulka a několik jejích podtříd
    • Rozmyslete algoritmus hledající optimální rozložení písmen na klávesnici mobilního telefonu jsouli zadány frekvence použití jednotlivých písmen
    • Dodělat: dopsat komentáře ke kolektivním domácím úkolům
     
    Hodně studentů neposlalo dosud specifikaci zápočtové úlohy - termín prodloužen do 27.května
     
    Nejpozději do 22.června byste se měli stavit na konzultaci a ukázat, co máte na zápočtové úloze uděláno, co jste rozmysleli a jaké máte potíže (výjimky nutno domluvit individuálně).
    1.-7. června tu nejsem