Computabilidade

Computabilidade

1. Função e Importância

   • Resolver problemas de forma efetiva.
   • A importância da computabilidade ligada à existência de um algoritmo para resolver o problema.

2. Classificação dos problemas

   • Solucionabilidade
     • 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, consequentemente, os limites do que pode efetivamente ser implementado em um computador. Em particular, o estudo da solucionabilidade objetiva evitar a pesquisa de soluções inexistentes
   • Computabilidade
     • A ideia central da computabilidade é a dos problemas computacionais, que é uma tarefa cuja computabilidade pode ser explorada.
       • tipos de problemas
         • Problemas de decisão
           • Fixam um conjunto S, que pode conter strings, números naturais, ou outros objetos retirados de um conjunto maior U. Uma instancia particular do problema é decidir, dado um elemento de u de U, se u está contido em S. O Teste de Primalidade é um desses exemplos.
         • Problemas de função
           • consistem de uma função f de um conjunto U para um conjunto V. Uma instância do problema é computar, dado um elemento u de U, o elemento correspondente f(u) em V. Por exemplo, U e V podem ser o conjunto de todas as strings binárias, e f pode ser uma função que recebe uma string e retorna a string obtida ao reverter todos os dígitos da entrada (logo, f(0101) = 1010).
     • Problemas de decisão
       • um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não.

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

   • A relação de problema e linguagem é decidível (tratável ou não) se e somente se ele é resolvível por um algoritmo, para qualquer entrada pertencente ao seu domínio; caso contrário ele é um problema indecidível.

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

   • A complexidade e onde se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si. Neste contexto, um problema computacional é entendido como uma tarefa que é, em princípio, passível de ser resolvida por um computador