En las Ciencias de la Computación teórica, vemos a las computadoras como algo más amplio; para esta ciencia, una computadora no es solo una máquina artificial, sino que pueden ser flores, personas, sistemas sociales, los mercados financieros, etc. Todo lo que se ve en la naturaleza se entiende como una entidad computacional, una secuencia de pasos finita, que evoluciona de un estado a otro. El objeto de estudio de la teoría de la computación son las capacidades y límites de la computación en la naturaleza; originalmente iniciada en las matemáticas puras, e inspirada en la forma de pensar de un matemático como una máquina. Así, podemos estudiar las capacidades que tenemos para demostrar teoremas, como si fuera una máquina. En síntesis, se estudian los fundamentos teóricos de la computación, qué es lo que se puede hacer, digamos, en nuestra vida real.
El proyecto “PINV15-0208 Grafos y Complejidad Computacional” es un proyecto de Investigación Institucional, cofinanciado por el Consejo Nacional de Ciencia y Tecnología – Conacyt Paraguay y la Facultad Politécnica de la UNA.
Objetivo General del Proyecto
Realizar investigación básica y aplicada en teoría de grafos y complejidad computacional.
Resultados Esperados
1. Creación y fortalecimiento del primer grupo de investigación en la UNA en Teoría de la Computación.
2. Cursos cortos en Teoría de la Computación y las investigaciones realizadas en este proyecto.
3. Seminarios en teoría de la computación.
4. Artículos publicados en proceedings de conferencias.
El Dr. Marcos Villagra*, Investigador Principal del proyecto, nos explica en qué consiste este trabajo que está en plena implementación:
Este es un proyecto de fortalecimiento, y es la primera vez que se adopta una línea de investigación en Teoría de Computación en Paraguay. Comenzamos este proyecto en conjunto con el Dr. Eduardo Canale, profesor de la FP-UNA y de la Universidad de la República de Montevideo.
Normalmente, la gente confunde Teoría de la Computación con Informática. La Ciencia de Computación Teórica es un área de las Matemáticas Puras, que sigue las ideas originales de Alonzo Church, Kurt Gödel y Alan Turing. El proyecto está enfocado en fortalecer esta línea de investigación, lo cual significa: tener un fondo de dinero, a través de Conacyt, para poder realizar publicaciones y presentaciones en conferencias internacionales, realizar colaboraciones internacionales, y capturar estudiantes para formarse en esta línea de investigación financiando sus estudios de grado, maestría y doctorado.
Cuando menciona las ideas de Turing y demás estudiosos, ¿a qué ideas se refiere?
Alan Turing y sus colegas trataban de responder uno de los problemas principales del milenio que fueron formulados por David Hilbert en 1900, en una conferencia de matemáticas muy famosa. Ese problema era conocido como “El décimo Problema de Hilbert”, y es un problema matemático: Si yo te doy un polinomio, y los coeficientes del polinomio son coeficientes racionales, la pregunta es: “¿existe o no un método para determinar si este polinomio, que se llama ‘Ecuación diofántica’, tiene o no raíces que son números enteros?”. Esto es: “yo te doy un polinomio y estos son tus coeficientes; ¿tiene o no raíces enteras?”. (Números enteros son: 1, 2, 3, -1, y número que no es entero, es ½, por ejemplo).
Las “Raíces” son las soluciones del polinomio. Entonces, en base a eso, Turing, Church y otros, motivados por este problema, comenzaron a estudiar cómo responder esta pregunta, e idearon y comenzaron lo que hoy se conoce como la “Ciencia de la computación”. Eventualmente, esto llevó a la revolución de las computadoras, y vino la informática y todo lo que hoy en día tenemos en el día a día.
Para responder esta pregunta, Turing y sus colegas establecieron las bases para que esa pregunta se pueda responder, a través de un artículo muy famoso de 1936: "On Computable Numbers, with an Application to the Entscheidungsproblem":
Así, se descubrió lo que hoy se conoce como “La máquina de Turing”. Esto posibilitó que, 70 años después de la conferencia de David Hilbert, se pudiera resolver el décimo problema de Hilbert con una respuesta negativa.
 |
