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
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