MO640 - Ata de Exercícios (2004.12.01)

  1. Para esta questão, considere genomas lineares e operações posicionais como no artigo de Dias, Fortuna e Meidanis, 2004. Determine todas as ordenações ótimas por tranposições de prefixo que levam o genoma [4,3,2,1] à identidade.
    Operação Antes Depois
    (1, 2, 3) [4, 3, 2, 1] [3, 4, 2, 1]
    (1, 3, 4) [3, 4, 2, 1] [2, 3, 4, 1]
    (1, 4, 5) [2, 3, 4, 1] [1, 2, 3, 4]
    (1, 2, 3) [4, 3, 2, 1] [3, 4, 2, 1]
    (1, 3, 5) [3, 4, 2, 1] [2, 1, 3, 4]
    (1, 2, 3) [2, 1, 3, 4] [1, 2, 3, 4]
    Operação Antes Depois
    (1, 2, 4) [4, 3, 2, 1] [3, 2, 4, 1]
    (1, 2, 3) [3, 2, 4, 1] [2, 3, 4, 1]
    (1, 4, 5) [2, 3, 4, 1] [1, 2, 3, 4]
    (1, 2, 5) [4, 3, 2, 1] [3, 2, 1, 4]
    (1, 2, 4) [3, 2, 1, 4] [2, 1, 3, 4]
    (1, 2, 3) [2, 1, 3, 4] [1, 2, 3, 4]
    Operação Antes Depois
    (1, 2, 5) [4, 3, 2, 1] [3, 2, 1, 4]
    (1, 2, 3) [3, 2, 1, 4] [2, 3, 1, 4]
    (1, 3, 4) [2, 3, 1, 4] [1, 2, 3, 4]
    (1, 3, 4) [4, 3, 2, 1] [2, 4, 3, 1]
    (1, 3, 5) [2, 4, 3, 1] [3, 1, 2, 4]
    (1, 2, 4) [3, 1, 2, 4] [1, 2, 3, 4]
  2. Aplique o algoritmo de ordenação descrito no artigo de Dias, Fortuna e Meidanis, 2004 ao genoma [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Mostre cada genoma intermediário, e indique F1, F2 e F3.
    Operação Antes Depois Fase
    (1, 2, 20) [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] [18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 19] F0
    (1, 2, 19) [18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 19] [17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 18, 19] F0
    (1, 2, 18) [17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 18, 19] [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 17, 18, 19] F0
    n = 19 - 3 [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 17, 18, 19] [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] F0 - Final
    (1, 5, 16) [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 16, 15, 14, 13, 1] F1
    (1, 5, 14) [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 16, 15, 14, 13, 1] [8, 7, 6, 5, 4, 3, 2, 16, 15, 12, 11, 10, 9, 14, 13, 1] F1
    (1, 5, 12) [8, 7, 6, 5, 4, 3, 2, 16, 15, 12, 11, 10, 9, 14, 13, 1] [4, 3, 2, 16, 15, 12, 11, 8, 7, 6, 5, 10, 9, 14, 13, 1] F1
    (1, 3, 10) [4, 3, 2, 16, 15, 12, 11, 8, 7, 6, 5, 10, 9, 14, 13, 1] [2, 16, 15, 12, 11, 8, 7, 4, 3, 6, 5, 10, 9, 14, 13, 1] F1 - Final
    (1, 3, 17) [2, 16, 15, 12, 11, 8, 7, 4, 3, 6, 5, 10, 9, 14, 13, 1] [15, 12, 11, 8, 7, 4, 3, 6, 5, 10, 9, 14, 13, 1, 2, 16] F2
    (1, 3, 13) [15, 12, 11, 8, 7, 4, 3, 6, 5, 10, 9, 14, 13, 1, 2, 16] [11, 8, 7, 4, 3, 6, 5, 10, 9, 14, 15, 12, 13, 1, 2, 16] F2
    (1, 3, 9) [11, 8, 7, 4, 3, 6, 5, 10, 9, 14, 15, 12, 13, 1, 2, 16] [7, 4, 3, 6, 5, 10, 11, 8, 9, 14, 15, 12, 13, 1, 2, 16] F2
    (1, 3, 5) [7, 4, 3, 6, 5, 10, 11, 8, 9, 14, 15, 12, 13, 1, 2, 16] [3, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13, 1, 2, 16] F2 - Final
    (1, 12, 16) [3, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13, 1, 2, 16] [12, 13, 1, 2, 3, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 16] F3
    (1, 8, 12) [12, 13, 1, 2, 3, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 16] [4, 5, 10, 11, 12, 13, 1, 2, 3, 6, 7, 8, 9, 14, 15, 16] F3
    (1, 3, 10) [4, 5, 10, 11, 12, 13, 1, 2, 3, 6, 7, 8, 9, 14, 15, 16] [10, 11, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 16] F3 - Final
    (1, 5, 14) [10, 11, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 16] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] F4 - Final

MO640 Home

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