Automatas, computabilidad y complejidad

INTRODUCCIÓN

Universidad Autónoma de Sinaloa

Facultad de Informática

Fundamentos Teóricos de la Computación

Unidad 1

La teoría de la computación es una ciencia, en particular una rama de la matemática y de la computación que centra su interés en el estudio y definición formal de los cálculos. Se le llama cálculo a la obtención de una solución o resultado (en el sentidomatemático/aritmético), a partir de datos o entradas utilizando para ello un proceso o algoritmo.

Las tres áreas tradicionales de la teoría de la computación son: Autómatas, Computabilidad y Complejidad. Las cuales están unidas por la pregunta:

AUTÓMATAS, COMPUTABILIDAD Y COMPLEJIDAD
¿Cuáles son las capacidades y las limitaciones de las computadoras?

Esta interrogante se remonta a la década de 1930cuando la lógica matemática comenzó a explorar el significado de la computación. Los avances tecnológicos desde entonces han aumentado nuestra capacidad de cálculo y han llevado a cabo esta cuestión del ámbito de la teoría a la práctica. En cada uno de los tres ámbitos autómatas, computabilidad y complejidad se interpreta de manera diferente, y las respuestas varían de acuerdo a lainterpretación. Tras este capítulo introductorio, se explorará cada de estas áreas por separado.

Los problemas computacionales vienen en diferentes variedades, algunas son fáciles, y algunos difíciles. Por ejemplo, la clasificación es un problema fácil. Si se necesita organizar una lista de números en orden ascendente un pequeño equipo puede ordenar un millón de números rápidamente. Que comparado alproblema de programar un calendario de clases para toda la universidad satisfaciendo algunas peticiones razonables, por ejemplo, dos clases no pueden ser impartidas en el mismo salón al mismo tiempo. Así, el problema de programación parece ser mucho más difícil que el problema de clasificación. Si sólo se tiene un millar de clases, encontrar el mejor horario podrá tardar siglos, incluso con unasupercomputadora. ¿Qué hace que algunos problemas sean computacionalmente difíciles y otros fáciles? Esta es la interrogante central de la teoría de la complejidad. Sorprendentemente, no sabemos la respuesta, aunque se ha investigado intensamente durante los últimos 35 años.

TEORÍA DE COMPLEJIDAD

Lic. Roy Jonny Sida López

1

Universidad Autónoma de Sinaloa

La teoría de la complejidadcomputacional en sí, es la rama de la teoría de la computación que estudia, de manera teórica, los recursos necesarios durante el cómputo de un algoritmo en la solución de un problema. Los recursos comúnmente estudiados son; el tiempo (utilizando una aproximación del número y tipo de pasos de ejecución del algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad dememoria utilizada para resolver el problema). También es posible estudiar otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo.

Facultad de Informática

Fundamentos Teóricos de la Computación

Unidad 1

Durante la primera mitad del siglo XX, matemáticos como Kurt Gödel, Alan Turing y Alonzo Church descubrieron que ciertos problemas nopueden resolverse por las computadoras. Un ejemplo de este fenómeno es el problema de determinar si un enunciado matemático es verdadero o falso. Esta tarea es el pan y la mantequilla de matemáticos. Parece una solución natural para una computadora, ya que se encuentra estrictamente en el ámbito de las matemáticas. Pero, un algoritmo computacional no puede realizar esta tarea. Como consecuencias deeste resultado se desarrollaron ideas sobre modelos teóricos para los equipos que eventualmente ayudarían a llevar a la construcción real de las computadoras.

TEORÍA DE LA COMPUTABILIDAD

Las teorías de Computabilidad y Complejidad están estrechamente relacionadas. La teoría de complejidad tiene como objetivo clasificar los problemas en fáciles y difíciles, mientras que en la teoría de...