| Obtenido de: https://www.researchgate.net/figure/Schematic-illustration-of-a-Turing-Machine_fig1_268509885 |
¿Qué es la máquina de Turing?
Lo que la hace la máquina de Turing es modelar todas las posibles computaciones que podemos pensar nosotros, y que existen en el mundo; por ejemplo, las computadoras digitales. En las Ciencias de la Computación teórica vemos a las computadoras como algo más amplio; para esta ciencia, una computadora no es solo una máquina artificial, sino que pueden ser flores, personas, sistemas sociales, los mercados financieros, etc. Todo se ve como una entidad computacional, una secuencia de pasos finita, que va de un estado a otro estado y, eso, es lo que Turing modeló con su máquina.
Entonces, hoy con estas ideas, se pudo responder a la pregunta de David Hilbert con una respuesta negativa: no existen métodos o algoritmos para saber si las ecuaciones diofánticas tienen raíz entera o no. Esto, originó lo que hoy se conoce como la “Teoría de la computación”, la cual, actualmente, tiene muchas ramas y muchas especialidades que permean toda la matemática pura y aplicada.
El objeto de estudio fue, originalmente, entender los límites de las matemáticas, en donde se ve a la forma de pensar de un matemático como una máquina. Entonces, se estudian las capacidades que tenemos para demostrar teoremas, como si fuera una máquina y, eso, lo modelamos a través de la Máquina de Turing. Hoy en día, se extiende a otras ramas de la ingeniería y las ciencias, como por ejemplo: Análisis de datos, Teoría de grafos, Redes de computadoras, Sistemas de resolución de sistemas algebraicos, Teoría de algoritmos, que tienen importancia no solo en Ingeniería en Informática, ya que es importante en todos lados. La Teoría de la computación es la base del mundo moderno, de la computación y el procesamiento de la información. Estudia los fundamentos teóricos de la computación, que es lo que se puede realizar computacionalmente en la vida real.
Entones, este tipo de investigaciones, permite que se sienten las bases para poder simular modelos…
Todo lo que hacen los modelos computacionales tienen como base teórica a la Teoría de la Computación; es como la “Física de la computación”, si querés expresarlo de cierta forma. Lo que estudiamos nosotros son las “leyes computacionales” que permiten que estos modelos computacionales funcionen. Son aplicaciones, pero lo nuestro es más académico; es decir, estudiamos qué se puede hacer y qué no se puede hacer con la computación que tenemos disponible. Y la computación que tenemos disponible actualmente, por ejemplo, son las computadoras digitales: entonces, nos preguntamos qué podemos hacer y qué no podemos hacer con estas computadoras que tenemos en nuestras oficinas. También, podemos pensar en modelos de computadoras más complejos, tecnologías que existen o pueden llegar a existir en el futuro, como la computación cuántica o computación molecular basada en ADN, etc., y nos preguntamos qué pueden hacer estas hipotéticas computadoras y qué no pueden hacer, pero desde un punto de vista académico-teórico.
Si se demuestra, por ejemplo, que “la computadora no puede hacer esto”; entonces, en la vida real tampoco vas a poder hacer. Saber si el algoritmo de tu sistema operativo se va a colgar o no, ese es un problema que a todo el mundo le pasa y le gustaría saber, y nosotros sabemos que no podemos detectar eso. Tenemos teoremas matemáticos que nos dicen: “eso es imposible de saber”.
 |
| Prof. Dr. Marcos Villagra, Investigador Principal |
La Teoría de la Computación: el punto de partida.
Lo nuestro es mucho más académico. Te voy a dar una explicación práctica: para usar un cajero automático, hay “protocolos criptográficos”. Estos protocolos son algoritmos que te permiten introducir tu PIN y saber que, cuando eso se va a una computadora, nadie va a estar mirando cuál es tu PIN, y vas a poder retirar la cantidad de dinero que pediste y no se te va a sacar más dinero de lo que querés sacar de tu cuenta, de manera segura y confiable. El área que estudia estos algoritmos de control que se encargan de que todo eso suceda en forma segura y confiable se llama “Criptografía”, la cual es una sub-área de la Teoría de la Computación. Este mecanismo, llamado criptografía de clave pública, que hace que todo esto funcione, se originó a finales de los 70 con los famosos artículos de Diffie, Hellman (1) y Merkle (2) .
Ellos diseñaron matemáticamente cómo estos sistemas tienen que funcionar para que todo sea seguro. Y en esa época, es decir, cuando se descubrió esto a finales de los 70, era todo teoría matemática, hasta que se demostró experimentalmente que estos trabajos sí se pueden hacer, y los ingenieros lo implementaron. Entonces, esto es algo que hoy en día está en todos lados; es muy difícil concebir nuestro moderno sin la criptografía; para leer tu correo electrónico también necesitás de esto. Los principios de funcionamiento de la criptografía de clave pública se basan y dependen fuertemente de la Teoría de la computación; en una idea que llamamos “indistinguibilidad” en complejidad computacional, la cual -de vuelta- está basada en las ideas de Turing, ya de los años 30.
Sobre los resultados esperados del proyecto, uno de ellos, es la conformación de un grupo de investigación que trabaje en esta línea…
El Grupo de Investigación en Teoría de la Computación – GITOC ya está conformado y oficializado por la Facultad Politécnica, según la Resolución del Consejo Directivo 16/30/07-00 Acta 985/07/11/2016.
Tenemos:
2 estudiantes de doctorado: Pedro Villalba y Cristhian Martínez.
3 estudiantes de maestría: Fabricio Mendoza-Granada, Sergio Mercado y Marcos Ibarra, y
2 de iniciación científica: Tadashi Akagi y Carlos Ruíz Díaz.
 |
| De izquierda a derecha: Lic. Johana Pineda, Ms. Pedro Villalba, Dr. Marcos Villagra, Lic. Fabricio Mendoza-Granada y Lic. Marcos Ibarra, integrantes del GITOC. |
"Siempre estamos organizando seminarios abiertos en Teoría de computación; sabemos que no es muy popular por lo que queremos mejorar nuestro marketing".
 |
