MO405 - Atas das Aulas
 

Ata de Aula:     28/08/2002

Capitulo:  2.3 Optimization and Trees

Ata de Aula:     28/08/2002
Redator:           Evandro Cesar Bracht   014860
 

Tópicos Discutidos mais importantes:

1- Grafo com pesos nas arestas

* Um grafo com pesos nas arestas é um grafo com rótulos nas arestas, os quais podem representar informações sobre distâncias, custos, etc.

* Com a utilização de pesos nas arestas podemos representar vários problemas de otimização como sendo um grafo, por exemplo o problema da conectividade de pontos em uma rede. O problema consiste em encontrar uma configuração onde todos os pontos estão conectados com um custo mínimo. Neste caso a árvore geradora de custo mínimo nos dá a solução ótima.

2- Arvore geradora mínima
G = grafo utilizado como exemplo em sala de aula para demonstrar os algoritmos de geração da arvore mínima.

  2.1- Algoritmo de Kruskal
  O algoritmo de Kruskal retorna uma arvore geradora mínima ótima. Seguem abaixo os principais passos tendo como entrada um grafo G conexo e como saída uma arvore H. 

* V(H) <- V(G)
* Enquanto H for desconexo
*    Selecione a menor aresta em E(G) que não foi verificada
*    se a aresta não formar ciclos em H, acrescente-a a H
Aplicando o algoritmo temos a arvore resultante

  2.2- Algoritmo de Dijkstra
  O algoritmo de Dijkstra encontra todos os menores caminhos a partir de um nó especificado formando assim uma arvore de caminhos mínimos. Esta árvore em geral é diferente da árvore geradora mínima do algoritmo anterior. 
* O algoritmo primeiramente cria uma lista de vértices com atribuições de
distancia infinita exceto pro vértice escolhido como o inicial, que
ganha distância zero.

Posteriormente, a cada passo da iteração é escolhido o vértice que não
foi verificado ainda e que possua a menor distancia em relação ao
vértice de origem, e as distâncias de seus vizinhos são atualizadas.

Estas escolhas de vértices vão definindo a arvore.


OBS: O primeiro algoritmo algoritmo funciona mesmo se tiver custos negativos. Já o segundo só funciona com pesos maiores ou igual a zero.

2.3- Busca em Largura
  O algoritmo da busca em largura é utilizado, por exemplo, para obter as distâncias no caso de todos os pesos serem iguais. É mais simples que o algoritmo de Dijkstra.

3- Arvores na Ciência da Computação
  Um dos principais pontos em computação é que as arvores possuem raiz que nada mais é do que escolher um vértice que vai receber o rotulo de raiz. Isso traz as definições usuais como vizinhos, pais, filhos, ancestrais, etc.

Outro ponto relevante nesta parte é uma sub classe das arvores, que são as arvores binárias, onde cada nó é folha ou possue no máximo dois filhos, filho da esquerda e filho da direita. Esta é uma estrutura muito utilizada na computação.