Godieboy

Propiedades de las Transacciones

Queridos lectores, para empezar el año con el pie derecho os traigo a ustedes un libro que encontré en la red, bastante fácil de leer para los que se estén preparando para su curso toefl y contiene muchos tips útiles para hacer nuestro examen toefl y certificarnos en el idioma del inglés por un periodo de un año.

Nos menciona que podemos hacer cuando no sabemos una respuesta en el examen, nos dice como mejorar nuestro “tin marin de do pingüe”, que palabras son muy comunes en el examen y nos sugieren actividades para aprender palabras nuevas.

Una preciosidad, espero que les sirva y suerte en su examen, para aquellos que solo quieren aprender el idioma me parece que no es la mejor opcion pues el numero de palabras es reducido y mucho del texto se centra en como resolver el examen…. De igual manera el ingles se ha vuelto casi indispensable en estos dias y seguro les da una ayudadita.

Suerte a todos, espero hayan disfrutado las fiestas decembrinas.

Hola queridos lectores, como ya estuvo bien de tanta weba hoy aportare algo a la comunidad a peticion del publico. Como es que se aplican las pilas en problemas de recursion (al menos asi lo entendi en los comentarios).

Bueno para lograr este cometido vamos a definir lo que es recursion y pilas de una manera breve, si quuieren profundizar mas, deberán leer post anteriores.

Definición formal

Recursión.-(Segun wikipedia) es la forma en la cual se especifica un proceso basado en su propia definición.

Yo diría que la recursión se hace presente cuando, un proceso definido para darle solucion a un problema tenga que llamarse a si mismo 1 o varias veces para lograr su cometido. Hay muchos ejemplos de recursión. En esta ocasion lo representare con la siguiente imagen:

Bueno, esperando que ya se tenga mas clara la idea de recursión, continuaremos con la definición de pila.

Pila: Es una lista de elementos a la cual se le pueden insertar y retirar elementos solo por uno de los extremos. En consecuencia, los elementos de una pila seran retirados en orden inverso al que se insertaron. Ver detalle…

Pues bien, ahora lo que sigue es dar un ejemplo de como es que se fusionan estos dos conceptos.

Fusión

No me quebrare la cabeza y pondré un ejemplo típico de recursividad. Imaginemos que tenemos que calcular la siguiente operación: 6! (este es un numero factorial, para los que no están enterados, este numero se calcula así: 6*5*4*3*2*1=720, entonces 6!=720)

Suponiendo que tenemos el siguiente método que resuelve el problema:

Algoritmo

factorial( n )

si n=0 entonces

return 1; //estado básico del método recursivo

si no

return n*factorial(n-1); //llamada recursiva

Fin // si n=0

Fin //del método

Explicación

Pero que pasa cuando se llama el metodo a si mismo? que pasa con las variables?. Aqui es donde entran en accion las pilas. Estos valores son guardados en pilas para poder ser recuperados posteriormente de tal manera que no se altere el producto. Para expliar mejor eso, vamos la siguiete tabla:

En el primer paso n es igual a 4, por lo tanto siguiendo el algoritmo debe hacerse 4*3!, pero no puede realizarse la operación por que 3! no ha sido calculado. Así que hay que guardar el valor de n en la pila para calcular con el mismo algoritmo factorial el valor de 3!. Ahora continuamos trabajando con n=3. Tenemos otra vez la misma situación, el algoritmo quiere hacer la operación 3*2!, pero 2! no esta calculado aun, así que de nuevo guardamos el valor de n en la pila y continuamos con n=2. Esto se repetirá hasta que el método llegue a su estado básico, cuando esto suceda, el método factorial por fin arrojará un valor y se podrán empezar a calcular todos los valores que esperan en la pila. En el paso 6 extraemos el valor 1 de la pila y lo multiplicamos por el factorial de 0, de esta operación resulta 1. Se saca el 2 de la pila y se multiplica por el factorial de 1! recién calculado (!0*1=1!), se obtiene el factorial de 2! (!1*2=!2), y asi sucesivamente hasta obtener el !4. Espero aclarar su mente con la siguiente figurilla:

