TeX2014-10-22 22-35-16928

Estética

•

ESTÁCIO

Thomas Turbano Armando Pinto

21/05/2024

Prévia do material em texto

Teoria dos Grafos - COS 242
2014/2
Sexta Lista de Exerćıcios
ATENÇÃO! Para ajudar no treinamento para as provas faça as listas de forma que todas
as respostas estejam devidamente comentadas.
Questão 1: Considere o problema da mochila (knapsack problem). Descreva (em pseudo-
código) um algoritmo guloso de complexidade polinomial para o problema. Dica: determine
uma regra gulosa promissora para a obtenção da solução ótima. Construa um contra-exemplo
mostrando que seu algoritmo guloso nem sempre produz a solução ótima.
Questão 2: Considere o problema da mochila (knapsack problem). Dado a matriz M cons-
trúıda pelo algoritmo apresentado em aula que utiliza programação dinâmica, onde M [i, w] =
OPT (i, w), descreva um algoritmo (em pseudo-código) que imprime os elementos so subconjunto
que constituem a solução ótima. Seu algoritmo recebe como entrada a matriz M preenchida.
Questão 4: Considere o problema de alinhamento de sequência e o algoritmo que utiliza
programação dinâmica visto em aula. Assuma que o custo de emparelhamento dos śımbols x
e y é αx,y = 0 se x = y, αx,y = 1 se x e y são vogais e αx,y = 2 caso contrário, e que o custo
de inserção ou remoção é δ = 3. Mostre a matriz constrúıda pelo algoritmo ao fazermos o
alinhamento entre as palavras “empada” e “camarada”. Desenhe o alinhamento ótimo.
Questão 5: O problema LCS (Longest Common Subsequence), conhecido também por pro-
blema da subsequência comum mais longa, consiste em determinar a maior subsequência comum
a duas sequências. Por exemplo, a subsequência comum mais longa entre as palavras “estu-
dante” e “universitario” é “esta”, entre as palavras “cachorro” e “gato” é “ao”. Construa um
algoritmo eficiente que recebe como entrada duas sequências X = x1x2 . . . xm e Y = y1y2 . . . yn
e retorna o tamanho da subsequência comum mais longa. Avalie a complexidade do seu algo-
ritmo. Modifique seu algoritmo para retornar a subsequência comum mais longa em si e não
apenas seu tamanho.
Questão 6: Considere o algoritmo de Floyd-Warshall apresentado em aula. Mostre a
execução passo-a-passo do algoritmo no grafo ilustrado abaixo. Em particular, indique a matriz
de distâncias depois de cada passo mais externo do algoritmo, começando com a matriz inicial.
1
2
3
4
5
1
3
4 4
5
-2
1
Figura 1: Um grafo com pesos negativos.
1
Questão 7: Considere o algoritmo de Floyd-Warshall apresentado em aula. Mostre como o
pseudo-código do algoritmo pode ser modificado para que o mesmo detecte a presença de ciclos
negativos no grafo. Repare que neste caso o caminho mı́nimo não está definido e o algoritmo
deve informar isto.
Questão 8: Considere o algoritmo de Floyd-Warshall apresentado em aula. Modifique o
pseudo-código do algoritmo para que o mesmo obtenha também o caminho mı́nimo (sequência
de vértices) entre dois vértices i e j quaisquer. Repare que você deve criar e manter uma
estrutura de dados auxiliar para obter esta informação.
2