Teoria de la computacion

Subdirección Académica Departamento de sistemas y computación.

Teoría de la computación
Nombre: Medina Barrón Javier Andrés Carrera: Ing. En Sistemas Computacionales. Periodo: Febrero-Junio 2010Numero de control: 08210772 Fecha de entrega: 07/Junio/2010. Profesora: Enrique Comer Barragán Unidad: V Tema: Ensayo

1

Teoría de la computación.
Introducción. Antes que nada debemos deconocer de antemano el concepto en si de lo que es la Teoría de la computación, la cual es una rama de la matemática y computación que centra su interés en las limitaciones y capacidades fundamentales delas computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo y la clasificación de problemas de acuerdo a u grado de dificultad. Tras esteconcepto nos centraremos y daremos más profundidad al tema en cuestión.

Desarrollo. Dentro de lo aprendido al transcurrir a lo largo del semestre fuimos aprendiendo diversas cosas acerca de la materia,principalmente temas que tiene que ver con las principales subramas de la teoría de la computación. Acerca del tema de la teoría de autómatas, vimos como es que estos modelos matemáticos formalizan ensi el concepto de computadora o algoritmo de manera simplificada y que analizan a su vez las capacidades y limitaciones. Los principales modelos de autómatas son los finitos, pila y con maquina deturing de los cuales cada uno a su vez tiene sus variantes tanto deterministas como no deterministas.

2

La segunda subrama tratada es acerca de la teoría de la computabilidad, en la cual seexplora los límites de la posibilidad de solucionar problemas mediante algoritmos. Los problemas en este caso en particular se clasifican en esta teoría de acuerdo a su grado de imposibilidad. Dependiendode este grado se clasifican los problemas como computables, en los cuales si existe un algoritmo que siempre resuelve estos problemas. Los semicomputables son aquellos para los cuales hay un...