Teoria De La Computacion

TEORÍA DE LA COMPUTACIÓN
Introducción: La teoría de la computación es un poco más antigua que las computadoras electrónicas. Uno de sus pioneros,
Alan Turing, pudo anticipar el poder de las computadoras a través de un modelo conceptual en 1936. Las teorías de bases son dos: La teoría de autómatas y la teoría de los lenguajes formales. En general la teoría de la computación facilita lacomprensión de muchas áreas de la ciencia de la computación (como los compiladores), además:
1.-Se utiliza en el diseño y construcción de aplicaciones importantes de software y hardware.
2.-Ayuda a comprender que esperar del software.
3.-Permite deducir si es posible resolver un problema (determinar los límites de la computación).
Además, la comprensión de estas teorías representa en la práctica unconjunto de herramientas muy útiles como alternativas simples y eficientes para resolver problemas.

Ciencia de la computación: Es aquella que busca establecer una base científica para diversas áreas como:
-Diseño de computadoras (architecture of computers).
-Programación de computadoras (theoretical computer science).
-Elaboración de algoritmos para resolver problemas (Design and analysis ofalgorithms).

Es la ciencia en la que se apoyan las aplicaciones computacionales actuales y en la que se basarán las aplicaciones del mañana. Por lo tanto no se puede aprender la ciencia de la computación si solo se estudian unos cuantos temas como materias aisladas o si se limita a aprender a usar las herramientas de cómputo actuales. Esta debe ser estudiada de forma estructurada de forma talque permita un constante desarrollo y proyecciones a aplicaciones inimaginables.

Áreas de la teoría de la computación: Tres áreas centrales de la teoría de la computación son: “Autómatas, Computabilidad y Complejidad”, estas áreas se relacionan entre sí.

1.-Teoría de la Complejidad: Los problemas computacionales son muy variados algunos son fáciles de resolver (problemas de ordenación) yotros son difíciles (problemas de horarios). A pesar de haberse investigado aún no existe una respuesta de que es lo que hace que ciertos problemas sean computacionalmente fáciles y otros difíciles.
En la teoría de la complejidad, los investigadores han descubierto una forma de clasificar a los problemas de acuerdo con su dificultad computacional. Con esta forma de clasificar, se puede demostrar unmétodo que permita establecer la dificultad computacional. Un campo de aplicación que ha sido afectado por la teoría de la complejidad es la criptografía.

2.-Teoría de la Computabilidad: Los matemáticos Kurt Godel, Alan Turing y Alonzo Church descubrieron que ciertos problemas no pueden ser solucionados por el computador. Por ejemplo: Problema de determinar cuándo una afirmación matemática esverdadero o falso. Parece natural solucionar una afirmación pues está en el contexto de la matemática, sin embargo un algoritmo no podría solucionarlo. La consecuencia de este descubrimiento fue el desarrollo de ideas relacionadas con los modelos teóricos para los computadores, que ayudaron la construcción de los actuales computadores.
La teoría de la Computabilidad y la complejidad estánrelacionadas pues: La complejidad tiene como objetivo clasificar los problemas en fáciles y difíciles y la Computabilidad su objetivo es clasificar los problemas que tienen y no tienen solución.
3.-Teoría de Autómatas: Está relacionado con las definiciones y propiedades de los modelos matemáticos para la computación. Los modelos matemáticos son importantes en las áreas aplicadas de la ciencia de lacomputación. Estos modelos son:
-Autómata finito: Usado en procesadores de texto, compiladores y diseño de hardware.
-Gramática libre de contexto: Usado en los lenguajes de programación e inteligencia artificial.
En resumen, la teoría de autómatas es el inicio para el estudio de la teoría de la computación, pues permite introducir conceptos relevantes a otras áreas no teóricas de la ciencia de...