Diskrétní matematika - přednáška

Zde se průběžně budou objevovat informace k přednášce z diskrétní matematiky. (Typicky se nové informace budou objevovat pár desítek minut až pár jednotek hodin po přednášce.)

Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku.

Doporučená literatura: J. Matoušek, J. Nešetřil, Kapitoly z Diskrétní Matematiky

Informace ke zkoušce

Všechny termíny ke zkoušce z diskrétní matematiky už proběhly. Zde už najdete pouze popis toho, jaké byly podmínky ke zkoušce. Pro přihlášení na termín je potřeba mít buď zápočet nebo alespoň doporučení od cvičícího (to se hlavně týkalo předtermínu). Těžištěm zkoušky bude písemka na 2 hodiny. Z písemky lze získat známky 1, 2, 3, 3- nebo 4. V případě zisku 1 nebo 4, dostanete známku hned do SISu a do indexu. V případě zisku 2 nebo 3 se můžete známku pokusit o jeden stupeň vylepšit na následném ústním zkoušení. V případě zisku 3- je ústní zkoušení povinné (pokud nechcete rovnou 4), dá se vylepšit jedině na 3. Pokud dostanete po ústním zkoušení 2 nebo 3, tak se také můžete rozhodnout, že známku nechcete a přijdete na další termín.

Další upozornění:

Zkontrolujte si, zda opravdu máte zápočet nebo doporučení cvičícího (jinak písemku psát nemůžete).
Rezervujte si na zkoušku i odpoledne, abyste se případně mohli zúčastnit i ústního zkoušení.
Pokud se na zkoušku nedostavíte, termín Vám propadá. Pokud máte důležitý důvod, proč jste na zkoušku nemohli přijít (např. nemoc nebo nečekané problémy s dopravou), tak mi pošlete emailem co nejrychleji podrobné vysvětlení, a podle situace se popř. rozhodnu, že Vám termín nepropadne.

Vzorovou písemku naleznete zde. Bodování pro tuto konkrétní písemku by bylo 1: 23-30b; 2: 20-22b; 3: 16-19b; 3-: 8-15b; 4: 0-7b. (Pro jiné písemky může být bodování mírně upraveno podle obtížnosti písemky.)

Průběh přednášek

Přednáška 1 (7. 10.; přednášel Dušan Knop) Základní pojmy a značení, množiny. Důkaz sporem a matematickou indukcí, kartézský součin. Relace: reflexivita, symetrie, tranzitivita; relace ekvivalence a třídy ekvivalence.

Přednáška 2 (14. 10.; přednášel Dušan Knop) Částečná uspořádání, lineární uspořádání, ostré uspořádání, minimální a nejmenší prvek. Funkce, počet funkcí z n-prvkové množiny do m-prvkové, počet prostých funkcí. Počet podmnožin. Permutace, binomické koeficienty, počet k-prvkových podmnožin.

Přednáška 3 (21. 10.) Řetězce a antiřetězce, Hasseův diagram, věta o dlouhém a širokém. Počet sudých podmnožin, binomická věta. Princip inkluze a exkluze (motivační příklad + znění; důkaz bude příště).

Přednáška 4 (4. 11.) Důkaz principu inkluze a exkluze. Problém šatnářky a počet permutací bez pevného bodu. Základy diskrétní pravděpodobnosti: pravděpodobnostní prostor (neúplná definice), diskrétní pravděpodobnostní prostor, elementární jev, jev, příklady pravděpodobnostních prostorů; motivační příklad na podmíněnou pravděpodobnost.

Přednáška 5 (11. 11.) Podmíněná pravděpodobnost (příklad s výpočtem spolehlivosti testu), Bayesova věta. Nezávislé jevy. Součin diskrétních pravděpodobnostních prostorů. Náhodná veličina, střední hodnota náhodné veličiny. Linearita střední hodnoty, indikátory (příklad na využití indikátorů).

Přednáška 6 (18. 11.) Nezávislost náhodných veličin. Graf. Důležité grafy: úplný graf, nezávislá množina, kružnice, cesta, úplný bipartitní graf. Izomorfismus grafů. Sousednost (incidence), podgraf a indukovaný podgraf. Sled, tah a cesta v grafu. Relace ~ vyjadřující existenci cesty mezi dvěma vrcholy je ekvivalence. Souvislost grafu a komponenty souvislosti. Matice sousednosti. Věta o počtu sledů (zatím bez důkazu).

Přednáška 7 (25. 11.) Důkaz věty o počtu sledů. Stupeň vrcholu a skóre grafu. Princip sudosti a počet vrcholů lichého stupně. Věta o skóre. Eulerovské grafy. Charakterizace eulerovských grafů pomocí souvislosti a sudosti stupňů vrcholů. Definice orientovaného grafu.

Přednáška 8 (2. 12.) Tah v orientovaném grafu, eulerovské orientované grafy. Vstupní a výstupní stupeň vrcholu v orientovaném grafu, silná a slabá souvislost. Charakterizace orientovaných eulerovských grafů (důkaz se předpokládá na cvičeních). Aplikace eulerovských grafů na existenci cycklických posloupností nul a jedniček obsahujících, pro dané k všechny možné k-tice po sobě jdoucích nul a jedniček právě jednou. Stromy, definice stromu a listu. Lemma o existenci listů a tvrzení o trhání listů. Ekvivalentní charakterizace stromů (důkaz příště).

Přednáška 9 (9. 12.) Důkaz věty o ekvivalentní charakterizaci stromů. Kostra grafu, každý souvislý graf má kostru. Oblouk v rovině, nakreslení grafu. (Rovinné nakreslení vypadlo z definice, zadefinujeme příště). Rovinný graf je takový, který má rovinné nakreslení. Stěny rovinného nakreslení. Eulerův vzorec (zatím jen část důkazu).

Přednáška 10 (16. 12.) Dokončení důkazu Eulerova vzorce. Doplnění definice rovinného nakreslení. Odhad na maximální možný počet hran rovinného grafu (+ drobné poznámky navíc: dvojnásobek počtu hran je součet stupňů stěn, odhad pro rovinné grafy bez trojúhelníků, každý rovinný graf obsahuje vrchol stupně nejvýše 5). Barvení map, věta o čtyřech barvách (pro mapy neformálně). Chromatické číslo grafu, k-degenrované grafy a tvrzení o jejich chromatickém čísle. Věta o šesti barvách jako důsledek. Věta o pěti barvách (s důkazem).

Přednáška 11 (6. 1.) Erdős-Szekeresova věta (dva důkazy). Pravděpodobnostní důkazy: hledání velkého bipartitního podgrafu; náhodný graf G(n,p) a konkrétní příklad využití pro existenci grafu s 2^50 vrcholy bez nezávisle množiny velikosti 100 či úplného podgrafu velikosti 100.