Algoritmos Avançados › 40751

código no paco
40751
área científica
Informática
créditos
6
escolaridade
ensino teórico-prático (TP) - 3 horas/semana
idioma(s) de lecionação
a inserir brevemente
objectivos

A compreensão das características e do funcionamento de algoritmos de diferentes tipos, e o conhecimento quanto às possíveis estratégias de abordagem para determinados problemas, são componentes fundamentais da formação em Engenharia Informática.
Pretende-se fornecer formação adicional à adquirida no 1º ciclo (licenciatura) em algoritmia, tendo como ponto principal reconhecer que estrutura de dados e algoritmo padrão são mais apropriados para resolver um determinado problema.

competências

• Reconhecer as principais estratégias de desenvolvimento de algoritmos;
• Ser capaz de identificar e utilizar a melhor estrutura de dados para resolver um problema padrão;
• Reconhecer a aplicabilidade e as limitações de diferentes algoritmos para instâncias particulares de alguns problemas.

conteúdos

1. Revisão de conceitos fundamentais de algoritmia e estruturas de dados (estruturas de dados fundamentais,
algoritmos de procura e ordenação, complexidade computacional)
2. Estratégias algorítmicas (dividir para conquistar, programação dinâmica, força bruta)
3. Estruturas de dados diversas (árvores balanceadas, treaps e outras)
4. Problemas combinatórios (geração de todas as possibilidades, order statistics)
5. Problemas/algoritmos sobre grafos (todas as distâncias máximas entre pares de vértices, maximum network
flow)
6. Problemas da geometria computacional (convex hull, triangulação de Delaunay, diagrama de Voronoi)
7. Tópicos diversos (algoritmos probabilísticos, problemas NP-Completos, algoritmos aproximativos)

avaliação

A avaliação, do tipo contínua, compreende:
- pelo menos 4 exames escritos, distribuidos ao longo do semestre, que em conjunto valem 50% da nota final,
- pelo menos 2 trabalhos em grupos de 2 e pelo menos dois exames práticos individuais, que em conjunto valem
50% da nota final.

metodologia

Os conceitos e algoritmos são apresentados de modo expositivo e ilustrados com exemplos de aplicação.
Posteriormente, são desenvolvidos, implementados e testados algoritmos para problemas de diferentes tipos (com base num conjunto de guiões), e analisado o seu desempenho e aplicabilidade a instâncias com diferentes características.

bibliografia recomendada
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, e C. Stein. Introduction to Algorithms. The MIT press, terceira edição, 2009.
  • S. Skienna. The Algorithm Design Manual. Springer, segunda edição, 2008.
  • M. De Berg, M. van Kreveld, M. Overmars, e O. Schwarzkopf. Computational Geometry : Algorithms and Applications. Springer, segunda edição, 2000.
Este sítio web utiliza cookies sem recolher informação pessoal que permita a identificação dos utilizadores. Ao navegar neste sítio está a consentir a sua utilização.saber mais
Para que esta página funcione corretamente deve ativar a execução de Javascript. Se tal não for possível, algumas funcionalidades poderão estar limitadas.