MO640 - Ata de Exercícios (2004.10.11)

1. Considere a instância do problema de uns consecutivos apresentada na Figura 1 do artigo de Meidanis, Porto e Telles, 1998.  Construa a árvore PQR correspondente a esta instância.  Determine as coleções C barra, C ortogonal e a intersecção de ambas.
   Árvore PQR: (Q m₃ m₄ m₅ (P m₁ m₂))
   
   
   
2. Para cada inteiro n>= 1, achar uma árvore PQR T_n e um conjunto S_n tais que |S_n| = 2 e a adição de S_n a T_n produza uma árvore com pelo menos n nós a mais ou a menos que T_n.
   Sejam U, T e S:

   • U = {a₁, a₂, ..., a_n, a_n+1, a_n+2}
   • T = (P a₁ (P a₂ (P a₃ ... (P a_n (P a_n+1 a_n+2) ...)
   • S = {a₁, a_n+2}

   Nessas condições, a árvore resultante é T' = (Q a₁ a_n+2 a_n+1 a_n a_n-1 ... a₃ a₂). A árvore T possui n+1 nós P, enquanto T' tem um único nó Q. Portanto, a diferença no número de nós é n.
3. Tome U=abcdefghijk, e C={def, efghijk, gh, ijk, ghi}, que dão origem à árvore da Figura 3 do artigo de Booth e Leuker, 1976.  Usando S=ghijk, faça a decomposição da instância original do problema, conforme descrito na Seção 4.2 do artigo de Meidanis, Porto e Telles, 1998.
   , onde:
   
   
   
   

MO640 Home

Lista de exercícios original: © 2004 João Meidanis.
Ata compilada em 2004.10.11 por Marília Felippe Chiozo.