RECESSO
4 SET, SEG |
SEMANA DE ESTUDOS. N�O HAVER� AULA.
|
FERIADO
7 SET, QUI |
N�O HAVER� AULA.
|
AULA 5
11 SET, SEG |
- Resumo da aula anterior.
- Algoritmo de Dijkstra: invariantes, n�mero de itera��es e efici�ncia no
pior caso.
- Trailer dos pr�ximos epis�dios.
|
AULA 6
14 SET, QUI |
- Resumo da aula anterior.
- Ciclo de custo negativo: condi��o de inexist�ncia.
- Algoritmo gen�rico que recebe uma rede (N,A), uma fun��o-custo
c e devolve (1) um ciclo de custo negativo ou (2) uma
fun��o-potencial que respeita c.
- Invariantes e n�mero de itera��es do algoritmo.
- Trailer dos pr�ximos epis�dios.
|
AULA 7
18 SET, SEG |
- Resumo da aula anterior.
- Teorema. Seja (N,A) uma rede e c uma fun��o custo.
Vae uma e apenas uma das seguintes afirma��es:
(1) (N,A) possui um ciclo negativo;
(2) existe uma fun��o-potencial que respeita c.
- Algoritmo Fila-de-arcos: efici�ncia no pior caso.
- Trailer dos pr�ximos epis�dios.
|
AULA 8
21 SET, QUI |
- Resumo da aula anterior.
- Fluxos em redes: fluxos, saldos, excessos, fun��o-capacidade, valor de
um fluxo.
- Problema do Fluxo M�ximo: Dada uma rede (N,A), uma
fun��o-capacidade u e dois n�s distintos s e t,
encontrar um fluxo vi�vel de s a t de valor m�ximo.
- Condi��o de otimalidade: cortes de capacidade m�nima.
- Capacidade residual.
- Trailer dos pr�ximos epis�dios.
|
AULA 9
25 SET, SEG |
- Resumo da aula anterior.
- Lema b�sico. Se x � um fluxo vi�vel de s a
t e (Y,N-Y) � um corte vi�vel, ent�o a capacidade do corte �
pelo menos o valor do fluxo. (Conseq��ncia imediata: se a capacidade de um
corte vi�vel � igual ao valor do fluxo ent�o o fluxo � m�ximo e o corte tem
capacidade m�nima entre todos os cortes vi�veis.)
- Algoritmo dos caminhos aumentadores (Ford e Fulkerson): invariantes e
n�mero de itera��es (o algoritom � pseudo-polinomial).
- Trailer dos pr�ximos epis�dios.
|
AULA 10
28 SET, QUI |
- Resumo da aula anterior.
- Teorema do fluxo m�ximo e corte m�nimo.
- Teorema da integralidade do fluxo.
- Rede residual.
- Decomposi��o de fluxos: todo fluxo pode ser expresso como a soma de
fluxos e circula��es elementares.
- Trailer dos pr�ximos epis�dios.
|