Informações Gerais
Objectivos
Pretende-se que o estudante ganhe competência na área de técnicas de concepção e análise de algoritmos eficientes. Os principais objectivos de aprendizagem são:
- Enriquecimento do conhecimento sobre modelos genéricos de tipos de problemas e técnicas algorítmicas a eles associadas.
- Experiência prática na aplicação de algoritmos genéricos a problemas concretos.
- Competência na análise da complexidade de algoritmos.
Programa
Uma visão geral:
- Análise assintótica do tempo de execução de algoritmos:
- Notação Big O (O, Ω e Θ)
- Estimativas de tempo de execução
- Análise de programas iterativos
- Análise de programas recursivos
- Ordenação
- A ordenação como peça básica de outros algoritmos
- Algoritmos de ordenação comparativos e não comparativos
- Pesquisa binária e aplicações directas e indirectas
- Técnicas de Desenho de Algoritmos
- Pesquisa exaustiva
- Dividir para conquistar
- Algoritmos greedy
- Programação dinâmica
- Algumas estruturas de dados especializadas
- Filas de prioridade
- Conjuntos disjuntos
- Árvores Binárias Equilibradas
- Algoritmos de grafos
- Representação de grafos
- Pesquisa em largura e pesquisa em profundidade
- Árvores de cobertura mínima
- Caminhos mínimos
- Redes de fluxo
)