AULA 0
17 AGO, QUI |
NÃO HOUVE AULA.
|
AULA 1
21 AGO, SEG |
- Descrição da disciplina.
- Redes, passeios e caminhos em redes.
- O Problema do Fluxo de Custo Mínimo.
- Busca numa rede.
- Função-potencial.
- Propriedade fundamental de uma função-potencial viável.
- Trailer dos próximos episódios.
Aviso importante. Todos precisam inscrever-se o mais rápido
possível na
lista de discussão da disciplina (veja Lista de discussão desta disciplina).
|
AULA 2
24 AGO, QUI |
- Resumo da aula anterior.
- Algoritmo que recebe uma rede (N,A) e uma par s,t de nós
e devolve: (1) um caminho orientado de s a t ou
(2) uma função-potencial viável y tal que y(t) - y(s) >
0. Invariante e número de iterações.
- Algoritmo genérico: invariantes, número de iterações.
- Teorema. Para qualquer para s,t de nós de uma rede vale
que ou (1) existe um caminho orientado de s a t, ou
(2) existe uma função-potencial viável tal que y(t)-y(s)>0.
- Trailer dos próximos episódios.
|
AULA 3
28 AGO, SEG |
- Resumo da aula anterior.
- Caminhos mais curto: condição de otimalidade.
- Algoritmo que recebe uma rede (N,A) e um nó s e
devolve (1) uma função-potencial y que respeita 1, e (2)
para cada nó t tal que y(t) - y(s) < n uma caminho
Pt de s a t tal que
y(j) - y(i) = 1 para cada ij em Pt.
- Invariante e número de interações do algoritmo.
- Trailer dos próximos episódios.
|
AULA 4
31 AGO, QUI |
- Resumo da aula anterior.
- Algoritmo Busca-em-Largura.
- Número de iterações e eficiência no pior caso do algoritmo.
-
Teorema. Dados (N,A) e s,t em N, existe uma
função-potencial que respeita 1 talq que para cada j atingível a
partir de s, y(j) - y(s) é igual ao comprimento de um
caminho mais curto de s a t.
- Problema do caminho de custo mínimo. Em geral é o problema é
NP-difícil.
- Condição de otimalidade: função-potencial que respeita o custo.
- Algoritmo genérico.
- Trailer dos próximos episódios.
|