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...

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 a...

Sí, se demostró con cardinalidades entre conjuntos. Hoy voy a hablar de algo que me dejó consternada por un rato. Un día estaba leyendo la demostración, pensé que quizá si hubiera estado con mis compañeros también  hubieran sentido algo al enterarse del resultado... Luego recordé que quizá pensarían en cómo la demostración empoderaría a la clase trabajadora y yo aquí con tonterías pseudotrascendentales. (Facultad de Ciencias, Socialist Icon 💖)  En fin, empecemos.   Problemas de decisión Dentro de la Teoría de la Computación un problema de decisión es aquel donde la salida del algoritmo sólo es Sí o No, 0 o 1, True o False, o algún equivalente Por ejemplo, decidir si una gráfica es conexa o no, es un problema de decisión Supongamos que fuera posible pasar cada una de todas las infinitas gráficas posibles como input al algoritmo. Luego de eso podríamos ver a las infinitas gráficas separadas en dos conjuntos. Definiremos a L como el conjunto que contiene a todos los elemen...

Sean algunos algoritmos Árbol generador de peso mínimo Regresiones Cadena común más larga Page Rank Runge-Kutta Recorrido de un grafo por profundidad (DFS) Y los algoritmos fueron... Sabemos que los algoritmos existen y que la implementación de algunos es sencilla de encontrar en internet. Intuitivamente sabemos que podemos pensar en un algoritmo y con suficiente abstracción podemos implementarlo en algún lenguaje de programación. Un día quizá después de programar suficiente (o no) nacen las preguntas ¿qué algoritmo no puedo programar? ¿existe siquiera alguno que no pueda programar? Tengo este algoritmo ¿es posible programarlo? Dentro de la computación teórica existe el concepto de computabilidad, éste se encarga de estudiar lo anterior. Máquina de Turing (MT) Es una propuesta de Alan Turing hecha en 1936 en su artículo "On computable numbers, with an application to the Entscheidungsproblem", es un modelo teórico de computación en el cual están basadas todas las computadora...

Inicialmente pensé en iniciar una especie de taller para mostrar a compañeros de las licenciaturas de Física, Matemáticas, Actuaría e interesados en programación competitiva temas de Teoría de la Computación, pensé que podría serles útil en su travesía. Cambié la idea de un taller porque pensé que no habría suficiente espacio para divagar sobre el tema y verlo desde la perspectiva meta que me gustaría. Miento si digo que esa era mi única motivación. Verán, mi otra motivación viene a partir de que mi primer año de universidad está resumido en la frase " Excuse me professor, but what in Jesus’ name are you fucking talking about? ", pero eventualmente cambió a algo más positivo. Así que dado que tengo la sensación de una visión más clara, quisiera abordar los temas desde una perspectiva diferente y escuchar qué significan los resultados en el área para otras personas. Significado en un sentido humano, ¿qué significa ese resultado sobre nosotros los humanos y qué dice sobre ...