MAC328 - Algoritmos em grafos

BCC - 1o. Semestre de 2004

Sinopse das aulas - Maio

Aula 23 Terça 1/6/2004	Caminhos mínimos em grafos. Algoritmo de Dijkstra Transparências
Aula 24 Sexta 4/6/2004	Caminhos mínimos em grafos. Johnson: Dijkstra com heaps d-ários Algoritmo de Floyd Caminhos mínimos em grafos acíclicos; custos negativos permitidos Transparências
Terça 8/6/2004	Semana do Break!
Sexta 11/6/2004	Semana do Break!
Aula 25 Terça 15/6/2004	(Bloqueio do portão principal da USP) Redução de um problema de escalonamento simples a um problema de programação linear com restrições do tipo diferença, com restrição de sinal Redução de um problema de escalonamento com prazos (existência de solução, isto é, viabilidade) a um problema de viabilidade de um problema de programação linear com restrições do tipo diferença, sem restrição de sinal Uma aplicação de redes com custo negativo nos arcos: problemas de programação linear com restrições do tipo diferença, sem restrição de sinal. Conseqüência da redução: podemos resolver o problema de escalonamento com prazos usando um algoritmo de caminhos mínimos em redes sem restrição nos custos
Aula 26 Sexta 18/6/2004	Algoritmo de Bellman-Ford: descrição, prova da correcão Transparências
Aula 27 Terça 22/6/2004	Prova 2 [pdf \| ps \| dvi \| tex]
Aula 28 Sexta 25/6/2004	Fluxos em redes; teorema de Hall
Aula 29 Terça 29/6/2004	Prova 3 [pdf \| ps \| dvi \| tex]
Aula 30 Sexta 1/7/2004	Fluxos em redes

Calendário


     March 2004               April 2004                May 2004      
Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
    1  2  3  4  5  6                  1  2  3                        1 
 7  8  9 10 11 12 13      4  5  6  7  8  9 10      2  3  4  5  6  7  8 
14 15 16 17 18 19 20     11 12 13 14 15 16 17      9 10 11 12 13 14 15 
21 22 23 24 25 26 27     18 19 20 21 22 23 24     16 17 18 19 20 21 22 
28 29 30 31              25 26 27 28 29 30        23 24 25 26 27 28 29 
                                                  30 31

     June 2004        
Su Mo Tu We Th Fr Sa  
       1  2  3  4  5  
 6  7  8  9 10 11 12  
13 14 15 16 17 18 19  
20 21 22 23 24 25 26  
27 28 29 30

Sinopse das aulas de MAC328 (BCC - 1o. Semestre de 2004).
Página principal de MAC328 (BCC - 1o. Semestre de 2004).

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Tue Jun 29 11:14:21 BRT 2004