MO640/ MC668 - Ata de exercí­cios

Aula: 2007-18-06
Autor: Wagner Rogério de Andrade RA: 036546

  1. Ache a coleção completa correspondente à seguinte entrada: U=abcdef, C={abc, bec, cd}.

      2. Resposta:
      O colega Paulo Nascimento junto com o professor e alguns alunos chegaram a conclusão de que a coleção completa pedida no enunciado é:
      C = ∅
          a,b,c,d,e,f,
          ab,ac,ad,ae,bc,bd,be,cd,ce,de,
          abc,abd,abe,acd,ace,ade,bcd,bce,bde,cde,
          abcd,abce,abde,acde,bcde,
          abcde,
          abcdef
  2. Escreva um algoritmo para resolver o seguinte problema: dada uma árvore PQR T e um elemento a de U, decidir se existe alguma árvore equivalente a T cuja fronteira comece por a.

      3. Resposta:
       O colega Celmar encontrou um algoritmo que resolve o problema, este algoritmo foi melhorado pelo
      professor e alguns alunos durante a aula, resultando no algoritmo abaixo:

      PodeIniciar(T,a){
          Enquanto a ≠ raiz {
              pai ← a.pai;
              se (pai.tipo = NO_Q) e (pai.primeiroFilho ≠ a) e (pai.ultimoFilho ≠ a){
                  retorna falso ;
              }(fim-if)
               a ← pai;
          }(fim-enquanto)
          retorna true;
      }(fim-PodeIniciar)