- První přednáška (MB) (1.10.2019):
- Úvod, základní informace o přednášce, zkoušce a zápočtech,
- množiny, základní operace a značení,
- pojem množiny, mohutnost konečných množin, typy zápisu množin, výroky, Russellův paradox, číslené obory, základní operace s čísly [MN: kapitola 1.2],
- kvantifikátory a logické spojky, [MN: kapitola 1.2],
- množinové operace a jejich vlastnosti, De Morganovy zákony [MN: kapitola 1.2],
- typy důkazů,
- přímý důkaz, důkaz sporem, nepřímý důkaz jako speciální typ důkazu sporem, matematická indukce [MN: kapitola 1.3],
- ilustrace všech tří typů důkazů na konkrétním příkladě (3 dělí n3-n pro každé přirozené číslo n),
- zápisky [PDF] a prezentace [PDF].
- Druhá přednáška (MB) (8.10.2019):
- Relace na množinách,
- uspořádané dvojice a n-tice, Kartézský součin, [MN: kapitola 1.5],
- (binární) relace, značení relací třemi způsoby, operace na relacích (inverzní relace a skládání relací) [MN: kapitola 1.5],
- funkce, druhy funkcí (prosté, na, vzájemně jednoznačné), skládání funkcí, [MN: kapitola 1.4],
- pojem mohutnosti i pro nekonečné množiny, Cantorova–Bernsteinova věta (bez důkazu), Cantorova věta (náčrt Cantorovy diagonální metody),
- druhy relací (reflexivní, symetrická, tranzitivní, antisymetrická) [MN: kapitola 1.5],
- ekvivalence, třídy ekvivalence, tvrzení o třídách ekvivalence [MN: kapitola 1.6],
- zápisky [PDF] a prezentace [PDF].
- Třetí přednáška (MB) (15.10.2019)
- Částečná uspořádání,
- definice, Hasseův diagram, příklady, [MN: kapitola 2.1],
- minimální, maximální, nejmenší a největší prvky [MN: kapitola 2.2],
- každá konečná neprázdná částečně uspořádaná množina obsahuje minimální prvek, [MN: kapitola 2.2],
- každé konečné částečné uspořádání lze rozšířit na lineární uspořádání [MN: kapitola 2.2],
- každou částečně uspořádanou množinu lze vnořit do částečně uspořádané množiny uspořádané inkluzí [MN: kapitola 2.3],
- Věta o dlouhém a širokém [MN: kapitola 2.4],
- Erdősovo–Szekeresovo lemma o monotónních podposloupnostech [MN: kapitola 2.4],
- zápisky [PDF] a prezentace [PDF].
- Čtvrtá přednáška (ML) (22.10.2019)
- Kombinatorické počítání,
- počty všech zobrazení, počet podmnožin (dva důkazy), počet prostých, [MN: kapitola 3.1],
- zobrazení, počet a znázornění bijekcí, [MN: kapitola 3.1],
- binomické koeficienty, počet k-bodových podmnožin, míče a koše, znění, [MN: kapitola 3.2],
- binomické věty a důsledky, [MN: kapitola 3.3],
- zápisky [PDF].
- Pátá přednáška (29.10.2019): Přednáška se nekoná (Imatrikulace 1. ročníku).
- Šestá přednáška (ML) (5.11.2019)
- Princip inkluze a exkluze,
- tři důkazy (indukcí, počítáním, přes charakteristické funkce), [MN: kapitola 3.6],
- problém šatnářky, [MN: kapitola 3.7],
- počet surjektivních funkcí,
- vzorec pro Eulerovu funkci (nebude se zkoušet), [MN: kapitola 3.7],
- zápisky [PDF].
- Sedmá přednáška (12.11.2019): Přednáška se nekoná (Děkanský sportovní den).
- Osmá přednáška (IK) (19.11.2019):
- Úvod do teorie grafů,
- definice grafu, izomorfismus grafů, [MN: kapitola 4.1],
- důležité grafy: úplný, úplný bipartitní, kružnice, cesta, [MN: kapitola 4.1],
- další pojmy: bipartitní graf, podgraf, indukovaný podgraf, cesta v grafu, kružnice v grafu, souvislost, komponenty souvislosti, vzdálenost v grafu (poznámka o metrice), [MN: kapitola 4.2],
- poznámka o reprezentaci grafů (matice sousednosti, incidence, seznam sousedů), [MN: kapitola 4.2],
- Eulerovské grafy, charakterizace, [MN: kapitola 4.4],
- zápisky [PDF] a prezentace [PDF].
- Devátá přednáška (ML) (26.11.2019):
- Eulerovské grafy,
- Eulerova věta a její algoritmický důkaz, [MN: kapitola 4.5],
- Hamiltonovské kružnice a problém jejich nalezení, [MN: kapitola 4.5],
- orientovaná Eulerova věta a její aplikace, [MN: kapitola 4.6],
- princip sudosti, počet sledů, [MN: kapitola 4.4],
- grafová barevnost,
- grafová barevnost, příklady, odhady, chromatický polynom jako aplikace PIE, [MN: kapitola 6.4],
- zápisky [PDF].
- Desátá přednáška (MB) (3.12.2019):
- Skóre grafů,
- definice skóre grafu, příklady, rozhodnutí, zda je posloupnost skórem grafu, [MN: kapitola 4.3],
- Věta o skóre (Havlův algoritmus), [MN: kapitola 4.3],
- stromy,
- definice a příklady, [MN: kapitola 5.1],
- existence listů, odebírání a přidávání listů nepokazí vlastnost být stromem, [MN: kapitola 5.1],
- charakterizace stromů: pět ekvivalentních definic stromů, [MN: kapitola 5.1],
- zápisky [PDF] a prezentace [PDF].
- Jedenáctá přednáška (MB) (10.12.2019):
- Problém minimální kostry,
- definice kostry, ohodnoceného grafu, formulace Problému minimální kostry, motivace, [MN: kapitola 5.4],
- Jarníkův algoritmus a důkaz jeho korektnosti, [MN: kapitola 5.5],
- počítání dvěma způsoby a Cayleyho vzorec,
- počty koster úplného grafu na n vrcholech, malé případy, [MN: kapitola 8.1],
- Cayleyho vzorec a důkaz počítáním povykosů, [MN: kapitola 8.6],
- zápisky [PDF] a prezentace [PDF].
- Dvanáctá přednáška (MB) (17.12.2019):
- Rovinné grafy,
- definice oblouku a grafového nakreslení, rovinná nakreslení a jejich stěny, definice rovinných grafů, [MN: kapitola 6.1],
- Jordanovy křivky a Jordanova věta o kružnici (bez důkazu), [MN: kapitola 6.2],
- podrozdělení grafu, Kuratowského věta (bez důkazu), [MN: kapitola 6.2],
- Eulerova formule, odhad na počet hran rovinného grafu (náčrt důkazu), grafy K5 a K3,3 a jejich podrozdělení nejsou rovinné, [MN: kapitola 6.3],
- barvení rovinných grafů, duální graf, Věta o 4 barvách (bez důkazu), znění Věty o 5 barvách [MN: kapitola 6.4],
- zápisky [PDF] a prezentace [PDF].
- Třináctá přednáška (MB) (7.1.2020):
- Rovinné grafy,
- Věta o 5 barvách a její důkaz pomocí kontrakce hran [MN: kapitola 6.4],
- asymtptotické počítání a odhad faktoriálu,
- asymptotické počítání, Landauova notace a příklady [MN: kapitola 3.4],
- nn/2 ≤ n! ≤ nn a e(n/e)n ≤ n! ≤ en(n/e)n (důkaz indukcí) [MN: kapitola 3.4],
- Stirlingův vzorec (bez důkazu) [MN: kapitola 3.4],
- zápisky [PDF] a prezentace [PDF].
|