Teoria De La cOmputaciòn

CreadOres: AdministradOr[jOn Vela Trujillo], ModeradOres: [Evert Valencia Chung], [Manuel Vazquez Montiel], [Erwind Vazquez Viveros] !!!
 
ÍndiceFAQBuscarRegistrarseMiembrosGrupos de UsuariosConectarse

Comparte | 
 

 Unidad 1: Introducción

Ver el tema anterior Ver el tema siguiente Ir abajo 
AutorMensaje
Admin
Admin
Admin
avatar

Cantidad de envíos : 15
Edad : 30
Fecha de inscripción : 19/09/2007

MensajeTema: Unidad 1: Introducción   Miér Sep 19, 2007 8:26 am





La teoría de la computación es una ciencia, en particular una rama de la matemática y de la computación que centra su interés en el estudio y definición formal de los cómputos.

Se le llama cómputo a la obtención de una solución o resultado (generalmente en el sentido matemático/aritmético del término), a partir de ciertos datos o entradas utilizando para ello un proceso o algoritmo

Desde épocas antiguas, los cómputos han existido y se han efectuado de manera mental o asistida por rudimentos como cuentas, lápiz y papel, o tablas.

Los antecedentes de la computación mecánica, pueden trazarse hasta épocas antiguas, con el desarrollo de artefactos para asistir el proceso de los cálculos matemáticos mentales, por ejemplo el ábaco, la regla de cálculo o el quipu.

Aunque quizás sea más propicia como ejemplo precursor, la célebre calculadora griega de Antikythera, utilizada según los expertos para asistir en cálculos astronómicos, y considerada por muchos como la primera computadora. Otro ejemplo precursor son las máquinas sumadoras de Blaise Pascal. Aparatos que demuestran una notable pericia de sus creadores en el conocimiento sobre la forma de elaborar los cálculos deseados, al grado de poder representarlos en la forma de mecanismos más o menos elaborados.

Sin embargo, la teoría de la computación como ciencia comienza propiamente a principios del siglo XX, poco antes que las computadoras electrónicas fuesen inventadas.

En ese época varios matemáticos se preguntaban qué clase de problemas de la matemática, podían resolverse por "métodos simples" y cuales no. Y para ello debían en principio desarrollar una definición de "método para resolver problemas", es decir, necesitaban el desarrollo de una noción formal (matemática) de lo que es un cálculo/algoritmos la aritmética lógica

Durante el siglo XIX y XX diversas corrientes filosóficas allanaron el camino de la computación a partir de las definiciones de sistemas formales. Destacando Kurt Gödel y Bertrand Russell entre otros.

Varias definiciones y modelos formales de lo que es un cálculo fueron propuestos por precursores del dominio como Alan Turing y Alonzo Church; entre esos modelos están la máquina de Turing, las funciones recursivas, y el cálculo Lambda. Todos los cuales se ha demostrado posteriormente que son equivalentes en expresividad computacional, es decir, todos pueden representar la misma clase de cómputos o algoritmos, aunque lo hagan de maneras diferentes.

Se asume normalmente que las computadoras electrónicas son también equivalentes en capacidad de cómputo a cualquiera de esos tres modelos mencionados anteriormente (si se asume que una computadora puede tener memoria infinita), pero no existe una prueba formal de ello (igualmente que no existen contraejemplos), por tal razón a tal presunción razonable se le conoce como la conjetura de Church-Turing.

De allí la relevancia del estudio de las máquinas de Turing, pues gracias a tal conjetura ampliamente aceptada como verdadera, todo problema de cómputo que sea resoluble en una máquina de Turing, se considera que también lo será en una computadora, y viceversa.

Es meritorio el hecho que gracias a la equivalencia de máquinas de Turing y computadoras, se haya determinado que existen cálculos que no pueden ser resueltos en un tiempo razonable en ninguna computadora imaginable, o incluso, que no pueden resolverse en lo absoluto, por ejemplo el problema de correspondencia de Post o el problema de predecir si una máquina de Turing cualquiera va a llegar a un estado final (conocido como el problema del halting en inglés, o problema de la parada).

Otros temas de interés de la teoría de la computación, son la cantidad de tiempo o la cantidad de memoria necesaria para realizar un cálculo dado. Se ha determinado que existen cómputos resolubles, pero que necesitan cantidades irrealistas de tiempo o memoria para poder efectuarse. Es sumamente importante para los especialistas del dominio conocer la complejidad computacional de un algoritmo, pues ésta determinará la aplicabilidad del mismo.

Otro interés de esta ciencia, son los modelos reducidos de cómputo, que son en realidad casos particulares de una máquina de Turing. Como lo son las máquinas de estado finito esbozadas primero por Warren McCulloch y Walter Pitts en 1943, y los autómatas con pila.

Descargate La Unidad I: EstadO Del Arte De La Teoria De La Computación
Volver arriba Ir abajo
Ver perfil de usuario http://jonbrt.iespana.es/index.html
 
Unidad 1: Introducción
Ver el tema anterior Ver el tema siguiente Volver arriba 
Página 1 de 1.

Permisos de este foro:No puedes responder a temas en este foro.
Teoria De La cOmputaciòn :: Teoria De La Computación :: Unidades-
Cambiar a: