Literatura: Matousek, Nesetril, Kapitoly z Diskretni matematiky
Cviceni: podminka udeleni zapoctu: 2/3 bodu za pisemky a domaci ukoly
Prednaska 3.10.: Zakladni znaceni, prazdna mnozina, jak udelat prirozena cisla z prazdne mnoziny; jak udelat usporadane dvojice, co je relace, funkce, prosta a na. Co je podmnozina, potencni mnozina monoziny A. Dokazal jsem indukci ze jeji velikost je 2 na velikost A: ale na tohle se potrebuje ze mate-li bijekci mezi dvema konecnymi mnozinami tak maji stejnou velikost, a nerovnosti plati pri existenci prosteho zobrazeni a zobrazeni na. To jsem dal jako DU, tak si to cvicte na cviku. Dalsi DU: jak mnozinove definovat usporadanou k-tici.
Prednaska 10.10.: Ekvivalence a bijekce mezi mnozinou vsech rozkladu mnoziny X a mnozinou vsech ekvivalenci na X.
Prednaska 17.10.: Castecne usporadane mnoziny, jejich representace pomoci usporadani inkluzi, Hasseho diagram, veta o dlouhem a sirokem, existence rozsireni na linearni usporadani
Prednaska 24.10.: Kombinatoricke pocitani, pocet vsech zobrazeni, zobrazeni prostych, bijekci; znazornovani permutaci; binomicke koeficienty a jejich vyznam; binomicka a multinomicka veta; asymptoticke odhadovani funkci, odhady: faktorial, binomicke koeficienty. Cvicte prosim asymptoticke odhady, napr. 76/1,2,3 v Matousek, Nesetril
Prednaska 31.10.: Princip inkluze a exkluze, problem satnarky, pocet zobrazeni na. Cvicte prosim asymptoticke odhady a priklady na princip inkluze a exkluze.
Prednaska 7.11.: Eulerova funkce, uvod do pravdepodobnosti: diskretni pravdepodobnostni prostor, nahodne posloupnosti 0,1; nahodne permutace; definice grafu, C_n, K_n, nahodne grafy. Prosim cvicte PIE a ulohy na pravdepodobnost: nahodne permutace, nahodne grafy.
Prednaska 14.11.: uvod do pravdepodobnosti: podminena pravdepodobnost, veta o uplne pravdepodobnosti, Bayesova veta, nezavisle nahodne jevy. Prosim cvicte pravdepodobnost, konkretni priklady. napr. vice jevu, po dvojici nezavisle, ale celkove zavisle.
Prednaska 21.11.: uvod do pravdepodobnosti: Realne nahodne veliciny, stredni hodnota, linearita stredni hodnoty, rozptyl, Markovova a Cebysevova nerovnost, rovnomerne rozdeleni. Prosim cvicte pravdepodobnost, konkretni priklady na pravdepodobnost. Priste bude uvod do grafu.
Prednaska 28.11.: Uvod do teorie grafu: definice, zakladni grafy: prazdny, uplny, kruznice, cesta. Isomorfni a ruzne grafy a jejich pocty. Podgraf a indukovany podgraf. Definice cesty mezi dvema vrcholy, definice komponent souvislosti jako trid ekvivalence, souvisly graf. Definice vzdalenosti mezi vrcholy, a jeji vlastnosti. Strom: souvisly, bez kruznic. Intuice: je to nejjednodussi souvisly graf. Kostra souvisleho grafu G: podgraf ktery je strom a mnozina vrcholu je stejna jako mnozina vrcholu G. Pozorovani: kazdy souvisly graf ma kostru. Pozorovani: kazdy strom s aspon jednou hranou ma aspon 2 vrcholy stupne 1 (rikame jim listy). Pozorovani: trida stromu je presne trida grafu, ktere lze vytvorit z jedineho vrcholu postupnym provadenim jedne jednoduche operace: vem novy vrchol a spoj ho jedinou hranou s jiz vytvorenym grafem. Prosim cvicte uvod do grafu.
Prednaska 5.12.: Charakterizace stromu, eulerovske grafy, skore grafu
Prednaska 12.12.: Uvod rovinne grafy: kresleni grafu do roviny a na jine plochy, rod grafu, rovinna kresleni grafu, rovinne grafy, topologicke rovinne grafy, Jordanova veta o kruznici, K5, K33 nejsou rovinne grafy, Kuratowskeho veta, stena rovinneho topologickeho grafu, dualni graf.
Prednaska 19.12.: Steny rovinneho nakresleni, Euleruv vzorec, maximalni pocet hran rovinneho grafu, rovinneho grafu bez trojuhelniku. Platonska telesa.
Prednaska 09.01.: Problem 4 barev, prevod na barevnost rovinnych grafu, barevnost obecnych grafu, zavislost barevnosti na maximalnim stupni, veta o 5 barvach.
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.