Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos - Coggle Diagram
Algoritmos
Problemas decidíveis, mas intratáveis.
-
-
-
-
-
-
-
Crescimento exponencial de opções, em função do tamanho do input, a partir do qual uma solução precisa ser encontrado.
-
Um algoritmo não determinístico é um procedimento de dois estágios que
toma como entrada uma instância I de um problema de decisão e faz o seguinte.
Estágio não determinístico ("adivinhação"): Uma string arbitrária S é gerada que pode ser pensada como uma solução candidata para a instância I dada (mas pode ser jargão completo também).
Estágio determinístico ("verificação"): Um algoritmo determinístico leva tanto I e S como sua entrada e saídas, se S representar uma solução para a instância I. (Se S for não é uma solução para a instância I, o algoritmo não retorna ou não pode pare totalmente.)
Dizemos que um algoritmo não determinístico resolve um problema de decisão se e
somente se para cada instância positiva do problema ele retornar uma resposta positiva em alguma execução
-
-