Informações da Disciplina

 Preparar para impressão 

Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação


Instituto de Ciências Matemáticas e de Computação
 
Ciências de Computação
 
Disciplina: SCC0212 - Algoritmos em Grafos
Graph Algorithms

Créditos Aula: 2
Créditos Trabalho: 2
Carga Horária Total: 90 h
Tipo: Semestral
Ativação: 01/01/2012 Desativação:

Objetivos
Estudo e resolução de problemas que utilizam grafos. Desenvolvimento e implementação de algoritmos clássicos sobre grafos.
 
Problem solving using graphs. Development and implementation of classic algorithms on graphs.
 
 
Programa Resumido
Conceitos fundamentais: representações; operações básicas; travessias, buscas, ordenação topológica, caminhos mínimos, árvores geradoras mínimas, fluxo em redes. Aplicações. Análise dos algoritmos.
 
Fundamental concepts: representation, basic operations; transversals, search, topological sort, shortest paths, minimum spanning trees, networks flows. Applications. Analysis of algorithms.
 
 
Programa
Grafos: conceitos fundamentais; representação via matriz de adjacência, representação via listas de adjacências, outras representações; operações básicas sobre grafos, busca em largura e em profundidade. Aplicações de busca em profundidade: detecção de ciclos, componentes conexos e fortemente conexos, pontes e vértices de articulação, ordenação topológica. Árvores geradoras mínimas, caminhos mínimos, fluxo em rede, noções de redes complexas, aplicações em Computação e outras áreas, análise dos algoritmos.
 
Graphs: fundamental concepts; adjacency matrix representation, adjacency lists representation, other representations; basic operations on graphs, breadth-first search and depth-first search. Applications of in-depth search: cycle detection, connected components and strongly connected components, bridges and articulation vertices, topological sort. Minimum spanning trees, shortest paths, network flow. Basics of complex networks. Applications in computing and other areas. Analysis of algorithms.
 
 
Avaliação
     
Método
Exposição seguida de exercícios e trabalhos práticos, dentro e fora de classe. Prática de uso do computador.
Critério
Desenvolvimento de exercícios e trabalhos práticos dentro e fora de classe. A nota final será calculada pela média ponderada das notas obtidas pelo aluno nos trabalhos e provas.
Norma de Recuperação
-Critério de Aprovação: NP+(Mrec/2,5), se Mrec ou =7,5; ou Max {NP,Mrec}, se Mrec ou = 5,0; ou 5,0, se 5,0 ou = Mrec 7,5.( NP=1ª avaliação, Mrec=prova)
 
Bibliografia
     
· Livro Texto:- CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Editora Campus.2002.- SEDGEWICK. R. Algorithms in C, Part 5 – Graph Algorithms. 3rd edition. Addison-Wesley, 2002.- ZIVIANI, N. - Projeto de algoritmos: com implementações em Pascal e C. 2a. Edição. Pioneira Thomson Learning, 2005.· Bibliografia Complementar:- AHO,A.V.; HOPCROFT,J.E.; ULLMAN,J.D. Data Structure and Algorithms. Readings, Addison Wesley, 1982.- HOROWITZ,E.; SAHNI,S. Fundamentals of Data Structures in Pascal, Computer Science Press, 1990.- SCHRIBER,T.J. An Introduction to Simulation using GPSS/H, John Wiley & Sons, 1991.- SZWARCFITER,J.L. Grafos e Algoritmos Computacionais. Editora Campus, 1983.- TENEMBAUM,A.M. et alli Data Structures Using C, Prentice-Hall, 1990.


 

Clique para consultar os requisitos para SCC0212

Clique para consultar o oferecimento para SCC0212

Créditos | Fale conosco
© 1999 - 2022 - Superintendência de Tecnologia da Informação/USP