Análise e Desenho de Algoritmos (2012/2013) - Departamento de Informática

Informação adicional: http://moodle.fct.unl.pt/course/view.php?id=3427

Descrição

Estudo de algoritmos eficientes para resolver os problemas fundamentais de grafos, introdução de três técnicas de desenho de algoritmos e apresentação dos conceitos básicos da Teoria da Complexidade.

Objectivos
Saber
Saber Fazer
Competências Complementares
Programa

Programação dinâmica.

Introdução ao estudo de grafos. Definições fundamentais. Tipos abstractos de dados grafo não orientado e grafo orientado. Implementações de grafos.

Algoritmos elementares de grafos. Percursos em profundidade e em largura. Ordenação topológica. Teste à aciclicidade.

Árvores mínimas de cobertura. Algoritmo de Kruskal. Tipo abstracto de dados partição.

Complexidade amortizada. Métodos da contabilidade e do potencial.

Algoritmo de Prim. Tipo abstracto de dados fila com prioridade adaptável. Filas binomiais e de Fibonacci.

Caminhos mais curtos. Algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall.

Fluxos máximos. Método de Ford-Fulkerson. Algoritmo de Edmonds-Karp. Emparelhamentos máximos em grafos bipartidos. Cortes mínimos.

Introdução à Teoria da Complexidade. As classes P, FP, NP, PSPACE e EXPTIME. Os afixos co, difícil e completo. Redução de problemas. Alguns problemas em aberto.

Bibliografia Principal

Referências Principais

Referências Complementares

Requisitos Prévios

Os alunos deverão ter realizado as seguintes unidades curriculares:

Esforço do Aluno
  Horas por crédito 28
  Horas p/ semana Semanas Horas
Aulas práticas e laboratoriais 2 13 26.0
Aulas teóricas 3 14 42.0
Avaliação   5.0
Estudo   42.0
Orientação tutorial   3.0
Outras   2.0
Projectos e trabalhos   48.0
Total de Horas 168
ECTS 6.0