|
Objetivos
Programa
Apostila
Bibliografia
Resultados
Orientação
bookobj
Objetivos
- Proporcionar aos alunos o ferramental
teórico e as experiências práticas necessárias
ao projeto e análise de algoritmos em grafos.
Voltar
bookprog Programa da
Disciplina
| Aula |
Descrição |
| 01 |
Apresentação
dos objetivos e programa da disciplina, ligação com outras
disciplinas, comentário sobre a
bibliografia utilizada, metodologia de ensino, forma de
avaliação
etc. O histórico modelo de Euler.
|
| 02 |
Conceitos fundamentais em Grafos. Representação Matemática. Nó.
Aresta.
Grafo Rotulado. Grafo Ponderado. Hipergrafo. Grafo
Direcionado.
Multigrafo. Grafo Bipartido. Grafo Completo. Grafo Regular.
Grafo Planar. Subgrafo. Grafo Parcial. Vizinhanças. Fechos Transitivos.
Cadeias. Caminhos. |
| 03 |
Modelagem de problemas via Grafos. Exercícios. |
| 04 |
Representação dos Grafos. Matriz de Adjacência. Matriz de
Incidência.
Listas Encadeadas. Representação Vetorial. |
| 05 |
Árvore, Arborescências. Algoritmos para a Árvore Geradora Mínima. Algoritmos
de Kruskal, Prim. |
| 06 |
Algoritmos para a Árvore Geradora Mínima. Prim Colorido e Borüvka. |
| 07 |
Caminho mais curto em Grafos. Algoritmo de
Dijkstra. Algoritmo de Ford-Moore-Bellman |
| 08 |
Caminho mais curto em Grafos. Algoritmo de
Ford-Fulkerson. Algoritmo
de Floyd-Warshall. Algoritmo de Goldberg-Radzik. |
| 09 |
O Problema de Matching em Grafos. Algoritmo de Edmonds |
| 10 |
Primeiro Exame. |
| 11 |
O Problema do Matching Estável. O Problema do Casamento. O Problema
do Companheiro. O Problema do Matching com Gargalo |
| 12 |
O Problema das Componentes Conexas. Algoritmo de
Roy. O Problema do
Labirinto. Algoritmo de Trémaux. |
| 13 |
O Problema do Circuito Hamiltoniano. Jogo de Hamilton. Heurísticas
de Solução.
Heurística de Bellmore e Nemhauser. Heurísticas de
Inserção |
| 14 |
O Problema do Circuito Hamiltoniano. Heurísticas de Solução.
Heurística
de Substituições ou k-Opt |
| 15 |
O Problema dos Circuitos Eulerianos. Algoritmo de Gondran e Minoux. Algoritmo
de Fleury |
| 16 |
Árvore de Steiner. Algoritmo de Takahashi e
Matsuyama. |
| 17 |
O Problema do Fluxo Máximo em Redes Capacitadas. Algoritmo de Ford-Fulkerson |
| 18 |
O Problema do Fluxo Máximo em Redes Capacitadas. Algoritmo de Algoritmo
de Malhotra, Pramodh-Kamar e Maheshwari |
| 19 |
Segundo Exame |
| 20 |
O Problema do Conjunto Independente de Vértices. Algoritmo de Demoucron
e Herz. Partição Cromática. Número Cromático. |
| 21 |
O Problema da Coloração de Vértices.Algoritmo de Coloração
Sequencial.
Algoritmo de Welsh Powell |
| 22 |
O Problema da Coloração de Vértices. Árvore de Zykov. |
| 23 |
O Problema de Coloração de Arestas. Coloração Completa.
T-Coloração |
| 24 |
Branch-and-Bound como técnica exata de
busca |
| 25 |
Exemplos de algoritmos
aproximativos modernos: Algoritmos Genéticos. Exemplo de AG para o
Problema do Caixeiro Viajante |
| 26 |
Fatores de desempenho dos AG. Técnicas
de melhoria de desempenho - Memética e Transgenética |
| 27 |
Algoritmo de Busca Tabu. Fatores de
desempenho dos algoritmos
BT. Exemplo de algoritmo de Busca Tabu para o jogo das
8 rainhas |
| 28 |
Técnicas Multistart. Fatores
de desempenho dos algoritmos Multistart (GRASP etc), Exemplo do GRASP para a
Coloração de Vértices. |
| 29 |
Simulated Annealing (SA). Fatores de desempenho do SA. |
| 30 |
Terceiro Exame |
Voltar
bookori Orientação As avaliações serão realizadas
através de quatro exames escritos, sendo que, conforme o estatuto
da universidade, os alunos que obtiverem média ponderada igual ou
maior que 7,0 nos três primeiros exames estarão dispensados
da quarta prova. Não existe a previsão de avaliação
utilizando trabalhos elaborados em domicílio ou com consulta,
seja individual ou em grupo.
Voltar
bookbib
Bibliografia
Fortemente recomendada:
[01] Coermen, T. H., Leiserson, C. C., e R. L.
Rivert, (1991), Introduction to Algorithms, McGraw- Hill Books Company,
New York.
[02] Goldbarg, M. C. e H. L. L. Pacca, (2000),
Otimização Combinatória e Programação
Linear: Modelos e Algoritmos, Edt Campus
[03] Goldbarg, M. C. (1999), Tópicos em
Complexidade de Algoritmos, Notas de aula.
[04] Hochbaum, D. S. (1997), Approximation Algoritms
for NP-Hard Problems, PWS Publishing Company
[05] Aarts, E., e J. K. Lenstra, (1997), Local
Search in Combinatorial Optimization, John Wiley & Sons, Chichester.
[06] Campello, R. E., e N. Maculan, (1994), Algoritmos
e Heurísticas: Desenvolvimento e Avaliação de Performance.
Editora da Universidade Federal Fluminense, Niterói, RJ.
[07] Brassard, G., e P. Bratley, (1988), Algorithmics:
Theory & Pratice, Prentice-Hall, Inc, Englewood Cliffs.
[08] Rayward-Smith, V. J., Osman, I. H., Reeves,
C. R., e G. D. Smith, (1996), Modern Heuristic Search Methods, UNICON,
John Wiley and Sons, Chichester.
De apoio:
[01] Goldbarg, M.C., e E. F. Gouvêa, 2000, Transgenética Computacional, Relatório
técnico.
[02] Szwarcfiter, J. L. (1983), Grafos e Algoritmos
Computacionais, Editora Campus.
[03] Terada R. (1982), Desenvolvimento de Algoritmos
e Complexidade de Computação, Terceira Escola de Computação,
Rio de Janeiro, 1982.
Voltar
|