Algoritmos

UNIVERSIDAD AUTONOMA DE MEXICO.
FACULTAD DE INGENIERIA.
INGENIERÍA PETROLERA.

ALUMNO: SALINAS CANO JOSE ALBERTO.
BLOQUE: 129
FECHA DE ENTREGA: 14 de agosto de 2012.
TAREA: 4
“FUNDAMENTOS DE ALGORITMOS”.

FUNDAMENTOS DE ALGORITMOS
Objetivo: El alumno explicará la importancia de llevar un método formal para resolver problemas en la computadora; así mismo aplicará dicho método en laresolución de problemas matemáticos sencillos.
Contenido:
* La Computabilidad y Concepto de algoritmo: Máquina de Turing.

* Elementos de los algoritmos y tipos de datos

* Representación de los algoritmos (diagrama de flujo y pseudocódigo)

* Estructuras básicas (secuencia, condicional e iteración)

5.1 La Computabilidad y Concepto de algoritmo: Máquina de Turing.

Lateoría de la computabilidad, también denominada teoría de la recursión es una de las cuatro partes que constituyen la lógica matemática, siendo las otras tres, la teorías de conjuntos, la teoría de modelos y la teoría de la demostració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 a de autómatas,lenguajes y maquinas, es el fundamento de la informática teórica y esta, a su vez, de la industria de los ordenadores.
Desde tiempo inmemorial se sabe que cierta clase de problemas, la determinación del máximo común divisor de dos números enteros, mediante el algoritmo de Euclides, o la determinación de los números primos, mediante la criba de Eratóstenes, son algorítmicamente solubles, i.e., hayalgoritmos o procedimientos mecánicos que permiten obtener la solución del problema en cuestión. De manera que hasta principios del siglo XX se daba por hecho que existían algoritmos y que el único problema residía en determinarlos.
Así pues, si lo que se desea es determinar un algoritmo, no hay ninguna necesidad de definir la clase de todos los algoritmos; eso solo es necesario si se pretendedemostrar que algún problema no es algorítmicamente soluble, i.e., que para dicho problema no hay ningún algoritmo que lo resuelva.
Es posible que el primero en armar la no existencia de un algoritmo fuera Siete en 1908, quién dijo de los grupos de presentación ¯mita: \. . . la cuestión acerca de cuándo dos grupos son isomorfos no es soluble en general."
Pero parece ser que fue, por una parte, elproblema de la decidibilidad de la lógica de predicados planteado por Hilbert y Ackermann en su libro sobre lógica, publicado en 1928, y, por otra, el asunto de la solubilidad de todo problema matemático, lo que indujo, en aras a resolverlos, a diversos investigadores a partir de 1930, y entre los que cabe mencionar a GÄodel, Church y Turing, a proponer diversas formalizaciones del conceptoinformal de función mecánicamente computable. Debido a que de todas esas formalidades , y de otras propuestas por Keene, Post y Marko®, se demostró que eran dos a dos equivalentes, se propuso la hipótesis, conocida como Hipótesis de Church-Turing-Post-Keene, que arma la coincidencia entre el concepto- informal de función parcial mecánica o algorítmicamente computable, y el concepto formal, matemático,de aplicación parcial recursiva. Natural-mente, esa hipótesis, de carácter similar a otras hipótesis propuestas en las ciencias empiricas, no es demostrable, y su fundamento ultimo reside en lasequivalencias antes mencionadas.
Este curso estaría dedicado, en primer lugar, al estudio de diferentes clases de aplicaciones recursivas, desde las recursivas primitivas, hasta las parciales recursivas,pasando por las recursivas generales, así como al de diversas clases de relaciones, entre las que cabe citar a las recursivas primitivas, las recursivamente enumerables y a las recursivas, demostrando además, ciertos teoremas fundamentales de la teoría de la recursión, debidos en gran medida 12.
Kleene; y, en segundo lugar, a la aplicación de la teoría de la recursión a la demostración de la...