Informa??es da Disciplina

 Preparar para impressão 
Júpiter - Sistema de Graduação

Instituto de Ciências Matemáticas e de Computação
 
Ciências de Computação
 
Disciplina: SCC0216 - Modelagem Computacional em Grafos
Computational Modelling in Graphs

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

Objetivos
Ensinar ao aluno a importância de grafos em computação, mostrando seus conceitos fundamentais, principais estruturas de dados e aplicações resolvidas por meio de grafos.
 
Teach students the importance of graphs in computing, showing their fundamental concepts and main data structures, as well as major applications resolved through graphs.
 
 
Programa Resumido
Conceitos fundamentais em grafos, estrutura de dados e aplicações.
 
Fundamental concepts in graphs, data structures for graphs, applications.
 
 
Programa
Grafos - conceitos fundamentais, grafos dirigidos e não dirigidos, grafos ponderados, caminhos Eulerianos e Hamiltonianos, ciclos, operações básicas sobre grafos, busca em largura e em profundidade, isomorfismo. Representação de grafos via matriz de adjacência e listas de adjacências, operações e análise de algoritmos. Caminhos mínimos, 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 e aplicações.
 
Graphs - basic concepts, directed and undirected graphs, weighted graphs, Eulerian and Hamiltonian paths, cycles, basic operations on graphs, breadth and depth search, isomorphism. Representation of graphs via adjacency matrix and adjacency lists, operations, and algorithm analysis. Shortest paths, cycle detection, connected and strongly connected components, bridges and articulation vertices, topological sort. Minimum spanning trees, shortest paths, network flow. Basic notions of complex networks and applications.
 
 
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
Média ponderada das notas das provas e dos trabalhos em grupo.
Norma de Recuperação
Critério de Aprovação: NP+(Mrec/2,5), se Mrec >=7,5; ou Max {NP,Mrec}, se Mrec < 5,0;
ou 5,0, se 5,0 <= Mrec < 7,5.( NP=1ª avaliação, Mrec=prova).
 
Bibliografia
     
Texto:
CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos: Teoria e Prática. Editora Campus. 2002.
- ZIVIANI, N. - Projeto de algoritmos: com implementações em Pascal e C. 2a. Edição. Pioneira Thomson Learning, 2005.

Bibliografia Complementar:
- HOROWITZ,E.; SAHNI,S. Fundamentals of Data Structures in Pascal, Computer Science Press, 1990.
- TENEMBAUM,A.M. et alli Data Structures Using C, Prentice-Hall, 1990.
- SZWARCFITER,J.L. Grafos e Algoritmos Computacionais. Editora Campus, 1983.
- AHO,A.V.; HOPCROFT,J.E.; ULLMAN,J.D. Data Structure and Algorithms. Readings, Addison Wesley, 1982.
 

Clique para consultar os requisitos para SCC0216

Clique para consultar o oferecimento para SCC0216

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