Přednáška se koná v úterý od 9:00 v S5.
Doporučená literatura:
Cvičení a zápočty: Informace o zápočtech se dozvíte od svých cvičících.
Zkoušky: Přihlašování pomocí SISu, termíny tamtéž.
Co se zatím předneslo:
| 19. 2. | Odhady na faktoriály a
kombinační čísla. |
| 26. 2. |
Úvod do vytvořujících funkcí. |
| 5. 3. |
Pokračování vytvořujících
funkcí, Fibonacciho čísla, Catalanova čísla. |
| 12. 3. |
Projektivní roviny, latinské
čtverce. |
| 19. 3. |
Počítání koster grafů (úplný
graf, úplný graf bez hrany, odvození rekurence pro speciální grafy). |
| 26. 3. |
Počítání dvěma způsoby:
Spernerova věta, maximální počet hran v grafu bez trojúhelníku a bez
čtyřcyklu. |
| 2. 4. |
Toky a řezy v sítích: minimaxová
věta, nástin Fordova-Fulkersonova algoritmu. |
| 9. 4. |
Vrcholová a hranová souvislost
neorientovaných grafů. Mengerova věta a její hranová analogie. |
| 16. 4. |
Párování a vrcholové pokrytí v
bipartitních grafech: Kőnigova–Egerváryho věta. Systémy různých
reprezentantů: Hallova věta. Příklad aplikace: Birkhoffova–von
Neumannova věta o bistochastických maticích. |
| 23. 4. |
Lemma o uších. Ramseyova věta (ve verzi pro grafy a ve verzi pro barvení dvojic vrcholů více barvami). |
| 30. 4. |
Schurova věta. Nekonečná Ramseyova věta pro p-tice. |
| 7. 5. |
Princip kompaktnosti, jeho
aplikace na barevnost nekonečných grafů. Konečná verze
Ramseyovy věty pro p-tice. Kanonická Ramseyova věta pro
barvení dvojic. |
| 14. 5. |
Samoopravné kódy: základní pojmy
a jejich vlastnosti (Hammingova váha, vzdálenost kódu, lineární kód,
generující matice, ortogonální doplněk, kontrolní matice). |
| 21. 5. |
Hammingovy kódy, Hadamardovy kódy, Singletonův, Hammingův a Gilbertův-Varshamovův odhad na parametry kódů. |