ARBOLES

Definicion:
Es una estructura de datos no lineal para organizacion de informacion por niveles.

Utilidad:
Organizacion por jerarquia (diferenciacion entre elementos mayores y menores)
Aplicacion:
Estructuras organizacionales, tecnologica, ecpresiones aritmeticas, directorios,busqueda y ordenamiento.

Terminologia:

Nodo: Cada componente de un arbol, la comunicacion es descendiente, raiz hacia las hojas.

Subarbol: Es un nodo con sus descendientes.

Niveles: Posicion nodo en una linea horizontal

Peso: Cantidad de hojas

Altura: Cantidad de niveles

Nodo entero: tiene padres e hijos

Arbol general: Un arbol tienehijos indeterminadamente

Implementacion: 

Estatica ( vectores)

Dinamica (Nodos)

Arboles Binarios

Son aquellos que tienen maximo 2 hilos por nodos.

Completo: Todos los nodos tienen 1 o 0 hijos

Balanceado:  La diferencia entre las alturas de los subarboles para todos los nodos

Degenerado: Todos los nodos solo tienen un descendiente excepto las hojas

Lleno: Todos los niveles tienen el maximo de nodos 2n-1

Arboles binarios

Implementacion:

Funciones de recorrido

Arbol de expresiones

Arbol binario completo que se utiliza para representar y evaluar expresiones aritmeticas, en estos, las hojas son los operandos y el resto de nodos los operadores.

EXPRESION: a+b*c

Arboles abb:

Arbol binario de busqueda, contiene un  algoritmo que permite ordenar y hacer mas eficiente, el proceso de busqueda, que en las estructuras vistas anteriormente.

mayor eficiencia,menor numero de comparacion es al buscar un elemento.

en el proceso de búsqueda cuando se avanza se hace un descarte del 50%

Avl, operaciones

Insertar: se aplica inicialmente la misma regla de los ABB,pero adicionalmente se calcula el FACTOR DE EQUILIBRIO en la rama de la insercion.

FE= hSi(Altura subarbol izquierdo)- hSd(Altura subarbol derecho)

Comenzando por la hoja y subimos por la raiz. si se encuentran un nodo "FE=0"  o llegamos a la raiz con FE normal en balance, paramos si un nodo presenta FE fuera de un rango de balance, se produce una restauracion del arbol dependiendo de los siguientes casos: 

Casos de rotacion IZQUIERDA- IZQUIERDA (I.I)

Insertar c,b,a

Caso de rotacion  DERECHA- DERECHA( D.D)
Insertar: a,b,c

Caso de rotacion  IZQUIERDA - DERECHA (I.D)

Insertar:c,a,b

Caso de rotacion DERECHA- IZQUIERDA(D.I)
Insertar a,c,b

EJERCICIO:

INSERTAR EN EL ARBOL AVL LAS SIGUIENTES CLAVES:

8,15,5,17,23,29,39,36,30,44,3,4,9,11

Read More

Mapa mental pilas y colas

Read More

Cola circular, bicolas y recursividad

Cola circular

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. son un poco mas claras que las colas normales ya que esta permite que los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida y de esta forma se haría mas fácil la eliminación y la adición de un dato. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

En esta, las instrucciones son diferentes, ejemplo: cuando esta llena: (frente==0 &&fin==max-1)

Bicolas:

La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola. Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.

Esta estructura es una cola bidimensional en que las inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la bicola. Gráficamente representamos una bicola de la siguiente manera:



Recursividad:

Propiedad de las funciones (metodos) de auto llamarse, son una alternativa de los procesos iterativos. "Todo lo que se haga iterativamente tambien puede hacerse recursivamente"

"Todo lo que se haga con: "For- while- do while" son procesos iterativos"
La recursividad es util cuando el proceso iterativo es muy complejo.
-Recorrido de estructuras no lineales, solucion de formulas matematicas complejas-
- Recursividad vs Iteracion: Primero que todo, la recursividad se aplica en metodos, la iteracion se aplica con for, while, do-while.
-La recursividad tiene reduccion de codigo, la logica es simple, mientras que la iteracion no reduce el codigo.

