Material 1

Universidad Don Bosco
Facultad de Ingeniería
Escuela de Ingeniería en Computación
Asignatura: Teoría de la Computación
Ciclo / Grupo: 03 – 2015 / 01T
Docente: Ing. Herson Miguel Serrano Chacón

I.

INTRODUCCIÓN A LA TEORÍA DE LA COMPUTACIÓN

Como punto de partida, conviene definir qué es la computación para estudiar la teoría de la computación. Podría
decirse que consiste en la ejecución de unalgoritmo, es decir, partir de ciertas entradas y seguir un
procedimiento paso a paso que lleva a un resultado.
¿Cuáles tipos específicos de pasos se permiten en un algoritmo?
Una forma de conceptuarlo es pensar en los pasos posibles en los lenguajes de alto nivel usados para
programar la computadora (por ejemplo, el lenguaje C). Sin embargo, en vez de ello pensaremos en las
computadoras mismas.Diremos que un paso está permitido en la computación si es una operación que puede
ejecutar la computadora. En otras palabras, la computación es una secuencia de pasos que puede ejecutar
la computadora.
Las computadoras que estudiaremos no son reales. Por principio de cuentas, una teoría basada en
especificaciones de hardware real no sería muy útil, ya que tendría que modificarse cada vez que secambie o
mejore dicho hardware.
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ómputos.
Se le llama cómputo a la obtención de una solución o resultado (generalmente en el sentido
matemático/aritmético del término), a partir de ciertos datos o entradas utilizando para ello unproceso
o algoritmo.

La teoría de la Computación es un poco más antigua que las computadoras electrónicas. Uno de sus pioneros,
Alan Turing pudo anticipar el poder de las computadoras a través de un modelo conceptual en 1936. Otras
disciplinas como la matemática, filosofía, lingüística, biología e ingeniería eléctrica intervienen para completar
sus teorías. Las teorías de bases son dos: Teoría deAutómatas y Teoría de los Lenguajes Formales. En
general, la Teoría de la Computación facilita la comprensión de muchas áreas de la ciencia de la computación
(como los compiladores), además:
1. Se utiliza en el diseño y construcción de aplicaciones importantes de software y hardware.
2. Ayuda a comprender que esperar del software.
Teoría de la Computación / Clase 1 - Semana 1 / Ciclo 03 / 2015

Página 13. Permite deducir si es posible resolver un problema (determinar los límites de la computación).
Además, la comprensión de estas teorías representa en la práctica un conjunto de herramientas muy útiles
como alternativas simples y eficientes para resolver problemas.

II.

NOCIONES MATEMÁTICAS

CONJUNTOS
El fundamento más importante para el estudio de los lenguajes y autómatas es la teoría deconjuntos. En efecto,
siempre que hablemos de “formalizar” una noción, estaremos diciendo en realidad “expresar en términos de
Teoría de Conjuntos”.
A continuación se presentan los conceptos básicos de la Teoría de Conjuntos.
Conjunto: colección de objetos (del mismo tipo) sin repetición. Un conjunto está determinado por sus
elementos.
Un conjunto que vamos a utilizar con frecuencia es el de losnúmeros naturales {1, 2, 3,4,…}, denotado por N.
Los conjuntos pueden expresarse de dos maneras básicamente:
a) En extensión, lo que quiere decir que citamos explícitamente cada uno de sus elementos, como en el
caso del conjunto {1, 2,3}, que contiene exactamente 3 elementos.
b) En intención, dando una descripción precisa de los elementos que forman parte del conjunto en vez
de citarlos explícitamente.Por ejemplo, el conjunto del punto anterior puede ser visto como {i ∈ impar
(i), i < 6}, donde se supone que los números impares cumplen la condición impar.
Representamos a los conjuntos con letras mayúsculas, como en A = {2, 4}. Los conjuntos pueden tener otros
conjuntos como elementos, como B = {{a}, {b, c}}. El conjunto sin elementos (vacío) se representa por ∅ o bien
por { }.
La notación...