Desenho e Análise de Algoritmos
Ano Letivo: 2015/16
Departamento: Informática
Carga horária: T: 2:00 h; TP: 1:30 h; OT: 2:00 h;
Área Científica: Informática;
Objetivos da Unidade Curricular
Adquirir um conjunto avançado de tópicos em algoritmia para complementar o conhecimento padrão de algoritmos e estruturas de dados de uma pós-graduação em engenharia informática.
Pré-requisitos
- Introdução à Programação (26722)
- Algoritmos e Estruturas de Dados (26723)
Conteúdos
Complexidade. Análise de algoritmos recursivos. Análise Amortizada. Ordenação e Order Statistics. Programação Dinâmica. Algoritmos Gananciosos. Grafos. Pesquisa de Soluções - algoritmos exactos e algoritmos aproximados. Conjuntos Disjuntos (Union-Find). Strings. Árvores. Skip-Lists. Algoritmos Aleatórios.
Descrição detalhada dos conteúdos programáticos
Componente Teórica
Complexidade. Análise de algoritmos recursivos. Análise Amortizada. Ordenação e Order Statistics. Programação Dinâmica. Algoritmos Gananciosos. Grafos. Pesquisa de Soluções - algoritmos exactos e algoritmos aproximados. Conjuntos Disjuntos (Union-Find). Strings. Árvores. Skip-Lists. Algoritmos Aleatórios.
Componente Teórica-Prática
Complexidade. Análise de algoritmos recursivos. Análise Amortizada. Ordenação e Order Statistics. Programação Dinâmica. Algoritmos Gananciosos. Grafos. Pesquisa de Soluções - algoritmos exactos e algoritmos aproximados. Conjuntos Disjuntos (Union-Find). Strings. Árvores. Skip-Lists. Algoritmos Aleatórios.
Bibliografia
Recomendada
Introduction to Algorithms, Third Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. MIT Press 2009. ISBN-10: 0-262-03384-4. ISBN-13: 978-0-262-03384-8.
Outros elementos de estudo
Slides das aulas. Artigos científicos.
Métodos de Ensino
Aulas teóricas de exposição da matéria e aulas teórico-práticas de resolução de exercícios.
Métodos de Avaliação
Avaliação contínua baseada no trabalho realizado nas aulas teórico-práticas, eventualmente completado fora da sala de aula. Projecto de investigação, envolvendo a análise de um problema, e o desenho e implementação de uma solução. Exame final.
Língua de ensino
Português