087-2005

MO640 - Questão para a prova oral
Número: 087
Enunciado: Segundo o artigo de Benzer (1959), On the topology of genetic fine structure, qual das seguintes matrizes está na ordem do dicionário:

A.

1 2 3 4 5 1 0 1 0 0 0 2 1 0 0 1 0 3 0 0 0 0 0 4 0 1 0 0 0 5 0 0 0 0 0

B.

1 2 3 4 5 1 0 1 1 1 1 2 1 0 0 1 1 3 1 0 0 0 1 4 1 1 0 0 0 5 1 1 1 0 0

C.

1 2 3 4 5 1 0 1 0 0 0 2 1 0 0 1 0 3 0 0 0 0 0 4 0 1 0 0 1 5 0 0 0 1 0

D.

1 2 3 4 5 1 0 1 1 1 1 2 1 0 0 1 0 3 1 0 0 0 1 4 1 1 0 0 0 5 1 0 1 0 0

E. NDA

Autor(a): Roseane Midori Miya

086-2005

MO640 - Questão para a prova oral
Número: 086
Enunciado:
Sobre o modelo de grafo utilizado por Christie em seu artigo de 1996 sobre intercâmbio de blocos, é INCORRETO afirmar que:

1. Um intercâmbio de blocos modifica apenas as arestas pretas
2. A permutação identidade possui n + 1 ciclos alternantes
3. Não segue o modelo introduzido por Bafna e Pevzner
4. É formado por um conjunto de vértices {0,1,...,n+1}, por arestas direcionadas cinzas e pretas.
5. NDA

Autor(a): Alan Braz

085-2005

MO640 - Questão para a prova oral
Número: 085
Enunciado:
Assinale a alternativa INCORRETA a respeito das operações de Block-Interchange

1. Uma operação de block-interchange pode ser vista como uma generalização da transposição
2. Em qualquer permutação, com exceção da identidade, é possível encontrarmos uma operação de block-interchange que remova ao menos dois breakpoints
3. Uma operação de block-interchange pode remover até 4 breakpoints, e assim adicionar até 4 ciclos em uma permutação
4. Quando uma operação de block-interchange mínima é aplicada, o número de ciclos de uma permutação é acrescido de 2
5. NDA

Autor(a): Leonardo Elias Mariote

084-2005

MO640 - Questão para a prova oral
Número: 084
Enunciado:
Qual das afirmações abaixo é INCORRETA com relação ao algoritmo de ordenação por intercâmbio de blocos, proposto por Christie, no artigo Sorting permutations by block-interchanges:

1. O algoritmo possui complexidade O(n²).
2. O algoritmo se basea numa operação chamada de minimal block-interchange que sempre remove 2 pontos de quebra.
3. O número de ciclos do grafo de ciclos (cycle graph) é sempre aumentado de 2 a cada operação de intercâmbio de blocos realizada pelo algoritmo.
4. O algoritmo possui fator de aproximação 2, já que é possível realizar operações de intercâmbio de blocos que removem até 4 pontos de quebra.
5. NDA

Autor(a): Marcelo de Almeida Oliveira

083-2005

MO640 - Questão para a prova oral
Número: 083
Enunciado:
Sobre permutações fáceis, no contexto de ordenação por transposição de prefixos, NÃO podemos afirmar que:

1. Uma permutação fácil deve ter um número ímpar de pontos de quebra.
2. O número de permutações fáceis cai drasticamente em proporção às não-fáceis com o aumento do comprimento da permutação.
3. Sempre passaremos por uma permutação fácil para ordenar uma permutação.
4. Para verificar que uma permutação é fácil, basta encontrar uma transposição que reduza em dois o número de pontos de quebra e verificar se a permutação resultante também possui uma transposição com tal propriedade.
5. NDA.

Autor: Tony Minoru Tamura Lopes

082-2005

MO640 - Questão para a prova oral
Número: 082
Enunciado:
Assinale a alternativa INCORRETA a respeito de transposições de prefixo

1. O número máximo de breakpoints que uma transposição de prefixo pode eliminar é igual ao de uma transposição qualquer
2. Para qualquer transposição t (que não seja de prefixo) e permutação p, é possível obtermos duas transformações de prefixo t1 e t2 tais que tp = t1t2p
3. Para uma permutação diferente da identidade, sempre é possível encontrarmos uma transposição de prefixo que reduza seu número de breakpoints em pelo menos um
4. Em uma permutação fácil, a ordenação pode ser feita utilizando apenas transposições de prefixo que removam dois breakpoints cada
5. NDA

Autor(a): Leonardo Elias Mariote

081-2005

MO640 - Questão para a prova oral
Número: 081
Enunciado:
Dada a permutação fácil (8 5 4 7 6 11 12 9 10 2 3 13 1) e o algoritmo polinomial para a ordenação ótima por transposições de prefixo (Fortuna 2005). Qual será o estado da permutação após 3 transposições de prefixo?

1. (9 10 2 3 4 7 8 5 6 11 12 13 1)
2. (7 8 9 10 2 3 4 5 6 11 12 13 1)
3. (2 3 4 5 6 11 12 13 1 7 8 9 10)
4. (2 3 4 9 10 11 12 13 1 5 6 7 8)
5. NDA

Autor(a): Marcelo de Almeida Oliveira