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

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]

Kombinatorika a teorie grafů

• barevnost grafů,
  • Danova přednáška (seženu výpisky)
• regulární grafy,
• souvislost grafů,
• 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í, viz Diestel,
• algebraické vlastnosti grafů,
  • Kratova přednáška
• teorie párování,
  • http://books.google.com/books?id=mqGeSQ6dJycC&lpg=PP1&pg=PA453#v=onepage&q&f=true
• Ramseyova teorie,
  • Diestel, kapitola 9
• nekonečná kombinatorika,
  • Diestel, kapitola 8
• strukturální vlastnosti množinových systémů
  • combinatorial discrepancy (viz MatousekPM)

Pravděpodobnostní metody a algoritmy

• kombinatorické počítání
• vytvořující funkce,
• rekurence,
• základní pravděpodobnostní modely,
• linearita střední hodnoty
• použití variace
• aplikace na konkrétní příklady
• asymptotické odhady funkcí
  • O, Theta a Omega notace
  • odhady faktoriálu, binomických koeficientů
• pravděpodobnostní konstrukce a algoritmy.

Kombinatorická optimalizace

• grafové algoritmy
• algebraické a aritmetické algoritmy
• teorie mnohostěnů
• problém obchodního cestujícího
• speciální matice
• celočíselnost
• párování a toky v sítích,
• teorie matroidů,
• elipsoidová metoda.
  • MatLin, pg. 106
  • http://www.cs.toronto.edu/~avner/teaching/S7-2411/LN/6/lec6.pdf