Disciplina Curricular
Desenho e Análise de Algoritmos DAAlgo
Mestrado Bolonha em Engenharia Geoespacial - 1_MEGE 2017/18
Contextos
Grupo: 1_MEGE 2017/18 > 2º Ciclo > Parte Escolar > Opcionais > 760_1º Ano do Mestrado em Engenharia Geoespacial > 2º semestre
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 assintótica de algoritmos; fazer provas de correção para algoritmos; demonstrar conhecer problemas reais e os seus algoritmos; aplicar um conjunto de técnicas de desenho e análise para problemas no contexto de aplicações computacionais.
Programa
Análise de algoritmos. Passos para desenvolver um algoritmo utilizável. Conjuntos disjuntos (union-find). Grafos. Grafos dirigidos. Pesquisa (em profundidade e em largura). Componentes ligadas. Ordenação topológica. Dividir para conquistar. Análise de algoritmos recursivos. Algoritmos gananciosos. Programação dinâmica. Redes de fluxo. Reduções em tempo polinomial. Certificação eficiente e a definição da classe NP. Problemas NP-completos.
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. Projecto 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. Exame final.