Zdroje

Formát: jméno dokumentu, autor, [kód používaný k odkazování]

Probabilistic Method, Matoušek, [MatPM]
Graph Theory, Diestel, [Diestel]
Understanding and Using Linear Programming, Matoušek, [MatLin]
Kapitoly z diskrétní matematiky, Matoušek, Nešetřil, [Kapitoly]
Kombinatorika a grafy I, Matoušek, Valla, ke stažení, [SkriptaKG]

Kombinatorika a teorie grafů

barevnost grafů,
- Danova přednáška (seženu výpisky)
- Perfektní grafy (někdo už z nich v historii letěl)
- Brooks, Vizing.
- Thomassenova věta o 5-vybíravosti.
- Zlomkové barvení.
- Kernely a Galvinova věta o hranové vybíravosti.
- Grötschova věta (formulace).
- Gerafy s libovolným diametrem a barevností.
regulární grafy,

:: Dvě varianty, co jsem měl připraveny: * Moorovy grafy, * Kernel, * Turánova věta, grafy; :: nebo * Regularita, Erdös-Stone, Removal. (To bych si nemyslel že sem patří)

souvislost grafů,
- Ford-Fulkersonova věta, Mengerova věta (souvislost a hranově/vrcholově disj. cesty) [SkriptaKG].
- Maderova věta -- důkaz (existují alespoň dvě, druhá mluví o existenci topologického minoru v grafu s dostatečně velkým prům. stupněm a někdy se bere v graf. alg.)
- Souvislost implikuje velký (topologický) minor (přesněji: velká souvislost => velký minimální stupeň a tedy i velký průměrný stupeň => velký (topologický) minor dle Madera).
- Linkovanost. Souvislost implikuje velkou linkovanost.
speciální vlastnosti orientovaných grafů,
- algoritmus na hledání silně souvislých komponent,
- hamiltonovské cesty v turnajích, viz MatPM,
- kernel pro listové obarvení (seznamovou barevnost), viz Diestel,
- orientovaný graf obsahuje cyklus dělitelný $k$ (MatPM).
algebraické vlastnosti grafů,
- Kratova přednáška -- vlastní čísla, jejich proplétání, Moorovy grafy.
- Expandéry, jejich vlastnosti a konstrukce.
- Alternativně/Navíc: Tuttův polynom, algebraické toky, dualita cyklů a řezů jako prostorů.
teorie párování,
- Hallova a Tutteho věta
- http://books.google.com/books?id=mqGeSQ6dJycC&lpg=PP1&pg=PA453#v=onepage&q&f=true
- Matching polytope, totální unimodularita, Edmondsův algoritmus.
Ramseyova teorie,
- Diestel, kapitola 9
- Hales-Jewett, Van Der Warden (mj. viz převyprávění důkazu HJ od MJe), horní/dolní odhady. (Viz MatPM).
nekonečná kombinatorika,
- z KG 1: důkaz Cantorovy-Bernsteinovy věty pomocí nekonečných grafů, Königova věta o nekonečných stromech, věta o kompaktnosti výrokové logiky a její použití na barvení spočetných grafů, spočetná Hallova věta, viz MJova skripta
- asi také: ultrahomogenní struktury, amalgamace (předmět Vybrané kapitoly z komb. I) (Tohle tam fakt nebude)
- Diestel, kapitola 8
strukturální vlastnosti množinových systémů
- Sunflower Lemma,
- Erdös-Ko-Rado (MatPM),
- Bollobásova věta o systémech disj. množin (Jukna nebo MatPM), Spernerova věta jako důsledek,
- Dilworth,
- combinatorial discrepancy (viz MatPM).

Pravděpodobnostní metody a algoritmy

