MO640 – Biologia Computacional
Ata de Exercícios (13/09/2004)
Autor: Danilo L. Benzatti – RA: 980942.

Os exercícios desta aula se encontram em:
Setubal e Meidanis 1997 - SETUBAL, J. C.; MEIDANIS, J. Introduction to Computational Molecular Biology. PWS Publishing Company, 1997. Capítulo1, páginas 43 e 44.


6. Mostre a matriz de adjacência e a lista de adjacência para os grafos da figura 2.1.
R.:

Grafo 1

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

1 : 2 , 3

2 : 1 , 3 , 4

3 : 1 , 2

4 : 2

5 : 6

6 : 5

Grafo 2

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

1

2

3 : 1 , 2

4

5 : 1 , 2 , 3 , 4

8. Sejam dois algoritmos A₁ e A₂ para um mesmo problema cujo tamanho é definido pelo parâmetro n. Se A₁ roda em O(n/log(n)) e A₂ roda em O(sqrt(n)) qual é o mais rápido assintoticamente.
R.:

Dividindo a complexidade de A₁ pela de A₂, pode-se demostrar que o fator multiplicativo tende a infinito. Logo, A₂é mais rápido.

9. Sabe-se que um grafo é Euleriano se e somente se ele é conexo e todos os vértices tem grau par. Baseado nesta observação, proponha um algoritmo que encontre um ciclo Euleriano em um grafo se o ciclo existir.

Usando a notação do livro temos:

ciclo <- lista contendo um vértice qualquer do grafo

enquanto houver v que pertence a ciclo com d(v) > 0

faça

ref <- v

enquanto houver vizinho u de v diferente de ref

faça

apaga (u,v) do grafo

insere v em ciclo na posição anterior a ref

v <- u

fim

insere v no ciclo na posição anterior a ref

apaga aresta(v,ref)

fim

retorna os elementos do ciclo em ordem

14. Suponha um problema X de complexidade desconhecida. Você obtém uma redução de tempo polinomial de X a um problema NP-completo conhecido. O que pode-se afirmar sobre a complexidade de X?

R.:

X pertence à NP porque existe um algoritmo não determinístico em tempo polinomial para resolvê-lo.

Obs: Pare este exercício foi admitido que reduções são sempre polinomiais.