Teaching

This part of my homepage is in Czech only -- I don't think anyone else than my students would use it.

Vyuka

V zimnim semestru 2001/2002 vedu cviceni k predmetu Programovani I. Konzultacni hodiny nemam, nicmene pokud budete chtit s cimkoliv poradit/pomoci, nejak se dohodneme (pokud se to bude tykat tohoto predmetu, slibuji, ze si cas najdu, ale i pokud to bude cokoliv jineho, o cem budu neco vedet, tak se pokusim).

Za co je zapocet:

Cosi, co se tvari jako zkouska, vypada to jako zkouska a neni to zkouska, a je to zalezitost vyucujiciho a me se to moc netyka
Zapoctovy program -- tema byste mi meli oznamit do 30.11.2001, pokud vas nic nenapada, zkuste se podivat sem. I pokud uz nejake tema mate, stejne se vyplati tam podivat -- vicemene vsechny tam uvedene informace (dokumentace, osetreni vstupu, ...) plati i u me (jen jsem liny je sem psat). Jiz prirazena temata:
- Petr Kratochvil -- jezdec na sachovnici
- Erik Kratochvíl -- knihovna operaci s polynomy
- Vaclav Krajicek -- funkce (grafy, reseni rovnic, ...)
- Pavel Krc -- editor binarnich souboru
- Jakub Kotowski -- Life
- Jan Kodym -- hadani zvirat
- Daniel Konecny -- zobrazovani teles
- Pavel Kohout -- matice
Vyreseni alespon (2*n) div 3 domacich ukolu, kde n je pocet domacich ukolu, ktere zadam (toto nemusi byt uplne pravda, pokud bude vychazet, ze z vas podle tohohle kriteria 3/4 vyhodim, upravim pravidla). Zatim zadane ukoly:
- (Do 2.11.) Na vstupu mate cele cislo x a posloupnost celych cisel a₀, a₁, ... a_n zakoncenou cislem -31415 (ktere se mezi a_i nevyskytuje). Urcete
  1. hodnotu polynomu a₀+a₁x+a₂x²+...
  2. hodnotu polynomu a₀xⁿ+a₁x^n-1+a₂x^n-2+...
  Pri reseni nepouzivejte pole. Pozor, toto zadani se trochu lisi od toho, jak jsem ho rikal na cviceni -- delku posloupnosti dopredu neznate!!! Casova slozitost by mela byt linearni (jinak a presneji receno -- meli byste pouzit nanejvys 2(n+1) nasobeni).
  Vyresili:
  - Pavel Janda
  - Petr Kratochvil
  - Erik Kratochvil
  - Michal Kovac
  - Jakub Kotowski
  - Tomas Kovarik
  - Pavel Krc
  - Daniel Konecny
  - Fanda Kovarik
  - Peter Houska (1/2)
  - Pavel Kohout
  - Jan Kodym
  - Vit Koumar
  - Juraj Konecny
- (Do 9.11.) Na vstupu mame prirozena cisla n a k. Krome toho je zadana neklesajici posloupnost celych cisel a_1 <= ... <= a_k nasledujicim zpusobem: k dispozici mame dve funkce, get_first a get_last. Funkce get_first z teto posloupnosti odebere 1. prvek (tedy posloupnost o 1 prvek zkrati) a vrati ho. Funkce get_last z ni odebere posledni prvek a vrati ho. (Neni specifikovano, co se stane, kdyz temito funkcemi sezerete celou posloupnost a zkusite je vyvolat -- tedy byste to nemeli delat.) Vas program by mel najit cisla i, j takova, ze a_i + a_j = n, nebo ohlasit, ze takova neexistuji. Pri reseni nepouzivejte pole.
  Vyresili:
  - Petr Kratochvil
  - Erik Kratochvil
  - Vaclav Krajicek
  - Pavel Janda
  - Jan Kodym
  - Peter Houska
  - Vit Koumar
  - Pavel Krc
  - Jakub Kotowski
  - Michal Kovac
  - Daniel Konecny
  - Juraj Konecny
