ZKOUSKA: Hlavni casti zkousky je 90minutova pisemka. Odkaz na pozadavky ke zkousce najdete o nekolik radek nize. Na zkousku se hlaste pres SIS. Terminy zkousky: 6. a 13. ledna (oba 12:15 hod.), 18., 25. ledna, 1. unora (vse 9:00 hod), 9. unora (8:45 !!), 22. brezna (8:55). Vzdy od 9:00 (ci 8:45) pisemka, odpoledne (cca. ve 14 hod.) vysledky zkousky, pote pripadne ustni dozkouseni. Zde se muzete podivat na vzor pisemky a na vzorove reseni (vypracovane dr. Fialou).
Na zkousku si nezapomente prinest index a zkusebni zpravu. Na zkousku musite mit udelen zapocet, za coz povazuji situaci, kdy ho mate zapsany v indexu nebo SISu nebo mate pisemne doporuceni od cviciciho (zapisu Vam ho zaroven se zkouskou; bohuzel podle pokynu vedeni fakulty letos vetsina cvicicich zapocet nemuze do indexu zapisovat). Pokud Vam cvicici prislibil(a) zapocet jeste pred zacatkem zkouskoveho obdobi, meli byste ho nyni mit zapsan v SISu s datem 13.1. (radeji si to zkontrolujte).
ZAPOCET: Na zkousku potrebujete zapocet (tyka se vsech forem studia).
Udeluje Vam ho cvicici, ve vetsine pripadu zapisuje prednasejici (u zkousky).
Pokud nepatrite
do zadneho kruhu (kombinovane studium apod.), podivejte se
sem.
Seznam prednasek a cviceni z DM
Emaily cvicicich:
Jakub Cerny: kuba (zavinac) atrey.karlin.mff.cuni.cz,
Diana Piguet: diana (zavinac) kam.ms.mff.cuni.cz,
Veronika Douchova: veronika (zavinac) kam.ms.mff.cuni.cz,
Helena Nyklova: nyklova (zavinac) kam.ms.mff.cuni.cz,
Petra Smolikova: petra (zavinac) kam.ms.mff.cuni.cz,
Kamila Bumbova: kamila (zavinac) kam.ms.mff.cuni.cz,
Eva Ondrackova: ondre1am (zavinac) artax.karlin.mff.cuni.cz,
Peter Bella: bellp2am (zavinac) artax.karlin.mff.cuni.cz,
Jiri Fink: fink (zavinac) atrey.karlin.mff.cuni.cz
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). K dostani v prodejne skript v Troji (loni 240 Kc) ci v Knihkupectvi Karolinum v Celetne 18 (loni 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.
Zapisky kolegy Baudise: Pan Petr Baudis, ktery navstevoval odpoledni prednasku, mi poslal odkaz na jeho zapisky z prednasky v elektronicke podobe (ale pozor, tyto zapisky nekontroluji a nerucim tudiz za obsah; myslim, ze nektere casti jsou zestrucneny a vetsinou bez obrazku).
1. prednaska 5.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, kart. soucin, relace (tj. binarni relace), [***POUZE DOPOLEDNE: vlastnosti relaci (reflexivita, symetrie, tranzitivita, ekvivalence), trida ekvivalence urcena prvkem x ***]
2. prednaska 12.10. [***POUZE ODPOLEDNE: 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), slozeni zobrazeni (je to skutecne zobrazeni), zobrazeni proste, na, bijekce, (Kapitola 2.) permutace a faktorial
3. prednaska 19.10. 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, binomicka veta (ve tvaru (x+y) na n=...), jeji dukaz indukci podle n
4. prednaska 26.10. multinomicka veta (bez dukazu), 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 2.11. pocet zobrazeni z n-prvkove na l-prvkovou mnozinu (za pouziti PIE), vanocni besidka (satnarka); (Kapitola 3.) uvod do teorie grafu: graf, kresleni grafu obrazkem, uplny graf, kruznice, cesta, [***POUZE DOPOLEDNE: (uplny) bipart. graf ***]
6. prednaska 9.11. [***POUZE ODPOLEDNE: (uplny) bipart. graf, ***] izomorfismus grafu, (indukovane) podgrafy, pocet induk. podgrafu grafu na n vrcholech je 2 na n, souvislost, komponenty grafu, vzdalenost v grafu, soused, matice sousednosti, stupen grafu, veta o sudosti (princip sudosti): soucet stupnu v lib. grafu je roven dvojnasobku poctu hran, [***POUZE DOPOLEDNE: dusledek: v kazdem grafu je pocet vrcholu licheho stupne sudy, definice skore grafu ***]
7. prednaska 23.11. [***POUZE ODPOLEDNE: dusledek: v kazdem grafu je pocet vrcholu licheho stupne sudy, definice skore grafu, ***] veta o skore, kresleni grafu 1 uzavrenym tahem: graf je eulerovsky (lze nakreslit 1 uzavrenym tahem) prave kdyz je souvisly a ma vsechny stupne sude, nektere jednoduche grafove operace (pridani a odebrani hrany, odebrani vrcholu)
8. prednaska 30.11. deleni hrany, deleni grafu, (vrcholove) 2-souvisly graf, 2-souv. graf zustane souvisly po vyhozeni hrany, deleni 2-souv. grafu je 2-souvisle, hranove 2-souv. graf, graf je 2-souvisly <==> vznikne z trojuhelniku postupnym pridavanim a delenim hran (dukaz implikace zleva doprava vynechan), v 2-souvislem grafu kazde 2 vrcholy lezi na kruznici, v 2-souvislem grafu lezi kazde dve hrany na spolecne kruznici (bez dukazu), (Kapitola 4.) strom, list, strom s alespon 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) - zacatek dukazu
9. prednaska 7.12. 4 charekteristiky stromu (Tvrzeni 4.1.4 skript) - dokonceni dukazu, kostra grafu, Kruskaluv (hladovy) algoritmus na nalezeni min. kostry souv. grafu vcetne dukazu spravnosti (dokonceni priste)
10. prednaska 14.12. zopakovani a dokonceni dukazu spravnosti hladoveho (Kruskalova) algoritmu (poznamka: dukaz spravnosti udelan jinak nez ve skriptech; na zkousku staci znat kterykoliv z nich), Jarnikuv a Boruvkuv algoritmus (bez dukazu spravnosti), (Kapitola 5.) definice oblouku, rovinne grafy, rovinne nakresleni grafu, definice steny a topologicke kruznice, Jordanova veta o topologicke kruznici (bez dukazu), K_5 a K_3,3 nejsou rovinne grafy, G rovinny <==> kazde jeho deleni je rovinne, Kuratowskeho veta: G rovinny <==> G neobsahuje deleni K_5 ani deleni K_3,3 (implikace zleva doprava vyplyva z predchoziho, implikace zprava nedokazovana)
11. prednaska 21.12.
Euleruv vztah pro souvisle rovinne grafy,
stena lib. rov. nakresleni rov.
2-souv. grafu odpovida kruznici,
horni odhad poctu hran v rovinnem grafu a v rov. grafu
bez trojuhelniku, dva dusledky: 1. kazdy rov. graf ma vrchol stupne
nejvyse 5, 2. grafy K_5 a K_3,3 nejsou rovinne,
barveni map a grafu, barevnost nekterych trid grafu (kruznice,
uplny (bip.) graf, strom), vztah mezi barvenim rov. grafu a map, problem 4
barev
Pro zajimavost: O problemu 4 barev je sepsana
pekna anglicky psana
kniha (o historii problemu, s jednoduse podanymi hlavnimi myslenkami reseni),
k dostani v Palaci knih Neoluxor
12. prednaska 4.1. dukaz vety o 5 barvach, (Kapitola 6.) pocitani 2 zpusoby: dukaz principu sudosti pocitanim 2 zpusoby, Spernerova veta o nezavislem systemu mnozin (pozor, Spernerova veta je neco uplne jineho nez Spernerovo LEMMA, i kdyz oboji je ve skriptech blizko sebe, Spernerovo lemma jsme neprobirali) , horni odhad na max. pocet hran grafu bez 4-cyklu
13. prednaska 11.1.
[[ POUZE ODPOLEDNE: dalsi dukaz vety o 5 barvach vcetne
umeleckeho ztvarneni
skupinou studentu, ]]
orientovane grafy a Eulerovske orientovane grafy (podkapitola 3.7 skript),
Cayleyho formule o poctu koster uplneho grafu (kapitola 7 skript)
- mirne upraveny nejnovejsi (Pitmanuv)
dukaz (na zkousku je pozadovano znat jeden (libov.) jeji dukaz),
[[ POUZE DOPOLEDNE: stereograficka projekce (posledni odstavec
podkapitoly 5.1): ukazuje se pomoci ni ze graf lze nakreslit
do roviny bez krizeni (je rovinny)
prave kdyz ho lze nakreslit bez krizeni na povrch koule - protoze
se tato drobnost probrala pouze na dopoledni prednasce, nemusite ji na zkousku
umet ]]