1. 6. 2015 Jelínek

1. Definujte pojmy "vrcholový řez" a vrcholová souvislost grafu G [5 bodů].

2. Zformulujte a dokažte Spernerovu větu o maximální velikosti nezávislého množinového systému [10 bodů].

3. Nechť M je matice se čtyřmi řádky a osmi sloupci, jejíž sloupce jsou přesně všechny různé binární vektory délky 4 mající na posledním místě jedničku. Nechť C je lineární kód s kontrolní maticí M. Jakou má C dimenzi a jakou má minimální vzdálenost. Svou odpověď zdůvodněte [5 bodů].

4. Mějme dvě posloupnosti čísel (a1, a2, ...), (b1, b2, ...) definované pomocí následující rovnosti:
   a0 = 0
   b0 = -1
   an = an-1 - bn-1
   bn = 2an-1 + bn-1

Najděte vzorce v uzavřeném tvaru pro příslušné vytvořující funkce A(x) a B(x)...

Bodování po 5 bodech (hranice možná +- 1 u dvojky a trojky), tj.: 30-26: 1 26-20 (?): 2 20-15 (?): 3

Opravování mé písemky bylo velmi příznivé, snaha najít co se student snažil říct. U vytvořující funkce nešlo jen o výsledek ale opravdu hodně o postup. Konkrétně jak opravil mojí písemku se můžete podívat na fotkách zde (neručím za to, že ten odkaz časem nezačne ukazovat na void): http://1drv.ms/1dGkRE8

Co se týče ústní:
měl jsem 17 bodů, šel jsem na ústní s tím, že tam se toho moc zkazit nedá.
Dostal jsem zadáno jak souvisí minimální řez & maximální tok. S tím, že pokud si vzpomenu na důkaz tak můžu přidat.
Teorii jsem vybudoval celkem dobře. Na důkaz jsem si vzpomněl jenom na to, že se to dělalo sporem.

Pak mi dal další otázku na latinské čtverce.
Opět definice dobrá & pak jsem ještě ukázal že množina ortogonálních čtverců nemůže být větší než [n - 1]

Pak mi dal další otázku na odhad kombinační čísla $$\binom{2n}{n}$$
tam jsem střelil $$\frac{2^{n-2}}{2n+1} \leq {2n \choose n} \leq 2^{n-2}$$ což je blbě...

Na toto už jsem mu odpověděl, že mi to nemyslí a že toho radši necháme, tak mi dal 17 bodů & 3 do SISu.