Publicação em Diário da República: Despacho n.º 9184/2020 - 25/09/2020
6 ECTS; 2º Ano, 1º Semestre, 28,0 PL + 28,0 TP + 5,0 OT , Cód. 814333.
Docente(s)
- Sandra Maria Gonçalves Vilas Boas Jardim (1)(2)
(1) Docente Responsável
(2) Docente que lecciona
Pré-requisitos
Não aplicável.
Objetivos
Formação de nível intermédio em algoritmia e complexidade, familiarizando os alunos com técnicas de análise e síntese de algoritmos e estruturas de dados.
1. Conhecimento dos fundamentos da análise e síntese de algoritmos.
2. Análise da realização prática de algoritmos e estruturas de dados.
3. Perspectiva abrangente das aplicações dos algoritmos em Ciências Informáticas.
Programa
Introdução à análise e síntese de algoritmos
Fundamentos matemáticos para análise de algoritmos
Revisão de algoritmos de ordenação: Mergesort; Heapsort; Quicksort; algoritmos de ordenação não baseados em comparação
Revisão de estruturas de dados: Listas; Pilhas; Filas; Tabelas de dispersão; Árvores de procura binária; Árvores equilibradas
Análise amortizada. Exemplos de aplicação: Amontoados Binomiais
Introdução à Geometria Computacional. Algoritmos em grafos: Algoritmos elementares; Árvores abrangentes de menor custo; Caminhos mais curtos; Fluxos máximos
Introdução à Programação Linear: Algoritmo Simplex
Técnicas de síntese de algoritmos: Programação dinâmica; Algoritmos gananciosos
Algoritmos para emparelhamentos máximos
Introdução à complexidade: Classes P e NP; Problemas NP-completos; Teorema de Cook; Estudo de alguns problemas NP-completos; Algoritmos de aproximação para problemas NP-díficeis
Metodologia de avaliação
Avaliação por frequência - Dois testes escritos, tendo o primeiro um peso de 30% e o segundo um peso de 40% e dois trabalhos práticos, com um peso de 15% cada um.
Avaliação final - Exame escrito, com um peso de 70%, e um trabalho prático, com um peso de 30%.
Os alunos deverão ter, em cada um dos elementos de avaliação, uma nota mínima de 7,5.
Bibliografia
- H. Cormen, T. e E. Leiserson, C. e L. Rivest, R. e Stein, C. (2009). Introduction to Algorithms. (Vol. 1). (pp. 1-1292). USA: The MIT Press; 3rd edition
Método de Ensino
As aulas destinam-se à apresentação dos temas e de exemplos práticos. Os tópicos principais são igualmente explorados através da realização de exercícios e de trabalhos práticos baseados em computador.
Software utilizado nas aulas
Code Blocks; ferramentas de produtividade; plataforma de eLearning.