Ojalá que esta explicación macabra les sea de utilidad. Mucha suerte en todo.

Fin

Hace unos días escuche esta frase:

No hay preguntas tontas, solo tontos que no preguntan someone

Y la neta la gente a veces no pregunta por que no entiende o le da weba así que si alguna vez estas en alguna clase y tienes dudas aunque parezca tonta, pregúntale al profesor el te dirá la respuesta o por lo menos te dará alguna pista si no entonces pregúntale a Mr google .

Hice una clase Pila como se explico uno posts antes para que hagan el ejercicio de las torres de hanoi sin recursividad.

Si hay algun error favor de avisar en los comentarios

Clic para ver el codigo .. Seguirlo leyendo .

Al parecer los compas del notitec quieran hacer una parodia de naruto llamada narutec:

El plata de sasuke
El keko de rock lee
El ruko de naruto
El trip de kiba
El ayala de Neji
yo de chino
El big tio de chouji
El berna de Shikamaru

jajaja aca el post original Narutec

El post anteriores dimos solucion al problema de las torres de Hanoi, de manera recursiva y no recursiva. Para la segunda opcion utilizamos estructuras de tipo pila, pero algunos lectores me regañaron que por que no saben que es una pila, asi que este dia explicare de manera bastante simple lo que es una pila y como funciona.

Definicion formal

Pila: Es una lista de elementos a la cual se le pueden insertar y retirar elementos solo por uno de los extremos. En consecuencia, los elementos de una pila seran retirados en orden inverso al que se insertaron.

Ejemplos graficos

Imaginemos que queremos untar deliciosa y cremosa cajeta en estos panes, lo mas normal es que tomemos el pan que esta hasta arriba y untemos en él la cajeta, despues tomamos el que sigue, el que sigue, y asi hasta llegar al final. Seria mas incomodo sacar panes del medio para untarlos todos, o de la parte de abajo (que weba).

Otro ejemplo es una torre de discos, para sacar el disco de hasta abajo, tienes que sacar primero todos los que estan arriba de el, y es mas lata cuando no sabes que disco es, tienes que buscar de uno por uno e irlos sacando.

¿y pa que fregados me sirve eso?

Bueno, las utilidades de esta estructura son bastantes, entre ellas esta la construccion de calculadoras, sumulacion de recursion o recorrido de arboles por niveles entre muuuchas otras cosas mas. La forma de programarlas varian segun el lenguaje, pero a continuacion explicare estas pilas en forma de arreglos de elementos.

Las pilas en la programacion

Weno, suponiendo que tenemos un arreglo en cualquier lenguaje. Dependiendo del lenguaje podremos sacar valores de dicho arreglo en desorden si asi lo deseamos de diferentes formas, la idea es crear un arreglo con ciertas restricciones, en donde solo se puedan retirar elementos de un solo lado y solo se pueda retirar el elemento que esta hasta la orilla de dicho arreglo. Para retirar elementos es muy coum utilizar el metodo pop, y para introducirlos, el metodo push. Asi, deberemos bloquear todas las modificaciones que podamos hacerle al arreglo y manipular estos movimientos con metodos creados por nosotros que solo permitan sacar el elemento  que se encuentra en el tope e introducir nuevos elementos encima del tope.

Movimientos permitidos en una pila

Pseudocodigo de los metodos push y pop

Bueno, aca les dejo el pseudocodigo que deben utilizar para lograr agregar y quitar elementos de una cola

//este algoritmo almacena el valor dato en la pila manejando la variable tope como el puntero del ultimo elemento.
//max es el numero maximo de elementos que puede almacenar la pila

push(pila, max, tope, dato)

si tope < max //solo si deseamos manejar un limite de elementos en la pila si no, no es necesario
entonces

tope=tope + 1
pila[tope]=dato //almacena un nuevo elemento en el siguiente espacio disponible

