Teoria da Computação

Teoria da Computação

1. Computabilidade

   • É a capacidade de resolver eficientemente os problemas.
   • A sua função é determinar quais problemas podem ser computados, utilizando um modelo formal.
   • A sua importância é determinar o que pode ou não ser resolvido computacionalmente.

2. Classificação de Problemas

   • Solucionabilidade
     • Tem como propósito evitar a pesquisa de soluções inexistentes para problemas.
   • Tipos de problemas
     • Solucionáveis.
       • São aqueles que podem ser resolvidos por um modelo computacional existente.
     • Não solucionáveis.
       • São aqueles que não podem ser resolvidos por um modelo computacional existente.
     • Parcialmente solucionáveis.
       • São aqueles que possem partes que podem ser solucionadas por um modelo computacional existente, e que normalmente um problema desse tipo é dividido em sub-problemas que podem ser ou não solucionáveis.

3. Problemas de decisão

   • Esse tipo de problema serve para determinar se um determinado elemento de algum universo pertence ou não a um determinado conjunto ou se satisfaz alguma propriedade. Um exemplo pode ser possível dividir dois números, x e y.

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

   • Um problema de decisão pode ser representado como uma linguagem formal, onde os membros pertencentes á linguagem retorna como resposta um "sim" e os membros não pertencentes à linguagem retorna como resposta um "não".

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

   • A análise matemática de um algoritmo fornece uma medida de desempenho proporcional ao tempo de execução e podem ser classificadas por
     • Tempo, ou seja, analisa o tempo necessário para computar o resultado de uma instância de um problema de tamanho n.
     • Espaço, ou seja, a quantidade de memória será necessária para armazenar as estruturas utilizadas pelo algoritmo.