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 ($\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.