Questões de Computabilidade

Explore questões resolvidas de Computabilidade. Acesse respostas e explicações detalhadas para estudar e evoluir.

78% confiança
Problemas incomputáveis não podem ser resolvidos por algoritmos com um número finito de passos. Marque V para verdadeiro e F para falso para as afirmações a respeito dessa categoria de problemas: ( ) Problemas que não podem ser resolvidos em uma máquina de Turing podem ser resolvidos via cálculo lambda. ( ) Se dois programas computam o mesmo resultado para qualquer entrada, então eles processam a mesma linguagem. ( ) Um problema que pode ser resolvido por um algoritmo computacional pode ser resolvido por uma máquina de Turing. ( ) A versão mais eficiente de um algoritmo pode ser obtida por meio de uma máquina de Turing com fita de tamanho infinito. Assinale a alternativa que apresenta a sequência correta:
computabilidade computacao maquinas-de-turing
88% confiança
A solução para dado problema pode ser obtida por meio da descrição de um algoritmo que o resolva. Para isso, no entanto, é fundamental que se analise a computabilidade do problema. Sobre o conceito de computabilidade, leia as assertivas a seguir. I. Se um problema em um cenário prático é dito computável, então qualquer algoritmo que o resolva pode ser empregado. II. Um algoritmo de complexidade O(cn) é dito intratável, já que o seu tempo de resposta é inviável para um problema prático. III. Algoritmos que resolvem problemas incomputáveis têm complexidade de tempo inviável para situações práticas. IV. Um algoritmo com complexidade O(n!) é menos eficiente do que qualquer algoritmo para problemas tratáveis. Quais estão corretas?
complexidade-de-algoritmos computabilidade computacao