Zde se průběžně budou objevovat informace k přednášce z diskrétní matematiky. (Typicky se nové informace budou objevovat odpoledne/večer po přednášce nebo druhý den.)
Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku.
Vřele doporučuji, ať si někdy uděláte čas a zajdete se podívat, jaké chyby jste v písemce měli (i pokud jste už uspěli). To je možné po domluvě emailem v mé kanceláři nebo také jeden z velmi vhodných termínů je pondělí 5. června v cca 9:15 v učebně S10. Upozorňuji, že dříve než 5. června nebudu v Praze.
Předtermín: V pátek 26. 5. bude předtermín, viz informace v SIS. Předtermín bude speciální: Zkouška na předtermínu bude pouze písemná, příklady i teorie. Předtermín může být malinko těžší než regulerní zkoušky. Nic však neriskujete, zapisovat se budou pouze známky 1 nebo 2 (lze odmítnout), ostatní známky se zapisovat nebudou (tedy známky 3 a 4; pokud tyto známky dostanete, nepočítá se tento předtermín jako neúspěšný pokus). Zápočet pro účast na předtermínu nevyžaduju. (Pro regulerní termíny ale bude potřeba.)
Na předtermínu může být i látka z poslední přednášky, což budou lineární kódy. Pokud se na ni chcete podívat dopředu, doporučuji konzultovat naskenované přípravy doc. Fialy, viz jeho domovská stránka. (Podrobnější čtení o kódech můžete nalézt v skriptech T. Kaisera, viz literatura [K] níže, ale tato skripta obsahují mnohem více informací než na přednášce probereme.)
Regulerní termíny: Regulerní termíny najdete v SISu. Jde o 7. 6. (st), 13. 6 (út), 15. 6. (čt) a 28. 6. (st). Na regulerním termínu bude 1 hodina písemka na počítání příkladů a poté hned bude navazovat ústní zkoušení (s písemnou přípravou) z teorie. Dále plánuji jeden termín v srpnu nebo září, viz informace na začátku stránky.
[MN] J. Matoušek, J. Nešetřil, Kapitoly z Diskrétní Matematiky, vydání z roku 2009 (Varování! Číslování kapitol ve starších vydáních je jiné. Neodpovídá tedy mému číslování pro průběh přednášek.)
[VM] T. Valla, J. Matoušek, skriptíčka Kombinatorika a Grafy I. Ke stažení, viz také stránka Tomáše Vally.
[K] T. Kaiser skripta o samoopravných kódech, zde.Cvičení k mé skupině vede Jan Kynčl (stránka k cvičení) a já (stránka k cvičení). Také doporučuji se podívat do sbírky úloh.
Přednáška 1 Odhady faktoriálu a kombinačních čísel: Triviální odhad faktoriálu pomocí n^(n/2) a n^n. Stirlingova formule a poměrně těsné nerovnosti pro faktoriál (bez důkazu). Rozumný odhad faktoriálu s důkazem. Nerovnost: e^x je vždy alespoň 1 + x. Porovnávání kombinačních čísel na témže řádku Pascalova trojúhelníku. Odhady prostředního kombinačního čísla; nejprve pomocí binomické věty, dále přes Stirlingovu formuli a nakonec relativně přesný odhad s důkazem. Příklad využití: pravděpodobnost, že spravedlivou mincí naházíme stejný počet orlů a panen. Literatura: [MN, 3.4 a 3.5]
Přednáška 2 Generující funkce (známé též jako vytvořující funkce): Motivační příklad s korunami, dvoukorunami a pětikorunami. Definice generující funkce posloupnosti. Připomenutí z analýzy: kdy mocninná řada konverguje (absolutně). Operace s generujícími funkcemi. Příklad výpočtu generující funkce. Zobecněná kombinační čísla a zobecněná binomická věta. Výpočet (-n) nad k. Náznak důkazu zobecněné binomické věty přes Taylorův polynom. Literatura: [MN, 12.1 a 12.2]
Přednáška 3 Aplikace generujících funkcí. Počet binárních posloupností bez dvou po sobě jdoucích 0. Fibonacciho posloupnost a její generující funkce. Dopočet explicitního vzorce. (Dobrovolně: explicitní vzoreček pro lineární homogenní rekurentně zadané posloupnosti přes charakteristický polynom; vede to ke snazším výpočtům.) Počet binárních stromů a Catalanova čísla. Zatím jenom výpočet generující funkce pro Catalanova čísla. (Zbývá dopočítat koeficienty.) Literatura: [MN, 12.3 a 12.4]
Přednáška 4 Dopočítání explicitního vzorce pro Catalanova čísla. Zmínka o dalších situacích, kdy se Catalanova čísla vyskytují (korektní uzávorkování, cesty pod diagonálou). Konečné projektivní roviny: Motivace s reálnou projektivní rovinou. Axiomatická definice konečné projektivní roviny. Věta, všechny přímky mají stejný počet bodů. Definice řádu. Věta o počtu přímek procházejících jedním bodem, a o celkovém počtu bodů a přímek v kon. proj. rovině řádu q (počet přímek zatím nedokázaný). Duální (množinový) systém. Věta, že duální systém kon. proj. roviny je také kon. proj. rovina (důkaz příště). Literatura: [MN, 12.4 a 9.1]
Přednáška 5 Důkaz z minula o duálním systému a také dokončení důkazu pro počet přímek projektivní roviny řádu q. Věta o existenci konečných projektivních rovin pro mocniny prvočísla. Důkaz pomocí existence konečných komutativních těles s počtem prvků mocnina prvočísla (tato věta bez důkazu); základní konstrukce funguje i pro nekonečná tělesa. Náhledy na reálnou projektivní rovinu (a kreslení grafů na ni). Latinské čtverce a jejich ortogonalita. Pozorování: ortogonalita nezávisí na přeznačení prvků jednoho ze čtverců. Literatura: [MN, 9.1, 9.2 a 9.3]
Přednáška 6 Věta o maximálním počtu ortogonálních latinských čtverců. Věta o existenci proj. rovin a ortogonálních latinských čtvercích (z důkazu pouze konstrukce). Počet koster: Cayleyho formule (důkaz přes počítání "povykosů"). Počet koster úplného grafu bez hrany. Literatura: [MN, 9.3, 8.1, 8.6]
Přednáška 7 Věta o počtu koster pomocí determinantů. (Laplaceova matice (multi)grafu; tvrzení, že determinant ve znění nezávisí na volbě prvního vrcholu.) Spernerova věta o velikosti maximálního antiřetězce v systému podmnožin [n] uspořádaného inkluzí. Literatura: [MN, 8.5, 7.2]
Přednáška 8 Toky v síti, maximální tok, kapacita řezu. Hlavní věta o tocích (velikost maximálního toku je rovna minimální kapacitě řezu). Pozorování: elementární řez je řez a každý řez obsahuje elementární řez. Lemma, velikost toku lze určit na libovolném elementárním řezu. Implikuje polovinu hlavní věty o tocích: každý tok má velikost nejvýše rovnou kapacitě jakéhokoliv řezu. Nasycená a zlepšující cesta. Tok je maximální, právě když je nasycený, a když je maximální, tak existuje řez, že velikost toku je rovna kapacitě tohoto řezu. (Implikuje zbytek hlavní věty o tocích.) Literatura: [VM, 2.1, 2.2]
Přednáška 9 Ford-Fulkersonův algoritmus pro maximální tok. Pozorování, že algoritmus skončí, pokud jsou kapacity racionální. Hallova věta: formulace přes systém různých reprezentantů a také přes párování v bipartitním grafu. Königova věta (maximální párování v bip. grafu odpovídá minimálnímu vrcholovému pokrytí). Důsledek Hallovy věty: k-regulární graf lze rozložit na perfektní párování. Latinské obdélníky; každý latinský obdélník lze doplnit na latinský čtverec (zatím jen znění). Literatura: [VM, 2.3, 4, 4.1]
Přednáška 10 Vrcholová a hranová k-souvislost. Pár základních příkladů. Vrcholová k-souvislost implikuje hranovou k-souvislost. Mengerova a Ford-Fulkersonova (též hranová Mengerova) věta. (Důkaz Mengerovy věty nedokončen.) Literatura: [VM, 3] (některé důkazy jsem dělal trochu jinak)
Přednáška 11 (s kolegou Fialou) Dokončení důkazu z minule. Ramseyova věta pro grafy. Literatura: [VM, 3, 1]
Přednáška 12 Schurova věta. Ramseyova věta pro p-tice. Podrozdělování hran 2-souvislého grafu. Ušaté lemma. Literatura: [VM, 1], [MN, 4.7] (Nezahrnuje Schurovu větu, zdroj v angličtině byť tento odkaz bohužel není v ideální formě.)
Přednáška 13 Samoopravné kódy. Kód a jeho parametry. Hammingova vzdálenost. Příklady: opakovací kód, Hammingův kód, Hadamardovy kódy. Koule v Hammingově vzdálenosti. Horní odhad na velikost kódu při zadané délce a vzdálenosti. Perfektní kódy. Gilbert-Varshamovův dolní odhad: existence dostatečně velkého kódu při zadané délce a vzdálenosti. Literatura: [K, 1.1-1.6, 4.1, 10.1, 12.2] (Upozornění: na přednášce jsme nezáchazeli do všech podrobností jako zmiňované kapitoly. Na druhou stranu jsme kódy dělali nad obecnou abecedou.)
Přednáška 14 Lineární kódy. Generující matice. Pozorování, že může být zvolena ve standardním tvaru. Kódování a dekódování pomocí gen. matice ve standardním tvaru. Skalární součin a duální kód. Lemma o dimenzi duálního kódu. Kontrolní matice. Pozorování, že slova kódu lze získat pomocí kontrolní matice. Oprava chyb pomocí předpřipravené tabulky pro syndromy. Literatura: [K, 3.1, 3.2]