10-2011 - MO640 - Questão para a prova oral

De acordo com o texto Haplotype Inference , quanto aos três primeiros algoritmos para resolver o problema Perfect Phylogeny Haplotype, é correto afirmar:

1. O primeiro algoritmo para resolver o problema Perfect Phylogeny Haplotype é chamado de LPPH. Seu tempo de execução teórica inicial é O(nmα (nm)), onde α é a função inversa de Ackerman, geralmente considerado como sendo uma constante na prática;

2. O segundo algoritmo para resolver o problema Perfect Phylogeny Haplotype é chamado de BPPH. Esse algoritmo possui o pior caso de tempo de O(nm²) e pode ser usado para localizar e representar todas as soluções;

3. O terceiro algoritmo para resolver o problema Perfect Phylogeny Haplotype é chamado de DPPH. Esse algoritmo possui o pior caso de tempo de O(nm²) e pode ser usado para localizar e representar todas as soluções;

4. Os três algoritmos possuem, no pior caso de tempo, O(nm²).

5. NDA.