Disciplina Curricular
Desenho e Análise de Algoritmos DAAlgo
Mestrado Bolonha em Informática - 3_MI 2020/21
Contextos
Grupo: 3_MI 2020/21 > 2º Ciclo > Parte Escolar > Optativas > 892 - Mestrado em Informática - Geral > 2º semestre
Período:
Grupo: 3_MI 2020/21 > 2º Ciclo > Parte Escolar > Optativas > 787 - Mestrado em Informática - CTP
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
Exercícios de programação com um valor de quatro créditos. Dois projetos de investigação individuais, com um valor de oito créditos cada, compreendendo a análise de um problema, e o design e implementação de uma solução. Qualquer um dos projetos poderá incluir uma apresentação. Esta unidade curricular não tem exame.