Computer Science and Math

Eres de computación, vas saliendo de una conferencia, coloquio, clase magistral... Y escuchas al tipo que va hablando con la voz más alta posible para que todos puedan escucharlo - ¡Oh sí! NP, NP-hard, Heurísticas, Algoritmos Probabilísticos bla bla bla... 🙄 Ni la cultura ni el conocimiento debería ser privilegio de clase o motivo de ego, ok?   Un problema que es NP-completo es una llave muy importante dentro de la computación ya que resolver un problema de este tipo significaría obtener en automático la solución para otra gran cantidad de problemas, en realidad una familia de problemas; los problemas NP. Dicho de otro modo, un problema NP-Completo es aquel que al resolverlo, resuelve todos los problemas de tipo NP. Pero vamos por pasos. Máquinas de Turing Veamos el siguiente diagrama:     Autómata determinista. Lo anterior es un autómata  y puede entenderse como una simplificación de una máquina de Turing.    A cada q i le llamaremos estado. Los estados del autómata anterior son el

Las siguientes no son definiciones formales sino ideas/nociones generales dadas en lenguaje coloquial o lenguaje no técnico o para poder entender mejor lo que estaré publicando 😊  Se estará actualizando con cada post nuevo. Algoritmo Conjunto ordenado, finito de pasos bien definidos, no ambiguos. Los algoritmos pueden tener datos de entrada y estos datos pueden ser transformados en datos de salida. Un algoritmo es cualquier programa escrito en cualquier lenguaje de programación. Computable Decimos que algo es computable si existe al menos una máquina de Turing que puede realizar esta tarea. Notemos  que esta propiedad es algo fuerte, ya que dado que todas las computadoras existentes hasta ahora trabajan bajo este modelo, si algo es computable significa que puede ser realizado en cualquier computadora existente. Demostración (Dentro de las Matemáticas) Argumento correcto para asentar la veracidad de un enunciado. Dentro del sistema formal de las matemáticas, se pueden hacer afirmacion