Diskrétní matematika DMI002 (ZS 09/10)

(přednášející J. Matoušek, paralelka "X")

Vítejte na stránkách přednášky z Diskrétní 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...)!

O zkousce

Nove: Vypsan "zachytny" termin 11.3. (ctvrtek) od 2. Upozornuji, ze potom uz dalsi moje oficialni terminy nebudou. V rozumne zduvodnenych pripadech je mozne se domluvit s prednasejicimi ostatnich dvou paralelek a delat zkousku u nich, pokud budou mit nejaky pozdejsi termin.

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 vypisuji v SIS: streda 13.ledna (to je predtermin, mysleny hlavne pro ty, kdo latku bez vetsich problemu zvladaji uz behem semestru), patek 22.ledna, streda 27.ledna a streda 3.unora (s omluvou oznamuji presunuti terminu z puvodne planovaneho 9. unora).

Podminkou ke konani zkousky je zapocet. Vyjimka na predtermin 13.1. mozno prijit i bez zapoctu. Nicmene zkousku oficialne zapisu az po udeleni zapoctu.
Postupne 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, vetsinou neni problem vypsat pozdejsi terminy tyz den. 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.

Preju prijemne uceni a mnoho uspechu!

Přednáška se koná v pondělí od 14:00 v S3. Bude na ní probrána část z knihy J. Matouška a J. Nešetřila (viz níže kolonku Literatura), místy s mírnými obměnami, a dale stručný úvod do diskrétní pravděpodobnosti. Průběžně aktualizovaný seznam probrané látky najdete na konci této stránky. Zatím si můžete o obsahu udělat představu podle mojí loňské přednášky.

Související předměty

Těm, které diskrétní i jiná matematika baví, doporučuji Úvod do řešení problémů kombinatorických, matematických i jiných (NDMI050). Těm, kdo si nejsou moc jisti v matematickém vyjadřování a značení, není jim jasný rozdíl mezi definicí a větou a pod., doporučuji předmět Matematické dovednosti (NMAI069).

Cvičení

K mé paralelce vedou cvičení Tereza Klimošová (tereza.klimosova@seznam.cz), Jan Kynčl, Lukáš Mach a Ondřej Suchý. Ti rozhodují o věcech souvisejících s cvičeními a o zápočtech.

Zde informace pro studenty kombinovaného studia

Dalším dvěma paralelkám přednášejí Petr Kolman a Ondřej Pangrác.

Literatura

J. Matoušek a J. Nešetřil, Kapitoly z diskrétní matematiky. Čtvrté vydání odevzdáno do tisku, mělo by se objevit koncem kalendářního roku. Třetí, rozšířené a opravené vydání: Karolinum 2007. Předchozí vydání Karolinum 2000, dotisky 2002, 2003, ještě starší vydání Matfyzpress 1996. K dostání např. v Knihkupectví Karolinum (Celetná 18, otevřeno po-pá 9-19, so-ne 11-17) či v prodejně skript v Troji. Nějaké výtisky jsou k vypůjčení v knihovně MFF. Zde najdete odhalené chyb(k)y.

Probraná látka

1. prednaska 5/10

Nekolik motivacnich prikladu. Matematicka indukce: zakladni formulace; ukazka: Fibonacciho cisla (F₀=0, F₁=1,F_n+1=F_n+F_n-1), dukaz indukci, ze pro vsechna n prirozena plati F_n mensi nebo rovno fi^n-1, kde fi=(1+odmocnina z 5)/2 (potreba overit pro n=1 a n=2, a potom indukcni krok: z platnosti pro n=n₀ a pro n=n₀-1 se odvodi platnost pro n=n₀+1, pro libovolne n₀ vetsi nebo rovne 2). Zakladni znaceni: zapis mnozin, ciselne obory, dolni a horni cela cast, sumy a souciny, mnozinove operace sjednoceni, prunik, rozdil. Znaceni 2^X pro mnozinu vsech podmnozin. Doporucena cviceni: Ukazat indukci dolni odhad F_n vetsi nebo rovno fi^n-2 pro vsechna n aspon 1. Dalsi priklady na indukci. Ukazat, ze resenim ulohy s mrakodrapy (pocet obarveni n-patroveho mrakodrapu, kde kazde patro smi byt ruzove nebo zelene a dve ruzova patra po sobe jsou zakazana) jsou Fibonacciho cisla (posunuta o 2).

2. prednaska 12/10

Usporadana dvojice (x,y), kartezsky soucin X x Y, binarni relace. Zapis xRy. Skladani relaci. Funkce (neboli zobrazeni) jako specialni typ relace. Funkce prosta (neboli injektivni), funkce na (neboli surjektivni), funkce bijektivni (neboli bijekce), permutace, dvouradkovy a jednoradkovy zapis. Uzitecny FAKT: Pokud X je konecna a existuje bijekce z X do Y, potom |X|=|Y|. Kombinatoricke pocitani: Tvrzeni: n-prvkova mnozina ma prave 2ⁿ podmnozin (dukaz indukci). Pocet funkci z n-prvkove mnoziny do m-prvkove (zase indukci). Pocet prostych funkci z n-prvkove mnoziny do m-prvkove (doporucene cviceni). Charakteristicka funkce podmnoziny; z toho jiny zpusob, jak ukazat, ze n-prvkova mnozina ma 2ⁿ podmnozin.