| Prof. Pablo Romero, Jornada de Grafos y Computación, 3 al 12 de setiembre 2019. Facultad Politécnica UNA, Campus de la UNA, San Lorenzo. |
 |
| Estudiantes de grado, maestría y doctorado en Ciencias de la Computación junto a expositores. Jornada de Grafos y Computación, 3 al 12 de setiembre 2019. Facultad Politécnica UNA, Campus de la UNA, San Lorenzo. |
Publicaciones
Nuestros resultados (de investigación) son las publicaciones científicas hechas en el área que, desde el 2016, empezaron ya a salir con firma de afiliación de la Universidad Nacional de Asunción del Paraguay.
En este proyecto, tenemos 6 publicaciones en conferencias internacionales con revisión por pares, una en revista indexada internacional, y un capítulo de libro. Tenemos otra conferencia pendiente, y otros dos artículos ya sometidos para evaluación en revista indexada internacional y, al menos, otros dos artículos más en preparación.
Ya va a salir también una tesis de grado, por primera vez en el área: de Tadashi Akagi, estudiante de Ingeniería Informática de la FP-UNA, que realizó su defensa técnica el 6 de setiembre. También ya van a salir tres tesis de maestría para el año 2020 y, en el futuro, la tesis doctoral de Pedro Villalba.
Acceso a los trabajos de investigación:
¿Algo más que agregar?
Casi todos nuestros artículos los tenemos en acceso gratuito, por una cuestión de ética; y yo, también insisto mucho en esto. Utilizamos un repositorio de acceso abierto, llamado arXiv, en donde ponemos versiones preliminares antes de pasar por el filtro de las revistas. Pero, nosotros sabemos que la versión que ponemos es una versión ya casi final de acceso abierto y gratuito a la que todos pueden acceder. A nosotros nos pagan con dinero del estado, y no es justo que la persona que quiera leer, un paraguayo que quiera leer, otra vez tenga que volver a pagar por algo que ya pagó. Entonces, por eso, lo hacemos de esa manera; eso se llama Open science. Por supuesto, también contamos con valiosa colaboración de colegas de Argentina, Letonia, India, Japón, y otros, que trabajan con nosotros.
Es importante resaltar que todos nuestros artículos están indexados en los mejores índices tales como Scopus, Web of Science, Scimago, JCR, etc. En Matemáticas, para nosotros, los más importantes son Mathscinet https://mathscinet.ams.org de la AMS de USA, y zbMATH https://zbmath.org de Austria, por ejemplo.
Los objetivos que nos hemos trazado en el proyecto han sido superados. Por ejemplo, prometimos dos conferencias internacionales, hicimos 6, y van a venir más. Y encima, también tenemos publicaciones en revistas, libros y más artículos sometidos a otras dos revistas más.
Creo que para un grupo tan pequeño como nosotros, en matemáticas, nos consideramos productivos. En Paraguay, lamentablemente, creo que no hay otros grupos de investigación que publiquen en teoría de la computación. Por ahora, creo que somos los únicos, pero esperamos cambiar eso en el futuro.
Por último, la Teoría de la computación es una materia que normalmente se enseña en una carrera de Ingeniería Informática en Paraguay, pero históricamente se enseñaba y se sigue enseñando mal. Acá en la FP-UNA, no tenemos un curso así, por el momento, pero otras universidades sí lo tienen. Me consta que se enseña mal porque no hay personas capacitadas para enseñar estos contenidos (docentes sin postgrados y sin publicaciones en el área), y los estudiantes terminan odiando y sin apreciar la materia porque el docente no entiende de lo que habla. Ahora, por suerte siguen llegando gente especializada de afuera, como el Dr. Sebastián Grillo de la UAA, con quien estamos tratando de generar una masa crítica en el área para que, en el futuro, podamos contar con docentes especializados y se enseñe bien esta materia.
Áreas de investigación del GITOC
Teoría de la Computación
Complejidad algebraica
Teoría de números computacionales
Computación cuántica: fundamentos (por qué esto funciona así; se puede por ejemplo simular por computadora la física cuántica o no eficientemente. Es un problema que mucha gente quiere saber)
Teoría de autómatas
Semigrupos, mucha álgebra, mucha combinatoria también y mucha teoría de grafos. Nos movemos en todas esas áreas.-
Equipo de trabajo
Ms. Pedro Villalba, Director del Proyecto
Dr. Marcos Villagra, Investigador Principal
Acceder a currículum:
Referencias:
(1), Whitfield; Hellman, Martin E. (November 1976). "New Directions in Cryptography" (PDF). IEEE
Transactions on Information Theory. 22 (6): 644–654. CiteSeerX 10.1.1.37.9720.
doi:10.1109/TIT.1976.1055638
(2), Ralph C. (April 1978). "Secure Communications Over Insecure Channels". Communications of
the ACM. 21 (4): 294–299. CiteSeerX 10.1.1.364.5157. doi:10.1145/359460.359473. Received
August, 1975; revised September 1977