PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Horário: 3as-feiras de 13 às 16 horas - Sala 154L
26 de abril de 2009
Data da Entrega: 26 de maio de 2009
Período: 2009.1
PROJETO E ANÁLISE DE ALGORITMOS (INF 2926)

1o Trabalho de Implementação

Descrição

Este trabalho prático consiste em desenvolver códigos para diferentes 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 um conjunto de instâncias que será distribuido. 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. Árvore Balanceada (Árvore AVL, Árvore Vermelha-Preta, etc.)
  2. Heap que permita a união de heaps (Leftist Heap do Knuth), com e sem operações preguiçosas (LAZY) -- Alternativamente pode ser utilizada uma Heap de Fibonacci, que também utiliza operações preguiçosas.
1. Problema da Árvore Geradora Mínima

  1. Implementar o Algoritmo de Prim utilizando as estruturas de dados, listadas a seguir, para selecionar o vértice mais próximo da árvore corrente. Nestas estruturas, cada vértice tem como valor-chave o peso da menor aresta que o conecta à árvore corrente. (ver links na página do curso para textos sobre algoritmos para a MST, em especial para o algoritm de Round-Robin, ver também links para instâncias do problema).

    Lista de estruturas de dados a utilizar:
    1. Árvore Balanceada de Busca
    2. Heap sem lazy ou Heap de Fibonacci.
    3. Heap com lazy ou Heap de Fibonacci.

    A Heap sugerida para ser implementada é a Leftist Heap ver texto no link heap na página do curso. A Heap de Fibonacci está descrita no livro ``Introduction to Algorithms'', T.H. Cormen, C.E. Leiserson e R.L. Rivest, McGraw-Hill.

  2. Implementar o Algoritmo de Round-Robin (Tarjan) (equivalente ao algoritmo de Solin ou Borüvka) nesse algoritmo inicia-se com uma árvore associada a cada vértice (n árvores) armazenado-se numa min heap as arestas que ligam cada árvore ao restante do grafo. A cada iteração uma árvore é conectada a uma outra e suas min heaps combinadas. A ordem em que as árvore são combinadas segue o critério FIFO onde a ordem inicial é arbitrária (1,2,...,n por exemplo). Utilize as seguintes heaps com operação de união:
    1. Heap sem lazy ou Heap de Fibonacci.
    2. Heap com lazy ou Heap de Fibonacci.
2. Problema da Mochila Fracionária (pode-se colocar parte de um objeto na mochila)

[KP-frac] Dado um conjunto de n objetos divisíveis com pesos positivos wj, j=1,...,n e valores também positivos vj, j=1,...,n. Sabendo que uma mochila tem a capacidade W, determinar os objetos que podem ser levados na mochila cuja soma dos valores é máxima.

  1. Implementar algoritmos para o problema da mochila fracionária com as seguintes complexidades teóricas em função do número n de itens candidatos a serem colocados na mochila:
    1. O(n log n)
    2. O(n)
    3. Considere que o seu algoritmo do item (b) utiliza particionamentos em sequencia com pivot calculado apropriadamente para garantir a complexidade O(n). Utilize agora como pivot o valor calculado pela expressão:
      pivot =
      1

      |K|
       
      å
      j Î K
      vj

      wj
      onde K é o conjunto de itens considerados.
      1. Prove que a complexidade (pior caso) do algoritmo resultante é O(n2).
      2. Estime sua complexidade sobre as intâncias testadas.
      3. Assim como para os itens (a) e (b) apresente experiências computacionais comparativas.
3. Encontrar os componentes fortemente conexos de um grafo orientado.

  1. Implementar algoritmos com a seguinte complexidade::
    1. O(n2 + nm)
    2. O(|C|.(n + m)) onde C é o conjunto de componentes fortemente conexos.
    3. O(n + m)
  2. Utilize esse algoritmo para determinar se uma instância do problema 2-SAT pode ser satisfeita ou não.

This document was translated from LATEX by HEVEA.