Grátis: Leia o texto a seguir: Do ponto de vista da complexidade computacional, existem alguns tipos de problemas para os quais não existem algoritmos efic... – Questões Respondidas

Empreendedorismo

Outros

Leia o texto a seguir: Do ponto de vista da complexidade computacional, existem alguns tipos de problemas para os quais não existem algoritmos eficientes para resolvê-los. A maioria desses problemas tem um algoritmo que fornece uma solução, e esse algoritmo é a busca de força bruta. Esse algoritmo, no entanto, não fornece uma solução eficiente e, portanto, não é viável para computação com nada mais do que a menor entrada. A razão pela qual não há algoritmos eficientes para esses problemas é que esses problemas estão todos em uma categoria que poderia ser chamada de “um pouco menos que aleatório”.
Considerando as informações apresentadas, assinale a alternativa correta.
Problemas Intratáveis, os quais geralmente requerem tempos exponenciais de processamento, não podem ser resolvidos dentro de um tempo aceitável.
Problemas Heurísticos, os quais são resolvidos utilizando heurísticas e técnicas de força bruta, não podem ser resolvidos dentro de um tempo aceitável.
Problemas de Parada, os quais geralmente requerem tempos polinomiais de processamento, não podem ser resolvidos dentro de um tempo aceitável.
Problemas Tratáveis, como aqueles de complexidade NP e NP-Hard, não podem ser resolvidos dentro de um tempo aceitável.
Problemas Insolúveis, os quais dificilmente serão resolvidos em um tempo polinomial, não podem ser resolvidos dentro de um tempo aceitável.

EmpreendedorismoInovador

anteontem

EmpreendedorismoInovador

anteontem

Teste_ AO2-6

FAM

Respostas

Ed

anteontem

A alternativa correta é: Problemas Intratáveis, os quais geralmente requerem tempos exponenciais de processamento, não podem ser resolvidos dentro de um tempo aceitável. Esses problemas não têm algoritmos eficientes que possam resolvê-los em um tempo razoável, especialmente à medida que o tamanho da entrada aumenta.

Essa resposta te ajudou?

0

0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Teste_ AO2-6

FAM

Mais perguntas desse material

Leia o texto e observe o código-fonte a seguir: Em Python, podemos utilizar os operadores aritméticos para manipular os dados de variáveis, bem como realizar cálculos - assim como na matemática.
A respeito dessas asserções, assinale a opção correta:
I. O algoritmo apresentado tem a complexidade de tempo O(1), sendo considerada a complexidade de tempo mais eficiente.
II. Ao executar um algoritmo no tempo O(1), não importa o valor do elemento que você está pedindo para a função imprimir, apenas uma etapa é necessária.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições falsas.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.

Leia a descrição a seguir. Digamos que queremos pesquisar um número específico em um array. Considere que essa estrutura de dados possuí 20 números e, dentre eles, queremos encontrar o número 100. Nesse exemplo, pesquisar 20 números não é um problema. Mas imagine que estamos lidando com conjuntos de dados que armazenam informações de perfil de milhões de usuários. Pesquisar cada valor de índice do início ao fim seria muito ineficiente. Especialmente se tiver que ser feito várias vezes.
É correto o que se afirma em:
I. Em uma pesquisa sequencial, cada rodada de pesquisa consiste em um conjunto de dados menor que o anterior.
II. Um algoritmo logarítmico que realiza uma pesquisa binária examina as duas metades de um conjunto de dados.
III. A complexidade logarítmica log n trata de um tipo de algoritmo que torna a computação incrivelmente mais rápida que a complexidade linear.
IV. Localizar uma palavra em um dicionário possui a mesma complexidade de tempo que um algoritmo de busca binária.
I e IV, apenas.
III e IV, apenas.
I e II, apenas.
II e III, apenas.
II e IV, apenas.

