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
[ic , fc] =
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 ic e fc
encontrados na fase de verificação da compatibilidade dos filhos de parent.
Por exemplo:
I = {i0, i1, ... , in-1}
F = {f0, f1, ... , fn-1}