Disciplina Curricular
Análise e Síntese de Algoritmos ASA
Licenciatura Bolonha em Engenharia Informática e de Computadores - Taguspark - LEIC-T 2006
Contextos
Grupo: LEIC-T 2006 > 1º Ciclo > Ciências da Engenharia Informática
Período:
Peso
6.0 (para cálculo da média)
Objectivos
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. Conhecimento dos fundamentos da análise e síntese de algoritmos. Análise da realização prática de algoritmos e estruturas de dados. Perspectiva abrangente das aplicações dos algoritmos em Engenharia Informática.
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
2 testes de igual valor (70%) com nota mínima de 7,5 valores na média dos 2 testes; 3 mini-projectos de igual valor (30%);