Cvičení se koná každé úterý od 15:40 na Malé Straně v učebně S11 (záznam v SISu), stručný obsah přednášky naleznete zde.
Pokud budete chtít přijít na konzultaci, napište mi e-mail (janvolec-tady_neco_chybi-jikos.cz) a domluvíme se.
Body je možné navzájem směnovat v kurzu 3:1, neboli 3 body jednoho druhu je možné vyměnit za 1 bod druhého. Pokud tedy např. získáte 80 bodů za úkoly, písemku psát nemusíte.
Domácí úlohy budou zadávány na témata, která byla probírána na cvičeních. Na jejich vypracování budou zpravidla dva týdny. Odevzdávají se pak písemně na začátku cvičení, kde si společně ukážeme jejich řešení.
Úvodní cvičení, opakovali jsme některé důležité pojmy z diskretní matematiky, několik příkladů na pravděpodobnost (poslední z nich dokončíme na příštím cvičení).
Přiklady na linearitu střední hodnoty, porovnání rychlosti růstu funkcí, srovnání {n choose k} a {n choose k+1}.
Řešení úloh na linearitu střední hodnoty, Hasseho diagramy, princip inkluze a exkluze, funkce šatnářky.
Řešení úloh na částečná uspořádání, různá lineární uspořádání přirozených čísel, zakladní vytvořující funkce a různé způsoby, jak je odvodit.
Vytvořující funkce a operace s nimi - součty, posunutí, dosazení, vyjádření z rovnice a různé další triky.
Suploval Martin Mareš – použití vytvořujících funkcí ke spočtení n-tého čtverečkového čísla (suma i^2) a ke zjištení počtu stromů na n vrcholech (Catalanova čísla).
Suploval Pavel Klavík – další dávka vytvořujících funkcí, odvození Catalnových čísel kombinatorickou úvahou, úloha s automatem na 1kč a 2kč.
Suplovala Eva Jelínková – vrcholová/hranová k-souvislost grafu, změna k-souvislostí po odebrání hrany resp. vrcholu, vztah mezi hran. a vrchol. k-souvislostí, věta o syntéze 2-souvislých grafů a pozorování, že v 2-souvislém grafu leží každé dva vrcholy na společné kružnici.
Suploval Pavel Klavík – 2-souvislý graf a dvě hrany na společné kružnici, k-souvislý graf a k vrcholů na společné kružnici, ošklivé toky pro Ford-Fulkersona, blokový graf je strom, vztah mezi min. stupněm a nalezením cesty, která není řez.
Byl domluven termín písemky na 12.5.. Hallova věta o SRR, bip. graf, kde min. stupeň partity A je větší nebo roven max. stupni partity B, obsahuje párování pokrývající partitu A, k-reg. bip. graf má obě partity stejně velké, neobsahuje most a existuje v něm perfektní párování.
Konečné projektivní roviny (KPR) a jejich základní vlasnosti, latinské čtverce (LČ) a latinské obdélníky (LO), kolmost LČ, navzájem ortogonalní latinské čtverce (NOLČ), horní odhad na počet NOLČ, každý LO lze rozšířit na LČ, duální KPR, Fanova rovina. Upozornění: příští týden bude písemka.
Psala se písemka.
Vzorová řešení příkladů z písemky a započtování.
| 1. úk. | 2. úk. | 3. úk. | 4. úk. | 5. úk. | 6. úk. | 7. úk. | 8. úk. | Σ př. | pís. | záp. | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Hujer Dokonalý | 23 | 13 | 16 | 16 | 12 | 9 | 15 | - | 104 | 61 | Ano |
Objevíte-li někde chybu, dejte mi, prosím, vědět.
Stránka vytvořena za pomoci programů vi, bash a perl. Poslední změna: 15.09.2009