kontakt: Honza Hladký
konzultace: po domluvě
Podmínky zápočtu: budou dvě písemky (polovina semestru a konec) na jednoduché příklady, požaduji 60% bodů z každé z nich. Komu se nějaká písemka nepovede bude potřebovat k tomu, aby dostal zápočet aktivní účast na cvičeních a donést vyřešené nějaké domácí úkoly (jednak ty, které budu zadávat průbežně, jednak nějaké zadám na konci semestru).
Pokud budete mít zájem mi nějaký úkol ukázat vyřešený již v průběhu semestru, rád ho zkontroluji a opravený vrátím.
3. ledna
Aktualizováno 15. ledna
Nárok mají
01) Kmet, Michal, kombinovana
02) Males, Branislav, 47
03) Marko, Michal, 47
04) Marchenko, Maryna, 47
05) Masek, Petr, 47
06) Nemejc, Karel, 47
07) Odchazel, Ondrej, 47
08) Papez, Michal, 47
09) Pavlik, Jan, 47
10) Rajcan, Simon, 47
11) Remes, Vaclav, 47
12) Sequens, Jan, 47
13) Skalicky, Tomas, 47
14) Slivka, Lukas, 47
15) Sobotka, Petr, 47
16) Tarabic, Radomir, 47
Nemaji
01) Maly, Lukas, 47
02) Stary, Tomas, 47
Přitom jsem do toho promítl i dnes odevzdané příklady. Dva studenti se určitě budou cítit ukřivdění, protože mi dnes odevzdali úkoly. Jenže se nepodepsali. Napište mi!
1. úkol: Dokažte, že v každém grafu existuje bipartitní pograf, který obsahuje alespoň polovinu hran původního grafu. Hint: indukce.
20. prosince Zápočtová písemka - vzrové řešení najdete tady. Výsledky:
Marko: 0.5+2+0.5+1+0.5=4.5
Starý: 1+2+0+2+1=6
Mašek: 1+4+0.5+1+0.5=7
Marchenko: 1.5+4+0.5+1.5+0=7.5
Malý: 1.5+1.5+2+0+3=8
Odcházal: 0.5+1+2+2+3=8.5
Remeš: 1.5+1+4+3+0.5=9
Maleš: 1+1.5+1+2.5+3=9
Slivka: 1+2+1+2.5+3=9.5
Marek: 2+3+2+0+3=10
Rajčan: 2+1.5+1+3+3=10.5
Němejc: 1+2+2+4+3=12
Skalický: 1.5+4+2+1.5+3=12
Sequens: 2+3.5+2+1.5+3=12
Kmeť: 1.5+4+2+3.5+2.5=13.5
Sobotka: 2+4+1.5+4+3=14.5
Pavlík: 1.5+4+2+4.5+3=15
Papež: 3+4+2+5+3=17
Potřebovali jste 9 bodů. Za každý chybějící bod mi doneste 3 příklady (případně 2 příklady za půlbod) z grafové části - ideálně ty, které jsou na této stránce, případně, komu to nebude stačit, nechť se podívá na příklady Vítka Jelínka. Michal Marko by mi navíc mohl donést ukázat vzorově vyřešenou tuto písemku (ale vlastními slovy, ne opsat vzorové řešení z webu)
Pro ty, kteří na písemku vůbec nepřišli: ozvěte se mailem. Předběžně počítejte s tím, že někdy po vánocích by byl druhý termín, mimo výuku, dále od vás budu požadovat donést na písemku 6 doma spočítaných příkladů (takže o Vánocích na tom můžete pracovat :) ).
13. prosince Barevnost, požární cvičení, barevnost.
6. prosince Rovinnost, barevnost.
1. úkol: Rozhodněte, zda jsou tyto grafy rovinné.
29. listopadu Stromy, kostry.
K promyšlení (zkuste to zapsat!!): Kolik nejvíce hran může mít graf s c komponentami souvislosti na n vrcholech?
K promyšlení (zkuste to zapsat!!): Na cvičení jsme řešili obdobu problému minimální kostry, s tím že cena kostry se brala jako součit (kladných) cen hran. Dohodli jsme se, že na nalezení takto minimální kostry stačí používat obyčejný Kruskalův algoritmus. Proč? Precizně zdůvodněte!
1. úkol: Může být doplněk nesouvislého grafu nesouvislý graf?
K promyšlení (pokud na to nikdo nepřijde, udělám příště) Nechť T je strom na n vrcholech, d(x,y) je funkce "vzdálenost vrcholu x a y ve stromu T". Dokažte, že pro každý vrchol u stromu T platí:
22. listopadu 2-souvislost.
1. úkol: Dokažte že graf je dva 2-souvislý právě pokud má alespoň dvě hrany a pro každé dvě hrany existuje kružnice, která jimi prochází. Zkuste dokázat (i) s použitím ušatého lemmatu, (ii) bez něj.
15. listopadu Věta o skóre. Eulerovské grafy.
Úlohy typu Stephan King (zadávám príklady, chtěl bych, abyste mi příště odevzdali 4počet příkladů*0.4Kingovská konstanta*20shruba tolik vás je=32 řešení (aktuálně jich mám: 16); pokud jich nebude dost, tak příště nebudu dělat důkazy z přednášky. Tyto úlohy nemají vliv na získání zápočtu.).
1. úkol (King): Vyšetřete, zda-li (i) (1,2,2,2,3,4) (ii) (1,2,2,2,2,3) (iii) (1,2,2,2,2,3,3,3) jsou skóre nějakého grafu. Pokud ano, najděte takové (pomocí věty o skóre)
2. úkol (King): Nechť G je silně souvislý orientovaný graf. Následující podmínky jsou ekvivalentní:
(i) G obsahuje orientovaný cykl sudé délky.
(ii) Vrcholy G lze obarvit dvěma barvami tak, že z každého vrcholu vede šipka do vrcholu jiné barvy.
Dokažte. Pokud se vám nepodaří dokázat obě implikace, pokuste se aspoň o jednu.
3. úkol (King): (i) Dokažte, že hrany libovolného neorientovaného grafu lze zorientovat tak, že vstupní a výstupní stupeň každého vrcholu se liší maximálně o 1. (ii) Mám graf, jehož všechny stupně jsou sudé. Dokažte, že existuje orientace, tak, že vstupní a výstupní stupeň každého vrcholu se rovnají. (1. hint: Eulerova charakterizace, zkuste nějak použít její důkaz, 2. hint (i) je docela těžké, zkuste nejdřív (ii)).
4. úkol (King): Dokažte (zhruba jsem to dělal na cvičeních) charakterizační větu pro Eulerovskost orientovaných grafů.
Spolupráce (tj. sdílení myšlenky) povolená je, opisování ne. Částečná řešení jsou možná za částečný počet bodů.
8. listopadu Midterm (tady je i s řešením).
Výsledky písemky
Marchenko: 3+2+0+1.5=6.5 (sorry, indukce byla bodovaná třemi body a ne dvěma)
Skalický: 3+0.5+0+3=6.5
Malý: 3+1.5+0+2=6.5
Kmeť: 2+1+0.5+3=6.5
Němejc: 3+2+0+2=7
Rajčan: 1+3.5+0.5+2=7
Starý: 3+1+0.5+2.5=7
Marko: 3+2.5+0+2=7.5
Maleš: 3+2.5+0+2.5=8
Mašek: 2+2.5+2+2=8.5
Odcházal: 1.5+3+1+3=8.5
Marek: 3+2.5+2+2=9.5
Sobotka: 3+3+2+2=10
Pavlík: 3+4+2+1=10
Remeš: 3+2+2+3=10
Papež: 2+4+2+2=10
Slivka: 3+2.5+2+3=10.5
Tarabic: 3+3.5+1+3=10.5
Sequens: 3+3+2+3=11
Bylo zadáno 10 úkolů z negrafové části. Komu chybí k limitu z písemky (=7 bodů) 1 bod, nechť donese dva vzorně vyřešené příklady, 2 chybějící body jsou za čtyři příklady.
1. úkol: Naprogramujte program, který zjistí, zda existuje graf se zadaným skóre a pokud ano, pak nějaký najde (tj. neodevzdáváte papír s řešením, ale pošlete zdroják fungujícího programu).
1. listopadu Dodělání PIE, grafy (definice, cesta, prázdný graf, úplný graf, cyklus, doplněk, izomorfismus).
1. úkol: Počítali jsme nějaký příklad s 2n manželskými páry kolem kulatého stolu. Tak to dopočítejte.
2. úkol: Zjistěte, zda jsou následující dvojice grafů G_1 a G_2 izomorfní. Pokud ano, najděte izomorfismus, pokud ne, dokažte, že izomorfimus neexistuje. První tři dvojice jsou nakresleny na obrázku, další dvojici zadávám takto: G_1 je graf na množině vrcholů {1,2,...12} takový, že vrchol i je spojený hranou s vrcholem j (i,j=1,2,..12) právě pokud čísla i a j mají různé zbytky modulo 3. G_2 je graf na množině vrcholů {1,2,...12} takový, že vrchol i je spojený hranou s vrcholem j (i,j=1,2,..12) právě pokud čísla i a j mají různé zbytky modulo 4.
25. řijna Cvičná písemka, tady je i s řešením. Princip inkluze a exkluze.
1. úkol: Kolik existuje zobrazení n-prvkové množiny na m-prvkovou (zkuste speciálně m=2,3)?
2. úkol: (a) Kolik existuje ekvivalencí na m-prvkové množině, které mají právě k tříd ekvivalence?
(a) Kolik existuje ekvivalencí na m-prvkové množině?
Výsledky písemky
Starý: 0+1+3+0=4
Odcházal: 2+0+1.5+1=4,5
Marko: 0.5+0+3+1.5=5
zase čtvěrečkovaná A4, tentokrát drobné písmo: 0.5+0+3+2=5.5
Rajčan: 1+0+3+2=6
Maleš: 2+0+3+2=7
Kmeť: 2+0+2+3=7
Sobotka: 2+0+3+2.5=7.5
Němejc: 2+0+3+4=9
čtvěrečkovaná A4: 2+3+3+1=9
Pavlík: 2+0.5+3+4=9.5
Skalický: 2+2+3+0=7
Slivka: 2+4+3+1.5=10.5
Sequens: 0+4+3+4=11
Remeš: 2+2.5+3+4=11.5
Papež: 2+4+3+4=13
Písemky rozdám na příštím cvičení. Podle mě dopadly celkem dobře. Rezervy jsou hlavně v zapisování (4. příklad většina řešila tak, že napsala výsledek a na postup nějak zapomněla).
18. října Uspořádání, kombinatorické počítání.
1. úkol: Kolik je podmnožin A, B množiny {1,2,...,n} takových, že A je podmnožinou B?
2. úkol: Kolik je neklesajicích funkcí f: {1,2,...,n}->{1,2,...,n}?
11. října Relace.
1. úkol: Průnik dvou ekvivalencí je ekvivalence.
2. úkol: R relace, Pak relace T=R \cup (R \circ R) \cup (R \circ R \circ R) \cup (R \circ R \circ R \circ R) \cup ... je transitvní. Dokažte. (\cup značí sjednocení a \circ operaci skládání)
3. úkol: Najděte prostou funkci f: N->N, která není na. Najděte funkci f: N->N, která je na a není prostá. Najděte funkci f: N->Z, která je na. (N značí množinu přirozených čísel, N={1,2,3,...}, Z značí množinu celých čísel, Z={...,-2,-1,0,1,2,...}).
K promyšlení:
1. úkol nefunguje, když průnik nahradím sjednocením nebo množinovým rozdílem. Najděte protipříklady. Jak to bude se symetrickým množinovým rozdílem?
Mějme T průnik dvou ekvivalencí R a S (jako v 1. úkolu). V jakém vztahu jsou třídy ekvilance T vůči třídám ekvivalence R a S?
Dívejme se na funkce sin a cos jako na relace. Zaveďme funkci f(x)=sin(cos(x)). V jakém vztahu je tato funkce k složením sin \circ cos a cos \circ sin?
Nechť f je funkce f: X->X, kde X je konečná množina. Dokažte, že f je prostá, právě když je na (podotázky 3. úkolu ukazují, že předpoklad konečnosti X je podstatný).
4. října Indukce. Úkol: Dokažte, že každý čtverec o rozměrech 2^k x 2^k lze pokrýt kostkami tvaru L (rozměr L je 2 x 2) tak, že jediné nepokryté pole je rohové.
