Vitejte na strankach prednasky z Diskretni matematiky. Na prednasce jsme v prubehu semestru probrali podstatnou cast prvnich 7 kapitol knihy J. Matouska a J. Nesetrila (viz nize Zakladni literatura).
ZAPOCET: Na zkousku misite mit zapocet zapsany v indexu.
Udeluje Vam ho cvicici.
Pokud nepatrite
do zadneho kruhu (kombinovane studium apod.), podivejte se
sem.
Seznam cviceni
Emaily cvicicich:
Tomas Chudlarsky: tomas zavinac kam.mff.cuni.cz,
Jakub Cerny: kuba zavinac atrey.karlin.mff.cuni.cz,
Tomas Vanicek: vanicek zavinac fsv.cvut.cz,
Diana Piguet: diana zavinac kam.ms.mff.cuni.cz,
Kamila Bumbova: kamila zavinac kam.ms.mff.cuni.cz,
Marek Janata: janata zavinac kam.ms.mff.cuni.cz.
ZKOUSKY: Hlavni casti zkousky je pisemna cast. Mate na ni mit 90 minut. Ustni cast nasleduje odpoledne (pocitejte, ze pri vetsim poctu prihlasenych studentu se muze zkouska protahnout az do pozdniho odpoledne, vyjimecne i dele). Pisemka se sklada ze 4 prikladu (jeden na definice, jeden dukaz, dva priklady podobne jako na cviceni). Zde se muzete podivat na vzor pisemky a na vzorove reseni (vypracovane dr. Fialou). Na zkousku si nezapomente prinest index a zkusebni zpravu se zapsanym zapoctem.
TERMINY ZKOUSEK: Posledni termin: utery 24.2. 9:00 (Mala Strana, 2.patro, mistnost 226). Individualne mohu po tomto terminu jeste vyzkouset jedince, kteri budou mit splneny ostatni predepsane zkousky.
Zakladni literatura: J. Matousek a J. Nesetril, Kapitoly z diskretni matematiky, Karolinum 2000 (dotisk 2002; predchozi vydani lisici se jen v drobnostech: Matfyzpress 1996). K dostani v prodejne skript v Troji (240 Kc) ci v Knihkupectvi Karolinum v Celetne 18 (240 Kc, otevreno po-pa 9-19, so-ne 11-17), zacatkem semestru mivaji tyto prodejny slevy. Nejake vytisky k vypujceni jsou snad tez v knihovne MFF. Kniha je napsana peclive, presto se Vam mohou hodit odhalene chyby (pozor zejmena ve vydani z r. 1996 na nespravnou definici eulerovskych grafu na str. 108).
1. prednaska 30.9. (Kapitola 1.) nekolik motivacnich problemu (satnarka, kresleni 1 tahem, propojovani 3+3 domku neprotinajicimi se vedenimi); ciselne obory (N, Z, Q, R), mnoziny, prazdna mnozina, podmnozina, prunik, sjednoceni, velikost mnoziny, potencni mnozina, velikost pot. mnoziny konecne mnoziny, priklad dukazu matematickou indukci, usp. a neusp. dvojice, kart. soucin, relace
2. prednaska 7. 10. vlastnosti relaci (reflexivita, symetrie, tranzitivita), ekvivalence, jednoduchy priklad na ekvivalenci, tridy ekvivalence, rozklad mnoziny na tridy ekvivalence, (castecne) usporadani, linearni usporadani, jednoduche priklady na castecne a linearni usporadani, definice zobrazeni (=funkce), slozeni zobrazeni (je to skutecne zobrazeni), zobrazeni proste, na, bijekce, (Kapitola 2.) permutace a faktorialy, pocet permutaci na n-prvkove mnozine je n!
3. prednaska 14. 10. 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, binomicka veta (ve tvaru (x+y) na n=...), multinomicka veta (bez dukazu), odhad faktorialu zdola a shora (zatim pouze zneni a zacatek dukazu)
4. prednaska 21.10. 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), pocet zobrazeni z n-prvkove na l-prvkovou mnozinu (za pouziti PIE), matem. formulace vanocni besidky (satnarky)
5. prednaska 4.11. vanocni besidka (satnarka); (Kapitola 3.) uvod do teorie grafu: graf, kresleni grafu obrazkem, uplny graf, kruznice, cesta, (uplny) bipart. graf, izomorfismus grafu, (indukovane) podgrafy, pocet induk. podgrafu grafu na n vrcholech je 2 na n
6. prednaska 11.11. souvislost, komponenty grafu, vzdalenost v grafu, soused, matice sousednosti, stupen grafu, princip sudosti, veta o skore, kresleni grafu 1 uzavrenym tahem: graf je eulerovsky prave kdyz je souvisly a ma vsechny stupne sude (dukaz priste)
7. a 8. prednaska 18.11. dukaz vety o eul. grafech, nektere grafove operace (pridani a odebrani hrany, odebrani vrcholu, deleni hrany), definice deleni grafu, (vrcholove) 2-souvisle grafy, hranove 2-souv. grafy, 2-souv. graf zustane souvisly po vyhozeni hrany, deleni 2-souv. grafu je 2-souvisle, lemma o usich, graf je 2-souvisly <==> vznikne z trojuhelniku postupnym pridavanim a delenim hran, graf je 2-souvisly <==> kazde 2 vrcholy lezi na kruznici, v 2-souvislem grafu lezi kazde dve hrany na spolecne kruznici (bez dukazu), (Kapitola 4.) definice stromu, strom s al. 2 vrcholy ma alespon 2 listy, G je strom <==> G-list je strom, dusledek: G strom <==> z G dostaneme K_1 postupnym odebiranim listu, 4 charekteristiky stromu (Tvrzeni 4.1.4 skript)
9. prednaska 25.11. (doc. Klazar) izomorfismus stromu: kodovani 0-1 posloupnostmi, kostra grafu, minimalni kostra grafu, Kruskaluv (hladovy) algoritmus na nalezeni min. kostry souv. grafu (dokonceni analyzy spravnosti priste)
10. prednaska 2.12.
priklad kodovani stromu 0-1 posloupnostmi,
analyza spravnosti hladoveho algoritmu (poznamka: analyza spravnosti
udelana jinak nez ve skriptech; na zkousku staci znat kteroukoliv z nich),
(Kapitola 5.)
definice oblouku, rovinne grafy, rovinne nakresleni grafu
(Prednaska se i pri DOD konala, nebyl jsem informovan o jejim zruseni.
Nicmene objem nove latky
byl mnohem mensi nez obvykle. Kdo jste na prednasce nebyli, doplnte si prosim
dukaz spravnosti hladoveho algoritmu na min. kostru a
definici oblouku, rovinneho grafu a rovinneho nakresleni. Pokud
nemate k dispozici neci poznamky z prednasky, toto vse
je ve skriptech.)
11. prednaska 9. 12. definice steny a topologicke kruznice, Jordanova veta o topologicke kruznici (bez dukazu), stena lib. rov. nakresleni rov. 2-souv. grafu odpovida kruznici, Euleruv vztah pro souvisle rovinne grafy, horni odhad poctu hran v rovinnem grafu a v rov. grafu bez trojuhelniku, dva dusledky: kazdy rov. graf ma vrchol stupne nejvyse 5, grafy K_5 a K_3,3 nejsou rovinne, graf je rovinny prave kdyz kazde jeho deleni je rovinne, Kuratowskeho veta o rovinnych grafech (bez dukazu), barveni map a grafu, problem 4 barev
12. prednaska 6.1. priklady barevnosti nekterych grafu (kruznice, uplny graf, bip. graf, strom), vztah mezi barevnosti map a rov. grafu, veta o 4 barvach pro rov. grafy a jeji dukaz, (Kapitola 6.) dukaz principu sudosti pocitanim 2 zpusoby, Spernerova veta o max. velikosti nezavisleho systemu podmnozin n-prvkove mnoziny, (Kapitola 7.) pocet koster uplneho grafu na n vrcholech je roven n na n-2 (Pitmanuv dukaz pres povykosy)