domingo, 25 de abril de 2010
Proyecto 4
El tema que escojimos fue el de listas doblemente enlazadas.
Mis compañeras Danya Peralta y Lucero Guzman nos reunimos un par de ocasiones en la FIME para organizarnos y checar mas o menos como hariamos este proyecto e intercambiar nuestras ideas.
Entre las tres llegamos a una conclusion y es asi como hicimos nuestra presentacion.
Yo pienso que debo mejorar un poco en entender las clases, poner mas atencion aunque algunas las vemos algo rapidas y llega un momento en que no entiendo muy claro, es por eso qe acudo a las asesorias.
Nos hemos apoyado mutuamente, ya que si una no entiende algo, pues cualquiera de las otras 2 intregantes nos puede explicar y asi comprender mas el tema.
Se puede decir que las tres hacemos el trabajo por igual, y son muy buenas compañeras, ya que nos repartimos el trabajo de igual manera.
Estos proyectos son buenos hacerlos en equipo para poder apoyarnos entre si, ya que es algo dificil de comprender.
http://daaniiha.blogspot.com/
http://lucygc.blogspot.com/
domingo, 14 de marzo de 2010
Torres de Hanói
Introducción
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Pseudocódigo
Pseudocodigo Algoritmo Recursivo
hanoi(n, origen, destino, auxiliar)
si n=1
entonces
mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}
si no
//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino
//{mover n-1 discos de la torre auxiliar a la torre destino}
llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}
fin
fin
Pseudocódigo Algoritmo Iterativo
//los argumentos origen, destino y axuliar son variables representando las tres torres del problema original (pueden ser estructuras o simplemente el nombre de cada torre, en este caso solo representan el nombre de las torres por tanto, se asume que son de tipo texto).
//n es el numero de discos
//pilaN, pilaO, pilaD y pilaA son estructuras de tipo PILA
//tope es una variable de tipo entero.
//varaux es una variable de tipo texto (en este caso por que las torres son representadas unicamente por su nombre, es decir, esta variable debe ser del mismo tipo que origen, destino y auxiliar)
//bandera es una variable de tipo boleano
Solución Iterativa(n, origen, destino, auxiliar)
hacer tope=0 y bandera = falso
repetir mientras (n>0) y (bandera=falso)
repetir mientras (N>1)
//se guardan en las pilas los valores actuales de los parametros
tope=tope+1
pilaN[tope]=n
pilaO[tope]=origen
pilaD[tope]=destio
pilaA[tope]=auxiliar
n=n-1
varaux=destino
destino=auxiliar
auxiliar = varaux
Fin //fin de repetir mientras (N>1)
mover disco de origen a destino
bandera=verdadero
si tope >0 entonces //quiere decir que las pilas no estan vacias
n=pilaN[tope]
origen=pilaO[tope]
destino=pilaD[tope]
auxiliar=pilaA[tope]
tope=tope-1
mover disco de origen a destino
n=n-1
varaux=origen
origen=auxiliar
auxiliar=varaux
bandera=falso
Fin //fin de si tope >0 entonces
Fin //fin de repetir mientras (n>0) y (band=falso)
Fin //fin del metodo
hanoi(n, origen, destino, auxiliar)
si n=1
entonces
mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}
si no
//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino
//{mover n-1 discos de la torre auxiliar a la torre destino}
llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}
fin
fin
Pseudocódigo Algoritmo Iterativo
//los argumentos origen, destino y axuliar son variables representando las tres torres del problema original (pueden ser estructuras o simplemente el nombre de cada torre, en este caso solo representan el nombre de las torres por tanto, se asume que son de tipo texto).
//n es el numero de discos
//pilaN, pilaO, pilaD y pilaA son estructuras de tipo PILA
//tope es una variable de tipo entero.
//varaux es una variable de tipo texto (en este caso por que las torres son representadas unicamente por su nombre, es decir, esta variable debe ser del mismo tipo que origen, destino y auxiliar)
//bandera es una variable de tipo boleano
Solución Iterativa(n, origen, destino, auxiliar)
hacer tope=0 y bandera = falso
repetir mientras (n>0) y (bandera=falso)
repetir mientras (N>1)
//se guardan en las pilas los valores actuales de los parametros
tope=tope+1
pilaN[tope]=n
pilaO[tope]=origen
pilaD[tope]=destio
pilaA[tope]=auxiliar
n=n-1
varaux=destino
destino=auxiliar
auxiliar = varaux
Fin //fin de repetir mientras (N>1)
mover disco de origen a destino
bandera=verdadero
si tope >0 entonces //quiere decir que las pilas no estan vacias
n=pilaN[tope]
origen=pilaO[tope]
destino=pilaD[tope]
auxiliar=pilaA[tope]
tope=tope-1
mover disco de origen a destino
n=n-1
varaux=origen
origen=auxiliar
auxiliar=varaux
bandera=falso
Fin //fin de si tope >0 entonces
Fin //fin de repetir mientras (n>0) y (band=falso)
Fin //fin del metodo
Algoritmo recursivo
La Torre de Hanoi suele aparecer como ejemplo para ilustrar el concepto de recursión en los cursos de programación de computadoras, ya que existe un algoritmo recursivo sorprendentemente simple que lo resuelve (por si alguien no lo sabe, un algoritmo es recursivo si se llama a sí mismo en alguno de sus pasos). Supongamos que queremos trasladar los ocho discos del poste A al poste C. Como el disco 8 siempre está abajo del todo, la única forma de hacerlo es trasladar primero la torre de siete discos 1...7 al poste B. Entonces podremos llevar el disco 8 de A a C, y para terminar tendremos que trasladar de nuevo la torre 1...7, ahora de B a C.
Pero los discos 1...7 forman una torre totalmente similar a la inicial, así que en dos de los tres pasos anteriores nos enfrentamos con un problema análogo al original. De hecho, puede resolverse de la misma forma, trasladando ahora la torre 1...6. Por ejemplo, el primer paso (trasladar la torre 1...7 de A a B) se puede descomponer en estos tres pasos.
Por supuesto, en dos de estos tres pasos nos volvemos a encontrar con el problema original, ahora con n = 6. El proceso no es infinito, ya que llega el momento en que una torre equivale a trasladar un solo disco (esto ocurre cuando la torre es de un solo disco, claro). En resumen, el algoritmo recursivo es el siguiente.
Algoritmo para trasladar la torre 1...n del poste X al poste Z, usando como auxiliar el poste Y.
1.-Si n = 1, lleva el disco 1 de X a Z y termina.
2.-Traslada la torre 1...n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z.
3.-Lleva el disco n de X a Z.
4.-Traslada la torre 1...n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X.
Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. En realidad, lo único que hace es especificar unos pasos inevitables. Por ejemplo, como vimos antes, para resolver el puzzle es obligatorio llevar el disco n de A a C, y para ello es obligatorio llevar antes la torre 1...n a B, etc. La secuencia de movimientos que produce este algoritmo es la única solución óptima (o sea, de longitud mínima) posible. El número de movimientos es M3(n) = 2n−1, como se puede demostrar fácilmente por inducción sobre el número de discos.
Se cumple para n = 1
M3(1) = 1 = 21−1.
Si se cumple para n, se cumple para d+1
Al ejecutarse el algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así queM3(n+1) = 2 × M3(n) + 1 = 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1.
Para n = 8 el número de movimientos es de 28−1 = 255. Para n = 64, de 264−1 = 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.
Los algoritmos recursivos funcionan bien con ordenadores, pero son difíciles de aplicar para un ser humano. Si intentas resolver la torre de ocho discos aplicando el método descrito es fácil que te pierdas a no ser que vayas tomando notas de por dónde vas. Incluso para los ordenadores los algoritmos recursivos suelen ser poco económicos, en el sentido de que consumen bastante memoria (y es que ellos también necesitan. La alternativa a los algoritmos recursivos son los iterativos, en los que no hay llamadas a sí mismo, sino uno o varios bucles. Muy a menudo no existe o no se conoce una alternativa iterativa para un algoritmo recursivo, y cuando sí se conoce, suele ser mucho más complicada que la versión recursiva. Sin embargo, en el caso de la Torre de Hanoi, existen varios algoritmos iterativos muy simples.
La Torre de Hanoi suele aparecer como ejemplo para ilustrar el concepto de recursión en los cursos de programación de computadoras, ya que existe un algoritmo recursivo sorprendentemente simple que lo resuelve (por si alguien no lo sabe, un algoritmo es recursivo si se llama a sí mismo en alguno de sus pasos). Supongamos que queremos trasladar los ocho discos del poste A al poste C. Como el disco 8 siempre está abajo del todo, la única forma de hacerlo es trasladar primero la torre de siete discos 1...7 al poste B. Entonces podremos llevar el disco 8 de A a C, y para terminar tendremos que trasladar de nuevo la torre 1...7, ahora de B a C.
Pero los discos 1...7 forman una torre totalmente similar a la inicial, así que en dos de los tres pasos anteriores nos enfrentamos con un problema análogo al original. De hecho, puede resolverse de la misma forma, trasladando ahora la torre 1...6. Por ejemplo, el primer paso (trasladar la torre 1...7 de A a B) se puede descomponer en estos tres pasos.
Por supuesto, en dos de estos tres pasos nos volvemos a encontrar con el problema original, ahora con n = 6. El proceso no es infinito, ya que llega el momento en que una torre equivale a trasladar un solo disco (esto ocurre cuando la torre es de un solo disco, claro). En resumen, el algoritmo recursivo es el siguiente.
Algoritmo para trasladar la torre 1...n del poste X al poste Z, usando como auxiliar el poste Y.
1.-Si n = 1, lleva el disco 1 de X a Z y termina.
2.-Traslada la torre 1...n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z.
3.-Lleva el disco n de X a Z.
4.-Traslada la torre 1...n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X.
Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. En realidad, lo único que hace es especificar unos pasos inevitables. Por ejemplo, como vimos antes, para resolver el puzzle es obligatorio llevar el disco n de A a C, y para ello es obligatorio llevar antes la torre 1...n a B, etc. La secuencia de movimientos que produce este algoritmo es la única solución óptima (o sea, de longitud mínima) posible. El número de movimientos es M3(n) = 2n−1, como se puede demostrar fácilmente por inducción sobre el número de discos.
Se cumple para n = 1
M3(1) = 1 = 21−1.
Si se cumple para n, se cumple para d+1
Al ejecutarse el algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así queM3(n+1) = 2 × M3(n) + 1 = 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1.
Para n = 8 el número de movimientos es de 28−1 = 255. Para n = 64, de 264−1 = 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.
Los algoritmos recursivos funcionan bien con ordenadores, pero son difíciles de aplicar para un ser humano. Si intentas resolver la torre de ocho discos aplicando el método descrito es fácil que te pierdas a no ser que vayas tomando notas de por dónde vas. Incluso para los ordenadores los algoritmos recursivos suelen ser poco económicos, en el sentido de que consumen bastante memoria (y es que ellos también necesitan. La alternativa a los algoritmos recursivos son los iterativos, en los que no hay llamadas a sí mismo, sino uno o varios bucles. Muy a menudo no existe o no se conoce una alternativa iterativa para un algoritmo recursivo, y cuando sí se conoce, suele ser mucho más complicada que la versión recursiva. Sin embargo, en el caso de la Torre de Hanoi, existen varios algoritmos iterativos muy simples.
Suscribirse a:
Entradas (Atom)
