MO640 - Soluções dos exercícios sobre a aula de 2008-11-13

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

    2. SOLUÇÃO: São os triviais mais todos os subconjuntos de abcde. Para ver isto, observe que os binários ab, bc, cd e be estão na coleção completa, e b tem grau 3. Pelo Teorema 24 do artigo de Meidanis, Porto e Telles (1998), isto significa que todos os binários de abcde estão na coleção completa. Mas é fácil construir todos os subconjuntos a partir dos binários.

  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. SOLUÇÃO:

    Entrada: a, T

    v ← a
    while TRUE
      if pai(v) é Q e v não é da ponta
        return FALSE
      if v é a raiz
        return TRUE
      v ← pai(v)

    Saída: booleano que indica de existe uma árvore equivalente a T cuja fronteira comece por a.

MO640 Home

© 2008 João Meidanis