MAC338 Análise de Algoritmos

BCC - 1o. Semestre de 2000

Programas para Árvores Geradoras Mínimas

Para atacar este desafio, o ideal é que você esteja fazendo ou já tenha feito grafos (MAC328) e conheça o Stanford GraphBase (SGB) de Knuth. Formem equipes em que haja várias pessoas que entendam do SGB. Vamos usar o módulo miles_span do SGB, que compara vários métodos para se encontrar uma árvore geradora mínima em um grafo.
  1. Estude cuidadosamente o módulo miles_span, dando especial atenção às funções que implementam os algoritmos de Kruskal e Jarník/Prim (com heaps binários). Estude também a seção 71 (a seção de conclusões) deste programa.
  2. A máquina usada por Knuth para elaborar os dados da seção 71 foi uma Sun SPARCstation 2. Faça uma análise semelhante para máquinas Pentium rodando GNU/Linux. Os custos médios de um mem (em tempo) nestas arquiteturas são muito diferentes? Como afetam este custo médio os níveis de otimização de código feitas pelo gcc (opções -g, -O2, -O3)?
  3. A contagem de mems é uma forma de se estudar a eficiência de um programa. Os dados da seção 71 de miles_span mostram que este método é bom para a Sparc 2 usada para compilar estes dados. Este método funciona bem também em máquinas Pentium? Faz alguma diferença? Faça seus testes comparando as melhores máquinas RISC que temos com as melhores máquinas Pentium que temos.
  4. Escreva outros programas para encontrar árvores geradoras mínimas, que contem mems, e tente conseguir programas mais eficientes que os de Knuth.
[Página principal dos desafios de MAC338 | Página principal de MAC338 (BCC - 1o. Semestre de 2000)]
Netscape-HTML Checked!
Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Fri Apr 28 11:03:12 BRT 2000