- První přednáška (5.10.2022):
- Úvod, základní informace o přednášce,
- odhady faktoriálu a binomických koeficientů,
- 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],
- odhady binomického koeficientu, (n/k)k ≤ C(n,k) ≤ nk [MN: kapitola 3.5],
- odhady největšího binomického koeficientu, 22n/(2n1/2) ≤ C(2n,n) ≤ 22n/(2n)1/2 [MN: kapitola 3.5],
- aplikace: náhodné procházky po celočíselné ose [I: kapitola 1.4],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Druhá přednáška (12.10.2022):
- Vytvořující funkce,
- motivační příklad, základní vytvořující funkce [MN: kapitola 12.1],
- přechod mezi posloupnostmi a vytvořujícími funkcemi, základní operace s vytvořujícími funkcemi [MN: kapitola 12.2],
- Fibonacciho čísla a zlatý řez [MN: kapitola 12.3],
- řešení lineárních rekurentních rovnic, ukázáno na konkrétním příkladě: odvození Binetova vzorce pro Fibonacciho čísla [MN: kapitola 12.3] (pro zájemce [M1]),
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Třetí přednáška (19.10.2022):
- Vytvořující funkce a jejich aplikace, připomenutí z minula,
- zobecněná binomická věta a náčrt jejího důkazu [MN: kapitola 12.2],
- důsledek zobecněné binomické věty o funkcích (1-x)-n (důkaz pomocí zobecněné binomické věty) [MN: kapitola 12.2],
- zakořeněné binární stromy a důkaz faktu, že počet zakořeněných binárních stromů na n vrcholech se rovná n-tému Catalanovu číslu [MN: kapitola 12.4],
- odvození vytvořujících funkcí pro počet uspořádaných a neuspořádaných rozkladů přirozených čísel na kladné sčítance [MN: kapitola 12.7],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Čtvrtá přednáška (26.10.2022):
- Konečné projektivní roviny,
- definice, Fanova rovina [MN: kapitola 9.1],
- každé dvě přímky v konečné projektivní rovině mají stejný počet bodů, řád konečné projektivní roviny [MN: kapitola 9.1],
- každým bodem konečné projektivní roviny (X,P) řádu n prochází n+1 přímek, |X|=n2+n+1 a |P|=n2+n+1 [MN: kapitola 9.1],
- incidenční graf množinového systému a duální množinové systémy [MN: kapitola 9.1],
- duálem konečné projektivní roviny řádu n je konečná projektivní rovina řádu n [MN: kapitola 9.1],
- existence konečných projektivních rovin pro jednotlivé řády, zmínka o konstrukci konečných projektivních rovin z konečných těles [MN: kapitola 9.2],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Pátá přednáška (2.11.2022):
- Konečné projektivní roviny, připomenutí z minula,
- algebraická konstrukce konečných projektivních rovin z konečných těles [MN: kapitola 9.2],
- latinské čtverce a jejich ortogonalita [MN: kapitola 9.3],
- horní odhad n-1 na počet navzájem ortogonálních latinských čtverců řádu n [MN: kapitola 9.3],
- konečná projektivní rovina řádu n ≥ 2 existuje právě tehdy, když existuje n-1 navzájem ortogonálních latinských čtverců řádu n [MN: kapitola 9.3],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Šestá přednáška (9.11.2022):
- Toky v sítích, přednáška se fyzicky nekoná (Děkanský den)
- sítě, toky, velikost toku, existence toku maximální velikosti (jen náčrt důkazu) [MV: kapitoly 2.1 a 2.5],
- řezy, kapacita řezu [MV: kapitola 2.1],
- Hlavní věta o tocích (maximální velikost toku = minimální kapacita řezu), elementární řezy a jejich vlastnosti, zlepšující cesty (důkaz se nezkouší) [MV: kapitola 2.2],
- Fordův–Fulkersonův algoritmus a Věta o celočíselnosti (důkaz se nezkouší) [MV: kapitola 2.3],
- starý záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Sedmá přednáška (16.11.2022):
- Aplikace toků v sítích, připomenutí toků,
- Kőnigova–Egerváryho věta o maximálním párování a minimálním vrcholovém pokrytí v bipartitních grafech [M2: kapitola 1],
- Hallova věta ve verzi pro systém různých reprezentantů v množinovém systému a ve verzi pro párování v bipartitním grafu [MV: kapitola 4],
- důsledek Hallovy věty o párování v k-regulárních bipartitních grafech (v o něco obecnějším znění) [MV: kapitola 4.1],
- rozšiřování latinských obdélníků [MV: kapitola 4.1],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Osmá přednáška (23.11.2022):
- Míra souvislosti grafů,
- hranový řez, vrcholový řez, hranová a vrcholová souvislost, hranově t-souvislé grafy a vrcholově t-souvislé grafy [MV: kapitola 3],
- při odebírání hrany hranová i vrcholová souvislost klesne nanejvýš o jedna [MV: kapitola 3],
- vrcholová souvislost je nanejvýš tak velká jako hranová souvislost [MV: kapitola 3],
- Fordova–Fulkersonova věta [MV: kapitola 3],
- Mengerova věta [MV: kapitola 3],
- starý záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Devátá přednáška (30.11.2022):
- Míra souvislosti grafů, připomenutí z minula,
- most, artikulace, zachování vrcholové 2-souvislosti při dělení hrany [MN: kapitola 4.7],
- 2-souvislost a Ušaté lemma [MN: kapitola 4.7],
- počítání dvěma způsoby,
- Cayleyho vzorec (důkaz pomocí počítání POVYKOSů) [MN: kapitola 8.6],
- počet koster úplného grafu Kn bez jedné hrany [MN: cvičení 8.1.2],
- Kirchhoffova věta o počítání koster pomocí determinantu Laplaciánu (bez důkazu) [MN: kapitola 8.5],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Desátá přednáška (7.12.2022):
- Počítání dvěma způsoby,
- Spernerova věta [MN: kapitola 7.2],
- úvod do Ramseyovy teorie,
- Dirichletův princip [MN: kapitola 11.1],
- Ramseyovo číslo R(k,l), důkaz faktu R(3,3) = 6 [MN: kapitola 11.1],
- důkaz horního odhadu R(k,l) ≤ (k+l-2 nad k-1) [MN: kapitola 11.2],
- důkaz dolního odhadu R(k,k) ≥ 2k/2 pro k ≥ 3 [MN: kapitola 11.3],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Jedenáctá přednáška (14.12.2022):
- Úvod do Ramseyovy teorie, připomenutí z minula,
- Ramseyova věta pro p-tice [MV: kapitola 1],
- aplikace: Erdősova–Szekeresova věta [MV: kapitola 1],
- nekonečná verze Ramseyovy věty pro p-tice [M3],
- Kőnigovo lemma (bez důkazu) [M4],
- nekonečná Ramseyova věta implikuje konečnou Ramseyovu větu,
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Dvanáctá přednáška (21.12.2022):
- Samoopravné kódy,
- základní terminologie, abeceda, slova, kódy a jejich parametry [K],
- příklady kódů: opakovací kódy, charakteristické vektory přímek konečných projektivních rovin, Hadamardovy kódy [K],
- ekvivalence kódů, [K],
- Hammingův odhad a Gilbertův–Varshamův odhad [K],
- definice lineárních kódů a jejich příklady [K],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
- Třináctá přednáška (4.1.2023):
- Samoopravné kódy, připomenutí z minula
- generující matice lineárního kódu, duální kód, kontrolní matice lineárního kódu [K],
- kódování pomocí lineárních kódů [K],
- dekódování pomocí lineárních kódů, syndrom a jeho vlastnosti [K],
- souvislost mezi minimální vzdáleností lineárního kódu a sloupci kontrolní matice [K],
- Hammingovy kódy a jejich parametry, důkaz perfektnosti, lepší reprezentace inverzu k syndromu [K],
- záznam [ZIP], zápisky [PDF] a prezentace [PDF].
|