Compiladores

TEORÍA DE LA COMPUTACIÓN

UNIDAD I.- Introducción

1.1 Autómatas, Complejidad y Computabilidad

Autómata: es un sistema secuencial (robot), programable en lenguaje no informático diseñado para controlar en tiempo real y en ambiente industrial.

Computabilidad: cosas que pueden ser realizadas por un ser humano y que pudieran automizar el trabajo tedioso y lleno de errores del ser humano.

Complejidad: es el estudio de la cantidad de tiempo (número de pasos de ejecución de un algoritmo para resolver un problema) y de espacio (cantidad de memoria utilizada para resolver un problema), que toma la ejecución de un cómputo dado.

La terminología utilizada para describir la complejidad de los algoritmos es:

COMPLEJIDAD TERMINOLOGÍA

1.- O (1) Complejidad constante

2.- O (log n) Complejidad logarítmica

3.- O (n) Complejidad lineal

4.- O (n log n) Complejidad n log n

5.- O (bn) Complejidad polinómica

6.- O (bn) donde b > n Complejidad exponencial

7.- O (n!) Complejidad factorial

Ejemplos:

1.- Encuentra el mayor de cien números de una lista de n € (n ≥ 100)

C1= complejidad constante

2.- Búsqueda binaria

C2= complejidad logarítmica

3.- Búsqueda lineal

C3= complejidad lineal.

CLASES DE COMPLEJIDAD

Existen problemas tratables, pues pueden resolverse utilizando un algoritmo de complejidad 5, con una entrada de datos razonable en un tiempo relativamente corto.

Los problemas intratables, son todos aquellos que no se pueden resolver con un algoritmo de complejidad polinómica en el peor de los casos.

Generalmente requieren un tiempo extremadamente largo aún con un valor de entrada pequeño, en la práctica se utilizan soluciones aproximadas que no difieren mucho con las exactas.

Para algunos problemas no existen algoritmos que puedan solucionarlos, por lo que éstos se les denominarán no resolubles o irresolubles.

1.2 NOCIONES MATEMÁTICAS

La inducción matemática es definitivamente una forma de deducción, donde la mencionada concluye con una certeza deductiva.

1.2.1 CONJUNTOS

Conjunto: unión ó agrupación de varios objetos que comparten una característica en común. { }.

Objeto: es un elemento perteneciente a un conjunto que posee características propias. { a,z,y}.

Los siguientes conjuntos, desempeñan un papel importante:

N= {0,1,2,3,4….} Conjunto de los números naturales.

Z= {…,-2,-1,0,1,2,..} Conjunto de los números enteros.

Z+ = {1,2,3,…} Conjunto de los números enteros positivos.

Q = { p/q│ p € z, q € z, q ≠ 0} Conjunto de números racionales.

R = son parte del sistema numérico, es decir es todo el conjunto de los números reales.

IGUALDAD DE CONJUNTOS

Dos conjuntos son iguales sí y sólo sí tienen los mismos elementos.

Ejemplo:

{1,3,5} {5,3,1} = Conjuntos iguales.

SUBCONJUNTO

El conjunto A se dice que es un subconjunto de B sí y sólo sí todo elemento de A es también elemento de B. se utiliza la notación A ⊆ B para indicar que A es un subconjunto de B.

Ejemplo:

El conjunto de los enteros positivos impares menores que 10 es un subconjunto de los enteros positivos menores que 10.

Ejemplo 2:

El conjunto de todos los estudiantes de I.S.C. es un subconjunto del conjunto de todos los estudiantes del Tecnológico.

CARDINALIDAD

Sea S un conjunto, si hay exactamente n elementos distintos en S, donde n es un entero no negativo, decimos que S es un conjunto finito y n es el cardenal de S, se denota por: │S│.

Ejemplo:

Sea A el conjunto de números enteros positivos impares menores que 10.

A= {1,3,5,7,9} │A│= 5

Ejemplo 2:

Sea S el conjunto de letras del alfabeto. S= Alfabeto │S│=27

CONJUNTO INFINITO

Es aquél que no es finito.

CONJUNTO DE LAS PARTES

Dado un conjunto S el conjunto de las partes de S es el conjunto

...