Questoes-Algoritmos-Ordenacao-MergeSort-Insertion-Inducao-Matematica-Recorrencia

PERGUNTA 4 Em relação aos algoritmos de ordenação MergeSort e Insertion podemos afirmar I O algoritmo InsertionSort é mais eficiente que algoritmo MergeSort uma vez que possui tempo de execução Θ n log n ao passo que o algoritmo MergeSort tem tempo de execução de pior caso O n2 II 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 III A etapa de divisão no algoritmo MergeSort simplesmente calcula o ponto médio do subarranjo o que demora um tempo constante assim é O 1 Assinale a alternativa correta Somente a afirmação I está correta As afirmações I e II estão corretas Todas as afirmações estão corretas Nenhuma das afirmações está correta As afirmações II e I II estão corretas PERGUNTA 5 Em relação ao primeiro princípio e o segundo princípio da indução matemática podemos afirmar I Os dois princípios diferem na segunda proposição proposição 2 onde no primeiro princípio precisamos provar que k Pk verdade Pk1 verdade ao passo que no segundo princípio precisamos provar que Pk verdade para todo t 1 t k Pk 1 verdade II Somente prova das proposições dos dois princípios da indução é suficiente de forma a garantirmos a proposição Pn é verdade para todo inteiro positivo n A prova de somente um dos princípios é incompleta III A vantagem no uso do segundo princípio da indução é que não precisamos provar a base da indução P1 Assinale a alternativa correta As afirmações I e II estão corretas Nenhuma das afirmações estão correta Todas as afirmações estão corretas Somente a afirmação I está correta As afirmações I e II estão corretas PERGUNTA 6 Em relação a recorrência podemos afirmar I 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 II Uma das utilizações da recorrência é no uso da estratégia de divisão e conquista utilizada por alguns algoritmos III As equações de recorrência nos ajudam a resolver problemas no tempo de execução dos algoritmos Assinale a alternativa correta As afirmações I e II estão corretas As afirmações I e II estão corretas Nenhuma das afirmações está correta Todas as afirmações estão corretas Somente a afirmação I está correta PERGUNTA 1 Na estratégia de divisão e conquista para o projeto de algoritmos resolvemos o problema recursivamente em três etapas sucessivas Quais são elas ordenação divisão conquista recursão conquista divisão divisão conquista combinação conquista divisão recombinação divisão ordenação conquista PERGUNTA 2 Quando representamos a recorrência na forma de uma cada representa de um naquele nível chamada da função recursiva Indique a alternativa que preenche corretamente as lacunas ordenação termo o limite assintótico subproblema combinação termo o custo único parâmetro árvore de recursão nó da árvore o custo único subproblema função soma a adição limite assintótico substituição troca o valor único subproblema PERGUNTA 3 Três métodos são comumente utilizados para obter limites assintóticos para recorrência são eles método da substituição método da árvore de recursão método mestre método da recorrência método da árvore de recursão método central método da indução matemática método mestre método central método da substituição método da composição método mestre método da ordenação método da recorrência método da árvore de recursão PERGUNTA 4 Considere o problema da multiplicação de duas matrizes n x n com n sendo uma potência de 2 Neste âmbito podemos afirmar que I a única forma de resolver este problema é através de um algoritmo recursivo II o algoritmo de Strassen apresenta uma forma eficiente para o cálculo do produto de matrizes reduzindo o número de multiplicações de matrizes n2 x n2 de cada subproblema na estratégia de divisão e conquista de 8 para 7 III o melhor tempo de execução para um algoritmo de multiplicação de duas matrizes é Tn θn3 Indique a alternativa correta Nenhuma das afirmações está correta As afirmações I e II estão corretas Somente a afirmação III está correta Todas as afirmações estão corretas As afirmações II e III estão corretas PERGUNTA 5 Em relação à estratégia de divisão e conquista para o projeto de algoritmos podemos afirmar I Às vezes além de subproblemas que são instâncias menores do mesmo problema temos de resolver subproblemas que não são exatamente iguais ao problema original Consideramos a solução de tais problemas como parte da etapa combinar II Nem sempre o problema original será quebrado em metades iguais Assim por exemplo podemos ter equações de recorrência na forma Tn T23n T13 θn ou ainda Tn Tn 7 θ1 III A estratégia de divisão e conquista soluciona problemas maiores dividindoos em problemas menores utilizando a notação assintótica para combinar apropriadamente as suas respostas Indique a alternativa correta As afirmações I e II estão corretas As afirmações I e III estão corretas Todas as afirmações estão corretas Somente a afirmação I está correta Nenhuma das afirmações está correta PERGUNTA 6 Com o intuito de resolver recorrências o método começa supondo para uma recorrência e então usa a para tentar provar que estava correta Indique a alternativa que preenche corretamente as lacunas da árvore de recursão uma árvore expansão árvore da substituição um limite assintótico indução matemática a suposição mestre uma expressão recursão expressão mestre um limitante redução a recorrência ordenação uma sequência ordenação sequência PERGUNTA 7 Em relação ao método da substituição utilizado para determinação de limites assintóticos para recorrências podemos afirmar I O método consiste em assumir inicialmente uma forma para Tn e em seguida utilizar a indução matemática para determinar as constantes e mostrar que a suposição inicial está correta II Em algumas situações uma árvore de recursão pode ser usada para gerar uma boa suposição inicial para Tn que é então verificada pelo método de substituição III O método da substituição e o método mestre consistem basicamente na mesma metodologia sendo comum termos dificuldade de diferenciar uma abordagem da outra Indique a alternativa correta Somente a afirmação II está correta Nenhuma das afirmações está correta As afirmações I e II estão corretas As afirmações II e III estão corretas Todas as afirmações estão corretas PERGUNTA 1 Podemos dizer que um grafo é um conjunto nãovazio de e um conjunto de tais que cada conecta dois Assinale a alternativa que completa corretamente as lacunas acima vértices arestas aresta vértices arestas arcos nós vértices arcos vértices vértice arcos subgrafos arestas aresta subgrafos nós vértices aresta arcos PERGUNTA 2 A utilizada em um algoritmo iterativo que implementa o procedimento pode ser substituída pela levando a construção de um algoritmo Assinale a alternativa que completa corretamente as lacunas acima recursão DFS pilha mais eficiente pilha BFS fila mais eficiente fila DFS pilha recursivo pilha DFS recursas recursivo pilha BFS fila recursivo PERGUNTA 1 Em relação à notação assintótica para análise de algoritmos podemos afirmar I A notação O nos dá um limite superior para o tempo de execução de um algoritmo II A notação Ω nos dá um limitante inferior para o tempo de execução de um algoritmo III 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 Somente a afirmação I está correta Todas as afirmações estão corretas As afirmações II e III estão corretas As afirmações I e II estão corretas Nenhuma das afirmações está correta PERGUNTA 2 Em relação aos modelos computacionais podemos afirmar que são exemplos de modelos computacionais Máquina de Turing Modelo RAM Máquinas de Estados Finitos modelo de Corretude modelo Formal modelo por Indução Máquinas de Turing Máquinas de Estados Finitos Máquinas de estados infinitos modelo restritivo modelo regular modelo assintótico modelo RAM modelo ROM modelo CACHE PERGUNTA 3 Em relação a corretude podemos afirmar I A análise de corretude é utilizada para provar que um algoritmo é capaz de produzir uma resposta correta para qualquer instância de entrada II Basta que exista uma única instância de entrada que não produza uma resposta correta para que o algoritmo não esteja correto III A prova de que um algoritmo está correto normalmente é realizada através da análise assintótica Assinale a alternativa correta Todas as afirmações estão corretas As afirmações II e III estão corretas As afirmações I e II estão corretas Nenhuma das afirmações está correta Somente a afirmação I está correta PERGUNTA 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 complexidade número de linhas de código utilizadas variável de entrada execução eficiência número de passos gastos uma instância de entrada análise corretude tempo assintótico gasto um problema espera velocidade recurso consumido uma constante de entrada análise complexidade custo demandado um problema PERGUNTA 1 Em relação aos algoritmos de ordenação MergeSort e InsertionSort podemos afirmar I O algoritmo MergeSort utiliza a estratégia de intercalação para realizar a ordenação de uma instância de entrada de tamanho n II 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á inserilo em um vetor já ordenado de tal forma que o vetor resultante também esteja ordenado III Uma implementação possível para o algoritmo MergeSort é através do uso de recursão Assinale a alternativa correta Somente a afirmação I está correta Todas as afirmações estão corretas As afirmações II e III estão corretas As afirmações I e II estão corretas Nenhuma das afirmações está correta PERGUNTA 2 Quando um algoritmo contém uma a si mesmo o pode frequentemente ser por uma Assinale a alternativa que completa corretamente as lacunas acima instância referenciada nível de complexidade aumentado instância de tamanho n chamada recursiva tempo de execução descrito equação de recorrência recursão código descrito invariante de laço referência tempo do execução reduzido quantidade n recorrência nivel de complexidade aumentado quantidade adicional de tempo PERGUNTA 3 O de indução matemática é A conclusão é uma da forma para todo inteiro positivo n Assinale a alternativa que completa corretamente as lacunas acima segundo princípio uma recursão equação recursiva Pk1 Pk P1 terceiro princípio indutivo proposição A indução vale primeiro princípio um condicional proposição Pn é verdade primeiro princípio o caso base uma condicional Pn é solução teorema universal solução A indução vale PERGUNTA 3 Em relação ao procedimento de busca em profundidade DFS em grafos podemos afirmar que I ao contrário do BFS que possui tempo de execução O VE sendo V o número de vértices e E o número de arestas do grafo O algoritmo o DFS possui tempo de execução OV² II este procedimento é a base para vários algoritmos como por exemplo algoritmos de exploração em labirintos III o DFS pode ser implementado através de um algoritmo recursivo Assinale a alternativa correta Todas as afirmações estão corretas As afirmações I e III estão corretas Somente a afirmação II está correta Nenhuma das afirmações está correta As afirmações II e III estão corretas PERGUNTA 4 Em relação ao procedimento de busca em largura BFS em grafos podemos afirmar I O procedimento resolve o problema de encontrarmos o caminho mínimo entre um determinado vértice s e todos os outros vértices alcançáveis de um grafo a partir de s II O procedimento BFS constrói uma floresta de busca III A busca em largura é executada em tempo linear Assinale a alternativa correta As afirmações I e III estão corretas As afirmações II e III estão corretas Nenhuma das afirmações está correta Somente a afirmação I está correta Todas as afirmações estão corretas PERGUNTA 5 Em relação às representações de grafos para fins computacionais podemos afirmar I Se G é um grafo não dirigido representado por listas de adjacências a soma dos comprimentos de todas as listas de adjacências é igual ao dobro do número de arestas do grafo II Existem basicamente duas formas de representar grafos como uma coleção de listas de adjacências ou através de uma matriz de adjacências III Na representação por matriz de adjacências os elementos da matriz que possuem valor 0 zero indica ausência de vértice naquela posição Assinale a alternativa correta Todas as afirmações estão corretas As afirmações I e II estão corretas Nenhuma das afirmações está correta As afirmações II e III estão corretas Somente a afirmação I está correta PERGUNTA 6 Suponha a execução do algoritmo BFS aplicada a um vértice s de uma componente conexa de um grafo não conexo onde a componente conexa possui ns vértices e ms arestas sendo que o grafo original possui V vértices e E arestas Então podemos afirmar em relação ao tempo de execução do algoritmo que só é possível afirmar que o tempo de execução é Θnsms só é possível afirmar que o tempo de execução é OVE o tempo de execução é ΘVE não é possível fazer qualquer afirmação com base nas informações fornecidas no problema o tempo de execução é Θnsms e ΟVE PERGUNTA 7 Em relação às terminologias utilizadas em grafos podemos dizer I O grau de um nó é o número de extremidades de arcos naquele nó II Um arco com extremidades no mesmo nó em um grafo forma um ciclo III Em um grafo conexo o número de arestas é sempre a metade do número de vértices ou seja cada aresta conecta dois vértices Assinale a alternativa correta As afirmações II e III estão corretas Todas as afirmações estão corretas Nenhuma das afirmações está correta Somente a afirmação I está correta As afirmações I e II estão corretas Pergunta 1 Todas as afirmações estão corretas Pergunta 2 Máquinas de Turing Máquinas de Estados Finitos Máquinas de Estados Infinitos Pergunta 3 As afirmações I e II estão corretas Pergunta 4 execução eficiência número de passos gastos uma instância de entrada Pergunta 1 Todas as afirmações estão corretas Pergunta 2 chamada recursiva tempo de execução descrito equação de recorrência Pergunta 3 primeiro princípio um condicional proposição Pn é verdade Pergunta 4 As afirmações II e III estão corretas Pergunta 5 Somente a afirmação I está correta Pergunta 6 Todas as afirmações estão corretas Pergunta 1 divisão conquista combinação Pergunta 2 árvore de recursão nó da árvore o custo único subproblema Pergunta 3 método da substituição método da árvore de recursão método mestre Pergunta 4 Somente a afirmação II está correta Pergunta 5 As afirmações I e II estão corretas Pergunta 6 da substituição um limite assintótico indução matemática a suposição Pergunta 7 As afirmações I e II estão corretas Pergunta 1 vértices arestas aresta vértices Pergunta 2 pilha DFS recursão recursivo Pergunta 3 Todas as afirmações estão corretas Pergunta 4 As afirmações II e III estão corretas Pergunta 5 As afirmações I e II estão corretas Pergunta 6 O tempo de execução é Θnsms e OV E Pergunta 7 As afirmações I e II estão corretas Pergunta 1 Todas as afirmações estão corretas Pergunta 2 Máquinas de Turing Máquinas de Estados Finitos Máquinas de Estados Infinitos Pergunta 3 As afirmações I e II estão corretas Pergunta 4 execução eficiência número de passos gastos uma instância de entrada Pergunta 1 Todas as afirmações estão corretas Pergunta 2 chamada recursiva tempo de execução descrito equação de recorrência Pergunta 3 primeiro princípio um condicional proposição Pn é verdade Pergunta 4 As afirmações II e III estão corretas Pergunta 5 Somente a afirmação I está correta Pergunta 6 Todas as afirmações estão corretas Pergunta 1 divisão conquista combinação Pergunta 2 árvore de recursão nó da árvore o custo único subproblema Pergunta 3 método da substituição método da árvore de recursão método mestre Pergunta 4 Somente a afirmação II está correta Pergunta 5 As afirmações I e II estão corretas Pergunta 6 da substituição um limite assintótico indução matemática a suposição Pergunta 7 As afirmações I e II estão corretas Pergunta 1 vértices arestas aresta vértices Pergunta 2 pilha DFS recursão recursivo Pergunta 3 Todas as afirmações estão corretas Pergunta 4 As afirmações II e III estão corretas Pergunta 5 As afirmações I e II estão corretas Pergunta 6 O tempo de execução é Θ𝑛𝑠 𝑚𝑠 e 𝑂𝑉 𝐸 Pergunta 7 As afirmações I e II estão corretas