Informace k prednasce "Diskretni matematika"

Literatura: Matousek, Nesetril, Kapitoly z Diskretni matematiky

Cviceni: podminka udeleni zapoctu: domaci ukoly celkem 100 bodu, nutno ziskat aspopn 70. Budou 3 pisemky, kazda 100 bodu, nutno ziskat celkove aspon 210 bodu. Navic bude jedna opravna pisemka.Dale je mozne ziskat bonusove body za praci na cviceni: to zalezi na cvicicim.

ZKOUSKA: kombinace pisemne a ustni zkousky: studenti sedi v jedne poslucharne, kazdy dostane 2 ulohy, vypracuje je na papir, zkousejici si vypracovani precte, pripadne se na neco zepta nebo da dodatecne ukoly.

Prednaska 4.10.: Zakladni znaceni, sumy, souciny, matematicka indukce, prazdna mnozina, jak udelat prirozena cisla z prazdne mnoziny. Co je podmnozina. Potencni mnozina konecne mnoziny A. Jeji velikost je 2 na velikost A: a na tohle se potrebuje ze mate-li vzajemne jednoznacne zobrazeni mezi dvema konecnymi mnozinami tak maji stejnou velikost. Vzajemne jednoznacne zobrazeni (mezi konecnymi mnozinami) jsme jeste nedefinovali a toto tvrzeni jsme meli jen jako intuitivni pozorovani.

Prednaska 11.10.: Kartezsky soucin, Relace na mnozině: definice značení (graf, matice sousednosti), asi sedm příkladů (m.j. dělitelnost, inkluze, přesmyčky, porovnání funkcí), rozdíl mezi binární relací a binární operací, definice vlastností (reflexivní, symetrická, tranzitivní, antisymetrická) a operací (inverze, skládání). Pak zobrazení (včetně relace mezi mnozinami), prosté, na, bijekce. Skládání zobrazení. Rozmyslet ze u relace na konečné X je na ekvivalentní prosté. Taky proč to na nekonečné neprojde. Pak jsem nadefinoval ekvivalenci, ukázal dva příklady: kongruenci, resp. zbytkové třídy a přesmyčky na slovech. Tvrzení o třídách ekvivalence včetně důkazu.

Prednaska 18.10.: Pocet vsech zobrazeni a prostych zobrazeni. Mnozina vsech k-bodovych podmnozin a jeji velikost, binomicka veta, interpretace binomickych koeficientu, multinomicka veta (rozmyslet, rict na cviceni).

Prednaska 25.10.: Princip inkluze a exkluze, 3 dukazy, problem satnarky

Prednaska 1.11.: Uvod do teorie grafu, chromaticky polynom grafu jako aplikace principu inkluze a exkluze

Prednaska 15.11.: Chromaticky polynom grafu jako aplikace principu inkluze a exkluze, grafova metrika, matice sousednosti a sledy, stupen vrcholu, princip sudosti, skore grafu

Prednaska 22.11.: skore grafu, veta o Eulerovskych tazich, stromy: zakladni charakteristiky

Prednaska 29.11.: izomorfismus stromu, kostra grafu, hledani minimalni kostry

Prednaska 6.12.: Kruskaluv hladovy algoritmus na hledani minimalni kostry, rovinne grafy: uvod, steny, euleruv vzorec

Prednaska 13.12.: Rovinne grafy

Prednaska 20.12.: Usporadani, pocet koster uplneho grafu

Prednaska 3.1.: kombinatoricke pocitani, odhady faktorialu a kombinacnich cisel. Rozsirujici latka (nebude se zkouset): pojem mohutnosti pro konecne a nekonecne mnoziny, Veta Cantor-Bernstein, charakterizace nekonecnych bipartitnich grafu pomoci axiomu vyberu.

Prednaska 10.1.: Rozsirujici latka (nebude se zkouset) Prostor cyklu a prostor rezu, problem max cut, duality: algebraicka, geometricka, enumeracni; Isingova particni funkce, generujici funkce sudych podgrafu a generujici funkce rezu.