Computabilidad







“2013 AÑO DEL CENTENARIO DEL NATALICIO DE GRISELDA ÁLVAREZ”

ESCUELA SUPERIOR DE INGENIERÍA MECÁNICA Y ELÉCTRICA


INVESTIGACIÓN


MATEMÁTICAS DISCRETAS

D.F., DEL. COYOACÁN A25 DE FEBRERO DEL 2013
INVESTIGACIÓN
“COMPUTABILIDAD Y COMPLEJIDAD”

Computabilidad
Dado un determinado problema, existe un algoritmo representable en una computadora que puede hallar susolución; entendiéndose un algoritmo como una secuencia o receta de pasos finitos que solucionan el problema.
Consiste en ser capaz de encontrar la representación adecuada para la descripción de un problemao fenómeno.
Para tal representación es necesario:
Un conjunto finito de símbolos.
Hacer asociaciones entre conceptos y elementos del lenguaje (de símbolos).
Encontrar las combinaciones adecuadasde símbolos para evitar ambigüedad.
Definir una manera de confirmar tal descripción para que terceros puedan reproducirla y llegar a los mismos resultados.

Teoría de Computabilidad.

La teoría dela computabilidad, también denominada de la recursión, es una de las cuatro partes que constituyen la lógica matemática siendo las otras tres, la teoría de conjuntos, teoría de modelos y teoría de lademostración, y se ocupa del estudio y clasificación de las relaciones y aplicaciones computables. Además, la teoría de la computabilidad, junto con la teoría de autómatas, lenguajes y máquinas, esel fundamento de la informática teórica y esta, a su vez, de la industria de los ordenadores.

Consiste en encontrar maneras de representar descripciones de procesos, de tal manera que se puedaasegurar si existe o no una representación.
Se dice que un algoritmo es una manera formal y sistemática de representar la descripción de un proceso.


Teoría de la complejidad computacional
La Teoríade la complejidad computacional es la parte de la Teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema. Un cálculo resulta complejo cuando es...