Estruturas de Dados - Grafos Ordenação Topológica (Dibio)

Prévia do material em texto

dibio@unb.br
Assuntos 
● Outras Aplicações de Grafos
– Escalonamento
– Ordenação Topológica
– Caminho Crítico (PERT “Program Evaluation and 
Review Technique”/CPM “Critical Path Method”)
dibio@unb.br
Exemplo 
● Quanto tempo vai durar esse projeto?
dibio@unb.br
Exemplo 
● Relações diretas entre as atividades
dibio@unb.br
Como modelar e resolver?
● Quais os pontos críticos?
● Qual o caminho mais longo?
● Algoritmo?
dibio@unb.br
Escalonamento
● Dado um conjunto de 
tarefas a serem 
realizadas, com 
condições de restrições e 
precedências, qual ordem 
escalonar as tarefas?
● Grafo com nós para 
tarefas e arestas 
indicando precedências.
dibio@unb.br
Ordenação Topológica
dibio@unb.br
Ordenação Topológica
dibio@unb.br
Ordenação Topológica
dibio@unb.br
Ordenação Topológica
dibio@unb.br
Aplicando Busca em Profundidade 
em um Grafo Orientado Aciclíco
dibio@unb.br
Caminho Crítico PERT/CPM 
● Tarefa v requer t[v] unidades de tempo de 
processamento (e.g. Processamento em tempo 
real)
● Algumas tarefas podem ser feitas em paralelo, mas 
outras possuem precedência
● Como terminar as tarefas no menor tempo 
possível?
● Qual o caminho crítico?
● Quais os riscos?
dibio@unb.br
Exemplo CPM/PERT
● Histórico: 
– Critical Path Method (E I Du Pont de Nemours & Co., 1957) para 
estudo de uma nova fábrica química e fechamento de instalação 
antiga. Envolve estudo de tarefas repetitivas e mensuráveis.
– Project Evaluation and Review Technique (Marinha Norte-
Americana, 1958 projeto de misseis POLARIS) para estudo de 
estiamtivas em trabalhos não repetitivos. 
dibio@unb.br
Exemplo CPM/PERT
● Quanto tempo vai durar esse projeto?
dibio@unb.br
Exemplo CPM/PERT
● Relações diretas entre as atividades
dibio@unb.br
Exemplo CPM/PERT
● Rede de atividades
dibio@unb.br
Caminho Crítico PERT/CPM 
● Modelar como um 
grafo
dibio@unb.br
Caminho Crítico PERT/CPM 
(Grafo Orientado Acíclico)
dibio@unb.br
Referências
● Cormen, T.; Leiserson, C. & Rivest, R. 
 Algoritmos: teoria e prática, Campus Editora, RJ, 
 2002.
● Sedgewick, R. Algorithms in C, 3rd edition, 
Addison Wesley, EUA, 2002.
● Tenenbaum, A.; Langsam, Y. & Augenstein, M. 
 Estruturas de Dados usando C, Makron Books, 
 RJ, 1995.
● Ziviani, N. Projetos de Algoritmos com 
Implementações em Pascal e C, Cengage 
Learning, SP, 2004.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18