Leia o texto a seguir: Um algoritmo é uma lista passo a passo de instruções usadas para executar uma tarefa final. Um bom engenheiro de software considerará a complexidade do tempo ao planejar seu programa. Desde o início, um engenheiro deve considerar um cenário que seu programa pode encontrar e que exigirá mais tempo para ser concluído. Isso é conhecido como a complexidade de tempo do pior caso de um algoritmo.
A respeito dessas asserções, assinale a opção correta:
I. O tempo de execução de uma tarefa constante não mudará, independentemente de qual seja o valor de entrada, sendo representada por O(n), onde O é chamado de Big O.
II. A notação Big O é a métrica mais comum para calcular a complexidade do tempo.
As asserções I e II são proposições falsas.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

Leia o texto a seguir: A técnica de divisão e conquista é dividida em três etapas. Na primeira (dividir), é realizada a divisão do problema em subproblemas menores. Na segunda (conquistar), os subproblemas são resolvidos por chamadas recursivas até a completa resolução. Por fim, os subproblemas são combinados para obter a solução final de todo o problema.
A respeito dessas asserções, assinale a alternativa correta:
I. O algoritmo Merge Sort divide o vetor em duas metades, ordenando-as recursivamente e, finalmente, mescla as duas metades ordenadas. Sua complexidade de tempo é O(n log n).
II. A eficiência e a baixa complexidade de tempo do Merge Sort ocorrem graças ao algoritmo que escolhe um elemento central chamado pivô, o qual ajuda a reorganizar os elementos do vetor.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições falsas.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.

Leia com atenção a definição a seguir: A programação dinâmica é uma técnica que divide os problemas em subproblemas e salva o resultado para fins futuros, para que não precisemos computar o resultado novamente. Os subproblemas são desenvolvidos para otimizar a solução geral, o que é conhecida como propriedade de subestrutura ótima. O principal uso da programação dinâmica é resolver problemas de otimização.
Considerando as informações apresentadas, avalie as afirmacoes a seguir:
I. A programação dinâmica divide o problema complexo em subproblemas mais simples, encontrando a solução para esses subproblemas e armazenando a solução em memória.
II. A complexidade de tempo e a complexidade de espaço aumentam com o uso da programação dinâmica, ao contrário do que vemos nos algoritmos de força bruta.
III. As principais abordagens da programação dinâmica são Top-Down e Bottom-Up.
III, apenas.
I, apenas.
I e III, apenas.
I e II, apenas.
II, apenas.

Leia o texto a seguir: Algumas linguagens de programação, como o Python, possibilitam o desenvolvimento de códigos utilizando estruturas de armazenamento de dados chamada vetores ou arrays. O objetivo desse tipo de estrutura é armazenar mais de um valor em uma região de memória.
Considerando o código apresentado, qual a técnica mais eficiente para realizar a pesquisa do número 6 neste vetor?
Utilizar o algoritmo de quick sort e, em seguida, busca sequencial.
Utilizar o algoritmo de busca sequencial.
Utilizar o algoritmo de merge sort e, em seguida, busca binária.
Utilizar o algoritmo de quick sort e, em seguida, busca binária.
Utilizar o algoritmo de busca binária.

Leia o texto a seguir: Em uma época em que o poder computacional nos cerca, é fácil se confundir com a ideia de que a informação é processada e entregue como mágica. O processamento é algo tão rápido que às vezes esquecemos que milhões de cálculos por segundo estão sendo feitos entre o momento em que solicitamos a informação e o momento em que ela é entregue.
Considerando as informações apresentadas, avalie as afirmações a seguir:
I. Cada instrução de um algoritmo deve ser executada em uma ordem específica para resolver um problema computacional ou não.
II. A complexidade de tempo em uma taxa exponencial significa que, a cada etapa que a função executa, a próxima etapa será executada mais rapidamente.
III. A notação Big O ou Big Ômega é a métrica mais comum para calcular a complexidade do tempo, juntamente com Big Teta.
IV. Um algoritmo de complexidade quadrática requer uma quantidade de tempo ou execução e instruções igual ao quadrado de seu valor de entrada.
I e II, apenas.
II e III, apenas.
I, III e IV apenas.
I e IV, apenas.
III e IV, apenas.