Please enable JavaScript.

Coggle requires JavaScript to display documents.

M14 (Levitin) - Coggle Diagram

- - - - Problemas tratáveis - são aqueles que podem ser resolvidos em tempo polinomial, isto é, existe um algoritmo capaz de solucioná-lo com eficiência temporal em O(p(n)), em que p(n) é um polinômio em função do tamanho n da entrada
        
        Em geral, os polinômios dessa categoria não passam da ordem 3
        
        Nessas categorias, normalmente são estudados os chamados Problemas de Decisão
        
        São problemas de resposta binária, isto é, sim/não, true/false. Tratam portanto de provar se algo é ou não possível de ser alcançado
        
        É extremamente útil converter para essa categoria problemas que normalmente não seriam de decisão, pois simplificando o objetivo do algoritmo, podem simplificar também a sua execução
        
        Podem-se de 2 tipos:
        
        Decidíveis, ou seja, que podem ser solucionados por um algoritmo
        
        Dependendo de como esses problemas são abordados pelos seus respectivos algoritmos, podem ser categorizados em 2 grupos:
        
        Problemas determinísticos, os quais são solucionados por meio de algoritmos determinísticos, isto é, algoritmos que encontram a solução exata com todos os casos possíveis de saída para todas as entradas possíveis. Ou seja, em problemas de decisão é capaz de retornar sim/não após encontrar todos os resultados possíveis para qualquer entrada fornecida
        
        2 more items...
        
        Problemas não determinísticos, os quais são "solucionados" por algoritmos não determinísticos, isto é, algoritmos que são capazes de verificar apenas se a entrada é satisfazível. Dessa forma, para problemas de decisão, eles retornam sim/não após encontrar um número limitado de resultados possíveis, considerando separadamente "candidatos" a possíveis soluções
        
        2 more items...
        
        Indecidíveis, ou seja, que não podem ser solucionados por nenhum algoritmo
        
        Ex.: Problema da parada proposto por Turing
      - Problemas intratáveis - são aquele que não podem ser resolvidos em tempo polinomial, isto é, não existe um algoritmo capaz de solucioná-lo com eficiência temporal em O(p(n)), em que p(n) é um polinômio em função do tamanho n da entrada
        
        Ex.s: Encontrar todos os subconjuntos de um conjunto com n elementos; encontrar todas as permutações de n elementos distintos