Diskrétní matematika DMI002, zimní semestr 2011/2012 (P. Kolman)

Místo a čas: Posluchárna S9 na Malé Straně (1. patro), pondeli 12:20.

Kromě toho se kona ještě další přednáška z DM se stejným obsahem (tzv. paralelka), na ktere přednáší O. Pangrác.

Doporučená literatura: J. Matoušek a J. Nešetřil: Kapitoly z Diskrétní matematiky
Sylabus úvodu do pravděpodobnosti (J. Matoušek)

Konzultační hodiny: Po předchozí emailové dohodě (prijmeni@kam.mff.cuni.cz).

Cvičení a zápočet: Veškeré informace o cvičeních, včetně podmínek pro udělování zápočtu, se dozvíte od svých cvičících, viz. rozvrh v SISu. Pro studenty kombinovaneho studia, kteri nemohou chodit na cviceni, rozhoduje o udelovani zapoctu kol. O. Pangrác. Pro procviceni doporucuji Sbirku prikladu.

• Pondeli 3.10.
  Uvod. Mnoziny, operace s nimi ap. Matematicka indukce. Kartezsky soucin. Relace (jen definice).
• Pondeli 10.10.
  Relace. Funkce. Počet všech funkcí z množiny X do množiny Y. Počet všech podmnožin množiny. Počet všech lichých podmnožin. Pocet vsech prostych funkci z X do Y.
• Pondeli 17.10.
  Drobnosti: Prosta funkce jako usporadana n-tice, faktorial, permutace.
  Dale: Kombinacni cisla a jejich vlastnosti, "X nad k". Pocet celociselnych nezapornych reseni lin. rovnice. Binomicka veta.
  Pokracovani s relacemi: Skladani. Vlastnosti. Ekvivalence, usporadani, uplne (linearni) usporadani (zatim jen definice a priklady).
• Pondeli 24.10.
  Vice o relacích. Dokázali jsme větu o ekvivalenci a rozkladu množiny na třídy ekvivalence. Pak jsme mluvili o částečně uspořádaných množinách: bezprostredni predchudci a veta o nich + Hasseuv diagram (tj. reprezentace CUMu), existence min. prvku v konecnych CUM, zuplnovani konecnych CUM. Skoncili jsem definici vnoreni CUM do CUM.
• Pondeli 31.10.
  Veta o vnoreni CUM (X,R) do (2^X,inkluze). Vetu o Dlouhem a Sirokem, Erdosovo-Szekeresovo lemma o monotonni podposloupnosti. Strucne Princip IE pro n=3. Pravdepodobnost: ilustracni priklad, definice diskretniho pstniho prostoru.
• Pondeli 7.11.
  Definice podminene pravdepodobnosti. Veta o uplne pravdepodobnosti. Bayesova veta (priklad HIV). Soucin pstnich prostoru. Definice nahodne veliciny a stredni hodnoty.
• Pondeli 14.11.
  Stredni hodnota vs. median. Linearita stredni hodnoty. Pojem indikator jevu, priklady. Def. nezavisle nah. veliciny. E[XY]=E[X]E[Y] pro nezavisle n.v. Rozptyl - jen def. Markovova nerovnost - zneni, dukaz.
• Pondeli 21.11.
  Cebysevova nerovnost. Rozdeleni nahodne veliciny a distribucni funkce. Alternativni, binomicke, normalni a Poissonovo rozdeleni.
  Grafy. Uplne grafy, cesty, cykly, uplne bipartitni grafy, bipartitni grafy, neformalne rovinne grafy. Izomorfismus grafu.
• Pondeli 28.11. (Ida Kantorová)
  Dolni odhad na pocet neizomorfnich grafu. Rada drobnosti: zavedeni pojmu podgraf, indukovany podgraf, a s jejich pomoci cesta v grafu, kruznice v grafu; take tah a sled v grafu, definice souvislosti, vzdalenosti (zminka o metrice), komponenty. Reprezentace grafu pomoci matice sousednoti. Veta o charakterizaci eulerovskych grafu.
• Pondeli 5.12.
  Dokončení důkazu o charakterizaci eulerovských grafů. Orientované grafy. Stromy - definice, ekvivalentní charakterizace.
• Pondeli 12.12.
  Alternativni charakterizace bipartitnich grafu (bez lichych cyklu). Rovinne grafy (nakreslni, rovinne nakresleni, Jordanova veta [zneni], steny, Euleruv vzorec, max. pocet hran, Kuratowskeho veta [zneni, vyznam], Platonska telesa, 5-barevnost).
• Pondeli 19.12. (Ida Kantorová)
  Veta o skore, degenerovanost, pozorovani, ze barevnost je shora omezena degenerovanosti +1, hex (tvrzeni + dukaz).

DM 2010/2011