TEORIA DA COMPUTAÇÃO

TEORIA DA COMPUTAÇÃO

1. Computabilidade

   • Computabilidade é a habilidade de resolver problemas de forma efetiva
   • Têm como função determinar quais problemas podem ser computados a partir de um modelo computacional
   • Sua importância se dá quando determinamos o que pode e o que não pode ser implementado por um computador

2. Classificação dos problemas

   • Solucionabilidade
     • Tem como objetivo evitar a pesquisa de soluções inexistentes para problemas
   • Tipos de problemas
     • Solucionáveis
     • Não-solucionáveis
     • Parcialmente solucionáveis

3. Problemas de decisão

   • Os problemas de decisão são problemas de determinar se um determinado elemento de algum universo pertence ou não a um determinado conjunto (ou equivalentemente, se satisfaz uma determinada propriedade). Por exemplo, o problema: "dados dois números x e y, y é divisível por x?" é um problema de decisão.

4. Relação dos problemas e as linguagens formais

   • Um problema de decisão pode ser visto como uma linguagem formal, onde os membros pertencentes à linguagem são instâncias cuja resposta é sim, e os membros não pertencentes à linguagem são instâncias cuja resposta é não

5. Classificação por complexidade e por espaço

   • A análise do algoritmo fornece uma medida objetiva de desempenho proporcional ao tempo de execução
   • Tempo
     • Quanto tempo é necessário para computar o resultado para uma instância do problema de tamanho n
   • Espaço
     • Quanto espaço de memória/disco é preciso para armazenar as estruturas utilizadas pelo algoritmo