Disciplina Curricular
Desenho e Análise de Algoritmos DAAlgo
Mestrado Bolonha em Engenharia Geoespacial - 2_MEGE 2023/24
Contextos
Grupo: 2_MEGE 2023/24 > 2º Ciclo > Parte Escolar > 636_MEGE - Opcionais 2º Ano (QA)
Período:
Grupo: 2_MEGE 2023/24 > 2º Ciclo > Parte Escolar > 635_MEGE - Opcionais 1º Ano/2º Sem (QA)
Período:
Peso
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étodos de ensino e avaliação
Aulas teóricas de exposição da matéria e aulas teórico-práticas de resolução de exercícios. Avaliação contínua baseada no trabalho realizado nas aulas teórico-práticas, eventualmente completado fora da sala de aula. Projeto de investigação, envolvendo a análise de um problema, e o desenho e implementação de uma solução. Estudo aprofundado e apresentação oral de um tópico relacionado com as matérias lecionadas.