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

Páginas: 5 (1192 palavras) Publicado: 2 de abril de 2012
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 doestudo 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 seexiste 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ávelse 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) Citeao menos três relacionamentos entre as classes de solucionabilidade.
R: - A união das classes dos problemas Solucionáveis com a dos Não-solucionáveis é o universo de todos os problemas.
- A união das classes dos problemas Parcialmente Solucionáveis com a dos Completamente Insolúveis é o universo de todos os problemas.
- A classe dos problemas Parcialmente Solucionáveis contém propriamente aclasse dos problemas Solucionáveis e parte da classe dos problemas Não-solucionáveis
- Todo problema Solucionável é Parcialmente Solucionável.
- Existem problemas Não-solucionáveis que possuem soluções parciais.
- Os problemas Completamente Insolúveis não possuem solução total nem parcial

8) Defina: Programas e máquinas.
R: Programas: Um conjunto de operações e testes compostos de acordocom uma estrutura de controle: Monolíticos, Iterativos e Recursivos.
Máquinas: Interpreta Programas e possui uma interpretação para cada operação ou teste que constituem o programa.

9) O que é tese de Church e o que significa para teoria da computação?
R: É uma hipótese sobre a natureza de artefatos mecânicos de cálculo, e sobre que tipo de algoritmos eles podem executar. Traz a importânciade comprovar que a máquina de Turing é o melhor método já criado para testes, e a possibilidade de se verificar o alcance e limites de um computador. 

10) Defina:
a) Função Computável: É possível construir uma Máquina de Turing (ou formalismo equivalente) que compute a função;
b) Função Não-Computável: Não existe Máquina de Turing (ou formalismo equivalente) que compute a função.11) O que é uma Função Recursiva?
R: Uma função recursiva é uma função que se refere a si própria. A idéia consiste em utilizar a própria função que estamos a definir na sua definição. Tem capacidade de chamar a si mesma, chamar outras sub-funções em seqüência, e em algum momento uma dessas funções vai chamar a função principal novamente.

12) O que é estrutura de invocação?
R: É...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Lista de Exercícios de Teoria da Computação
  • Lista de exercicio de computaçao
  • Lista de exercícios
  • Lista de Exercicios Teoria do Consumidor
  • Lista de exercícios: teoria dos conjuntos
  • Lista de Exercícios de Teoria das Filas
  • Lista Exercicios Teoria Assintotica
  • Lista de exercicios- teoria das filas

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!