Státnice - Informatika - I4: Diskrétní modely a algoritmy

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Zdroje[editovat | editovat zdroj]

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ů[editovat | editovat zdroj]

  • 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ů.
  • 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[editovat | editovat zdroj]

  • 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]] $, 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[editovat | editovat zdroj]

  • 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
    •  ?? 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.
Citováno z „http://wiki.matfyz.cz/index.php?title=Státnice_-_Informatika_-_I4:_Diskrétní_modely_a_algoritmy&oldid=21620“