Bacharelado em Computação 
DC - UFC

CK111 - Algoritmos em Grafos

Cláudia Linhares Sales

Avisos importantes:

• Veja as novas datas das provas estão marcadas !!!

• A terceira lista está na página.

• A 3a AP é dividida em 2 partes: a segunda chamada da 1a AP e da 2a AP. Os alunos que desejarem podem fazer toda ou parte da 3a AP.

Informações nesta página:

Horário , Local , Atendimento , Ementa , Pré-requisito , Avaliação (provas e listas de exercícios), Livro-texto e Bibliografia adicional .

Horário:

Terças e Quintas, 10:00h - 12:00h

Local:

Bloco 915, Sala 1035.

Atendimento:

Em minha sala, em qualquer horário, desde que com reserva antecipada. Uma reserva pode ser feita via correio eletrônico ou na sala de aula.

Ementa:

Um algoritmo é um processo sistemático para a resolução de um problema em um computador. O objetivo desse processo é a obtenção do resultado de um problema a partir da manipulação de certas informações inicialmente conhecidas e de novas informações obtidas ao longo da execução do algoritmo. O conteúdo deste curso é formado por diversas técnicas de projeto de algoritmos para resolver problemas em grafos. A ementa do curso é a seguinte, onde os tópicos sinalizados com (*) indicam que apenas uma revisão será feita:

• Introdução

  • Introdução

  • Conceitos de problema e algoritmo (*)

  • Recursividade  (*)

  • Princípio da indução matemática (*)

  • As notações O, Ômega e Teta (*)

  • Estimativa de tempo de execução de algoritmos (complexidade) (*)

  • Algoritmos ótimos (*)

• Elementos de teoria dos grafos

  • Definições (*)

  • Propriedades  (*)

  • Grafos orientados (*)

• Estruturas de dados elementares

  • Listas, pilhas e filas (*)

  • Heap (*)

  • Árvores (*)

  • Grafos (*)

• Percursos em grafos

  • Introdução

  • Percurso em largura

  • Componentes conexas

  • Percurso em profundidade

  • Ordenação topológica

• Caminhos mínimos

  • Definições

  • Algoritmo de Johnson

  • Algoritmo de Dijkstra

  • Pesos unitários

  • Algoritmo de Floyd

• Árvore geradora mínima

  • Definição

  • Algoritmo de Dijkstra

  • Algoritmo de Prim

• Fluxo máximo em redes

  • Introdução

  • Teorema do corte mínimo

  • Algoritmo de Ford-Fulkerson

  • Algoritmo de pré-fluxo

  • Emparelhamento em grafos bipartidos

Pré-requisito:

Estruturas de Dados.

Avaliação:

Listas:

• Lista 0 (arquivo pdf)

• Lista 1 (arquivo pdf)

• Lista 2 (arquivo pdf)

Datas das provas:

• 30 de Maio  (1ª AP)

• 18 de  Julho (2ª AP)

• 25 de Julho (3ª AP)

• 29 de Julho (FINAL)     

 A Média será calculada da forma que segue.

Sejam N1 e N2 as duas maiores notas de {AP1, AP2, AP3}.

Média = (N1 + N2)/2

Se Média >= 7, então o aluno não fará a PF. Caso contrário,  NF= (Média + PF)/2.

O aluno será aprovado se Média >= 7 ou NF >= 5. Caso contrário, o aluno será reprovado.

Livro-texto:

• T. H. Cormen, C. E. Leiserson e R. L. Rivest, Introduction to Algorithms , MIT Press e McGraw-Hill, 1990.

Bibliografia adicional:

• A. V. Aho e J. D. Ullman, Foundations of Computer Science , W. H. Freeman Company, 1992.

• Jayme L. Szwarcfiter, Algoritmos em Grafos, Editora Campus, 1987.

• Christos Papadimitriou e Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity , Dover, 1998.

Cláudia Linhares Sales
DC/UFC
Campos do Pici, Bloco 910
60455-760 Fortaleza, CE
Brazil

linhares@lia.ufc.br
http://www.lia.ufc.br/~linhares
+55 85 4008-9847 Ramal 210 (voice)
+55 85 4008-9841 (voice/fax)

Updated on May  04, 2006