si no

escribir “La pila esta llena”

Fin //si tope < max

Fin //del metodo

pop(pila, tope, dato)

si tope>0 //vemos si hay elementos en la pila
entonces

dato=pila[tope]
tope=tope-1

si no

escribir “Ya no hay elementos en la pila

Fin //si tope>0

Fin //del metodo

Si quieren dar solucion orientada a objetos, entonces deberan ponerle propiedades al objeto pila, en lugar de enviar los valores como parametro en los metodos. Depende del lenguaje que utilicen.

Si sigue sin servirles esto, poes…. ni modo jojojo!!!

Comenten xD

Ya explique el problema de las torres de Hanoi y publique una solucion recursiva a dicho problema. En este post pondre la solucion No recursiva  iterativa en modo de pseudocodigo.

Pseudocodigo

//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

solucionIterativa(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

Explicacion breve del pseudocodigo.

La recursion sacrifica mucho espacio en memoria para guardar el estado del flujo del programa en el momento en que la recursion es iniciada, por ello resulta costoso en cuanto a espacio en memoria y debemos buscar otro tipo de soluciones. En este caso simularemos la recursion utilizando pilas para guardar el estado de las variables.

En el algoritmo de recursion, utilizamos las variables n, origen, destino y auxiliar que pusimos como argumentos en el metodo HANOI. Bueno pues en este metodo tambien utilizaremos esas variables y para guardar el estado de cada una utilizaremos estructuras de tipo pila, crearemos una pila por variable y en estas pilas iremos guardando los valores que va tomando cada variable.

pilaN para guardar los valores de n
pilaO para guardar los valores de origen
pilaD para guardar los valores de destino
pilaA para guardar los valores de auxiliar

La variable tope la usaremos para indicar el ultimo valor de las pilas, es decir el que se encuentra hasta arriba por eso es de tipo entero, para indicar la posicion del elemento.

La variable varaux es una variable que sirve para rotar las pilas origen y destino, segun el movimiento que se desee hacer.

y la variable bandera, sirve como indicador, para saber si hay mas iteraciones que hacer o no, ya no habra mas movimientos que hacer si las pilas estan vacias.

En la siguiente tabla se muestran los valores que toman todas las variables en cada paso para un mejor entendimiento:

Comportamiento de variables en el metodo

tabla de valores que van adquiriendo las variables en cada paso

Donde A, B y C representan el valor existente en la variable origen, destino y auxiliar respectivamente y podemos ver como estos valores van cambiando de posicion conforme aumentan los pasos.

y donde

[A:C] quiere decir que se mueve el valor A al valor C (sin confundir que en realidad el movimiento es de la variable origen a la variable destino, como lo indica el algoritmo)

El día de today aprendí una cosa bien cura en mi clase de ingles, xD, algo muy útil.

Lo que significa la palabra

FUCK

Fornication
Under the
Conscentiment of the
King

Segun en la era prehistorica, no no tanto, en la edad media, antes de coger con cualquieera, una mujer, un hombre, un gato, un perro, un pay, tenias que pedirle permiso al rey del lugar, si no, te rebanaban the nuts o el rey se cogia 30 veces seguidas a la tia en cuestion…. no la neta o se que le pasaba a las tias pero algo asi ha de haber sido.

Tons ese es el origen de la palabra FUCK.

xD, bueno y que? a mi me dio risa ¬¬

Hoy quería hablarles de un pack de juegos pero dado que no sirve megaipload (¬¬), cambiare esa sesion por una divertidisima clase de arboles binarios.

Igualmente este sera un post divertidísimo =D, bueno en realidad no, pero igual les sirve para la escuela.

Intoducción

Primero, vamos a ver los tres tipos de recorridos que pueden llevarse a cabo en los arboles binarios para visitar todos los nodos que en el existen. Si no entienden estos términos ven la siguiente imagen:

Jaja, ya quedó claro?

Primero hay que definir recorrido de nodos de manera formal

Definición formal

Recorrido de nodos en un árbol binario: Visitar todos los nodos del árbol en forma sistemática de manera que solo sean visitados una sola vez.

Tipos de recorridos

Hay tres formas de hacerlo:

Recorrido preorden.- Hay que visitar los nodos en el siguiente orden:

Recorrido preorden

-Raíz
-Sub arbol izquierdo
-Sub árbol derecho

Recorrido inorden.-Hay que visitar los nodos en el siguiente orden:

recorrido inorden

-Sub arbol izquierdo
-Raíz
-Sub árbol derecho

Recorrido postorden.-Hay que visitar los nodos en el siguiente orden:

Recorrido postorden

-Sub arbol izquierdo
-Sub árbol derecho
-Raíz

Tomando como ejemplo la imagen tendriamos despues de visitar los nodos del arbol los siguientes resultados:
Visita preorden  —> A B D E C F G
Visita inorden     —> D B E A F C G
Visita postorden —> D E B F G C A

Con esto dejo en sus manos el PSEUDOCODIGO para programar este algoritmo:

Pseudocodigo  preorden

preorden( nodo )

//donde nodo es un  registro de tipo puntero
//valor, nIzq y nDer son campos del registro nodo.
//valor = valor del nodo que se esta visitando
//nIzq y nDer= valor de tipo apuntador (sirven para no perder los nodos derecho e izquierdo y poder volver cuando se necesite)

si nodo <> NULO  entonces //(si nodo no es nulo/vacío)

visitar el nodo //nodo.info (obtenemos el valor del nodo )
preorden(nodo.izq) //llamamos de nuevo el método preorden mandando como parámetro el nodo izquierdo del nodo actual.
preorden(nodo.der) //llamamos de nuevo el metodo preorden mandando como parámetro el nodo derecho del nodo actual

fin

fin

Explicación visual del pseudocodigo

Por alguna razon, esta imagen me aclara mas la idea del pseudocodigo:

Mi explicacion grafica y chafa del pseudocodigo

Para realizar el pseudocodigo postorden e inorden pos namas cambia unas cosillas del anterior, si no sabes como hacerlo pues, pegate un tiro ¬¬, igual los dejo acá abajo para que no se awiten:

Pseudocodigo  inorden

inorden( nodo )

//donde nodo es un registro de tipo puntero
//valor, nIzq y nDer son campos del registro nodo.
//valor = valor del nodo que se esta visitando
//nIzq y nDer= valor de tipo apuntador (sirven para no perder los nodos derecho e izquierdo y poder volver cuando se necesite)

si nodo <> NULO  entonces //(si nodo no es nulo/vacío)

inorden(nodo.izq) //llamamos de nuevo el método inorden mandando como parámetro el nodo izquierdo del nodo actual.
visitar el nodo //nodo.info (obtenemos el valor del nodo )
inorden(nodo.der) //llamamos de nuevo el método inorden mandando como parámetro el nodo derecho del nodo actual

fin

fin

Pseudocodigo  postorden

postorden( nodo )

//donde nodo es un registro de tipo puntero
//valor, nIzq y nDer son campos del registro nodo.
//valor = valor del nodo que se esta visitando
//nIzq y nDer= valor de tipo apuntador (sirven para no perder los nodos derecho e izquierdo y poder volver cuando se necesite)

si nodo <> NULO  entonces //(si nodo no es nulo/vacío)

postorden(nodo.izq) //llamamos de nuevo el método postorden mandando como parámetro el nodo izquierdo del nodo actual.
postorden(nodo.der) //llamamos de nuevo el método postorden mandando como parámetro el nodo derecho del nodo actual
visitar el nodo //nodo.info (obtenemos el valor del nodo )

fin

fin

Espero y les sirva si no pos, que chafa soy. Cualquier duda o extra que quieran agregar, ya saben, existen los comentarios, ahí abajito, Agradezcan no sean weyes. Salep, estudien