MO640 - Ata de resolução de exercícios

Autor: Mário César San Felice - RA 024645

Data da aula à qual os exercícios se referem: 20/06/2007

Data da aula na qual os exercícios foram resolvidos: 25/06/2007

Data de elaboração da ata: 25/06/2007

Exercício 1

Enunciado:

Escreva um algoritmo para resolver o seguinte problema: dada uma árvore PQR T e um conjunto, decidir se o conjunto faz parte de Compl(T).

Solução:

// Função que retorna verdadeiro se o conjunto c pertence ao Compl(T)
Bool ConjPertenceCompl(T, c)
 1-Encontra LCA // LCA é o nó raiz da menor subárvore que tem todos os elementos do conjunto c como folhas
 2-Se LCA for um nó do tipo P
 3-    Se todas as folhas da subárvore que tem o LCA como raiz estiverem no conjunto c
 4-        Retorna verdadeiro
 5-Se LCA for um nó do tipo Q
 6-    Se existe um subconjunto consecutivo de filhos do LCA cujas folhas da árvore são todas pertencentes ao conjunto c e que contem o conjunto c
 7-        Retorna verdadeiro
 8-    Se existe um subconjunto de filhos do LCA cujas folhas da árvore são todas pertencentes ao conjunto c e que contem o conjunto c
 9-        Retorna verdadeiro
10-Retorna falso

---

Exercício 2

Enunciado:

Escreva um algoritmo para resolver o seguinte problema: dadas duas árvores PQR T₁ e T₂ sobre o mesmo conjunto U, decidir se pode-se chegar de T₁ a T₂ adicionando conjuntos.

Solução:

// Função que retorna verdadeiro se é possível chegar de T1 a T2 adicionando conjuntos
Bool PossivelChegar(T1, T2, U)
 1-Para cada nó n de T1
 2-    Se n é P filho de P
 3-        Se (not ConjPertenceCompl(T2, n))
 4-            Retorne falso
 5-    Se n é Q ou R
 6-        Se (not ConjPertenceCompl(T2, n[i]Un[i+1])) para algum i
 7-            Retorne falso
 8-    Se n é R
 9-        Se (not ConjPertenceCompl(T2, n[1]Un [3]))
10-           Retorne falso
11-Retorne verdadeiro