Lista 10

Problema retirado do teste 10 do professor Carlos Brito, da disciplina de Contrução e Análise de Algoritmos (CAnA).

Considere os problemas a seguir:

  1. Cortes de Tora
    Uma tora deve ser cortada em n pontos para produzir n+1 pedaços de madeira. O custo para a realização de cada corte é proporcional ao tamanho do pedaço que está sendo cortado.
    Dados o comprimento L da tora e os pontos de corte c1, … , c n , o problema consiste em determinar uma ordem para a realização dos cortes que minize o custo total.
  2. Combinação de Listas
    Dadas k listas ordenadas, o problema consiste em formar uma lista ordenada combinando as listas duas de cada vez. O objetivo é minizar o número de comprações realizadas no processo.
  3. Árvore Binário (com nós exernos) ótima
    TEmos m registros indexados pela chaves h1, …, hn(onde h1 < hn+1) com os quais precisamos construir uma árvore binário com nós externos. sabe-se que cada registro hi será acessada mi vezes, e o custo de cada acesso a hi é proporcional à sua altura na árvore. O problema é construir uma árvore que minimize o custo total dos acessos.
    Nota: Uma árvore binára com nós externos é uma árvore binária de busca em que os registros hi, … ,hn são armazenados nas folhas da árvore. Os valores dos nós internos são arbitrários, e são apenas utilizados para navegar pela árvore e encontrar a folha correta em uma busca.

a) O problema (1) é logicamente equivalente a exatamento um dos outros dois problemas acima. Indique que problema é este.
Denote por (X) o problema indicado no item(a), e por (Y) o outro problema.
b) Prove que o problema (1) é logicamente equivalente ao problema (X) respondendo os itens a seguir:

  • b1) Mostre como transformar uma instância Pi do problema (1) em uma instância Px do problema (X).
  • b2) Mostre como transformar uma solução Sx para o problema Px em uma solução Si para o problema Pi.
  • b3) Mostre que se Sx é uma solução ótima para Px, então a solução Si, obtida pela transformação do item (b), é uma solução ótima para Pi.

c) Justifique porque o problema (1) nõa é lógicamente equivalente ao problema (Y).
d) Apresente um problema que seja lógicamente equivalente ao problema (Y). Justifique.
e) Modifique a definição do problema (1) de modo que ele seja logicamente equivalente ao (Y).

Anúncios

Deixe um comentário »

RSS feed for comments on this post. TrackBack URI

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Crie um website ou blog gratuito no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: