Martin Balko - personal webpage

Kombinatorika a grafy 1 (NDMI011) - přednáška

Hlavní stránka

Přednáška probíhá každé úterý ve 12:20 v místnosti M1.

Přednášku povede Martin Balko. E-mail přednášejícího: balko (AT) kam.mff.cuni.cz

Stránky cvičení k této paralelce:

středa 15:40, S6 (Marian Poljak),

středa 17:20, S6 (Peter Zeman),

středa 12:20, S11 (Jakub Pekárek),

středa 14:00, S10 (Irena Penev),

čtvrtek 9:00, S10 (Matej Lieskovský),

čtvrtek 10:40, S6 (Filip Čermák),

pátek 10:40, S10 (Jakub Pekárek).

Informace:
nahoru

2/2, Z+Zk, 5 kreditů.

Anotace: Základní kurs oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.

Zkouška:

Přihlašování pomocí SISu, termíny tamtéž. Zkouška je ústní s písemnou přípravou a skládá se z pěti otázek (tři otázky na základní pojmy a jejich aplikace, jedna otázka na ověření znalostí důkazů z přednášky a jedna přehledová). Je požadována i schopnost zobecnit a aplikovat získané teoretické znalosti při praktickém řešení úloh. Témata, která se mohou objevit u zkoušky, jsou vypsaná dole v obsahu jednotlivých přednášek.

Vzor zadání zkoušky.

V průběhu semestru zde budou přibývat zápisky z příprav k jednotlivým přednáškám. Pokud v zápiscích narazíte na jakékoli nepřesnosti, dejte mi, prosím, vědět e-mailem.

Konzultace probíhají po přednášce. V případě zájmu o konzultace v jiný čas mi dejte vědět například e-mailem a domluvíme se.

Seznam literatury:

[MN] Jiří Matoušek a Jaroslav Nešetřil: Kapitoly z Diskrétní matematiky, Karolinum 2007. [errata]

[MV] Jiří Matoušek a Tomáš Valla: Kombinatorika a grafy I. [link]

[K] Tomáš Kaiser: Učební text k přednášce Samoopravné kódy. [link]

[M1] Martin Mareš: Lineární rekurence. [PDF]

[M2] Martin Mareš: Krajinou grafových algoritmů. [link]

[M3] Martin Mareš: Ramseyovy věty. [PDF]

[M4] Martin Mareš: Kombinatorické drobnosti. [PDF]

[I] Irena Penev: Combinatorics and Graph Theory 1 (v angličtině). [PDF]

Jednotlivé přednášky:
nahoru

První přednáška (5.10.2021):

Úvod, základní informace o přednášce,

odhady faktoriálu a binomických koeficientů,

n^n/2 ≤ n! ≤ nⁿ a e(n/e)ⁿ ≤ n! ≤ en(n/e)ⁿ (důkaz indukcí) [MN: kapitola 3.4],

Stirlingův vzorec (bez důkazu) [MN: kapitola 3.4],

(n/k)^k ≤ C(n,k) ≤ n^k a 2²ⁿ/(2n+1) ≤ C(2n,n) ≤ 2²ⁿ [MN: kapitola 3.5],

odhady největšího binomického koeficientu, 2²ⁿ/(2n^1/2) ≤ C(2n,n) ≤ 2²ⁿ/(2n)^1/2 [MN: kapitola 3.5],

aplikace: náhodné procházky po celočíselné ose,

zápisky [PDF] a prezentace [PDF].

Druhá přednáška (12.10.2021):

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ápisky [PDF] a prezentace [PDF].

Třetí přednáška (19.10.2021):

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ápisky [PDF] a prezentace [PDF].

Čtvrtá přednáška (26.10.2021):

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|=n²+n+1 a |P|=n²+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, znění věty o konstrukci konečných projektivních rovin z konečných těles [MN: kapitola 9.2],

zápisky [PDF] a prezentace [PDF].

Pátá přednáška (2.11.2021):

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ápisky [PDF] a prezentace [PDF].

Šestá přednáška (9.11.2021):

Toky v sítích,

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 [MV: kapitola 2.2],

Fordův–Fulkersonův algoritmus a Věta o celočíselnosti [MV: kapitola 2.3],

zápisky [PDF] a prezentace [PDF].

Sedmá přednáška (16.11.2021):

Aplikace toků v sítích, připomenutí z minula,

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ápisky [PDF] a prezentace [PDF].

Osmá přednáška (23.11.2021):

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],

zápisky [PDF] a prezentace [PDF].

Devátá přednáška (30.11.2021):

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 K_n 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ápisky [PDF] a prezentace [PDF].

Desátá přednáška (7.12.2021):

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) ≥ 2^k/2 pro k ≥ 3 [MN: kapitola 11.3],

zápisky [PDF] a prezentace [PDF].

Jedenáctá přednáška (14.12.2021):

Ú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ápisky [PDF] a prezentace [PDF].

Dvanáctá přednáška (21.12.2021):

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ápisky [PDF] a prezentace [PDF].

Třináctá přednáška (4.1.2022):

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ápisky [PDF] a prezentace [PDF].