Classes de solucionabilidade de problemas

Classes de solucionabilidade de problemas

1. 1.Problema solucionável, totalmente solucionável ou decidiível

   • Se existe um algoritmo(máquina universal) que solucione o problema tal que sempre pare para qualquer entrada com resposta afirmativa (aceita) ou negativa (rejeita).
     • Equivale a classe das linguagens recursivas
       • Não fica em LOOP
     • Função total
       • Cada entrada tem uma saída (decidível)
       • Tem sempre um resultado
       • Não entra em LOOP, NUNCA!

2. 2. Problema parcialmente Solucionável ou Computável

   • Se existir um algoritmo (máquina universal) tal que para quando a resposta é afirmativa(ACEITA) e quando a resposta é negativa pode parar em (REJEITA) ou Permanecer em LOOP infinito.
     • Equivale a classe das linguagens Enumeráveis Recursivamente
     • Relacionado com função Parcial

3. 3. Problema não solucinável ou não decidível

   • Se não existe um algoritmo (máquina universal) tal que pare para todas as entradas.
     • Exemplo
       • Detector universal de Loops (Problema da parada)
       • Equivalencia de Compiladores
       • Detecção de ambiguidade em GLC´s
       • Não tenho um programa que faça isso!

4. 4. Problema completamente insolúvel ou não computável

   • Se não existe um algoritmo( máquina universal) que solucione o problema tal que pare quando a resposta é afirmativa.
     • Só quero garantir aceitação nesse caso
     • Relaciona-se com função parcial

5. TIPOS DE PROBLEMAS

   • Problemas de decisão
     • Sim
     • Não
     • Exemplos:
       • Circuito Hamiltoniano
         • Quero os "nós"
       • Circuito Euleriano
         • Pontes de Konisberg
   • Problema de localização
     • Visa encontrar uma solução viável
       • Qualquer solução que solucione o problema, não necessariamente a melhor
   • Problema de Otimização
     • Visa encontrar uma solução ótima dentre todas as soluções possíveis
       • Problema de Cobertura de Vértices
       • Problema de Cobertura Mínima de vértices
       • Àrvore Geradora Mínima
         • Prim
         • Kruskal
   • Solucionáveis
     • Tratável
       • Polinomial
     • Intratável
       • Exponencial