1
Em relação a notação assintótica para análise de algoritmos podemos afirmar, EXCETO:
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.
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.
2
Em relação aos modelos computacionais, podemos afirmar que são exemplos de modelos computacionais:
Máquinas de Turing, Máquinas de Estados Finitos, Máquinas de estados infinitos.
Modelo RAM, modelo ROM, modelo CACHE.
Modelo restritivo, modelo regular, modelo assintótico.
Máquina de Turing, Modelo RAM, Máquinas de Estados Finitos.
3
Em relação a corretude, podemos afirmar, EXCETO:
Basta que exista uma única instância de entrada que não produza uma resposta correta para que o algoritmo não esteja correto.
A análise de corretude é utilizada para provar que um algoritmo é capaz de produzir uma resposta correta para qualquer instância de entrada.
A prova de que um algoritmo está correto normalmente é realizada através da análise assintótica.
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, corretude, tempo assintótico gasto, um problema.
análise, complexidade, custo demandado, um problema.
5
Quando um algoritmo contém uma ________ a si mesmo, o ________ pode frequentemente ser _______ por uma _______.
chamada recursiva, tempo de execução, descrito, equação de recorrência.
recorrência, nível de complexidade, aumentado, quantidade adicional de tempo.
referência, tempo de execução, reduzido, quantidade n.
instância referenciada, nível de complexidade, aumentado, instância de tamanho n.
6
Em relação aos algoritmos de ordenação MergeSort e InsertionSort, podemos afirmar, EXCETO:
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.
O algoritmo MergeSort utiliza a estratégia de intercalação para realizar a ordenação de uma instância de entrada de tamanho n.
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.
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:
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".
A vantagem no uso do segundo princípio da indução é que não precisamos provar a base da indução (P(1)).
8
Em relação a recorrência, podemos afirmar, EXCETO:
As equações de recorrência nos ajudam a resolver problemas no tempo de execução dos 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.
Uma das utilizações da recorrência é no uso da estratégia de divisão e conquista utilizada por alguns 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 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.
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²).
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.
terceiro princípio, indutivo, proposição, A indução vale.
teorema, universal, solução, A indução vale.
segundo princípio, uma recursão, equação recursiva, P(k+1) = P(k) +P(1).