kombinatorické počítání
- Kapitoly (kapitola 3), předmět Komb. poč. (skripta)
- Základy: inkluze a exkluze, šatnářka, Cayleyho formule
- čísla Fibonacciho, Catalanova, Bellova, Stirlingova, možná taky Narayanova čísla (zjemnění Catalanových)
- dále viz vytvořující fce
- Burnsideovo lemma
vytvořující funkce,
- Kapitoly (kapitola 12), Kombinatorické počítání
- operace s nimi
- racionální vytvořující fce: použití na Fib. č. a další, charakterizace rac. VF
- algebraické vlastnosti moc. řad: okruh $C [x] (x)$ , jednotka
- možná i: exponenciální vytvořující funkce (součin, kompozice, použití na Bellova čísla, tedy počet ekvivalencí)
rekurence,
- řešení lineárních rekurencí (Text od MJe), z komb. poč.: P-rekurence a souvislost s rac. VF, možná i kvazipolynomy
základní pravděpodobnostní modely,
- asi se myslí mj. náhodné grafy G(n, p), případně pravděpodobnostní prostor náhodných permutací
linearita střední hodnoty
- Pravděpodobnostní metoda (MatPM)
  - metoda indikátorů (rozložení veličiny na indikátory) a princip průměru (existuje jeden elementární jev neostře menší než střední hodnota a jeden neostře větší)
    - př. vět: # Hamiltonovských cest v turnaji (existuje turnaj s $n!/2^{n-1}$ Ham. cestami), maxcut obsahuje alespoň polovinu hran grafu
  - metoda alternace (změny), Markovova nerovnost
    - slabá Turánova věta ( $α(G)≥n/(2d)\alpha(G)\geq n/(2d)$ ), existence grafu s velkou barevností a velkým obvodem (Erdös)
    - z přednášky (není v MatPM): trochu lepší odhad na Ramseyova čísla, max. min. plocha trojúhelníku (body v jednotkovém čtverci)
použití variace
- TODO: myslí se tím skutečně rozptyl? Jinak by mohlo jít ještě o jiné označení metody alternace ...
- Pravděpodobnostní metoda (MatPM)
  - rozptyl, kovariance, Čebyševova nerovnost
  - dolní odhad na prostřední binomický koeficient, prahové funkce (na výskyt trojúhelníků, $K_4$ či vyvážených grafů), klikovost náhodného grafu, (v MatPM není, ale na přednášce bylo: množiny s různými součty)
aplikace na konkrétní příklady
- asi opět Pravděpodobnostní metoda: použití na odhady Ramseyových čísel, velikosti množinových systémů (Sperner, Erdös-Ko-Rado, Bollobás), barevnosti (hyper)grafů, klikovosti náhodných grafů, ... viz MatPM.
asymptotické odhady funkcí
- O, Theta a Omega notace
- odhady faktoriálu (dolní a horní odhad, Stirlingova formule), binomických koeficientů (obecně, speciálně prostřední) -- Kapitoly, jen Stirling je ve skriptech Komb. poč.
pravděpodobnostní konstrukce a algoritmy
- přednáška Pravděpodobnostní algoritmy -- zdroje viz stránka přednášky (kniha Randomized algorithms by snad mohla být někde ke stažení)
  - pár algoritmů: QuickSort, MinCut, FastSelect
  - třídy pravděpodobnostnostních algoritmů: RP, co-RP, ZPP, BPP, PP; vzájemné vztahy a vztahy k NP a P
  - TODO: ještě něco? Směrování na hyperkrychli, náhodné procházky, Markovovy řetězce, expandery, Monte Carlo, ...?
- pravděpodobnostní konstrukce
  - expandery, např. náhodný d-regulární bipartitní graf je s pravděpodobnostní > konst. > 0 expander s hranovou expanzí d/2
  - TODO: nějaké další pravděpodobnostní konstrukce?

TODO: Vypadá to, že třeba Lovászovo Lokální Lemma nebo Černovova nerovnost z pstní metody nejsou potřeba. Ale je tomu tak?

Kombinatorická optimalizace

