Programa

Análise e Síntese de Algoritmos

Licenciatura (5 anos) em Engenharia Informática e de Computadores - Alameda

Programa

Introdução à análise e síntese de algoritmos. Fundamentos matemáticos para análise de algoritmos. Algoritmos de ordenação: Mergesort; Heapsort; Quicksort; algoritmos de ordenação não baseados em comparação. Introdução às estruturas de dados: Listas; Pilhas; Filas; Tabelas de dispersão; Árvores de procura binária; Árvores equilibradas. Técnicas de síntese de algoritmos: Programação dinâmica; Algoritmos ávaros; Análise amortizada. Exemplos de aplicação: Amontoados Binomiais; Compressão de ficheiros; Estruturas de dados para conjuntos disjuntos. Introdução à Geometria Computacional. Algoritmos em grafos: Algoritmos elementares; Árvores abrangentes de menor custo; Caminhos mais curtos; Fluxos máximos; Emparelhamentos máximos. Introdução à complexidade: Classes P e NP; Problemas NP-completos; Estudo de alguns problemas NP-completos; Algoritmos de aproximação para problemas NP-díficeis.

Análise e Síntese de Algoritmos

Licenciatura (5 anos) em Ciências Informáticas

Programa

Introdução à análise e síntese de algoritmos. Fundamentos matemáticos para análise de algoritmos. Algoritmos de ordenação: Mergesort; Heapsort; Quicksort; algoritmos de ordenação não baseados em comparação. Introdução às estruturas de dados: Listas; Pilhas; Filas; Tabelas de dispersão; Árvores de procura binária; Árvores equilibradas. Técnicas de síntese de algoritmos: Programação dinâmica; Algoritmos ávaros; Análise amortizada. Exemplos de aplicação: Amontoados Binomiais; Compressão de ficheiros; Estruturas de dados para conjuntos disjuntos. Introdução à Geometria Computacional. Algoritmos em grafos: Algoritmos elementares; Árvores abrangentes de menor custo; Caminhos mais curtos; Fluxos máximos; Emparelhamentos máximos. Introdução à complexidade: Classes P e NP; Problemas NP-completos; Estudo de alguns problemas NP-completos; Algoritmos de aproximação para problemas NP-díficeis.