Disciplina Curricular

Desenho e Análise de Algoritmos DAAlgo

Curso de Especialização em Informática - 11_Plano actual

Contextos

Grupo: 11_Plano actual > Especialização > Optativas > 829_Curso de Especialização em Informática - CTP

Período:

Grupo: 11_Plano actual > Especialização > Optativas > 833_Curso de Especialização em Informática

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.

Disciplinas Execução

2019/2020 - 2 Semestre

2018/2019 - 2 Semestre

2017/2018 - 2 Semestre

2016/2017 - 2 Semestre