Tópicos Especiais em Programação
Matemática
Modelagem Computacional de Problemas
de Logística, Transporte e Tráfego
Segundo Semestre de 2009
Prof. Fábio Protti - fabio@ic.uff.br
Prof. Carlos Martinhon - mart@dcc.ic.uff.br
Horário: 6as, 14:00 - 18:00
Programa do Curso
28/08 – Estruturas de dados básicas: vetores, matrizes, listas, pilhas, filas. Recursividade. Árvores e percursos em árvores.
04/09 – Modelagem por
grafos. Conceitos básicos em teoria de grafos. Percurso em
profundidade em grafos.
11/09 – Percurso em
profundidade em digrafos. Aplicações:
partição das arestas, componentes fortemente conexas.
18/09 – Outras aplicações de busca em profundidade: grafos bipartidos, labirintos. Backtracking.
25/09 – Outras aplicações de busca em profundidade: ordenação topológica, escalonamento de atividades.
02/10 – Percurso em largura. Caminhos mínimos. Algoritmo de Dijkstra. Aplicações.
09/10 – Caminhos mínimos entre todos os pares de nós. Algoritmo de Bellman-Ford. Aplicações.
16/10 – Sem aula (Dia do Professor)
23/10 – Algoritmo guloso. Árvores geradoras mínimas. Algoritmo de Kruskal. Algoritmo de Prim.
30/10 – Programação dinâmica.
06/11 – Fluxos em redes. Aplicação: emparelhamentos máximos em grafos bipartidos.
13/11 – Trilhas Eulerianas. Problema do carteiro chinês. Caminhos e ciclos Hamiltonianos.
20/11 – Sem aula (Zumbi)
27/11 – Problema do caixeiro viajante e variações.
04/12 – Apresentação de Trabalhos de Programação
11/12 – Apresentação de Trabalhos de Programação
18/12 – Término do
curso.
Critério de
Avaliação
Baseado na Apresentação de Trabalhos de Programação do site da Universidade de Valladolid, que poderão ser feitos em equipes.
Bibliografia
Steven S. Skiena e Miguel A. Revilla. Programming Challenges - The Programming Contest Training Manual. Editora Springer.
Cormen, Leiserson, Rivest e Stein. Algoritmos (Tradução da Segunda Edição Americana). Editora Campus.
Udi Manber. Introduction to Algorithms: A Creative Approach. Editora Addison-Wesley, 1989.
Links importantes