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 maio de 2009
Período: 2009.1
PROJETO E ANÁLISE DE ALGORITMOS (INF 2926)

3a Lista de Exercícios

  1. Considere o problema de Fluxo Máximo do vértice s ao vértice t em um grafo orientado G=(V,E) com a restrição de que as capacidades de todos os arcos no grafo é 1.
    1. Proponha um algoritmo com complexidade O(nm) para encontrar o fluxo máximo destes grafos e discuta a sua implementação. (Descreva o algoritmo informalmente, apresente as estruturas que devem ser utilizadas e as operações necessárias, reescreva o algoritmo em função destas operações e analise cuidadosamente sua complexidade).
    2. Hoje, o algoritmo de complexidade mais baixa para este problema tem complexidade O( min { n2/3m, m3/2 } ) (ver Ahuja seção 8.2). Qual o gargalo do seu algoritmo ? Onde o seu algoritmo pode ser melhorado ?
    3. Considere agora que os arcos da rede possuem capacidades quaisquer. Explique como este algoritmo pode ser utilizado para se obter um algoritmo para o problema genérico de Fluxo Máximo de complexidade polinomial dada por O(n.m.log U), onde U é a capacidade do arco com maior capacidade.

  2. Considere uma árvore binária de busca onde a sub-árvore com raiz em um nó x possui size[x] elementos. Seja a uma constante tal que 1/2 £ a < 1. Um nó x da árvore é dito balanceado se size[left[x]] £ a . size[x] e size[rigth[x]] £ a . size[x] onde left[x] e right[x] são os nós filhos à esquerda e à direita do nó x, respectivamente. A árvore de busca é a-balanceada se todos os seus nós são a-balanceados.

    1. Dado um nó x, arbitrário, mostre como reconstruir sua sub-árvore de modo que fique 1/2-balanceada. O algoritmo deve executar em O(size[x]) (que é Q ( size[x] )). Lembre que a sub-árvore de x já é uma sub-árvore de busca e size[v] diz quantos elementos estão na sub-árvore de v.

    2. Mostre que a operação de busca em uma árvore a-balanceada com n elementos é feita em O(log n). (Fácil !!)

    3. A partir deste item assuma que a > 1/2 (ou seja é estritamente maior que 1/2). Suponha que as operações de Insert e Delete sejam implementadas da forma habitual, sem rotações, exceto que quando algum nó não está mais a-balanceado, a operação do item a) (reconstrução para deixar 1/2-balanceada) é feita no nó desbalanceado de maior nível.

      A idéia é analisar este esquema de reconstrução utilizando o método do pontencial para análize amortizada. Para um nó x na árvore binária T define-se:
      D (x) = | size[left[x]] - size[right[x]] |
      Define-se também o potencial na ávore T, F (T) como:
      F (T) = c
       
      å
      x Î T | D(x) ³ 2
      D(x)
      onde c é uma constante sufucientemente grande que depende de a.

    4. Argumente que qualquer árvore binária de busca tem potencial não-negativo e que uma árvore 1/2-balanceada tem potencial 0.

    5. Suponha que m unidades de potencial podem pagar pela reconstrução de uma sub-árvore com m nós. Que valor, em função de a, deve ter c para que a operação de reconstrução tome tempo amortizado constante (O(1)), quando é aplicada sobre uma sub-árvore que não está a-balanceada ?

    6. Mostre que as operações de Insert e Delete tomam tempo amortizado O(log n).

This document was translated from LATEX by HEVEA.