Computacion

Teoría de la computación
De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
La teoría de la computación es una rama de la matemática y la computación que centra su interés en laslimitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y laclasificación de problemas.
Contenido [ocultar]  * 1 Principales subramas * 1.1 Teoría de autómatas * 1.2 Teoría de la computabilidad * 1.3 Teoría de la complejidad computacional * 2 Otrassubramas * 3 Historia * 4 Referencias |
[editar] Principales subramas
[editar] Teoría de autómatas
Artículo principal: Teoría de autómatas.
Esta teoría provee modelos matemáticos que formalizanel concepto de computadora o algoritmo de manera suficientemente simplificada y general para que se puedan analizar sus capacidades y limitaciones. Algunos de estos modelos juegan un papel central envarias aplicaciones de las ciencias de la computación, incluyendo procesamiento de texto, compiladores, diseño de hardware e inteligencia artificial.
Los tres principales modelos son los autómatasfinitos, autómatas con pila y máquinas de Turing, cada uno con sus variantes deterministas y no deterministas. Los autómatas finitos son buenos modelos de computadoras que tienen una cantidad limitadade memoria, los autómatas con pila modelan los que tienen gran cantidad de memoria pero que solo pueden manipularla a manera de pila (el último dato almacenado es el siguiente leído), y las máquinas deTuring modelan las computadoras que tienen una gran cantidad de memoria almacenada en una cinta. Estos autómatas están estrechamente relacionados con la teoría de lenguajes formales; cada autómata esequivalente a una gramática formal, lo que permite reinterpretar la jerarquía de Chomsky en términos de autómatas.
Existen muchos otros tipos de autómatas como las máquinas de acceso aleatorio,...