Please enable JavaScript.
Coggle requires JavaScript to display documents.
Autómatas (¿QUÉ OTROS FORMALISMOS EQUIVALEN A LAS MÁQUINAS DE TURING? (Los…
Autómatas
-
-
-
Tipos de clases
NP Algoritmos que se resuelven de forma polinomico no determinista; las soluciones pueden comprobarse de forma polinomica
NP COMPLETOS A estos problemas no se les conoce una solucion rapida ; si se descubriera una solucion P para uno de ellos , se podria aplicar a todo NP Problemas NP-C son tratados con heuristica y algoritmos de aproximacion
P Los algoritmos de complejidad polinomica son tratables , abordables en la practica. Como pueden ser comprobados de forma polinomica es subconjunto de NP
Ciclo Hamiltoniano
-
Ciclo Hamilton Inicia y termina en el mismo vértice Recorre todos los vértices sin repetirlo excepto del vértice del cual parte y el que llega
-
-
-
-