grafové algoritmy
- Viz příslušný předmět (a skripta k němu) (a také MJův textík http://mj.ucw.cz/vyuka/ads/25-grafy.pdf)
- např.:
  - nejmenší kostra (třeba Jarník s Fibonacciho haldou)
  - hledání nejkratších cesty
  - toky
  - topologicke trideni
  - rozklad na komponenty silne souvislosti
- Témata "hodná" magisterské zkoušky (názor):
  - Union-Find (s odhadem složitosti log*)
  - 3 Indové
  - Jarník s Fib. haldou
algebraické a aritmetické algoritmy
- Strassenův alg. na násobení matic (snad stačí zmínit základní myšlenku), viz PDF od MJe
- Eukleidův alg., prvočísla: Erastothes, Rabin-Miller, RSA -- viz Alg. okolo TeČo od MJe
- Násobení polynomů, rychlá Fourierova transformace (algoritmus FFT) a její inverze, viz skripta k ADS
- Detekce perf. párování pomocí determinantů/permanentů:
  - exaktní algoritmus na test, jestli perf. párování v bip. grafu existuje (Miniatura 24 z knihy 33 Miniatures od prof. Matouška)
  - aproximace počtu perf. párování přes permanenty (přednáška Pravděpodobnostní algoritmy, R. Motwani, P. Raghavan: Randomized algorithms -- 11.3)
- TODO: ještě něco?
teorie mnohostěnů

**Něco z Optimalizačních metod či KVG, např (http://iuuk.mff.cuni.cz/~sgall/vyuka/OPT/ třeba kapitola 3.) **Dualita, Farkas lemma?

popis pomocí konv. obalu vrcholů a pomocí průniku poloprostorů
stěna stěny je stěna
problém obchodního cestujícího
- z Aproximačních a online algoritmů: 2-apx. alg. (přes kostry), 3/2-apx. (Christofides), bez trojúhelníkové nerovnosti nelze aproximovat, (log n)-apx. asymetrického TSP -- viz http://www.designofapproxalgs.com/ kniha The design of appx. algs.]
speciální matice
- Jednotková, nulová, jedničková --- to se asi nemyslí.
- třeba permutační matice? K tomu mě napadá jen z KG BVN věta o bistochastických maticích (https://staff.fnwi.uva.nl/n.s.walton/Notes/Hall_Birkhoff.pdf)
- Hadamardova? http://en.wikipedia.org/wiki/Hadamard_matrix to jsme brali s Kratem na strukturách
  - Hadamardovy kódy, po dvou nezávislé proměnné (zmíněno i na přednášce Pravděpodobnostní algoritmy)
?? Rozklady matic (LUP dekompozice, SVD a další), adjunkce? Já fakt nevim...
PV: Asi hlavně totálně unimodulární (nebo unimodulární), což souvisí s následujícím bodem.
pozitivně semidefinitní matice
- formulace semidefinitního programování + příklad (např. MAXCUT)
- souvislost s elipsoidovou metodou
- vlastnosti (z lin. algebry)
- použití v analýze (stojí za zmínku)
Totálně unimodulární (celočíselnost LP), pozitivně semidefinitní?
celočíselnost
- zde se asi myslí celočíselnost LP
  - příklad celočíselného programu, příklad LP, který má celočíselná řešení (totální unimod.), příklad problému, který má LP ale není tot. unimod.
  - ILP jdou řešit polynomiálně v omezené dimenzi
- Hodí se sem aproximace a neaproximovatelnost?
- Kdy je celočíselnost poly a kdy je NP-úplná
párování a toky v sítích,
- párování
  - LP formulace (totálně unimodulární pro bip. grafy)
  - polytop párování
  - možná i primálně duální algoritmy
- toky v sítích
  - Zde prý hlavně multikriteriální toky
  - algoritmy viz. bod grafové algoritmy
teorie matroidů,
- předmět Teorie matroidů do Matroid intersection thm (včetně)
  - různé ekvivalentní def. (nezáv. mn., krce, báze, ranky), příklady (grafový, maticový)
  - dualita (nadrovina, kokrce, ranky v duálu)
  - reprezentace (grafy a maticemi nad nějakým tělesem)
  - hladový algoritmus na matroidu a matroid z hladového algoritmu
  - Matroid intersection thm a rovnost max. párování a min. vrcholového pokrytí pro bip. grafy
- V ITI sériích vyšla skripta: Daniel Král', Ondřej Pangrác: Introduction to Matroid Theory (bohužel nejsou ke stažení)
elipsoidová metoda.
- MatLin, pg. 106
- http://www.cs.toronto.edu/~avner/teaching/S7-2411/LN/6/lec6.pdf
- Kolmanova skripta

Category:%20Státnice%20Informatika%20Mgr.