1. 6. 2015 Jelínek

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
Uživatelský avatar
petrroll
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 23. 5. 2015 22:27
Typ studia: Informatika Bc.

1. 6. 2015 Jelínek

Příspěvek od petrroll »

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
anonym64578

Re: 1. 6. 2015 Jelínek

Příspěvek od anonym64578 »

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.
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“