Aunque si usted no ha comprendido bien la recursividad, la logica no le parecera simple, con respecto a la iteracion, la solucion (logica) depende del problema, y esta puede que sea muy compleja.
Aparentemente, la recursividad es mejor que las iteraciones, asi como ellas, esta tambien tiene us desventajas, como lo es el consumo considerable de memoria, ya que por cada autollamado se hace una copia de la funcion, que es guardada por el sistema operativo en una pila( llamado a subprogramas), Los procesos iterativos tienen un bajo nivel de consumo de memoria, por eso no se han desaparecido, ni creo que desapareceran, tienen un bajo nivel de consumo y son eficientes en sus procesos pequeños, ya que si toca, por ejemplo, imprimir 10 numeros con un "for", el solamente realiza 10 vueltas y los imprime, en cambio si usamos recursividad para imprimir los mismos 10 numeros, los imprimiria, pero esta duplicaria hasta 10 veces la cantidad de memoria por funciones.

Implementacion:
Igual que toda funcion, tiene una parte de acceso, para tener un modificador, puede tener un tipo, una clase, un nombre, y unos parametros( igual tiene sus variables, puede tener variables locales), expresado de la siguiente forma.

Acceso modificador/ clase nombre(parametros){
           //Variables locales
              //if(Condicion de parada){
                     Instrucciones
            }
 Instrucciones                              ---- Autollamado, Nombre(parametros actuales)




Consiste en, colocar el nombre del metodo con parametros actuales, es decir el mismo nombre del metodo se simula como un auto llamado, ella misma dentro de sus instrucciones se llama
-Los libros colocan como ejemplo los factoriales, aunque no creo que sea conveniente usar un proceso recursivo siendo este un proceso iterativo, pero bueno, recursivamente seria asi:

Si sabemos que n! = n*(n-1)!
entonces tenemos que:
5!=5*4!/24=120
4!=4*3!/6=24
3!=3*2!/2=6
2!=2*1!/1=2
1!=1*0!/1=1
0!=1
Vemos que "n" va disminuyendo entonces estoy seguro que (n==0) retorna un 1, pero si no  otra cosa, en codigo seria asi n*factorial (n-1)

public static long factorial(int n){
if(n==0){
return 1;
}else{
return n*factorial(n-1);
}
}
Cuando llegue hasta 0, una funcion iterativa normalmente no tiene funciones iterativas, solo tiene instrucciones condicionales que haran que en algun momento pare.

Read More

Quiz 2

Este fue el segundo quiz realizado

las respuestas son las siguientes:

Perfecto! :)

Expresion aritmetica:        (a+b)*c^1/2

                   -------        ab+*c^1/2

                   ------         ab+*c1^/2

                   ------         ab+c1^*/2

Respuesta:       -----    ab+c1^*2/

Read More

Colas

"¿Por que estas bloqueado?  - Por que tienes un solo cerebro y mientras estas pensando en muchas cosas dejaste la pregunta que te hice al final, es decir, en una COLA"


Definicion:  Es una regla que se aplica a una estructura lineal (arreglos y listas enlazadas) para que tengan un comportamieno FIFO( First in- First out) Primero en entrar - primero en salir, es decir primer elemento en almacenarse, primero en procesarse.

Una cola puede almacenar lo que nosotros queramos, números, personas, documentos, cualquier cosa. Esta estructura de datos tiene muchas aplicaciones en la informática al igual que la pila, por ejemplo cuando mandan a imprimir varios documentos a una impresora (Ejemplo puesto por el mismo profesor Juan Jose Puello), manda uno en word, manda otro en excel, manda otro en power point, para esto, existe una cola de impresión que sigue la filosofía, se imprimen los primeros documentos y si quiero imprimir un nuevo documento se adiciona al final de todos los documentos que están esperando a imprimirse.