- (Do 16.11.) Na vstupu mame zadana cela cisla a, b, c; napiste program, ktery najde alespon 1 reseni rovnice a * x = b (mod c) (tj. takove x, ze c deli a * x - b) nebo zjisti, ze neexistuje. Pri reseni muzete pouzit pole (ale vubec me nenapada, k cemu byste ho potrebovali :-). Casova slozitost reseni smi byt nejvyse logaritmicka v c (za predpokladu, ze operace jako nasobeni a deleni probihaji v konstantnim case).
  Vyresili:
  - Petr Kratochvil (1/2)
  - Michal Kovac
  Tak tohle jsem asi trochu prehnal ;-)
- (Do 23.11.) Na vstupu dostanete neorientovany graf zadany seznamem hran (tj. dostanete cisla n, m, kde n je pocet vrcholu, m je pocet hran, a dale m dvojic cisel 1..n, kde dvojice a, b odpovida tomu, ze mezi vrcholy a, b vede hrana). Ulohou je zjistit, zda tento graf je souvisly. Casova slozitost by mela byt radove m+n.
  Hint 1: Prevedte si graf do reprezentace, v niz budete ke kazdemu vrcholu znat seznam sousedu. Pak si zvolte jeden z vrcholu a provedte z nej prohledavani grafu (do hloubky nebo do sirky, to je jedno). Graf je nesouvisly prave tehdy, kdyz existuje vrchol, do ktereho jste se nedostali.
  Hint 2: Pokud nevite, jak se takove prohledavani grafu dela, a nedokazete to vymyslet, poslete mi alespon ten prevod, bude za to polovina ukolu.
  Vyresili:
  - Erik Kratochvil
  - Petr Kratochvil
  - Vaclav Krajicek
  - Jakub Kotowski
  - Jan Kodym
  - Pavel Krc (1/2)
  - Vit Koumar (1/2)
  - Pavel Janda (1/2)
- (Do 30.11., prodlouzeno do 7.12.) Mate dan zakoreneny binarni strom [Definice (nenechte se ji zmast, radeji se podivejte na obrazek (a opovazte se smat!)):
  1. () je ZBS
  2. Jsou-li A, B ZBS, v vrchol, je (v,A,B) ZBS
  3. Kazdy ZBS se da ziskat konecnym poctem opakovani pravidel 1, 2.
  tedy strom na obrazku je
```
(a,
 (b,
  (c,(),()),
  (d,(),())
  ),
 (e,
  (f,
   (g,(),()),
   (h,(),())
   ),
  (i,(),())
  )
 )
```
  ]. Dale bude nasledovat posloupnost dotazu, coz jsou dvojice vrcholu tohoto stromu. Vas program by mel na dostaz a, b odpovedet jejich nejblizsim spolecnym predchudcem (tj. vrchol v takovy, ze jsou-li c_a, c_b (jednoznacne urcene) cesty z a, b ke koreni, v lezi na obou z nich a zadny vrchol mezi a a v nelezi na c_b). Tedy napriklad na dotaz b, f je odpoved a, na dotaz e, h je to e.
  Pozn.: uplne mi staci reseni, ktere bude mit casovou slozitost na jeden dotaz umernou delce cesty mezi zadanymi vrcholy (ja vim, ze je to trivialita).
  Ale zda se, ze uz nikdo jiny (alespon se nikdo jeste ani nepokusil mi ulohu odevzdat); tak par hintu k mistum, ktere by mohly cinit potize:
  - ZBS jde reprezentovat jako pole recordu; v recordu budeme mit ulozeno oznaceni vrcholu a pozice, na nichz jsou ulozeny zaznamy o jeho synech (nebo nejake specialni hodnoty, jsou-li synove ()), plus pripadne dalsi pomocne informace.
  - Muzete si v rozumne mire upravit vstupni format (nijak zvlast me nezajima, zda si vrcholy budete oznacovat cisly, jestli misto () pouzijete nejaky jiny symbol nebo zda budete umoznovat mit ve vstupu mezery, odradkovani apod.)
  - Reseni samotne ulozky je jednoduche; mozna se vam ale bude hodit mit ve vrcholech ulozene dalsi pomocne informace (typu kdo je otcem daneho vrcholu apod.)
  Vyresili:
  - Petr Kratochvil
  - Vaclav Krajicek
  - Erik Kratochvil
  - Jakub Kotowski
  - Pavel Kohout
  - Jan Kodym (3/4)
  - Daniel Konecny (3/4)
