MO640 - Ata de exercícios

Aula: 2007-06-20
Autor: Paulo Renato Nascimento ra035209

Enunciados disponíveis em http://www.ic.unicamp.br/~meidanis/courses/mo640/2007s1/exerc/2007-06-18.html

1. Ache todos os conjuntos ortogonais à entrada: U=abcdef, C={abc, bec, cd}.

{},

{a}, {b}, {c}, {d}, {e}, {f},

{abcdef},

{abcde}

2. Escreva um algoritmo para resolver o seguinte problema: dada uma árvore PQR T e uma permutação α de U, decidir se existe alguma árvore equivalente a T cuja fronteira seja α.

O algoritmo montado em sala de aula utiliza uma abordagem bottom-up na árvore, verificando primeiro se os nós folhas são compatíveis com a permutação dada (caso trivial) e propagando-se recursivamente para os nós ancestrais.

A rotina compat recebe como parâmetros de entrada a permutação α (dada no problema) e o nó raiz da sub-árvore onde deseja-se verificar a compatibilidade. Obviamente na primeira chamada da rotina o parâmetro parent equivale à raiz da árvore T. A função retorna false caso a sub-árvore analisada não possua nenhuma árvore equivalente cuja fronteira seja compatível com α. Caso contrário retorna um par ordenado que indica o início e fim da sub-cadeia em α compatível com a fronteira da sub-árvore.

compat(, parent)

-- caso seja um nó folha, é trivial.

-- basta retornar o índice do nó como início e fim

if parent.children is empty then

return [i, i] | (i) = parent

-- verifica recursivamente se todos os filhos são compatíveis

for each node c in parent.children

[i_c , f_c] = compat(, c)

case type of parent is:

-- se é um nó Q, seus filhos devem ser consecutivos na permutação de entrada.

-- Caso o sejam, retorna no par ordenado o menor e maior índice encontrados.

Q if todos os filhos são consecutivos (crescentes ou decrescentes) em

return [ min(I F ), max(I F ) ]

else

return false

-- se é um nó P ou R, deve existir uma forma de rearranjar seus filhos

-- de modo que sejam consecutivos na permutação de entrada.

-- Caso exista, retorna no par ordenado o menor e maior índice encontrados

P, Rif existe uma permutação de filhos onde estes são consecutivos em

return [ min(I F ), max(I F ) ]

else

return false

Nota: No algoritmo, I e F representam, respectivamente, o conjunto de todos os índices i_c e f_c encontrados na fase de verificação da compatibilidade dos filhos de parent. Por exemplo:

I = {i₀, i₁, ... , i_n-1}

F = {f₀, f₁, ... , f_n-1}