Una vez comprendido en concepto ahora veamos como se implementa esto en un lenguaje de programación, por ahora lo implementaremos en Java. Java en sus librerías ya tiene la forma de implementar Colas (queue), nosotros ahora haremos como si no existiera, es decir crearemos nuestra versión, que es lo que generalmente se hace cuando se aprende colas en la universidad. Pues bien existen dos formas de implementar para que la cola sea o bien estática (reservamos un espacio fijo en memoria) o bien dinámica (el tamaño en memoria va creciendo según se requiere), se implementa con vectores o con listas enlazadas respectivamente. Nosotros implementaremos haciendo de un array bidimensional es decir de modo estático y al decir estático estamos diciendo que tendrá un limite para almacenar datos en la cola.

Para manipular elementos en el vector de la cola son necesarias variables que me digan en donde empiezan los elementos y otra en donde terminan, como tal vez estés pensando ¿porque no solo una? (una que me diga en donde termina asumiendo que siempre se empieza desde la posición 0 del vector), pues se puede implementar con solo una de estas variables pero presenta muchas desventajas pues si eliminamos un elemento de nuestra cola, (el primero justamente) tendríamos que recorrer todos los siguientes elementos una posición adelante y esta manera seria muy lenta de implementar pues que pasa si son 1000 elementos, eso es mucho tiempo perdido, entonces es por eso que usamos dos variables que me digan donde empieza y donde terminan los elementos de la cola, dos variables enteras que llamaremos inicio y fin, estas variables funcionan de la siguiente manera:

Colocar por un extremo, quitar por el otro

Por donde entra se colocaria la variable (Inicio) y por donde sale la variable( Fin), ahora, si consideramos que nuestro vector tiene 5 posiciones y deseamos ingresar un dato o, algo, primero debemos comprobar si esta llena la pila, o si esta vacia, ¿como lo hacemos? creando un metodo PUBLICO llamado "vacia" y otro llamado "llena", de la siguiente manera.

