TEORIA DE LA COMPUTACION
UNIDAD I
TEORIA DE LA COMPUTACION
La teoría de la computación es una ciencia
(rama de la matemática-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 a partir de ciertos datos o
entradas utilizando para ello un proceso o
algoritmo.
COMPUTABILIAD
La Teoría de la computabilidad es la parte de la
computación que estudia los problemas de decisión que
pueden ser resueltos con un algoritmo o equivalentemente
con una máquina de Turing. La teoría de la computabilidad
se interesa a cuatro preguntas:
• ¿Qué problemas puede resolver una máquina de Turing?
• ¿Qué otros formalismos equivalen a las máquinas de
Turing?
• ¿Qué problemas requieren máquinas más poderosas?
• ¿Qué problemas requieren máquinas menos poderosas?
COMPLEJIDAD
La teoría de la complejidad computacional es la
rama de la teoría de la computación que estudia,
de manera teórica, los recursos requeridos
durante el cómputo de un algoritmo para
resolver un problema. Los recursos comúnmente
estudiados son el tiempo (mediante una
aproximación al número y tipo de pasos de
ejecución de un algoritmo para resolver un
problema) y el espacio (mediante una
aproximación a la cantidad de memoria utilizada
para resolver un problema).
AUTOMATA
Un automata es una construccion logica que
recibe una entrada y produce una salida en
funcion de todo lo que recibido hasta ese
instante.
La palabra automata evoca algo que pretende
imitar las funciones propias de los seres vivos,
especialmente relacionadas con el
movimiento.
• En el campo de los Traductores, Procesadores,
Compiladores e interpretes, lo fundamental
no es la simulacion del movimiento, sino la
simulacion de procesos para tratar la
informacion.
CONJUNTO
Conjunto: Cualquier colección de objetos o
individuos. Se denota con mayúsculas.
Elemento: Cierto individuo x que es parte
del conjunto A. Se identifican con minúsculas.
Ejemplos:
A = { 0, 2, 4, 6, …}
OPERACIONES SOBRE
CONJUNTOS
UNION
Sean A y B dos conjuntos.
El conjunto A ⋃ B, llamado unión de A y B es
el conjunto que contiene todos los elementos
que pertenecen o bien a A o bien a B.
• x ∈ (A ⋃ B) ≡ ( x ∈ A ) V ( x ∈ B )
• A⋃B={x|x∈AV(x∈B}
A⋃B
INTERSECCION
Sean A y B dos conjuntos. El conjunto A ∩ B
llamado intersección de A y B es el conjunto
que contiene todos los elementos comunes a
ambos A y B
• x ∈ (A ∩ B) ≡ ( x ∈ A ) & ( x ∈ B )
• A∩B={x|x∈A&(x∈B}
A∩B
DIFERENCIA
Sean A y B dos conjuntos. El conjunto A-B,
llamado diferencia de A y B, es el conjunto de
todos los elementos de A que no pertenecen a
B
• x ∈ (A - B) ≡ ( x ∈ A ) & ( x ∉ B )
• A-B={x|x∈A&(x∉B}
A–B
COMPLEMENTO
• Sean A un conjunto. El complemento de A, se
escribe ~A, es el conjunto de todos los
elementos que no pertenecen a A.
x ∈ ~A ≡ ¬ ( x ∈ A )
~A = { x | x ∉ A}
~A
Descargar

TEORIA DE LA COMPUTACION