Matematicas Discretas - Proyecto Final








Matemáticas Discretas
Grupo 1

Proyecto Final de Matemáticas Discretas
















1. Juego de la Torre de Hanoi

a) Contexto histórico (busque la leyenda).

Cuenta la leyenda que en el templo de Benarés, en India, se encontraba una cúpula que, por su posición, señalaba el centro de la tierra. Allí había una bandeja en la que se erguían tres agujasde diamante. Cierta mañana de lluvia, el rey en curso mandó a colocar 64 discos de oro, todos de distintos diámetros. Los 64 discos fueron apilados de mayor a menor en una de las tres agujas de diamante. Junto con los discos se dieron instrucciones claras acerca del manejo de dichos discos; "El sacerdote de turno no debe mover más de un disco a la vez, y no puede situar un disco de mayor diámetroencima de otro de menor diámetro".
Otra versión o variante de la leyenda de las Torres de Hanoi cuenta que fue Dios quien colocó los discos de oro; y se cree que el día en que los monjes coloquen los 64 discs en la tercera aguja, bajo las reglas del orden establecido, el templo se desmoronará y el mundo desaparecerá.
Por otra parte fue el matemático francés Édouard Lucas quien inventó este“juego matemático” en 1883. El “juego matemático” sigue las mismas reglas y patrones de la leyenda, sin embargo se usaron 8 discos de madera para el primer prototipo.



b) Descripción del juego

El juego en su forma más simple consiste en colocar determinado número de discos de madera de diferentes diámetros (dependiendo el número de discos es la dificultad del juego), apilados de mayor amenor. Debe haber al menos tres discos, y máximo los que la aguja o varilla permita. De igual forma se pretende pasar todos los discos a una de las otras dos varillas disponibles, en el mismo orden; Los discos deben moverse uno a la vez, y un disco de mayor diámetro no debe colocarse sobre uno de menor diámetro. Entre menos sean los movimientos realizados, mejor se cree que fue la resolución deljuego.

c) Un algoritmo recursivo para Hn
Según investigamos, la suma de los movimientos de cada disco sigue el siguiente patrón de comportamiento:
20 + 21 + … + 2n-1 = 2n-1
Para entender mejor el algoritmo será necesario ejemplificarlo en su forma más sencilla: Si n=1 (siendo n el número de discos que tenemos en la torre A), se traslada ese primer y único disco a cualquiera de las dos torreslibres (B o C), de esta forma, se termina con el juego.
Ahora bien, otra forma de entender mediante un algoritmo este juego es usando tres discos.


Ej: Supongamos que n = 3. Apliquemos el algoritmo.
1. n = 3
2. Se mueve tanto el disco 1 como el disco 2 de A a B usando como auxiliar C, de tal forma que los discos 1 y 2 sean llevados según las reglas del juego. El poste C puede ser usado comoapoyo, sin embargo este deberá quedar vacío para cuando los discos 1 y 2 queden en el poste B.
3. Se lleva el disco 3 del poste A al poste C. No se usa ningún poste auxiliar.
4. Se traslada el disco 1 y el disco 2 al poste C respetando las reglas del juego. Se podrá usar como auxiliar el poste A.

d) Una formula explícita para Hn
Hn = 2n -1

2. El Método de Newton-Raphson

a) Contextohistórico

El método de Newton-Raphson es un algoritmo o proceso que es de suma utilidad para hallar aproximaciones de los ceros o raíces de una función real. En ocasiones es usado puede también para encontrar el máximo o mínimo de una función.
El método de Newton-Raphson fue descrito por Isaac Newton en “De analysi per aequationes número terminorun ifinitas” escrito en 1669 y en “Demetodis fluxionum et serierum infinitarum” escrito en 1671. El método contiene el nombre de Newton y Raphson por que fueron estos dos personajes quienes desarrollaron el método. El matemático Joseph Raphson, quien era de origen inglés, de igual forma descubrió y publicó su método. Ambos fueron publicados en años distintos, sin embargo ambos matemáticos son contemporáneos de su época.
Newton...