public boolean vacia() {retorna verdadero si la cola esta vacía es decir no tiene ningún elemento, para esto solo se pregunta si inicio es igual a fin.

public boolean llena(){ retorna verdad si es que la cola esta llena, pasa cuando se ha llenado todo el vector, la cantidad de elemento que permite la cola lo determina la variable Max.

poner() {adiciona un nuevo elemento a la cola, para esto solo se incrementa la variable fin y se coloca el elemento en esa posición.

quitar(){ extrae el primer elemento de la cola, para esto se retorna la posición inicio + 1 del vector y se incrementa inicio en 1.

Con todos estos métodos básicos se puede realizar cualquier operación que necesitemos

UTILIDAD: SIEMPRE QUE LOS RECURSOS DE PROCESAMIENTO SEAN MENORES A LAS DEMANDAS DE SU USO.

APLICACIONES: COLA DE PROCESOS, COLA DE IMPRESIÓN, SIMULACION

OPERACIONES: PONER Y QUITAR.

IMPLEMENTACION: VECTORES, LISTAS ENLAZADAS

coloquemos como ejemplo una variable que trabaje como un semáforo y los procesos como los carros. Los procesos pueden ser cooperativos o independientes. Dos o más procesos pueden cooperar mediante señales de forma que uno obliga a detenerse a los otros hasta que reciban una señal para continuar.
Se usa una variable de tipo semáforo, es decir,  para sincronizar los procesos.
Si un proceso está esperando una señal, se suspende hasta que la señal se envíe.
Se mantiene una cola de procesos en espera en el semáforo.
La forma de elegir los procesos de la cola en espera es mediante una política first in first out.
Asi como los procesos que hacemos que realice el sistema operativo de nuestro pc. igual.

Read More

Expresiones Aritmeticas: Evaluar sin parentesis y orden de prioridades

En informática y lenguajes de programación, se entiende por expresión aritmética a aquella donde los operadores que intervienen en ella son numéricos, el resultado es un número y los operadores son aritméticos. Los operadores aritméticos más comúnmente utilizados son: + , - , * , / y %.

Operadores: Símbolo que indica al compilador que ejecute determinadas operaciones con los elementos sobre los que opera (aritméticos, lógicos, de cadena y de comparación).

Operandos: constantes, variables u otras expresiones.

infija: 1+2*3                :  Operadores en medio ( la unica que tendra parentesis)   : 7
prefija: +1*23              : Operadores antes (orden de prioridades)                       :
posfija: 123*+             : Operadores despues (orden de prioridades)                   : 7        
( El primero que sacamos va a la derecha y el segundo a la izquierda, entre el signo)

REGLAS:
1. La evaluación de las operadores con la misma prioridad se realiza de izquierda a derecha.
2.Se toman los dos primeros operadores, si son de igual jerarquía, se realiza el más a la izquierda.
3.Se toman los dos primeros operadores, si son de diferente jerarquía, se mira el tercer operador y se realiza el de mayor jerarquía que esté más a la izquierda.
4.Los paréntesis se resuelven completamente antes de realizar cualquier operación fuera de ellos, siguiendo las reglas dadas.
5. Los paréntesis más internos se resuelven primero, siguiendo las reglas dadas.

Read More

El hijo prodigo

La parábola del Hijo Pródigo ha tenido distintos títulos, porque todo depende de cómo la lee cada uno y de la resonancia que tiene en el corazón de cada uno. Porque, a diferencia de otras parábolas, ésta tiene mucho de personal, de retrato de cada uno de nosotros. Es la parábola de Dios Padre. Es la parábola del corazón de Dios. Pero también es la parábola de cada uno de nosotros.

Porque, de una manera u otra:
Todos hemos tenido nuestras rebeldías interiores.
Todos hemos tenido nuestras experiencias de irnos de casa.
Todos hemos olvidado alguna vez el corazón y el dolor de nuestro Padre Dios.
Todos hemos vivido nuestros momentos de terribles vacíos interiores.
Todos hemos sentido miedo a que nos rechacen y echen de casa al llegar.

Porque ¿quién puede decir que, en algún momento de su vida, no le hemos reclamado a Dios nuestra libertad para hacer lo que nos venía en gana creyendo que sólo nosotros sabemos lo que nos conviene y nos hace felices?
Porque ¿quién de nosotros nunca ha experimentado el frío de la noche sin el calor del hogar paterno?
Porque ¿quién de nosotros no ha pasado por esos momentos en los que, en vez del pan caliente del hogar, hemos alimentado nuestras vidas con las cosas placenteras o de la borrachera o simplemente de prescindir de todo?
Porque, ¿quién de nosotros no ha tenido miedo a regresar o que incluso ha regresado y no siempre ha encontrado unos brazos calientes sino el rechazo y el mal humor de un confesor con dolor de hígado?
Porque, ¿quién no ha experimentado, alguna vez en su vida, unos brazos abiertos y calientes y unos besos que nos han abierto la puerta del regreso y nos han invitado a la mesa de la Eucaristía?

En algún momento de nuestras vidas nos hemos sentido ese “hijo que pide su herencia” y se larga de casa. O hemos sentido que más nos parecemos a nuestro hermano mayor, legalista y sin conocer el amor, que se niega a creer en nuestro regreso y hasta se escandaliza de que Dios nos ame tanto a los pródigos y haga fiesta por nosotros.

Pero la parábola no tiene tanto la finalidad de describirnos a nosotros mismos, sino de describir el corazón de Dios y de invitarnos a amar como él ama y a perdonar como él perdona y a celebrar como él celebra el regreso de alguien a la casa de la Iglesia que es la casa del Padre. Él sale a recibir al hijo que regresa de lejos. Y sale a llamar al hijo que está cerca y se niega a entrar.

Read More