Programa

Análise e Síntese de Algoritmos

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

Mestrado Bolonha em Engenharia e Gestão da Energia

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;