IA166 Fixed-Parameter Algorithms

Fakulta informatiky
jaro 2013
Rozsah
2/2. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
Sebastian Ordyniak, PhD (přednášející), prof. RNDr. Petr Hliněný, Ph.D. (zástupce)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Pá 14:00–15:50 C511
Předpoklady
A good understanding of algorithms and their worst-case analysis. A basic understanding of Graph Theory.
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
The course expands on courses Algorithm design I and Algorithm design II, and it couples IA101 Algorithmics for Hard Problems with a focus on the design of fixed-parameter algorithms for hard computing tasks. The course systematically explains, combines, and compares the main possibilities for designing efficient fixed-parameter algorithms.
Osnova
  • 1. Parameterized Complexity (Basic Theory, Examples and Interpretation)
  • I. Algorithmic Techniques: Bounded Search Tree
  • 2. Basic Ideas, Analyzing the size of the Search Tree
  • 3. Bounded Search for Vertex Cover, d-Hitting Set, Maximum Satisfiability
  • II. Kernelization
  • 4. Formal Definition, Basic Idea and Examples
  • 5. Kernelizations for Vertex Cover, d-Hitting Set, Maximum Satisfiability
  • 6. Combining Kernelization and Bounded Search Tree Algorithmic Techniques: Reduction to Problem Kernel
  • 7. Lower Bounds for Kernelization
  • III. Further Algorithmic Techniques
  • 8. Integer Linear Programming, Shrinking Search Trees by Dynamic Programming
  • 9. Color-Coding, Hashing (Examples: Longest Path/Cycle),Iterative Compression (Examples: Vertex Cover, Feedback Vertex Set)
  • IV. Applications:
  • 10. Computational Biology: Phylogenetic Trees, Structure Comparision for RNA
  • 11. AI: non-monotonic Reasoning, Satisfiability
Vyučovací jazyk
Angličtina
Informace učitele
Literature
Rolf Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press 2006; http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.4638&rep=rep1&type=pdf
Joerg Flum and Martin Grohe, Parameterized Complexity Theory, Springer 2006
Další komentáře
Studijní materiály
Předmět je vyučován jednorázově.
Předmět je zařazen také v obdobích jaro 2014.