El objetivo central de esta área es entender, formalizar y estudiar los procedimientos mecánicos, conocidos como algoritmos, que son utilizados al resolver un problema.
Para estudiar la noción de algoritmo, primero necesitamos un modelo matemático que sea capaz de formalizar este concepto. El modelo matemático clásico de algoritmo está constituido por las Máquinas de Turing, las cuales son máquinas de estado, con memoria y con una función de transición que indica cómo cambiar el estado y el contenido de la memoria de la máquina. Una vez formulado un modelo de computación, nos interesa conocer la cantidad de recursos computacionales que es necesario utilizar para resolver un problema. El primero de estos recursos es el tiempo: cuántos pasos o cuantas acciones debemos realizar para resolver el problema. También son importantes el espacio ocupado, la necesidad de utilizar una fuente de números aleatorios, la posibilidad de resolver sub-problemas en paralelo, entre otros. La formalización de un modelo de computación como objeto matemático nos permite expresar de manera precisa preguntas sobre problemas o algoritmos. En particular, si L es un problema. ¿Puede L ser resuelto por un algoritmo? ¿Puede ser L resuelto de manera eficiente? ¿Cómo podemos construir un algoritmo eficiente para L? ¿Es L un problema para el cual no existe un algoritmo que lo resuelva? Es importante destacar que el modelo de la Máquina de Turing es equivalente al computador moderno, por lo que una demostración matemática de que un problema no puede ser resuelto de manera eficiente en una Máquina de Turing nos da como consecuencia que este problema no puede ser resuelto de manera eficiente con los computadores que usamos hoy en día.
El área de teoría de la computación es particularmente interdisciplinaria, nutriéndose de cualquier otra área donde un problema deba ser resuelto por un algoritmo, tales como ingeniería, economía, matemáticas, biología y química, entre muchas otras.
Dentro de las sub-áreas y aplicaciones de teoría de la computación que son activamente investigadas en el IMC, podemos destacar:
Complejidad descriptiva: se estudia la complejidad de un problema en términos del lenguaje que es necesario utilizar para definirlo. En particular, distintas lógicas matemáticas son utilizadas como lenguajes para describir problemas.
Complejidad de lenguajes lógicos: se estudia la cantidad de recursos computacionales necesarios para evaluar una fórmula en una lógica matemática.
Expresividad de lenguajes lógicos: se estudia lo que puede ser expresado (o definido) en una lógica matemática, lo que permite entender el poder de esta lógica como modelo de computación.
Teoría de autómatas: se estudian modelos computacionales de menor complejidad basados en la idea de máquinas de estado con memoria limitada (o sin memoria). Estos modelos tienen buenas propiedades matemáticas y algorítmicas, siendo parte fundamental en el diseño e implementación de compiladores, verificación de sistemas, bases de datos, sistemas distribuidos, entre otros.
Fundamentos de manejo de datos: se estudian las bases matemáticas que modelan las diferentes tareas y aplicaciones relacionadas con el manejo de datos, lo cual requiere de la utilización de las técnicas y problemas mencionadas en los puntos anteriores.
Los profesores en el área de teoría de la computación son:
-
Marcelo Arenas, Departamento de Ciencia de la Computación, Escuela Ingeniería UC.
-
Juan Reutter, Departamento de Ciencia de la Computación, Escuela Ingeniería UC.
-
Cristian Riveros, Departamento de Ciencia de la Computación, Escuela Ingeniería UC.
-
Domagoj Vrgoc – Departamento de Ciencia de la Computación, Escuela Ingeniería UC
