Page 16 - Revista FIUDE 2014

Artículo Central

Un pantallazo a la Teoría de los Autómatas

Introducción a la Teoría de la Computación

Ing. Ariel Ron

Especialista en el desarrollo de aplicaciones en .NET, funda-
mentalmente portales colaborativos SharePoint. Actualmen-
te se desempeña como desarrollador en UruIT y docente uni-
versitario en la Universidad de la Empresa.

La teoría de la computación es una rama de la Ciencia de la Computación que se focaliza en definir
conceptos tales como los modelos computacionales y la complejidad y computabilidad de problemas
resolubles mediante algoritmos o programas.
La Teoría de la Computación se subdivide en tres grandes ramas de estudio: La Teoría de la Complejidad,
la Teoría de la Computabilidad y la Teoría de Autómatas.
La Teoría de la Complejidad estudia qué tan sencillo o complejo es resolver un problema determinado y
cuánto tiempo toma el hacerlo.
Un ejemplo es el problema de ordenar una lista de importes, de menor a mayor (posiblemente la lista de
importes de una compra al supermercado).
Tanto una persona como una computadora de la década anterior podría fácilmente ordenar estos
importes en el caso de hablar de 10 a 100 importes, y dejando de lado el factor humano, computadores
antiguos y de hoy en día no tendrían grandes problemas en ordenar miles de importes.

Sin embargo otros problemas no son tan sencillos de resolver, como por ejemplo el problema referente a
la asignación de maestros o profesores a salones de clase, asegurando que ningún salón esté reservado
para dos profesores al mismo tiempo y que ningún profesor dicte clases en dos salones al mismo tiempo
(y además tenga asignado todo el tiempo de clase necesario para dictar sus asignaturas).
Todo esto considerando las restricciones de agenda y disponibilidad horaria de cada profesor.
El problema de la asignación de personal disponiendo de determinados recursos (salones) es un problema
mucho más complejo que el problema de ordenación de una lista de importes.
En el caso de tratarse de una universidad con miles de salones y profesores, el encontrar la mejor
asignación posible de recursos podría tomarle a una computadora siglos, inclusive contando una
supercomputadora.
La Teoría de la Complejidad se enfoca en intentar responder la siguiente pregunta:
¿Qué hace que algunos problemas sean fáciles o difíciles de resolver desde el punto de vista
computacional?
La Teoría de la Computabilidad estudia qué problemas son computables y qué problemas son no
computables, es decir qué problemas son o no son resolubles por un computador.

Reflexiones sobre Ingeniería