Português English
Contato

Lista de Disciplinas | CMP588

Tópicos Especiais em Computação LXXXVIII: Algoritmos avançados

Carga horária / créditos: 60 / 4
Pré-requisitos:
Semestre oferecido: Primeiro Semestre

Responsável: Prof. Dr. Marcus Ritt

SÚMULA
Algoritmos, estruturas de dados e técnicas algorítmicas avançadas: algoritmos randomizados, algoritmos de aproximação, algoritmos parametrizados.

OBJETIVOS
A disciplina objetiva combinar a teoria de algoritmos com a prática de implementar e aplicar eles. Portanto, o conteúdo e apresentado em pares de aulas teóricas e práticas. Nas aulas teóricas o funcionamento dos algoritmos é explicado, a corretude é demonstrada e a complexidade é analisada. Nas aulas práticas os algoritmos são implementados, testados e avaliados. Especialmente, o objetivo da disciplina é que os alunos conhecem algoritmos avançados importantes e entendem o funcionamento deles; conhecem estruturas de dados avançados importantes e entendem o funcionamento delas; conhecem técnicas algorítmicas avançadas importantes e sabem aplicá-las; sabem implementar as estruturas de dados e algoritmos apresentados e são capazes adaptar e aplicar elas a novos problemas.

PROGRAMA

  1. Algoritmos avançados polinomiais
    a) Emparelhamento em grafos bi-partidos e grafos gerais
    b) Fluxo em redes
    2. Estruturas de dados avançados
    a) Fibonacci heaps e heaps binomiais
    b) Hashing e filtros de Bloom
    c) Filas de prioridade
    3. Técnicas algorítmicas avançadas
    a) Algoritmos randomizados
    b) Algoritmos de aproximação
    c) Algoritmos parametrizados.

CRITÉRIOS DE AVALIAÇÃO
O conteúdo teórico é avaliado através de uma prova escrita sobre toda matéria. A parte prática é avaliada através de trabalhos semanais realizados ao longo da disciplina. A nota final m resulta das notas da prova p e da nota média de trabalhos t seguindo m = (4p + 6t) / 10.
O conceito final corresponde à nota final e a frequência como segue:
A => 9 ? m ? 10 ? f ? 75%
B => 7.5 ? m < 9 ? f ? 75%
C => 6 ? m < 7.5 ? f ? 75%
D => m < 6 ? f ? 75%
FF => f < 75%
Para ser aprovado é necessário obter um conceito final de A, B ou C. Um aluno com conceito final D pode realizar uma única prova de recuperação.

BIBLIOGRAFIA
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
[2] Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001.
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation – Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, 1999.
[4] Vijay V. Vazirani. Approximation algorithms. Springer, 2001.
[5] Jon Kleinberg and Eva Tardos. Algorithm design. Addison-Wesley, 2005.
[6] Rolf Niedermeier. Invitation to fixed-parameter algorithms. Habilitationsschrift, Universität Tübingen, WSI für Informatik, Germany, September 2002.
[7] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
[8] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
[9] Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, Dover edition, 1982.