Zapocet: Na zkousku budete potrebovat zapocet (tyka se vsech forem studia). Pokud nepatrite do zadneho kruhu (kombinovane studium apod.), podivejte se sem.
Ve studijnim informacnim systemu na adrese https://is.cuni.cz/studium/login.php je vypsano nekolik terminu, na ktere se muzete jiz prihlasovat (pozor, prihlasujte se jen k ucitelum Matousek + Valtr, na terminy ucitelu jinych skupin by vas SIS sice nechal prihlasit, ale bez vaznych duvodu a predchozi ustni dohody vas jini ucitele nevyzkousi). Podminkou konani zkousky je predchozi ziskani zapoctu.
Slusnost veli nezaplnovat zbytecne termin, pokud vazne nepocitate s tim, ze na zkousku skutecne pujdete. Ve dnech, kdy je vice navazujicich "terminu" tehoz ucitele, se prosim prihlasujte na prvni volnou dobu.
Az se stavajici terminy zaplni, planujeme jeste zvysit jejich kapacitu, formalne vypsanim dalsich terminu na pozdejsi hodiny tehoz dne. Vypsani zkousky v jinych dnech uz neplanujeme.
Prejeme prijemne uceni a mnoho uspechu!
Webove stranky prednasejicich:
J. Matousek,
P. Valtr
Kontakt na cvicici:
J. Cibulka
P. Rytir: rytir (zavinac) kam.mff.cuni.cz
T. Valla
T. Vyskocil: tiger (zavinac) kam.mff.cuni.cz
Informace pro studenty kombinovaneho studia
Zakladni literatura: J. Matousek a J. Nesetril, Kapitoly z diskretni matematiky, Karolinum 2000, dotisky 2002, 2003 (predchozi vydani lisici se jen v drobnostech: Matfyzpress 1996). Momentalne rozebrane, nove rozsirene a opravene vydani ma byt podle sdeleni Nakladatelstvi Karolinum k dostani od 21. listopadu (v Knihkupectvi Karolinum, Celetna 18, otevreno po-pa 9-19, so-ne 11-17 ci v prodejne skript v Troji). Nejake vytisky jsou k vypujceni v knihovne MFF. Zde najdete odhalene chyb(k)y.
1. prednaska 2.10. 3 motivacni problemy: satnarka (formulovano jako rozdavani darku na vanocni besidce), kresleni 1 tahem, propojovani 3+3 domku neprotinajicimi se vedenimi; (Kapitola 1.) ciselne obory (N={1,2,..}, Z, Q, R), suma, priklad dukazu matem. indukci, mnoziny, zapisy mnozin, rovnost dvou mnozin, prazdna mnozina, podmnozina, prunik, sjednoceni, rozdil, velikost mnoziny, potencni mnozina, velikost pot. mnoziny konecne mnoziny, usp. a neusp. dvojice
2. prednaska 9.10. kart. soucin, (binarni) relace, vlastnosti relaci (reflexivita, symetrie, tranzitivita, ekvivalence), trida ekvivalence urcena prvkem x, jednoduchy priklad na ekvivalenci a tridy ekvivalence, rozklad mnoziny na tridy ekvivalence, (castecne) usporadani, linearni usporadani, jednoduche priklady na castecne a linearni usporadani, definice zobrazeni (=funkce), skladani zobrazeni, zobrazeni proste, na, vzajemne jednoznacne
3. prednaska 16.10. zobrazeni proste, na, bijekce (znaceni, porovnani velikosti mnozin pri techto zobrazenich); (Kapitola 2.) permutace, zapisy permutace, faktorial, pocet permutaci na n-prvkove mnozine je n!, pocty zobrazeni (resp. prostych zobrazeni, bijekci) z n-prvk. do k-prvk. mnoziny, kombinacni cislo - 2 definice (pomoci faktorialu, jako pocet k-prvk. podmn. n-prvk. mnoziny), dukaz jejich ekvivalence, zakladni vztahy mezi komb. cisly: (n nad k)=(n nad n-k), (n nad k)=(n-1 nad k-1)+(n-1 nad k), Pascaluv trojuhelnik
4. prednaska 23.10. binomicka veta (ve tvaru (x+y) na n = ...), odhady faktorialu: n na (n/2) < n! < ((n+1)/2) na n, odhady komb. cisel: 2 na n / (n+1) < (n nad [n/2]) < 2 na n, princip inkluze a exkluze (PIE)
5. prednaska 30.10. Fakt: pro vsechna realna x plati 1+x<=e^x (e je zaklad prirozenych logaritmu, tento fakt charakterizuje cislo e). Lepsi odhad faktorialu: e(n/e)^n <= n! <= en(n/e)^n. Dukaz indukci (na prednasce jen horni odhad). Problem satnarky, permutace bez pevneho bodu, funkce s s hackem (n), reseni pomoci PIE (A_i je mnozina vsech permutaci pi, pro nez pi(i)=i). Pocet vsech zobrazeni n-prvkove mnoziny na t-prvkovou (zase PIE, A_i = mnozina vsech zobrazeni, ktera nic nezobrazi na bod i, vysledkem je soucet t clenu).
6. prednaska 6.11. (Kapitola 3.) uvod do teorie grafu: graf, kresleni grafu obrazkem, uplny graf, kruznice, cesta, prazdny graf, (uplny) bipart. graf, izomorfismus grafu, (indukovane) podgrafy, pocet induk. podgrafu grafu na n vrcholech je (2 na n) - 1, souvislost, sled, komponenty grafu
7. prednaska 13.11. Vzdalenost v grafu (delka nejkratsi cesty mezi danymi vrcholy, pocitaji se hrany); jeji vypocet je jednim ze zakladnich algoritmickych problemu (algoritmy ted delat nebudeme). Matice sousednosti grafu. Uloha rozhodnout, zda ma graf trojuhelnik: zrejmy algoritmus potrebuje radove n^3 operaci, ale pomoci "rychleho maticoveho nasobeni" se da dostat algoritmus s radove mene operacemi. Uloha o mostech mesta Kralovce. Pojmy: tah (=sled, v nemz se neopakuji hrany), uzavreny tah (konci tam, kde zacal), eulerovsky tah (= uzavreny + prochazi vsechny hrany), eulerovsky graf (ma eulerovsky tah), stupen vrcholu, graf s nasobnymi hranami. Veta: graf je eulerovsky, prave kdyz je souvisly a stupne vsech vrcholu jsou sude (plati i pro grafy s nasobnymi hranami). Snadna implikace (eulerovsky => souvisly + sude stupne). Pro tezsi implikaci lemma: ma-li graf vsechny stupne sude a aspon jednu hranu, obsahuje kruznici. Dusledek: pro kazdy graf, v nemz jsou vsechny stupne sude, se mnozina hran da vyjadrit jako disjunktni sjednoceni mnozin hran kruznic.
8. prednaska 20.11. Dokonceni dukazu vety o eulerovskych grafech. Kresleni grafu jednim ne nutne uzavrenym tahem. Princip sudosti (kazdy konecny graf ma sudy pocet vrcholu licheho stupne). Pojem skore grafu, nektere nutne podminky pro skore, zminka o vete, charakterizujici skore. Poznamka o hamiltonovskych kruznicich (algoritmicky tezka uloha, zadna charakterizace podobna vete o eulerovskych grafech se neda cekat). Jednoduche grafove operace (G-e, G+e, G-v, G%e). Pojem k-souvisleho grafu a hranove k-souvisleho grafu. Lemma: kazdy 2-souvisly graf je tez hranove 2-souvisly. Veta: graf je 2-souvisly, prave kdyz ma aspon 2 vrcholy a kazde 2 vrcholy lezi na spolecne kruznici.
9. prednaska 27.11. Pojem oblouku v rovine (= spojity obraz intervalu), pojem rovinneho kresleni grafu. Graf je rovinny, pokud ma rovinne nakresleni. Fakt (zatim bez dukazu): K_5 neni rovinny. Hra Hex: pravidla. Oba hraci nemohou zaroven vybudovat cestu (trik s K_5). Veta: Pri zaplnene hexovnici ma aspon jeden hrac cestu (dukaz sporem, pres obarveni policek tremi barvami a pomoci principu sudosti pro vhodne definovany graf). Veta (Nash): Bily ma vyhravajici strategii. Prvni cast dukazu: bud buly nebo cerny ma vyhravajici strategii (pomoci pojmu "strom hry"). Druha cast: predpoklad, ze vyhravajici strategii ma cerny, vede ke sporu ("kradeni strategie" - bily muze kopirovat tahy cerneho na "antihexovnici"). Zde je zkracena verze prezentace pouzite v prednasce (format Microsoft Powerpoint).
10. prednaska 4.12. Stromy. Jejich ekvivalentni charakterizace (i)-(v). Na dukaz ekvivalence: lemma o koncovem vrcholu, lemma o vystavbe stromu. Dukaz ekvivalenci (i) s (ii) a s (v), ostatni ekvivalence na cviceni (budou se zkouset!). Kostra grafu. Problem minimalni kostry - uvod.
11. prednaska 11.12. Hladovy (Kruskaluv) algoritmus. Poznamka o hladovych algoritmech obecne (priklad s problemem prirazeni s maximalnim skore). Dukaz spravnosti hladoveho algoritmu (jinak nez je ve skriptech): definujeme slibnou mnozinu hran (je obsazena v nejake minimalni kostre); lemma: je-li F slibna mnozina hran v ohodnocenem grafu G=(V,E), U je vlastni podmnozina V takova, ze mezi U a jejim doplnkem nevede zadna hrana z F, a e je nejlevnejsi z hran spojujici U s jejim doplnkem, potom tez F sjednoceno s {e} je slibna mnozina hran. Dukaz spravnosti hladoveho algoritmu - indukci se dokaze, ze mnoziny hran postupne konstruovane algoritmem jsou slibne. Pocet koster grafu (oznaceni kapa(G)). Veta: kapa(K_n)=n^{n-2}. Na prednasce predveden Pitmanuv dukaz pres "povykosy", ke zkousce staci znat i jiny dukaz, pokud by nekomu vic vyhovoval.
12. prednaska 18.12. Uvod do extremalni teorie grafu. Veta o maximalnim moznem poctu hran grafu bez trojuhelniku na n vrcholech. Pripomenuti rovinnych grafu. Topologicky rovinny graf (= graf + jeho rovinne nakresleni), topologicka kruznice (tez jednoducha uzavrena krivka ci Jordanova krivka). Zneni Jordanovy vety o kruznici. Fakt: rovinne nakresleni grafu bez kruznice ma jedinou stenu. Euleruv vzorec, dukaz indukci podle poctu hran. Poznamka o tom, jak tridimenzionalni konvexni mnohosteny davaji topologicke rovinne grafy (odtud pochazeji nazvy vrchol, hrana, stena).
13. prednaska 8.1. horni odhad poctu hran v rovinnem grafu a v rov. grafu bez trojuhelniku (dokazano za pouziti nedokazovane charakterizace hranove maximalnich takovychto grafu), dva dusledky: 1. kazdy rov. graf ma vrchol stupne nejvyse 5, 2. K_5 a K_3,3 nejsou rovinne grafy, barveni polit. map, problem 4 barev, barveni grafu, barevnost nekterych grafu (kruznice, uplny (bipart.) graf, strom), vztah mezi barvenim map a rov. grafu, veta o 5 barvach, jeji dukaz doplneny hudebnim ztvarnenim