Tarea

1.1 Autómatas, Computabilidad y Complejidad

Autómata

En electrónica un autómata es un sistema secuencial, aunque en ocasiones la palabra es utilizada también para referirse a un robot. Puede definirse como un equipo electrónico programable en lenguaje no informático y diseñado para controlar, en tiempo real y en ambiente industrial, procesos secuenciales.

Sin embargo, la rápidaevolución de los autómatas hace que esta definición no está cerrada.

Complejidad computacional

La complejidad, es el estudio de la cantidad de tiempo y de espacio en memoria que toma la ejecución de un cómputo dado. La Teoría de la complejidad computacional es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema. Losrecursos comúnmente estudiados son el tiempo (numero de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad defiere de la teoría de la computabilidaden que esta última se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello. Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.
Estos problemas no tienen una solución práctica, es decir, una maquina no puederesolverlos en un tiempo razonable

Clases de complejidad.

Los problemas de decisión se clasifican en conjuntos de complejidad comparable llamados clases de complejidad. La clase de complejidad P es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina determinista en tiempo

Polinomio, lo que corresponde intuitivamente a problemas que pueden ser resueltos aunen el peor de sus casos. La clase de Complejidad NP es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no determinista en tiempo Polinomio. Esta clase contiene muchos problemas que se desean resolver en la práctica, incluyendo el problema de satisfacibilidad Booleana, el problema del camino de Hamilton y el problema de la cobertura de vértices. Todos losproblemas de esta clase tienen La propiedad de que su solución puede ser verificada efectivamente.
1.2 Nociones Matemáticas de Teoría de la Computación
La evolución del conocimiento matemático debe buscarse en la resultante del hombre como especie paulatinamente capaz de reunir experiencia y abstraer, y las muy condicionantes dinámicas propias de la evolución decada 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 primera vez en la evolución, se haya hecho capaz de trasmitir información sistemáticamente por vía distinta a la genética, ya desde eseestadio evolutivo en que dedica 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 con el surgimiento de las nociones matemáticas, primero del contar, de número como consecuencia del contar y relacionar, y de medirluego, 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 han sobrevivido. Contar con los dedos, medir por pulgadas, cuartas, pies, brazas, pasos, codos, etc., parecen residir en la memoria genética de la humanidad en su conjunto....