Jupiterweb

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: 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