Introduccion a la teoria de la computacion

Introducción a la Teoría de la Computación.
La asignatura de Teoría de la Computación trabaja con desarrollos de tipo matemático; siendo eje fundamental de distintas áreas encuadradas en la Informática Teórica.
Evolución Histórica de la Teoría de la Computación.
La Teoría de la Computación trata, con modelos de cálculo abstractos, las diferentes partes y tipos de computadores; modelos que, seocupan de cuestiones sobre la capacidad de los ordenadores, en general.
La Teoría de la Computación difiere de las áreas mencionadas en:
* Los modelos abstractos de cálculo abarca computadores que pueden llegar a existir o solo a imaginar.
* Lo importante no es la optimalidad, sino la computabilidad.
Computabilidad.
La computabilidad, iniciada por Gödel, Church, Post, Turing y Kleene,tiene sus raíces en la Lógica Matemática.
Un axioma o postulado es una fórmula bien formada de un lenguaje formal que se acepta sin demostración, como punto de partida para demostrar otras fórmulas.
1. La línea recta es la distancia más corta entre dos puntos.
2. Una proposición no puede ser verdadera y falsa al mismo tiempo.
3. Si a cantidades iguales se les añaden cantidadesiguales, las sumas resultantes también son iguales
4. El todo es mayor que cualquiera de sus partes.
La idea de David Hilbert era encontrar un algoritmo que determinara la verdad o falsedad de cualquier teorema en el sistema formal, posteriormente Gödel prueba que no todos los resultados son demostrables.
Por otra parte Kleene demuestra de forma independiente la equivalencia entre funcionesλ-definibles y funciones recursivas de Herbrand-Gödel.
Turing señaló que había tenido éxito en caracterizar la clase de las funciones calculables mediante un algoritmo (Tesis de Turing). Demostró que los conceptos de función λ-definible y función calculable por medio de una máquina de Turing coinciden.
La no computabilidad de cuestiones, como problemas de equivalencia, de parada, detotalidad y de verificación, incrementó la sensación de que casi cualquier pregunta acerca de algoritmos era no computable.
Complejidad Algorítmica.
Al objetivo de la parte de las Ciencias de la Computación sobre la dificultad computacional de las funciones computables, se le conoce como Complejidad Algorítmica.
Michel Oser Rabin sugirió una axiomática que fue la base para el desarrollo delestudio de medidas de complejidad abstracta de Blum y otros.
El artículo de J. Hartmanis y R. Stearns de 1965 introduce la noción fundamental de medida de complejidad definida como el tiempo de computación sobre una máquina de Turing multicinta y se demuestran los teoremas de jerarquía.
Cobham estaba interesado en una teoría independiente de las máquinas. Esto conduce a la identificación deproblemas que se pueden resolver en tiempo acotado por un polinomio sobre la longitud de la entrada. La distinción entre algoritmos de tiempo polinomial y algoritmos de tiempo exponencial fue hecha por primera vez por Von Neumann. La notación de P para la clase de los problemas resolubles en tiempo polinomial fue introducida por Karp.
La clase N P consta de todos los problemas decidibles en tiempopolinomial por una máquina de Turing no determinista. Cook demuestra que el problema de la satisfacibilidad booleana es NP-completo.
Máquinas Secuenciales y Autómatas Finitos.
La Teoría de Autómatas, tiene su origen en el campo de la Ingeniería Eléctrica. Claude E. estableció las bases para la aplicación de la Lógica Matemática a los circuitos combinatorios y posteriormenteHuffman los amplió a circuitos secuenciales y usó conceptos como estado de un autómata y tabla de transición.
El concepto de autómata finito aparece en 1943, describiendo los cálculos lógicos inmersos en una neurona artificial. A partir de entonces, se han desarrollado asociaciones de neuronas para constituir redes. Las redes neuronales, dentro del perfil de Teoría de la Computación,...