Diskretni Matematika DMI002 (ZS 08/09)

(prednasejici J. Matousek, paralelka "X")

Vitejte na strankach prednasky z Diskretni matematiky.

Zajimaji me

obecne i konkretni pripominky k prednasce, namety na zlepseni v budoucich letech a pod. Doporucuji vyplnit studentskou anketu (i pokud jste s prednaskami spokojeni...)!

Zde informace pro studenty kombinovaneho studia (kteri se nemohou ucastnit prednasek a cviceni)

Prednaska se kona v pondeli od 15:40 v S3. Bude na ni probrana cast z knihy J. Matouska a J. Nesetrila (viz nize kolonku Literatura), misty s mirnymi obmenami. Prubezne aktualizovany seznam probrane latky najdete na konci teto stranky. Ponevadz se studijni plany ponekud zmenily, bude obsah trochu odlisny od predchozich let.

Tem, ktere diskretni i jina matematika bavi, doporucuji Úvod do řešení problémů kombinatorických, matematických i jiných (NDMI050) (uterky od 19:19 v S3).

Cviceni k me paralelce vedou Pavel Rytir, Martin Balek (balek@kam...), Marek Sterzik, Petr Skoda (petr.skoda na adrese seznam.cz), Helena Nyklova a Rudolf Stolar (ruda@kam...). Ti rozhoduji o vecech souvisejicich s cvicenimi a o zapoctech.

Dalsim dvema paralelkam prednaseji Daniel Kral a Ondrej Pangrac.

Literatura

J. Matousek a J. Nesetril, Kapitoly z diskretni matematiky. Treti, rozsirene a opravene vydani: Karolinum 2007. Predchozi vydani Karolinum 2000, dotisky 2002, 2003, jeste starsi vydani Matfyzpress 1996. K dostani napr. 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.
Jako zdroj prikladu pro uceni se na zkousku muzete pouzit stare zkouskove pisemky zde a zde. Ovsem pozor, latka probirana tehdy a nyni se shoduji jen zcasti, a tudiz nektere priklady se k soucasne prednasce nevztahuji.

O zkousce

Zkouska bude ustni, zhruba pul hodiny bude na pisemnou pripravu zadanych otazek. Otazky budou jak teoreticke (definice, tvrzeni a dukazy probrane na prednasce) tak "pocitaci" (typu lehcich a stredne tezkych prikladu ze cviceni). Studijni materialy (poznamky, ucebnice, tahaky), kalkulacky, pocitace a pod. nejsou u zkousky povoleny. Ocekava se, ze definice a tvrzeni budete umet formulovat presne, se vsemi predpoklady (a to i na znamku "dobre"). Dukazy se zkouseji tez. Neucte se jenom ctenim poznamek, zkuste si pak na papir dulezite veci napsat zpameti.

Nekolik terminu je jiz vypsano v SIS: streda 14.ledna (to je predtermin, mysleny hlavne pro ty, kdo latku bez vetsich problemu zvladaji uz behem semestru), streda 21.ledna, streda 28.ledna a utery 17.unora.

Podminkou ke konani zkousky je zapocet. Vyjimka (a zmena): vzhledem k terminum zapoctovych pisemek je na predtermin 14.1. mozno prijit i bez zapoctu. Nicmene zkousku oficialne zapisu az po udeleni zapoctu.
Formalne vypisuji vice terminu na jeden den, abyste nemuseli prilis dlouho cekat, nez prijdete na radu. Pocitejte ale prosim s pripadnym skluzem, hlavne u pozdejsich terminu dany den.
Zkusenost ukazuje, ze tesne pred terminem se vetsinou rada lidi odhlasi a ze maximalni kapacita terminu je nakonec zridka vyuzita. Navic, bude-li kapacita naplnena a budou-li stale dalsi zajemci, neni problem vypsat dalsi termin nasledujici den (to se ovsem netyka predterminu 14.ledna!). Proto nema moc smysl "stat preventivne ve fronte" - prosim neblokujte zbytecne termin, pokud nejste rozhodnuti, ze opravdu budete delat zkousku - neni to slusne vuci ostatnim.
Mezi 28. lednem a 17. unorem zadny termin vypsat nemuzu. Pocitam jeste s jednim nebo dvema "zachytnymi" terminy koncem unora a v breznu.

Preju prijemne uceni a mnoho uspechu!

Probrana latka

1. prednaska 6/10

