Examen teoria de la computacion

EXAMEN 1ra. UNIDAD
1.- A MODO DE COMENTARIO, EXPLICAR, ¿QUE ES LA TEORÍA DE LA COMPUTACION?
R= rama de las matemáticas y de la computación que se encarga de descubrir las limitaciones y capacidadesfundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas de acuerdo asu grado de dificultad, a través de algoritmos programables.
2.- DEFINIR LOS SIGUIENTES CONCEPTOS:
COMPLEJIDAD: estudia la cantidad de tiempo y espacio de memoria que toma al ejecutarse un conjuntode datos o proposición.
COMPUTABILIDAD: parte de la computación que ayuda a resolver problemas a través de procesos computables y sus problemas de decisión
LENGUAJE: es un conjunto de cadenas en unalfabeto ∑, definido en cualquier cadena W, y que llevan una gramática, símbolos terminales y no terminales, patrón y proposiciones.
CADENA: es una secuencia finita de símbolos que pertenecen a unelemento ∑ y que se denota con la letra W, que pertenece a cierto alfabeto.
PROPOSICION: es un enunciado o expresión en un lenguaje de programación, integrado por símbolos terminales y no terminales yen el cual podemos saber si es verdadero o falso.
3.- EXPRESAR Y REPRESENTAR EN DIAGRAMAS DE VENN, LA NOTACIÓN MATEMÁTICA DE ACUERDO A LOS TIPOS DE OPERACIONES DE LA TEORIA DE CONJUNTOS.

U= {0,1, 2, 3, 4, 5, 6, 7, 8, 9}
A= {2, 5, 6, 7, 10}
B= {1, 3, 8, 6, 5, 9}
UNION
A U B = {1, 2, 3, 5, 6, 7, 8, 9, 10}
0 4U
A B

2 7
10 5
6
101 3
8
9

INTERSECCION
A ∩ B= {5,6}

SUSTRACCIÓN

U
5
6

4
1 3
8
9
2...