Período: 2008.1
15 de abril de 2008
Horário: 2as-feiras e 4as-feiras de 9 às 11 horas
ANÁLISE DE ALGORITMOS (INF 1721)

1o Trabalho de Implementação (T1b) (Parte b)

Data de Entrega: 23 de junho de 2008

Descrição

Este trabalho prático consiste em desenvolver códigos para algoritmos e estruturas de dados para resolver os problemas descritos abaixo e, principalmente, analisar o desempenho das implementações destes algoritmos com respeito ao tempo de CPU. O desenvolvimento destes códigos e a análise devem seguir os seguintes roteiros: A corretude código será testada sobre os conjuntos de instâncias distribuidos. O trabalho entregue deve conter:
0. Estruturas de Dados

O grupo deve implementar (ou usar códigos prontos) códigos para efetuar as seguintes operações nas estruturas de dados abaixo:
  1. d-Heap para um valor de d qualquer.
1. Problema da Caminho-mais-curto em grafos com distâncias não-negativas(veja o link ``Instâncias para CMC'' para grafos de teste)

  1. Implementar o Algoritmo de Dijskstra utilizando as estruturas de dados, listadas a seguir, para selecionar o próximo vértice mais próximo. Nestas estruturas, cada vértice tem como valor-chave a distância do menor caminho corrente que o conecta ao vértice de partida.

    Lista de estruturas de dados a utilizar:
    1. Vetor com os valores das distâncias.
    2. d-Heap, para os valores d=2, d=3 e d=5 .
2. Problema da Fluxo-Máximo em grafos (veja o link ``Instâncias para Fluxo Máximo'' para grafos de teste)

  1. Implementar o Algoritmo de Ford-Fulkerson (usa Busca em Profundidade para encontrar um caminho s-t na rede residual);
  2. Implementar o Algoritmo de Edmonds-Karp (usa Busca em Largura para encontrar um caminho s-t na rede residual);

This document was translated from LATEX by HEVEA.