Teroia de la computacion

CONCLUSIONES : INTRODUCCION A LA TEORIA DE LA COMPUTACION.

Reconocer los orígenes de la Teoría de la computación, y ver sus maneras de aplicación en compiladores y programación.

TEORIA DE LA COMPUTACION
PROCESO INFORMATICO
HERRAMIENTA DE COMPUTO

CONCEPTOS BASICOS

Alfabeto: conjunto finito de símbolos no vacíos.
Cadena (Palabra): Secuencia finita de símbolos que pertenecen a unalfabeto.
Lenguaje: conjunto de cadenas del mismo alfabeto.
Problema: Poder resolver la pertenencia de una cadena sobre un lenguaje.

Alfabeto: Σ={0,1}, Σ={a,b,c...z}
Cadena: {0110}, {Abel}
Lenguaje: Σ={0,1,a,b,c...z}

Dentro de un alfabeto pueden existir distintas cadenas donde el significado es el mismo.
Dentro de la teoría de la computación los lenguajes es el resultado de un análisis quepermite resolver un problema que puede ser de cualquier tipo, además dentro de los lenguajes existen condiciones que permiten evaluar su significado para lo cual es importante entender que la teoría de la computación se basa en estos lenguajes.

TEORIA DE CONJUNTOS
OPERACIONES CON CONJUNTOS

Unión u:
Para cada par de conjuntos Ay B existe un conjunto unión de los dos, se denota A u B el cualcontiene todos los elementos de A y B
AuB={x: x Є A o x Є B}

Intersección n: Los elementos comunes A y B forman un conjunto intersección de A y B denotado como AnB contiene elementos de A que al mismo tiempo están en B
AnB={x: x Є A y x Є B}

Partición: Dado un conjunto A, una familia de subconjuntos x={A,i} (con cada Ai dependiente de A) se denomina una partición de A si la unión de 2de ellos es A y son disjuntos dos a dos.
Ux= A y Ai n Aj=0 si i≠j

Diferencia: Los elementos de un conjunto A que no se encuentran en un conjunto B forman otro conjunto diferencia A-B

Complemento: de un conjunto A, es el conjunto de todos los elementos que no pertenecen a A, siempre respecto al conjunto universal que estamos tratando.

Producto Cartesiano: Un par ordenado de números (x,y)es tal si los pares (x,y) y (y,x) son uno mismo, si y solo si x=y.
Dado dos conjuntos A y B, definimos al conjunto producto cartesiano de A y B con ese orden, representado por AXB como el conjunto AXB={(x,y) |x Є A n y Є B}

TEORIA DE GRAFOS

Un grafo consiste de un conjunto finito de vértices y un conjunto finito de pares de vértices llamados enlaces. Un grafo tiene las siguientescaracterísticas:

1.- Camino: secuencia de vértices que permiten ir de un enlace a otro, es decir representa una sucesión de segmentos para ir de un nodo a otro.
2.- Sendero: camino de un nodo y a un nodo x, nunca se repiten.

Lazo

Segmento
Camino

Dentro de los grafos existe un concepto llamado Dígrafo que es un grafo dirigido que consiste en un conjunto finito de vértices y un conjuntofinito de arcos, que representan una sola dirección que los arcos. Un dígrafo es un grafo dirigido con una dirección asignada a cada segmento.

LENGUAJES FORMALES
Alfabeto: conjunto no vacío y finito de símbolos
Palabra: secuencia finita de símbolos de un alfabeto
Palabra vacía: denotada por {λ}
Lenguaje: conjunto de palabras de un alfabeto, lenguaje compuesto por todas las cadenas se llamacerradura de Σ o lenguaje universal denotado por Σ*

Lenguaje sobre alfabeto L( Σ): palabras de Σ de cualquier longitud.

OPERACIONES CON CADENAS
Longitud: numero de símbolos de una cadena.
Concatenación: cadena que se obtiene al añadir w a la cadena z se denota como wz
x=barce, y= lona; xy=barcelona

Inversión o Reflexión; x= A1, A2, A3.... An entonces x⁻1= An...A3, A2, A1
Potencia:w sobre un alfabeto n Є N

VISION GENERAL DE COMPUTADORES
Compilador: traductor especial que toma un lenguaje de alto nivel y lo traduce a su representación de bajo nivel. Que la computadora puede ejecutar en ultima instancia.

CONCLUSIONES: VISION GENERAL DE COMPUTADORES Y COMPILADORES
Comprender el comportamiento de los lenguajes en un compilador y las fases que se ejecutan para...