Apuntuntes de teoria

Unidad I. Introducción a la teoría de la computación.
1.1 Autómatas, Computabilidad y Complejidad

Un autómata es un sistema secuencial que también se usa para referirse a un robot, puede definirse como un equipo electrónico programable y diseñado para controlar en tiempo real y en ambiente procesos secuenciados, sin embargo, la evolución de los autómatas permite que la definición este enconstante cambio.
Un autómata programable se puede considerar como un sistema basado en un microprocesador, siendo sus partes fundamentales la unidad central de proceso, la memoria, y el sistema de entrada y salida.
A partir de las instrucciones almacenadas en memoria y de los datos que recibe de las entradas, genera las señales de salida.
El sistema de E/S recoge la información y envía lasacciones de control. Los dispositivos de entrada pueden ser pulsadores, interruptores, detectores de nivel, detectores de proximidad, contactos auxiliares, etc.
Computabilidad

Es la acción de llevar a cabo registros que pueden ser realizados por humanos y estos a su vez automatizados para estar libre de errores.

Complejidad
Es el estudio de la cantidad de tiempo y espacio en memoria que ocupa laejecución de un cómputo dado.
1.2. Nociones matemáticas de teoría de la computación
Conjuntos. Colección de objetos o elementos que se denotan con una letra mayúscula y entre llaves.
A A= {a,b,c,d,e}


Conjunto finito. Es todo conjunto coordinarle con un subconjunto propio de elementos de conjuntos naturales.
B= {1,2,3,4,5}
E= {a,b,c,…,z}
Conjunto nulo. Todo conjunto que carece deelementos.
F={0} G={ } conjunto vacio
Conjunto unitario. Es aquel conjunto que contiene un único valor.
M={7}
Conjunto solución. Los elementos que comprenden la solución al sistema.
X+Y=10
X-Y=2
I={6,4}
Conjunto coordinable. Son dos conjuntos entre los cuales se puede definir una correspondencia entre sus elementos.
A B

Conjuntos diferentes. Son conjuntos que difieren en por lo menosun elemento.
A= {a,b,c,d,e}
B= {a,b,c,e,x}
Por lo tanto A diferente de B.
Conjuntos iguales. Que todos los elementos de A y B sean iguales.
A= {a,b,c,d,e}
B= {a,b,c,d,e}
Conjuntos disyuntos. Conjuntos que no tienen elementos en común.
A= {a,b,c}
A= {m,n}
Entonces AnB= {0}
Conjunto diferencia. Complemento relativo de los elementos de un conjunto con respecto a otro.
A B


A={2,3,4}
B= {0,1,2}
A-B= {3,4}
B-A= {0,1}

Domino y contradomino

Dominio. El conjunto de elementos pertenecientes al primer conjunto.
Contradominio. Es la imagen o rango correspondiente a los elementos del dominio.
Subconjuntos.
Un subconjunto de A es un subconjunto de otro conjunto si y solo si cada elemento A es un elemento de B.
A= {1,2,3,4,5}
B= {1,2,3,4}
C= {1,3,5}
D= {1,4,5}
E={2,3,5}
AcB= {0}
BcA= {1,2,3,4}
EcA= {2,3,5}
DcA= {1,4,5}

Partición de un conjunto
Una partición de X es una subdivisión entre subconjuntos disyuntos y cuya unión es el mismo conjunto. Los conjuntos de una partición son llamadas células.
X= {1,2,3,4,5,6,7,8,9}
a) [{(1,3,5),(2,6),(4,8,9)}] no es partición
b) [{(1,3,5),(2,4,6,8),(5,7,9)}] no es partición
a)[{(1,3,5),(2,4,6,8),(7,9)}] si es partición

A= {a,b,c}
B= {d,e,f,g}
1-M= {(a,d),(a,e),(a,f),(a,g),(b,d),(b,e),(b,f),(b,g),(c,d),(c,e),(c,f),(c,g)}
M-1= {(a,d),(b,d),(c,d),(a,e),(b,e),(c,e),(a,f),(b,f),(c,f),(a,g),(b,g),(c,f)}
M-M= {(a,d),(b,e),(c,f),(a,g),(b,d),(c,e),(a,f),(b,g),(c,d),(a,e),(b,f),(c,g)}

A B A B

d e f g
a 1 1 1 1
b 1 1 1 1
c 1 1 1 1

V= {Todos los positivos}A= {0,2,4,6,8,10,12}
B= {0,1,2,3}
C= {1,3,6,9}
D= {0,1,2,3,4,5,6}
E= {1,2,3,4,5,6,7,8}
F= {1,2,3,4,5,6,7,8,9,10}
Realizar las siguientes operaciones:
AuB= {0,2,4,6,8,10,12,0,1,2,3}
DuE= {0,1,2,3,4,5,6,1,2,3,4,5,6,7,8}
FuB= {0,1,2,3,4,5,6,7,8,9,10,0,1,2,3}
AnB= {0,2}
DnE= {1,2,3,4,5,6}
FnB= {1,2,3}
A-B= {4,6,8,10,12}
D-E= {0}
F-B= {4,5,6,7,8,9,10}
AcC= {0}
DcE= {0}
FcB= {0}
AC=...