Vinicius Fernandes dos Santos — Exponential Algorithms and parameterized complexity
Vinicius Fernandes dos Santos — Algoritmos exatos exponenciais e complexidade parametrizada
Main page
Página principal
Disciplina: Algoritmos exatos exponenciais e complexidade parametrizada
Esta é uma disciplina de foco teórico que busca dar uma visão geral de técnicas de desenvolvimento de algoritmos exatos exponenciais para a resolução de problemas difíceis, isto é, problemas para os quais acredita-se não ser possível a resolução em tempo polinomial.
Uma motivação para o estudo destas técnicas nasce da necessidade de garantia de tempo de execução para a resolução de problemas NP-difíceis, ainda que o tempo total seja exponencial. Em diversas aplicações, não se pode abdicar de conhecer um limite superior para tal tempo de execução. Ainda assim, busca-se desenvolver algoritmos tão eficientes quanto possível, explorando a estrutura do problema.
Para cursar essa disciplina, é necessário conhecimento de conceitos de Matemática Discreta, Algoritmos e Complexidade de Algoritmos. Recomenda-se que alunos de graduação tenham cursado a disciplina Algoritmos e Estruturas de Dados III, ou que já dominem seu conteúdo.
Professor:
Programa:
- Revisão de teoria de grafos, programação dinâmica, Classes de complexidade P, NP
- Topicos em NP-completude e classes de complexidade
- Algoritmos exatos para problemas NP-difíceis
- Introdução à complexidade parametrizada
- Classes de complexidade XP e FPT
- Kernelização
- Árvores de altura limitada
- Compressão iterativa
- Métodos probabilísticos
- Treewidth
- Intratabilidade FPT
- Hipótese do tempo exponencial e Hipótese forte do tempo exponencial
Bibliografia:
- Rodney G. Downey, Michael R. Fellows. Fundamentals of Parameterized Complexity.
- Fedor V. Fomin, Dieter Kratsch. Exact Exponential Algorithms.
- Marek Cygan et al. Parameterized algorithms.
Bibliografia complementar:
Content available only in Portuguese.