- (Do 7.12., prodlouzeno do 14.12.) Mejme dan zakoreneny strom retezcem takto: Necht ma koren n synu, jejichz kody jsou s₁, s₂, ..., s_n. Pak Kod tohoto stromu je #s₁s₂...s_n^ (tedy kod stromu z minuleho prikladu je ###^#^^###^#^^#^^^). Prevedte tento strom do nasledujici reprezentace: vrcholy budou ulozeny za sebou v poli, pro kazdy vrchol si pamatujeme pozici jeho nejlevejsiho syna (0 nema-li ho) a jeho praveho bratra (0 nema-li ho). Tedy pro strom z minuleho prikladu:
```
vrchol : syn bratr
   1   :  2    0
   2   :  3    5
   3   :  0    4
   4   :  0    0
   5   :  6    0
   6   :  7    9
   7   :  0    8
   8   :  0    0
   9   :  0    0
```
  Vyresili:
  - Petr Kratochvil
  - Vaclav Krajicek
  - Erik Kratochvil
  - Michal Kovac
  - Pavel Kohout
  - Pavel Janda
  - Jan Kodym
- (Do neurcita) Regularni vyrazy jsou zpusob, jak zadat mnozinu slov (alespon z jednoho uhlu pohledu; chcete-li trochu jiny, konzultujte napr. grep, sed nebo perl). Jsou definovany takto:
  - Libovolne pismeno 'x' je regularni vyraz, jimz je definovana mnozina {'x'} (tj. obsahujici prave jen slovo 'x').
  - Jsou-li R₁, R₂ regularni vyrazy, jimz odpovidaji mnoziny slov M₁, M₂, pak R=(R₁)(R₂) je regularni vyraz odpovidajici mnozine slov M={uv|u je prvkem M₁, v je prvkem M₂} (tj. zretezeni slov).
  - Jsou-li R₁, R₂ regularni vyrazy, jimz odpovidaji mnoziny slov M₁, M₂, pak R=(R₁)|(R₂) je regularni vyraz odpovidajici mnozine slov M=M₁ sjednoceno M₂ (tj. libovolne slovo odpovidajici R₁ nebo R₂).
  - Je-li R₁ regularni vyraz, jemuz odpovida mnozina slov M₁, pak R=(R₁)? je regularni vyraz odpovidajici mnozine slov M=M₁ sjednoceno {''} (tj. libovolne slovo odpovidajici R₁ nebo slovo nulove delky).
  - Je-li R₁ regularni vyraz, jemuz odpovida mnozina slov M₁, pak R=(R₁)+ je regularni vyraz odpovidajici mnozine slov M={v₁...v_n, n>=1| v_i jsou prvkem M₁} (tj. libovolny kladny pocet opakovani slov odpovidajicich R₁).
  - Je-li R₁ regularni vyraz, jemuz odpovida mnozina slov M₁, pak R=(R₁)* je regularni vyraz se stejnym vyznamem jako (R₁)+? (tj. libovolny (i nulovy) pocet opakovani slov odpovidajicich R₁).
  - Vsechny regularni vyrazy lze vytvorit konecnym poctem opakovani vyse uvedenych pravidel.
  Pro pohodlnost se predpoklada, ze vyse uvedene operace maji prioritu v poradi + (nejvyssi), *, ?, zretezeni, | (nejnizsi) a zbytecne zavorky se vynechavaji obdobne jako u aritmetickych vyrazu; tj. nepiseme ((ab)c)|(d), ale jednoduse abc|d.
  Uloha: mate dan regularni vyraz; rozhodnete, zda je v mnozine jemu odpovidajici slovo '' (tj. slovo nulove delky). Ulohu by vas program mel resit v case linearnim k delce zadaneho vyrazu.
  Napoveda: asi nejslozitejsi na uloze je nacteni zadani; vsimnete si podobnosti s vyhodnocovanim aritmetickych vyrazu.

Ucast na cviceni neni povinna; na druhou stranu, pokud po me bude chtit zapocet nekdo, koho jsem na cviceni nikdy nevidel, asi bude mit problem.