Desenho e Análise de Algoritmos

Mestrado em Produção de Conteúdos Digitais
6 ECTS; 1º Ano, 1º Semestre, 30,0 T + 30,0 TP + 5,0 OT + 5,0 O

Docente(s)

Pré-requisitos
Não aplicável.

Objetivos
1-Dominar as técnicas gerais de concepção e análise de algoritmos.
2-Conhecer os modelos genéricos de problemas e as técnicas algorítmicas a eles associadas.
3-Aprofundar os conhecimentos sobre estruturas de dados e algoritmos.
4-Conceber e implementar algoritmos eficientes.

Programa
1-Análise de complexidade algorítmica:
- Notação assimptótica
- Classes de complexidade
- Espaço vs Tempo

2- Fundamentos de algoritmos:
- Algoritmos de execução sequencial
- Algoritmos recursivos
- Algoritmos de execução paralela e concorrente
- Estruturas de dados

3-Técnicas de desenho de algoritmos:
- Busca exaustiva
- Backtracking
- Pesquisa com adversários
- Decrementar para conquistar
- Dividir para conquistar
- Transformar para conquistar

4-Ordenação e ordens estatísticas:
- Métodos de ordenação simples
- Métodos de ordenação baseados em trocas
- Ordenação em tempo linear
- Ordens estatísticas

5-Algoritmos e Estruturas de dados avançadas.

Metodologia de avaliação
A avaliação é feita através de trabalhos de trabalhos de projecto, um trabalho de investigação e um exame final.

Bibliografia
- Rivest, R. e Leiserson, C. e Cormen, T. e Stein, C. (2009). Introduction to Algorithms. (Vol. 1). (pp. 1-1312). Cambridge: MIT Press
- Weiss, M. (2010). Data Structures and Problem Solving Using Java. (Vol. 1). (pp. 1-1024). Pearson: Addison-Wesley

Método de interação
Aulas expositivas para apresentação e demonstração dos conteúdos programáticos. Aulas práticas para implementação e validação dos conceitos teóricos através da resolução de pequenos exercícios.

Software utilizado nas aulas