Cvičení z diskrétní matematiky (ZS 2008/2009)

Cvičení se koná každý čtvrtek ve 12:20 v Troji v učebně T5 (záznam v SISu), stránky k přednášce najdete zde.

Konzultace

Pokud budete chtít přijít na konzultaci, napište mi e-mail (janvolec-tady_neco_chybi-jikos.cz) a domluvíme se.

K získání zápočtu je potřeba získat:

Za pravidelnou docházku na cvičení (nejvýše 4 absence) získáte dalších 5 bodů.


Co jsme dělali?

2.10.2008

Různé logické hříčky a příklady, příklad na špatné použití indukce, několik základních pojmů o množinách. Domácí příklady

9.10.2008

"Rozšifrování" úkolu s množinami, další porce úloh na logické myšlení, příklady na použití matematické indukce, kolik je sudých a kolik lichých podmnožin nějaké množiny. Domácí příklady

16.10.2008

Ukázka odvození vzorce pro n-té čtverečkové číslo, různé typy relací a jejich příklady, počet ekvivalencí na 3 prvcích. Domácí příklady

23.10.2008

Počet částečných uspořádání na 3 prvcích, počet téměř prostých funkcí, různé identity s kombinačními čísly a sumami, počet dvojic podmnožin, které jsou navzájem v inkluzi. Domácí příklady

30.10.2008

Počitání různých uspořádání, celkové počty určitých slov, princip inkluze a exkluze pro 2 a 3 množiny. Domácí příklady

6.11.2008

Graf, podgraf, doplňek grafu, komponenta souvislosti, počet všech grafů na n vrcholech, izomorfismus grafů, dolní odhad na počet po dvou neizomorfních grafů. Domácí příklady

13.11.2008

Rozebrání staršího úkolu na princip inkluze a exkluze, dolní odhady na počet listů stromu, bipartitni grafy (definice, charakteristika pomocí lichých kružnic), po dvou neizomorfni grafy na 4 vrcholech. Domácí příklady

20.11.2008

Rešení úkolu s posloupností odpovídající nějakému skóre stromu, grafy nakreslitelné k uzavřenými tahy, grafy nakreslitelné k tahy (nedokončili jsme). Domácí příklady

27.11.2008

Byl domluven termín písemky na 11.12.2008. Dokončení zapeklitého příkladu s charakterizací grafu nakreslitelných pomocí k tahů, důkladné rozebrání předposledních domácích úloh a meditace nad úskalím, které přináší konstruktivní indukce, rozebrání posledních domácích úloh, věta o skóre a hledání rozumně vypadajících posloupností, které skórem nejsou. Domácí příklady

4.12.2008

Důkaz nerovinnosti K_5 (z eulerovy formule), vztah mezi počtem hran a vrcholů u rovinného grafu bez trojúhelníků, degenerovanost grafu, různá pozorování o barevnosti (ne nutně rovinných) grafů. Upozornění: příští týden bude písemka. Domácí příklady

11.12.2008

Bylo dvojcviko - druhé místo lineární algebry, proto příští týden bodou naopak po sobě dvě cvika z lineární algebry.
V první části se psala písemka, v druhé se pak rozebíralo její řešení. Dále jsme si rozmysleli, že v každém souvislém grafu existuje vrchol (pokud je |V|>1, tak dokonce alespoň 2 vrcholy), po jehož odebrání zůstane graf souvislý, kódovali a dekódovali jsme kostru kliky pomocí Prüferova kódu. Domácí příklady

8.1.2009

Resumé kolem písemky, jednoduché příklady na pravděpodobnost během házení kostkami, příklad z přednášky na házení mincí dokud nepadne LLR resp. LRR (nedokončen). PS: náhradní písemka bude příští cvičení.

15.1.2009

Náhradní písemka / počet koster úplného grafu bez jedné hrany (počítáním 2 způsoby), eulerovské tahy v orientovaných grafech, příklady na podmíněnou pravděpodobnost a linearitu střední hodnoty.


Průbežné výsledky:

1. př.2. př.3. př.4. př.5. př.6. př.7. př.8. př.9. př.10. př.11. př.Σ př.účastpís.záp.

Objevíte-li někde chybu, dejte mi, prosím, vědět.

Poslední změna: 28.01.2009