Cvičení probíhá každé pondělí od 12:20 v učebně S10.
Na cvičení ke mně jsou přihlášeni tito studenti:
| Jméno | Zápočet |
|---|---|
| Michal Brabec | jo |
| Robert Brunetto | jo |
| Jan Čermák | jo |
| Jiří Čížek | |
| Michal Drobný | jo |
| Karel Foltýn | |
| František Haas | |
| Jaroslav Hejlek | |
| Michal Hošala | jo |
| Jaroslav Hromátka | |
| Jiří Jandl | |
| Petr Jankovský | 18.5. |
| Michal Kozák | jo |
| Ivan Krasičenko | |
| Petr Malý | jo |
| Matej Moravčík | |
| Alexand Pícha | |
| Ondřej Plátek | |
| Markéta Popelová | 11.5. |
| Martin Schmid | |
| Martina Šimůnková | jo |
| Jan Štětina | |
| Tomáš Tunys | jo |
| Petr Vévoda | jo |
| Jan Vinárek | jo |
| Tomáš Vodsloň | |
| Petr Votava | |
| Hana Zálohová |
Pokud se zde nevidíte, nejspíš jste se nedostavili na první ani druhé cvičení. V tom případě máte problém a zápočet se vám bude u mě shánět dosti těžko.
Povídání o podmínkách zápočtu a systému fungování cvik.
Asymptoticke odhady funkci a notace O, Omega, Theta, o, omega.
Počítání nejrůznějších odhadů.
Domácí úkoly
Sběratelská úloha, mám K druhů kartiček, náhodně kupuji po jedné,
kolik ve střední hodnotě nakoupím karet než mám celou sbírku?
V rámci toho: odhad harmonického čísla H_n, použití linearity střední hodnoty,
kolik průměrně hodů falešnou mincí musím udělat, než mi padne orel.
Generování náhodné permutace v počítači, několik algoritmů.
Domácí úkoly
Algoritmus topologického třídění grafu.
Povídání o částečných uspořádáních lineárních uspořádáních.
Když uvážím průnik,sjednocení,složení,rozdíl dvou ČU, vznikne opět ČU?
Může existovat relace, která je současně ekvivalence a ČU, jak bude vypadat?
Maximální řetězce a antiřetězce v ([n],|) a v (2^[n],\subset) (to druhé nedořešeno).
Domácí úkoly
Princip inkluze a exkluze.
Na kolik nul končí desítkový zápis $1000!$ ?
Kolika možnostmi lze do fronty na oběd v menze rozestavit 5 matematiků, 4 informatiky a 3 fyziky tak,
aby ani jeden obor netvořil jeden souvislý blok?
Kolik je funkcí [m]->[n], které jsou na? (nedořešeno)
Domácí úkoly
Kolik je funkcí [m]->[n], které jsou na?
Kolik je čisel <100 nedělitelných žádnou druhou mocninou?
Povídání o vytvořujících funkcích.
Domácí úkoly
Souvislost ulohy o poctu zpusobu jak mincemi zaplatit castku
s koeficientem u soucinu polynomu.
Variace na predchozi, ale restriktivnejsi podminky pro pocty minci.
Zobecnena binomicka veta.
Pouziti ZBV pri reseni predchozich uloh.
Operace s generujicim funkcemi, co to provadi s kodovanou posloupnosti.
Domácí úkoly
Kolika moznostmi se da vydlazdit mrizka 2xN dlazdicemi 2x1?
Vyroba GF k ruznym posloupnostem.
Vzorce pro n-ty clen pro ruzne GF (moc jsme jich nestihli).
Priklady na urceni GF z rekurentne zadane posloupnosti (moc jsme jich neudelali).
Domácí úkoly
Kvuli nahle nemoci bylo suplovani. Dusledek Halla - v bip. grafu s jednou partitou nizsich stupnu nez v te druhe existuje parovani, co pokryva celou tu partitu s nizsimi stupni. Hrany k-reg. bipart. grafu lze vyjadrit jako sjednoceni k perf. par. A nekolik dalsich (nevyresenych uloh).
Pro kazde M existuje G s prave M perf. parovanimi.
3,3-SAT je vzdy splnitelny (nedodelano).
Opakovani konecnych projektivnich rovin.
Fanova rovina je jedina KPR (az na izomorfismus) radu 2 (nedodelano).
Proc nelze vynechat axiom o 4 bodech v definici KPR.
Pocet latinskych obdelniku velikosti 2xN.
Ekvivalentni definice KPR (a dukaz ekvivalence obou definic).
Domácí úkoly
Opakovani toku v sitich.
Jak z toku v siti udelat cirkulaci pridanim hrany.
Velikost toku lze merit jak u zdroje, tak u stoku.
Velikost toku je vzdy mensi nez kapacita rezu (neudelano).
Uloha max. toku lze formulovat jako uloha LP (neudelano).
Ford-Fulkersonuv algoritmus a jeho vlastnosti.
FF dobehne na celociselnych i racionalnich sitich.
Priklad, kdy FF pobezi hodne pomalu.
Overeni, zda tok v nakreslene siti je maximalni, nalezeni minimalniho rezu.
Dokazte ci vyvratte: kazda sit ma celociselny tok; kazda sit ma celociselny maximalni tok;
kazda sit ma maximalni celociselny tok; kazda souvisla sit ma prave jeden maximalni tok;
tok je maximalni prave tehdy, kdyz existuje rez, co protina kazdou nenasycenou cestu.
Domácí úkoly
Opakovani pojmu okolo souvislosti grafu a prislusnych vety. 3-regularni bipartitni souvisly graf je vrcholove 2-souvisly. Mira vrcholove souvislosti K_n\C_n. k_e(G)-1 <= k_e(G-e) <= k_e(G), jak je to s mazanim vrcholu a kdyz merime k_v(G). Necht G je rovinny vrcholove 2-souvisly graf, potom v kazdem rov. nakresleni je hranice kazde steny grafova kruznice (nedodelano). G 3-regularni hranove 2-souvisly, potom je vrcholove 2-souvisly.
Napsali jsme si pisemku.
Domácí úkoly