Teoria de la computacio

INSTITUTO TECNOLÓGICO DE DURANGO

INGENIERÍA EN SISTEMAS COMPUTACIONALES

MATEMATICAS V

1ra UNIDAD

09041268 PEDRO ARTURO VALENLENZUELA FERMAN

DURANGO, DGO. A 05 de septiembre de 2011

Contenido
Autómatas 3
Computabilidad y Complejidad 3
Computabilidad 3
Complejidad 3
Nociones Matemáticas De Teoría De La Computación 4Conjuntos 5
Operaciones con conjuntos 6
Unión 6
Intersección 6
Diferencia 6
Complemento 6
Potencia 6
Producto Cartesiano 6
Funciones y Relaciones TC 7
Cadenas y Lenguajes 7
Bibliografía 7

Autómatas
Un autómata es un sistema secuencial. Puede definirse como un equipo electrónico programable en lenguaje no informático y diseñado para controlar, en tiempo real y en ambienteindustrial, procesos secuenciales. Un autómata programable se puede considerar como un sistema basado en un microprocesador, siendo sus partes fundamentales la Unidad Central de Proceso (CPU), la Memoria y el Sistema de Entradas y Salidas (E/S).
Computabilidad y Complejidad
Computabilidad.- Es la acción de llevar acabo registros que pueden ser realizados por humanos para ser automatizados y estarlibres de errores.
Complejidad.- Es el estudio de la cantidad de tiempo y espacio en memoria que ocupa la ejecución de un cómputo dado.
Teoría de la complejidad computacional
_ Estudio de los recursos necesarios para resolver los problemas teóricamente computables
_ Clasificación de los problemas computables y los algoritmos en términos de su “coste” o posibilidad de resolución efectiva
Cantidadde recursos necesarios para la resolución de:
_ Un problema,
_ Un algoritmo o
_ Un cálculo
Se analizan dos recursos principales:
_ Tiempo (pasos, operaciones elementales,...) Complejidad temporal
_ Espacio (celdas, posiciones de memoria,...) Complejidad espacial

Nociones Matemáticas De Teoría De La Computación
La evolución del conocimiento matemático debe buscarse en la resultante delhombre como especie paulatinamente capaz de reunir experiencia y abstraer, y las muy condicionantes dinámicas propias de la evolución de cada sociedad. En ese sentido es probable que haya sido el propio cuerpo humano el instrumento y la referencia para los procesos de inserción de la experiencia dentro de la lógica y de la generación de conocimiento. No es menor el hecho de que el humano, por primeravez en la evolución, se haya hecho capaz de trasmitir información sistemáticamente por vía distinta a la genética, ya desde ese estadio evolutivo en que dedicó casi todo su esfuerzo a las funciones primarias de sobrevivencia: caza, pesca, recolección, reproducción y defensa, y adaptación o fabricación de útiles y armas para mejorar su desempeño. Es de presumir que ese momento se corresponde conel surgimiento de las nociones matemáticas, primero del contar, de número como consecuencia del contar y relacionar, y de medir luego, y que el propio cuerpo haya sido el elemento relacionante para realizar esas actividades de interpretación matemática de la realidad. Muchas de las referencias corporales surgidas en culturas sin relación entre sí han sobrevivido. Contar con los dedos, medir porpulgadas, cuartas, pies, brazas, pasos, codos, etc., parecen residir en la memoria genética de la humanidad en su conjunto.

Conjuntos
Un conjunto en una colección de individuos u objetos.
Por ejemplo N= {1, 2, 3, . . .}
Los conjuntos pueden expresarse de dos maneras:
* En extensión, es decir que tomamos cada uno de sus elementos, como en el conjunto {1, 3, 5} que contiene exactamente losnúmeros 1, 3 y 5.

* En intención, dando una descripción precisa de los elementos que forman parte del conjunto, en vez de citarlos explícitamente. Por ejemplo, el conjunto del punto anterior puede ser visto como {i ∈ N|impar (i), i < 6 }, donde se supone que los números impares cumplen la condición impar (i).

El conjunto sin elementos (vacío) se representa por; ∅ bien por { }.

El...