Elementos da Teoria da Computação

Elementos da Teoria da Computação

1. Relação dos problemas (de Decisão) e as linguagens formais

   • 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).
   • Tradicionalmente, é comum definir-se o problema de decisão em termos do conjunto de entradas para as quais o problema retorna 'sim'. Nesse sentido, um problema de decisão é equivalente a uma linguagem formal.
   • Se existir um algoritmo que receba como entrada um elemento x e retorne como saída 'sim', caso x pertença ao conjunto A, ou 'não', caso contrário, então diz-se que o problema de decisão para o conjunto A é decidível. Do contrário, se não existir um algoritmo capaz de fazer essa avaliação, então diz-se que o problema de decisão para o conjunto A é indecidível.

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

   • Complexidade
     • Pode ser definida como: Tempo de execução do algoritmo determinado pelas instruções executadas :quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n;
   • Espaço
     • Pode ser definido como: Espaço de memória utilizado pelo algoritmo : quanto “espaço de memória/disco” é preciso para armazenar a(s) estrutura(s) utilizada(s) pelo algoritmo.

3. Problemas de Decisão

   • ano 1928: Se define como a existência de um procedimento mecânico capaz de decidir se dado enunciado (proposição) da lógica de primeira ordem seria válido ou não, em um tempo finito.
   • ano 1936: Começou a apresentar resultados a partir das pesquisas de Alonzo Church (não existe algoritmo via Funções Recursivas que decida se duas expressões em Cálculo Lambda são equivalentes ) e Alan Turing (contribuiu na resolução do Problema da Decisão transformando em Problema da Parada em sua máquina).
   • ano 1970: Declarado/ provado que tal algoritmo (problema de Decisão) não existe, tornando-se, impossível de ser 'implementado'.
   • Parte do sucesso do 'Problema de Decisão', foi chamado de Técnica de redução, o qual transforma partes de um problema em outro, para assim usa-los em resultados já conhecidos para obter resolução de partes do problema atual e, assim, resolvê-lo).

4. Computabilidade

   • É a habilidade de resolver problemas de forma efetiva. Sendo assim, nasceu do propósito de solucionar problemas matemáticos através de meios finitos.
   • Seu Objetivo é determinar a solucionabilidade dos problemas. Sendo assim, investigar a existência de algoritmos para solucionar determinada classe de problemas.
   • Sua importância para a computação é determinar oque pode ou não ser computado, ou seja, oque pode ou não ser implementado em um computador.

5. Classificação de Problemas

   • Solucionabilidade
     • Objetiva evitar a pesquisa de soluções inexistentes de problemas
   • Tipos de problemas
     • Solucionaveis
       • Um problema é dito Solucionável ou Totalmente Solucionável se existe um algoritmo (Máquina Universal) que solucione o problema tal que sempre pára para qualquer entrada, com uma resposta afirmativa (ACEITA) ou negativa (REJEITA) .
     • Não- solucionáveis
       • Um problema é dito Não-Solucionável se não existe um algoritmo (Máquina Universal) que solucione o problema tal que sempre pára para qualquer entrada.
     • Parcialmente Solucionáveis
       • Um problema é dito Parcialmente Solucionável ou Computável se existe um algoritmo (Máquina Universal) que solucione o problema tal que pare quando a resposta é afirmativa (ACEITA). Entretanto, quando a resposta esperada for negativa, o algoritmo pode parar (REJEITA) ou permanecer processando indefinidamente (LOOP).
     • Indecidíveis
       • Nenhum algoritmo é capaz de resolver
     • Intratáveis
       • Possivelmente não possuem algoritmos polinomiais
     • Tratáveis
       • Possuem algoritmos polinomiais