Plano de Estudos
Desenho e Análise de Algoritmos DAAlgo
Contextos
Groupo: 1_MCD 2018/19 a 2026/27 > 2º Ciclo > Parte Escolar > Opcionais > 733 - MCD - Grupo 4
Groupo: 1_MCD 2018/19 a 2026/27 > 2º Ciclo > Parte Escolar > Opcionais > 732 - MCD - Grupo 3
ECTS
6.0 (para cálculo da média)
Objectivos
Esta unidade curricular objetiva desenvolver um conjunto de competências avançadas para complementar o conhecimento padrão de algoritmos e estruturas de dados. Após conclusão da unidade curricular, os alunos deverão ser conseguir: analisar a complexidade de algoritmos; saber decompor problemas para obter ganhos de desempenho; modelar problemas em diversos paradigmas; aplicar um conjunto de técnicas de desenho e análise para problemas no contexto de aplicações computacionais, como desenhar algoritmos de aproximação polinomiais para tarefas de complexidade exponencial ou desenvolver algoritmos aleatórios para resolução de tarefas.
Programa
Modelação de problemas com grafos. Algoritmos de pesquisa (pesquisa por retrocesso, pesquisa heurística) e de pertença (bloom filters, árvores prefixas, conjuntos disjuntos). Decomposição de Problemas (divide-and-conquer, algoritmos gananciosos, programação dinâmica). Programação com restrições. Algoritmos randomizados (Monte-Carlo, Las-Vegas, algoritmo de Metropolis). Elementos de Teoria da Complexidade. Algoritmos de Aproximação. Programação Probabilística.
Método de Avaliação
Exame final (50%) + Projeto (50%)
Carga Horária
Carga Horária de Contacto -
Trabalho Autónomo - 119.0
Carga Total -
Bibliografia
Principal
- Algorithm Design: Jon Kleinberg and Éva Tardos 2006 Algorithm Design by Jon Kleinberg and Éva Tardos. Pearson, 2006. ISBN-13: 978-0321295354
- Python Algorithms, 2ed: Magnus Lie Hetland 2010 Python Algorithms 2ed by Magnus L Hetland. Apress 2010. ISBN-13 978-1484200568
Secundária
- Introduction to Algorithms: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein 2009 Introduction to Algorithms 3ed. Thomas H. Cormen et al. MIT Press 2009. ISBN-13: 978-0262033848
- Algorithms: Jeff Erickson 2019 Algorithms by Jeff Erickson. ISBN-10 1792644833