Lista de exercícios de teoria da computação

1192 palavras 5 páginas
1) Pesquisar: Problema da Parada.
R: Dada uma máquina universal “M” qualquer e uma palavra “W” qualquer sobre o alfabeto de entrada, existe um algoritmo que verifique que “M” para, aceitando ou rejeitando, ao processar a entrada “W”.

2) Pesquisar: Principio da Redução de Problema.
R: Investigar a solucionabilidade de um problema a partir de outro, cuja classe de solucionabilidade é conhecida.

3) Qual é o décimo problema de Hilbert?
R: Conceber um algoritmo que testasse se um polinômio tinha uma raiz inteira. OU Encontrar um algoritmo que determine se uma equação diofantina tem solução.

4) Qual a área de teoria da computação que se baseia em problemas com respostas binárias?
R: Solucionabilidade.

5) Qual o objetivo da área da questão anterior?
R: O objetivo do estudo da solucionabilidade de problemas é investigar a existência ou não de algoritmos que solucionem determinada classe de problemas, ou seja, investigar os limites da computabilidade e conseqüentemente os limites do que pode ser efetivamente implementado em um computador.

6) Quais são as classes de solucionabilidade? Defina.
R: Problema Solucionável: um problema é dito solucionável se existe um algoritmo que soluciona o problema, tal que sempre pára com uma resposta afirmativa ou negativa.
Problema Não-Solucionável: Um problema é dito Não-solucionável se não existe um algoritmo que solucione o problema tal que sempre pare para qualquer entrada.
Problema Parcialmente Solucionável ou Computável: Um problema é dito
Problema Parcialmente Solucionável ou Computável: é solucionável se existe um algoritmo que sempre pare quando a resposta é afirmativa (ACEITA). Entretanto, quando a resposta esperada for negativa, o programa pode parar (REJEITA) ou permanecer processando indefinidamente (LOOP).
Problema Completamente Insolúvel ou Não-Computável: quando não existe um algoritmo que solucione o problema tal que sempre pára quando a resposta é afirmativa (ACEITA).

7) Cite

Relacionados

  • Lista de Exercícios de Teoria da Computação
    543 palavras | 3 páginas
  • Aspectos Teóricos Lista 1
    640 palavras | 3 páginas
  • Modelo de Relatório Laboratório de Física
    1670 palavras | 7 páginas
  • Notas de aula de Teoria da Computação
    31426 palavras | 126 páginas
  • Engenharia de software
    494 palavras | 2 páginas
  • Estudante
    3578 palavras | 15 páginas
  • Sistemas de Informação
    501 palavras | 3 páginas
  • questionario de redes
    4075 palavras | 17 páginas
  • teste
    2297 palavras | 10 páginas
  • Física
    39761 palavras | 160 páginas