Nekolik motivacnich prikladu. Zakladni znaceni (zapis mnozin, mohutnost, ciselne obory, dolni a horni cela cast, sumy a souciny, mnozinove operace sjednoceni, prunik, rozdil). Matematicka indukce: obecna formulace, formulace jako dukaz sporem (uvazme nejmensi n, pro nez tvrzeni neplati). Ukazka: definice Fibonacciho cisel (F₀=0, F₁=1,F_n+1=F_n+F_n-1), dukaz indukci F_n mensi nebo rovno fi^n-1, kde fi=(1+odmocnina z 5)/2.

2. prednaska 13/10

Konvence: suma a soucin pres prazdnou mnozinu. Znaceni 2^X pro mnozinu vsech podmnozin. Tvrzeni: n-prvkova mnozina ma prave 2ⁿ podmnozin. Dukaz indukci. Usporadana dvojice (x,y), kartezsky soucin X x Y, binarni relace. Zapis xRy. Skladani relaci. Funkce (neboli zobrazeni) jako specialni typ relace. Skladani funkci. Pocet funkci z n-prvkove mnoziny do m-prvkove (zase indukci). Charakteristicka funkce podmnoziny; z toho jiny zpusob, jak ukazat, ze n-prvkova mnozina ma 2ⁿ podmnozin. Pojmy: funkce prosta (neboli injektivni), funkce na (neboli surjektivni), funkce bijektivni (neboli bijekce). Pokud X je konecna a existuje bijekce z X do Y, potom |X|=|Y|.

3. a 4. prednaska 27.10.

Pojem: permutace (bijekce mnoziny X na sebe). Pocet permutaci n-prvkove mnoziny je n! (faktorial). Dvouradkovy a jednoradkovy zapis permutace. Zapis X nad k pro mnozinu vsech k-prvkovych podmnozin mnoziny X. Veta: je jich |X| nad k (binomicky koeficient neboli kombinacni cislo; n nad k je definovano jako n(n-1)(n-2)...(n-k+1)/k! ). Dukaz: pocitani dvema zpusoby. Pocet nezapornych celociselnych reseni rovnice i₁+i₂+...+i_r=m (trik s prihradkami a prepazkami). Specialni typy relaci: reflexivni, symetricke, tranzitivni, slabe antisymetricke. Ekvivalence. Usporadani.

Pojem grafu. Znazorneni grafu obrazkem. Specialni grafy (uplny graf, cesta, kruznice, uplny bipartitni graf). Bipartitni graf. Podgraf. Indukovany podgraf. Stupen vrcholu v grafu. Skore grafu. Isomorfismus grafu (definice). Poznamky k isomorfismu (Je "snadne" overit, ze dva grafy jsou isomorfni, kdyz zname nejaky isomorfismus; ale neni znam zadny obecny zpusob, jak "snadno" overit, ze dva grafy isomorfni nejsou. Nekdy ale pomuze pocet vrcholu, pocet hran, skore ci jine invarianty.) Odhad maximalniho poctu navzajem neisomorfnich grafu na n vrcholech (horni odhad 2 na (n nad 2); tezsi - dolni odhad pocitanim).

5. prednaska 3.11.

Cesta a kruznice v grafu. Sled, tah. Relace ~, kde u~v znamena, ze existuje sled z u do v. Je to ekvivalence, jeji tridy se jmenuji komponenty grafu G. Graf je souvisly, pokud ma jen jednu komponentu. Eulerovsky graf (existuje uzavreny tah prochazejici vsechny vrcholy a hrany). Veta: G je eulerovsky, prave kdyz je souvisly a stupne vsech vrcholu jsou sude. (Idea dukazu tezsi implikace: vezmi nejdelsi mozny tah v G, ne nutne uzavreny.) Dusledek: G se da nakreslit 1 tahem, ne nutne uzavrenym, prave kdyz je souvisly a pocet vrcholu licheho stupne je 0 nebo 2.

Orientovany graf. Slaba souvislost. Vstupni a vystupni stupen. Veta (analogie predchozi): V orientovanem grafu G existuje uzavreny orientovany tah prochazejici vsechny vrcholy a hrany, prave kdyz je G slabe souvisly a pro kazdy vrchol se vstupni stupen rovna vystupnimu. (Dukaz jako cviceni.)

6. prednaska 10.11.

Strom (souvisly graf bez kruznic). Lemma o koncovem vrcholu. Lemma o vystavbe stromu. Veta: 5 ekvivalentnich definic stromu. Dukaz ekvivalenci (i)<=>(ii) a (i)<=>(v), zbyvajici jako cviceni nebo podle skript. Uvod do rovinnych grafu.

7. prednaska 24.11.

