Disciplina Curricular

Análise e Síntese de Algoritmos ASA

Licenciatura Bolonha em Engenharia Informática e de Computadores - Alameda - LEIC-A 2006

Contextos

Grupo: LEIC-A 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;