00_apresentacao_aplicacoes

Prévia do material em texto

Grafos e Algoritmos Computacionais 
 
 
Apresentação da disciplina e aplicações 
UMA VISÃO GERAL 
O professor 
O que são Grafos? 
Exemplos 
Objetivos 
O que será estudado? 
Critérios de avaliação 
Bibliografia 
O professor 
• Leonardo Conegundes Martinez 
• Graduação e Mestrado em C. Comp. pela UFMG 
• Professor do DCC-UFMG, PUC Minas 
• Áreas de interesse 
– Projeto e Análise de Algoritmos, Teoria dos Grafos, 
Aprendizado de Máquina e Finanças Computacionais 
• Empresas 
– Sistema de Informação do Investidor (SI2) 
– Soluções de Software Inteligentes (S10I) 
• Outros interesses: Maratona de Programação 
– Ex-competidor e atualmente técnico dos times da UFMG 
 
 
O que são Grafos? 
• Diagramas para representar elementos e a relação 
entre ele 
• Duas entidades principais: 
– Vértices: um objeto simples que pode ter nomes e outros 
atributos 
– Arestas: representam uma relação entre entre dois 
vértices 
 
Exemplo 1: Malha aérea TAM 
Exemplo 2: Copa do Mundo 2002 
Exemplo 3: Google Knowledge Graph 
Exemplo 4: Mapa Geográfico 
Universidade de Itaúna 
Exemplo 5: Mapa Social Facebook 
Exemplo 6: Matriz curricular – PUC/SI 
Exemplo 7: Metrô Barcelona 
Exemplo 8: Estados brasileiros 
Exemplo 9: Computação em Nuvens 
Exemplo 10: Jogos 
Objetivos 
• Gerais 
– Apresentar conceitos e propriedades de grafos 
– Introduzir grafos como uma poderosa ferramenta de modelagem 
– Levar o aluno a utilizar grafos na solução de problemas 
computacionais 
– Apresentar problemas clássicos da Teoria dos Grafos 
– Apresentar os principais algoritmos em grafos 
 
• O aluno deverá desenvolver habilidades relacionadas a: 
– modelar problemas em grafos 
– análise crítica, elaboração e validação de hipóteses 
– desenvolvimento de algoritmos em grafos 
– uso de grafos como ferramenta para resolução de problemas 
práticos 
– leitura de arquivos de entrada, armazenamento em estrutura 
de grafos, definição de formato de saída 
O que será estudado? 
• Introdução à Teoria de Grafos. 
• Noções, conceitos básicos e terminologia. 
• Grafos orientados e não-orientados. 
• Grafos simples. 
• Subgrafos. 
• Grafos Bipartites. 
• Isomorfismo. 
• Grafos complementares. 
• Caminhos e circuitos. 
• Problema de caminhos. 
O que será estudado? 
• Problema do Caixeiro Viajante e do Carteiro 
Chinês. 
• Movimentos do Cavalo em um Tabuleiro de 
Xadrez. 
• Árvores e Árvores Geradoras. 
• Árvore Geradora Mínima. 
• Conectividade de Vértices e de Arestas. 
• Grafos Planares e Dualidade. 
• Coloração de Faces, Arestas e Coloração de 
Vértices. 
O que será estudado? 
• Grafos Eulerianos e Unicursais. 
• Grafos Haniltonianos. 
• Número Cromático. 
• Independência e Dominância. 
• Casamentos. 
• Cobertura de Vértices e de Arestas. 
• Dígrafos. 
• Introdução à Teoria da Complexidade. 
• Algoritmos em Grafos. 
Critérios de avaliação 
• A decidir 
 
Bibliografia (Principal) 
• CORMEN, T. H., LEISERSON, C. E., RIVEST, R. L., 
STEIN, C.; Algoritmos: Teoria e Prática; Rio de 
Janeiro: Campus; 2002. 
• NETTO, B. Grafos: Teoria, Modelos, 
Algoritmos. São Paulo: Edgard Blucher 
Ltda.,2a.ed., 2001 
• ZIVIANI, N.; Projeto de Algoritmos com 
Implementações em Pascal e C; Pioneira 
Thompson Learning; São Paulo, Brasil; 2004.