Formalni definice: oblouk, nakresleni grafu, rovinne nakresleni. Topologicky rovinny graf (=rovinny graf plus nejake jeho rovinne nakresleni). Ekvivalence "dve vlnky" (x a y lze spojit obloukem, ktery se vyhyba nakresleni), nedokazovali jsme tranzitivitu. Stena rovinneho nakresleni (= trida ekvivalence "dve vlnky"). Jordanova veta o kruznici: kazde rovinne nakresleni (grafove) kruznice ma presne 2 steny (tezka veta, kdyz se ma dokazat presne, my nebudeme dokazovat). Euleruv vzorec: pro kazde rovinne nakresleni souvisleho rovinneho grafu G=(V,E) plati |V|-|E|+s=2. Dusledek: (i) pro kazdy rovinny graf s n vrcholy, n aspon 3, je pocet hran nejvys 3n-6; (ii) pokud graf navic neobsahuje K_3 (trojuhelniky), potom ma nejvys 2n-4 hran. (Dukaz jsme rekli pouze pro souvisle grafy a pro (i); (ii) se dela podobne - namet na cviceni.) Dusledek dusledku: kazdy rovinny graf obsahuje vrchol stupne nejvys 5. Poznamka: existuji rovinne grafy se vsemi stupni aspon 5 (cviceni).

8. prednaska 1.12.

Grafy K₅ a K_3,3 jsou nerovinne (z predchoziho). Pojem radneho obarveni grafu, barevnost chi(G). Definice: d-degenerovany graf. Tvrzeni: kazdy d-degenerovany graf ma barevnost nejvys d+1. Tvrzeni: kazdy strom je 1-degenerovany (cviceni), kazdy rovinny graf je 5-degenerovany. Poznamka: problem 4 barev, veta o 4 barvach, znamy pouze pocitacove dukazy. Poznamka: puvodni problem byl o barveni politickych map (staty ci hrabstvi, sousedici aspon kouskem hranice, museji mit ruzne barvy), souvislost s rovinnymi grafy pres dualni graf (neformalne: hlavni mesta + dalnice). My jsme dokazali, ze kazdy rovinny graf se da radne obarvit nejvys 5 barvami (indukci, tez v pisnove forme).

9. prednaska 8.12.

Uvod do teorie pravdepodobnosti. Matematicky model pravdepodobnosti: definice pravdepodobnostniho prostoru (elementarni jev, jev, axiomaticka definice, pojem sigma-algebry). Priklady. Bertranduv paradox. Podminena pravdepodobnost P[A | B].

10. prednaska 15.12.

Nezavisle jevy. Priklady. Soucin pravdepodobnostnich prostoru. Nahodna velicina. Stredni hodnota (jen pro konecne pravdep. prostory). Linearita stredni hodnoty. Indikator jevu, jeho stredni hodnota. Vypocet stredni hodnoty poctu jednicek v nahodne posloupnosti delky n - z definice (vyjde pomerne slozita suma) a pomoci indikatoru.

11. prednaska 5.1. 2009

Stredni hodnota poctu levych maxim nahodne permutace. Veta: Kazdy graf s m hranami obsahuje bipartitni podgraf s aspon m/2 hranami. Dukaz - pravdepodobnostni metoda - zvolima nahodnou podmnozinu vrcholu a pocitame stredni hodnotu poctu hran jdoucich "krizem". Distribucni funkce nahodne veliciny. Definice: nezavisle nahodne veliciny. Rozptyl nahodne veliciny (jista mira prumerne odchylky od stredni hodnoty). Markovova nerovnost. Cebysevova nerovnost.

12. prednaska 12.1. 2009

Částečně uspořádaná množina (opakování). Příklady (systém množin uspořádaný relací inkluze; přirozená čísla uspořádaná relací dělitelnosti; množina všech uspořádaných dvojic (x,y) přirozených čísel, relace = nerovnost v obou složkách). Pojmy: Minimální prvek částečně uspořádané množiny. Nejmenší prvek. Řetězec. Antiřetězec. alfa(P), omega(P). Věta (o dlouhém a širokém): Pro každou konečnou n-prvkovou částečně uspořádanou množinu P platí alfa(P).omega(P) je aspoň n. Důsledek (Erdosovo-Szekeresovo lemma): Libovolná posloupnost n²+1 reálných čísel obsahuje monotónní podposloupnost délky n+1. Pojem kostry grafu, označení kapa(G) počet koster grafu G. Věta (Cayleyho vzorec): kapa(K_n)=n^n-2. V rámci domácí přípravy na zkoušku nastudovat jeden důkaz (na přednášce byl začátek důkazu přes povykosy).