3. prednaska 19/10

Binomicky koeficient cili kombinacni cislo, n nad k je definovano jako n(n-1)(n-2)...(n-k+1)/k!. Znaceni X nad k pro mnozinu X. Veta: pocet k-prvkovych podmnozin n-prvkove mnoziny je roven n nad 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 trid ekvivalence, tvrzeni (bez dukazu): tridy kazde ekvivalence na mnozine X tvori rozklad mnoziny X. Usporadana mnozina. Linearni usporadani. Zuzeni relace na podmnozinu.

4. prednaska 26/10

Terminologie: částečné uspořádání (= totéž co uspořádání). Příklady částečně uspořádaných množin (systém množin uspořádaný relací inkluze; přirozená čísla uspořádaná relací dělitelnosti). Pojmy: Minimální prvek částečně uspořádané množiny. Nejmenší prvek. Řetězec. Antiřetězec (= nezávislá množina). 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 aspoň n²+1 reálných čísel obsahuje monotónní podposloupnost délky n+1 (důkaz: definujeme vhodné částečné uspořádání na množině {1,2,...,k}, k délka naší posloupnosti; k samostatnému rozmyšlení: řetězce odpovídají neklesajícím podposloupnostem, antiřetězce klesajícím podposloupnostem).

5. prednaska 2/11

Uvod do teorie pravdepodobnosti. Na prednasce rozdavam tisteny sylabus. Zde elektronicka verze (postscript). V teto prednasce probrany body 1-18. Doporucene cviceni: propocitat priklad na podminenou pravdepodobnost s testovanim HIV.

6. prednaska 9/11

Uvod do teorie pravdepodobnosti, body 19-28.

7. prednaska 16/11

Uvod do teorie pravdepodobnosti, body 29,30,32-41.

8. prednaska 23/11

Dulezita pravdepodobnostni rozdeleni (alternativni, binomicke, Poissonovo). Uvod do teorie grafu. 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, pozor na ni). 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 vlastnosti, ktere se isomorfismem zachovavaji.)

9. prednaska 30/11

Odhad maximalniho poctu navzajem neisomorfnich grafu na n vrcholech (horni odhad 2 na (n nad 2); tezsi - dolni odhad pocitanim; v jakem smyslu jsou horni a dolni odhad "blizke"). Cesta, tah, sled v grafu. Nejkratsi mozny sled z u do v je cesta. Souvisly graf. Relace ~, kde u~v znamena, ze existuje cesta z u do v. Je to ekvivalence, jeji tridy se jmenuji komponenty grafu G. Veta: G ma uzavreny tah, prochazejici vsemi vrcholy a vsemi hranami, 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 a silna 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 doporucene cviceni.)

10. prednaska 7.12.

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 pocitani stromu; pocet koster grafu kapa(G).

11. prednaska 14.12. (Martin Tancer)

Pocet koster uplneho grafu na n vrcholech je n^{n-2}, dukaz pomoci povykosu. Pojem rovinneho grafu, nakresleni, stena rovinneho nakresleni. Euleruv vzorec: |V|+s=|E|+2 (s pocet sten) pro kazde rovinne nakresleni souvisleho rovinneho grafu. Dukaz (neformalni) indukci podle poctu hran.

12. prednaska 4.1.2010

Maximalni pocet hran rovinneho grafu (ma-li rovinny graf n vrcholu, n aspon 3, pak ma nejvys 3n-6 hran, a pokud neobsahuje zadny trojuhelnik, pak ma nejvys 2n-4 hran). Dusledek: Kazdy rovinny graf ma vrchol stupne nejvys 5. Pravidelne mnohosteny, souvislost s rovinnymi grafy. Existuje (nejvys) 5 typu pravidelnych mnohostenu. Pojem deleni grafu. Kuratowskeho veta - jen zneni. Problem barveni map.

13. prednaska 11.1.2010

Interpretace mapy jako nakresleni rovinneho grafu. Dualni graf (konstrukce s hlavnimi mesty + dalnicemi). Pojem radneho obarveni a barevnosti grafu, priklady. d-degenerovany graf, proc ma barevnost nejvys d+1. Rovinne grafy jsou 5-degenerovane. Veta o 4 barvach (samozrejme bez dukazu). Veta o 5 barvach s dukazem (pomoci Kempeho retezcu). Hra HEX, nemoznost remizy v ni (zde matematicka cast prezentace v Powerpointu). Doporucena cviceni: Sestavit efektivni algoritmus na rozpoznavani, zda je dany graf bipartitni. Dokazat, ze neobsahuje-li graf kruznici liche delky, pak je bipartitni. Ukazat, ze kazdy strom je 1-degenerovany.