Análise de Algoritmo
Atividade de revisão
1
Em relação a notação assintótica para análise de algoritmos podemos afirmar, EXCETO:
A notação Ω nos dá um limite superior para o tempo de execução de um algoritmo.
A notação O nos dá um limite superior para o tempo de execução de um algoritmo.
A notação Ω nos dá um limitante inferior para o tempo de execução de um algoritmo.
A notação Θ é utilizada quando é possível estabelecer um limite superior e um limite inferior para o tempo de execução de um algoritmo a partir de uma mesma função.
2
Em relação aos modelos computacionais, podemos afirmar que são exemplos de modelos computacionais:
Modelo restritivo, modelo regular, modelo assintótico.
Máquinas de Turing, Máquinas de Estados Finitos, Máquinas de estados infinitos.
Máquina de Turing, Modelo RAM, Máquinas de Estados Finitos.
Modelo RAM, modelo ROM, modelo CACHE.
3
Em relação a corretude, podemos afirmar, EXCETO:
A prova de que um algoritmo está correto normalmente é realizada através da análise assintótica.
A análise de corretude é utilizada para provar que um algoritmo é capaz de produzir uma resposta correta para qualquer instância de entrada.
Basta que exista uma única instância de entrada que não produza uma resposta correta para que o algoritmo não esteja correto.
4
O tempo de _________ nos dá uma medida da _________ de um algoritmo, e está associado ao _________ pelo algoritmo para nos fornecer uma saída para _________.
execução, eficiência, número de passos gastos, uma instância de entrada.
execução, complexidade, número de linhas de código utilizadas, variável de entrada.
análise, complexidade, custo demandado, um problema.
análise, corretude, tempo assintótico gasto, um problema.
5
Quando um algoritmo contém uma ________ a si mesmo, o ________ pode frequentemente ser _______ por uma _______.
referência, tempo de execução, reduzido, quantidade n.
instância referenciada, nível de complexidade, aumentado, instância de tamanho n.
recorrência, nível de complexidade, aumentado, quantidade adicional de tempo.
chamada recursiva, tempo de execução, descrito, equação de recorrência.
6
Em relação aos algoritmos de ordenação MergeSort e InsertionSort, podemos afirmar, EXCETO:
No algoritmo InsertionSort podemos dizer que a estratégia é ir percorrendo o vetor de entrada (instância de entrada) e formando um vetor ordenado a cada novo elemento lido. Assim podemos dizer que para cada elemento lido no vetor de entrada, a tarefa será inseri-lo em um vetor já ordenado, de tal forma que o vetor resultante também esteja ordenado.
O algoritmo MergeSort utiliza a estratégia de intercalação para realizar a ordenação de uma instância de entrada de tamanho n.
O algoritmo MergeSort utiliza a estratégia do primeiro princípio matemático para realizar a ordenação de uma instância de entrada de tamanho n.
Uma implementação possível para o algoritmo MergeSort, é através do uso de recursão.
7
Em relação ao primeiro princípio e o segundo princípio da indução matemática, podemos afirmar:
A vantagem no uso do segundo princípio da indução é que não precisamos provar a base da indução (P(1)).
Somente prova das proposições dos dois princípios da indução é suficiente de forma a garantirmos a proposição "“P(n) é verdade para todo inteiro positivo n. A prova de somente um dos princípios é incompleta.
Os dois princípios diferem na segunda proposição (proposição 2), onde no primeiro princípio precisamos provar que " (∀ k )[P(k) verdade → P(k + 1) verdade] " , ao passo que no segundo princípio precisamos provar que " P(k) verdade para todo r, 1≤ r ≤ k → P(k + 1) verdade".
8
Em relação a recorrência, podemos afirmar, EXCETO:
Uma das utilizações da recorrência é no uso da estratégia de divisão e conquista utilizada por alguns algoritmos.
Quando um algoritmo contém uma chamada recursiva a si próprio, seu tempo de execução pode ser descrito frequentemente por uma recorrência, que descreve o tempo de execução global para um problema de tamanho n em termos do tempo de execução para entradas menores.
As equações de recorrência nos ajudam a resolver problemas no tempo de execução dos algoritmos.
9
Em relação aos algoritmos de ordenação MergeSort e Insertion podemos afirmar, EXCETO:
A etapa de divisão no algoritmo MergeSort simplesmente calcula o ponto médio do subarranjo, o que demora um tempo constante, assim é Θ (1).
O algoritmo InsertionSort é mais eficiente que algoritmo MergeSort, uma vez que possui tempo de execução Θ (n lg( n)), ao passo que o algoritmo MergeSort tem tempo de execução de pior caso Θ (n²).
O algoritmo Insertion sort pode levar quantidades de tempos diferentes para ordenar duas sequências de entrada de mesmo tamanho n, ao passo que o algoritmo MergeSort leva o mesmo tempo para qualquer entrada de tamanho n.
10
O _________ de indução matemática é __________. A conclusão é uma ________ da forma “________ para todo inteiro positivo n”.
primeiro princípio, um condicional, proposição, P(n) é verdade.
teorema, universal, solução, A indução vale.
segundo princípio, uma recursão, equação recursiva, P(k+1) = P(k) +P(1).
terceiro princípio, indutivo, proposição, A indução vale.
