Blog del sitio: Tecnológico

Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...113   ()
Imagen de PEDRO FELIX HERNANDEZ FRIAS_12217045
de PEDRO FELIX HERNANDEZ FRIAS_12217045 - lunes, 9 de junio de 2014, 16:19
Todo el mundo
Definición: Estructura no lineal, cuya principal característica es la de relación jerárquica entre cada uno de los elementos que la conforman. Las estructuras jerarquizadas no lineales como cronogramas y un torneo deportivo pueden ser ejemplos visuales de un árbol.
 
Su estructura: 
1. Todo árbol esta formado por nodos del mismo tipo.
2. Los nodos se conectan entre si con relaciones unidireccionales o bidireccionales según sea el caso.
3. Todo árbol tiene un elemento principal, el cual es el centro de la estructura y recibe por nombre raíz.
4. Cada nodo conectado a la raíz principal forma un sub-árbol dentro de la estructura principal.
5. Los nodos pueden ser padres e hijos dependiendo de que parte de la estructura se este tratando.
6. Toda relación de conectividad entre un padre y un hijo se denomina rama.
7. Los nodos pueden tener descendientes, cuando un nodo no tiene descendiente se denomina hoja o terminal.
8. Si a un árbol le quitamos la raíz, este queda dividido en arboles cuyo nombre es bosque.
9. Se denomina grado de un nodo al número de hijos que este tiene. Por tanto las hojas tiene grado cero.
10. El nivel de un nodo es uno más la longitud de su camino desde la raíz. Es contar cuantas ramas son necesarias para llegar al nodo. Por tanto el nivel del nodo raíz es uno.
11. La altura de un nodo es lo opuesto a su nivel, su calculo se realiza con: uno más la longitud del camino más largo desde dicho nodo hasta a una hoja de cualquiera de sus ramas.
 
Árbol especificación general:
Estructura de datos en la cuál no se tiene restricciones o limitaciones en el grado de sus nodos. Los más generales son los árboles n-arios, en los cuales el grado máximo de cualquiera de sus nodos es un valor entero positivo n.
 
Gráfico de un árbol típico
 
Identifiquemos cada una de sus partes.
Nodo raíz =9
Nodos hojas o terminales = 1,3,4,10,12 y 14
Subarboles= Hay 3 que surgen de quitar la raíz. El que inicia con el nodo 2, el que inicia con el nodo 10 y el que inicia con el nodo 13.
Elementos del nivel 1= 9
Elementos del nivel 2 = 2, 10 y 13
Elementos del nivel 3 = 1,3,4,12 y 14
Altura del árbol= se calcula con la altura del nodo raíz en este caso 3.
Número de nodos del árbol= 9 nodos.
Número de terminales= 6 nodos.
Descendientes del nodo 13= nodo12 y nodo 14.
Todos los nodos fuera de la raíz son descendiente de esta.
 
Recorridos de los árboles.
Consiste en visitar todos y cada uno de los elementos que conforman el árbol. dad su definición general un árbol puede tener n ramas y cada rama con n nodos, por tanto su recorrido no es lineal aunque entre dos nodos solo exista una línea. Los dos recorridos generales son recorrido en profundidad y recorrido en anchura.
 
Recorrido en profundidad.
Consiste en ingresar a la raíz y alejarse de ésta lo más posible hasta alcanzar uno de los nodos hoja o terminales. Una vez visitado ese nodo, se da un paso hacia atrás para desde allí alejarse nuevamente a una hoja desde ese punto alternativo. Esto implica que por un mismo nodo se pueden pasar n veces, cuando se visita por primera vez, cuando se regresa desde cada uno de sus nodos hijos. Este tipo de recorrido de ver sistemático y ordenado motivo por el cual se general tres tipo de recorridos en profundidad los cuales son: preorden, inorden y postorden.
 
Árbol de ejemplo para realizar el recorrido.

 Árbol de ejemplo para realizar el recorrido.

 

Recorrido en profundidad preorden.
Clave del recorrido raíz, izquierda, derecha. Cuando llega a un subarbol vuelve y aplica la fórmula. Significa que de cada árbol o subarbol al que llegue imprime primero la raíz del mimos, luego el nodo terminal de la izquierda, luego el nodo terminal de la derecha. Este es un fenómeno que desde el punto de vista de la programación se hace de forma recursiva.
 
 

 

 

 

 

 
[ Modificado: lunes, 9 de junio de 2014, 16:43 ]
 
Imagen de PEDRO FELIX HERNANDEZ FRIAS_12217045
de PEDRO FELIX HERNANDEZ FRIAS_12217045 - lunes, 9 de junio de 2014, 15:18
Todo el mundo

Es una técnica de programación que se utiliza para realizar una llamada a una función desde la misma función

ITERATIVIDAD

Es una técnica de programación  se utiliza bucles para realizar ciertas acciones repetidamente, hasta que se cumpla una condición

 

 

 

 

 
Imagen de PEDRO FELIX HERNANDEZ FRIAS_12217045
de PEDRO FELIX HERNANDEZ FRIAS_12217045 - lunes, 9 de junio de 2014, 15:09
Todo el mundo

Pero la serpiente era astuta, más que todos los animales del campo que Jehová Dios había hecho; la cual dijo a la mujer: ¿Conque Dios os ha dicho: No comáis de todo árbol del huerto?

Y la mujer respondió a la serpiente: Del fruto de los árboles del huerto podemos comer; pero del fruto del árbol que está en medio del huerto dijo Dios: No comeréis de él, ni le tocaréis, para que no muráis.

Entonces la serpiente dijo a la mujer: No moriréis; sino que sabe Dios que el día que comáis de él, serán abiertos vuestros ojos, y seréis como Dios, sabiendo el bien y el mal.

Y vio la mujer que el árbol era bueno para comer, y que era agradable a los ojos, y árbol codiciable para alcanzar la sabiduría; y tomó de su fruto, y comió; y dio también a su marido, el cual comió así como ella.

Entonces fueron abiertos los ojos de ambos, y conocieron que estaban desnudos; entonces cosieron hojas de higuera, y se hicieron delantales.

Y oyeron la voz de Jehová Dios que se paseaba en el huerto, al aire del día; y el hombre y su mujer se escondieron de la presencia de Jehová Dios entre los árboles del huerto.

Mas Jehová Dios llamó al hombre, y le dijo: ¿Dónde estás tú?

Y él respondió: Oí tu voz en el huerto, y tuve miedo, porque estaba desnudo; y me escondí.

Y Dios le dijo: ¿Quién te enseñó que estabas desnudo? ¿Has comido del árbol de que yo te mandé no comieses?

Y el hombre respondió: La mujer que me diste por compañera me dio del árbol, y yo comí.

Entonces Jehová Dios dijo a la mujer: ¿Qué es lo que has hecho? Y dijo la mujer: La serpiente me engañó, y comí.

Y Jehová Dios dijo a la serpiente: Por cuanto esto hiciste, maldita serás entre todas las bestias y entre todos los animales del campo; sobre tu pecho andarás, y polvo comerás todos los días de tu vida.

Y pondré enemistad entre ti y la mujer, y entre tu simiente y la simiente suya; ésta te herirá en la cabeza, y tú le herirás en el calcañar.

A la mujer dijo: Multiplicaré en gran manera los dolores en tus preñeces; con dolor darás a luz los hijos; y tu deseo será para tu marido, y él se enseñoreará de ti.

Y al hombre dijo: Por cuanto obedeciste a la voz de tu mujer, y comiste del árbol de que te mandé diciendo: No comerás de él; maldita será la tierra por tu causa; con dolor comerás de ella todos los días de tu vida.

Espinos y cardos te producirá, y comerás plantas del campo.

Con el sudor de tu rostro comerás el pan hasta que vuelvas a la tierra, porque de ella fuiste tomado; pues polvo eres, y al polvo volverás.

Y llamó Adán el nombre de su mujer, Eva, por cuanto ella era madre de todos los vivientes.

Y Jehová Dios hizo al hombre y a su mujer túnicas de pieles, y los vistió.

Y dijo Jehová Dios: He aquí el hombre es como uno de nosotros, sabiendo el bien y el mal; ahora, pues, que no alargue su mano, y tome también del árbol de la vida, y coma, y viva para siempre.

Y lo sacó Jehová del huerto del Edén, para que labrase la tierra de que fue tomado.

Echó, pues, fuera al hombre, y puso al oriente del huerto de Edén querubines, y una espada encendida que se revolvía por todos lados, para guardar el camino del árbol de la vida.

Génesis 3:1-24

 

 
Imagen de HEYNIS BARROSO JIMENEZ_12217065
de HEYNIS BARROSO JIMENEZ_12217065 - lunes, 9 de junio de 2014, 14:26
Todo el mundo

Clase 04 de Junio de 2014

Arboles ABB: Árbol Binario de Búsqueda para ordenamiento, que mejora la eficiencia en proceso de búsqueda con respecto a las estructuras vistas anteriormente (arreglos y listas).

Operaciones: Insertar – Eliminar.

Insertar: En el orden en que lleguen las claves se forman al árbol insertando las claves mayores a la derecha y las claves menores a la izquierda.

Ejemplo: 12, 10, 9, 14, 17, 11, 8, 4, 7, 13 

Nota: Cuando el árbol está lleno es completamente eficiente.

Eliminar:

a. Hoja: Simplemente se suprime.

b. Nodo con un subárbol: Se reemplaza por su descendiente inmediato.

c. Nodo con dos subárbol: Se reemplaza por el nodo más a la izquierda del subárbol derecho o por el nodo más a la derecha del subárbol izquierdo.

Ejemplo Eliminar

 

AVL: Árbol binario de búsqueda balanceado, mejora la eficiencia en el proceso de búsqueda de los ABB, cuando estos en sus operaciones tienden a degenerarse.

Operaciones: Inserción – Eliminar

Inserción: Inicialmente es el mismo procedimiento ABB, pero adicionalmente se calcula el FE en todos los nodos de la rama de la inserción, iniciando por la hoja y terminando en la raíz; hasta que (FE=0) o (FE=Z o FE = -2), en este último caso se somete el árbol a un proceso de reestructuración llamado rotación y que puede ser de 4 tipos.

Criterio AVL

FE: Factor de Equilibrio.

FE: hsd – hsi

Hsd: altura subárbol derecho

Hsi: altura subárbol izquierdo

Para todos los nodos

Si (FE >-2 Y FE <2)

   Árbol balanceado

Sino

   Árbol no balanceado

Finsi

 

TIPOS DE ROTACION

Comprometen tres nodos principalmente desde el nodo con FE fuera del rango de balance descendiendo hasta la hoja insertada. 

1. CASO 1: II IZQUIERDA – IZQUIERDA

2. CASO 2: DD DERECHA – DERECHA

3. CASO 3: ID IZQUIERDA – DERECHA

4. CASO 4: DI DERECHA – IZQUIERDA

EJEMPLO: 24, 32, 18, 12, 7, 4, 10, 8, 14, 3, 16, 11, 15, 23, 27, 44, 70, 55, 30

ELIMINAR:

Se aplica la misma regla ABB, adicionalmente se calcula FE si esta fuera de rango de balance, se reestructura el árbol dependiendo del respectivo tipo de rotación. 

[ Modificado: lunes, 9 de junio de 2014, 15:45 ]
 
Todo el mundo

ÁRBOLES EN EXPRESIONES

 

Es un árbol binario completo usado para representar y evaluar expresiones aritméticas.  En éste las hojas son los operandos y el resto de nodos los operadores.

 

Expresión: A+B*C

 

ÁRBOLES BINARIOS DE BÚSQUEDA (ABB)

 

Implementan un algoritmo que permite crear una estructura que ordena y aumenta la eficiencia en el proceso de búsqueda en comparación con estructuras como vectores y listas enlazadas.

 

v OPERACIONES:

  • Búsqueda: inicia en la raíz comparando los elementos, si es igual fue encontrado, sino, si el elemento es mayor al de la raíz se salta a la derecha, sino a la izquierda. El proceso se repite tomando el actual nodo como raíz.
  • Insertar: se busca el dato clave, si no existe se crea un nodo y se inserta en el extremo de la rama recorrida. Si es mayor a la derecha, si es menor a la izquierda.
  • Eliminar: se busca el dato clave, si existe pueden darse 3 casos:

1.  Si es una hoja, simplemente se suprime.

2.  Si tiene un solo subárbol, se reemplaza por su descendente inmediato.

3. Si tiene dos subárbol, se reemplazará por el nodo más a la izquierda del subárbol derecho, o se reemplazará por el nodo más a la derecha del subárbol izquierdo.

 

Crear un ABB a partir de las siguientes clases: 33, 44, 22, 12, 2, 53, 40, 8, 3

 

A continuación se explica la secuencia en la que se realiza la inserción de nodos.

 

 

Eliminar los nodos con clave 4, 22 y 33

 

 

ÁRBOLES BINARIOS DE BÚSQUEDA BALANCEADO (AVL)

 

Debido a que los ABB pueden tener una tendencia degenerada que afecta la eficiencia en la búsqueda, se propone el algoritmo AVL el cual reestructura el árbol cuando pierda balance y permite recuperar la eficiencia.

 

FACTOR DE EQUILIBRIO (FE): para que un árbol esté balanceado su FE debe estar en el rango de mayor que -2 y menor que 2.

 

v OPERACIONES

  • Insertar: inicialmente se aplica la regla ABB y luego se calcula el FE en todos los nodos. En caso de que el FE salga del rango de balance, se reestructura el árbol a través de rotación.

  • Eliminar: se aplica la regla ABB pero adicionalmente se calcula el FE en la rama de la eliminación. Si hay desbalance se aplica la reestructuración de acuerdo al caso de rotación.
[ Modificado: miércoles, 11 de junio de 2014, 22:05 ]
 
Todo el mundo

Public Static tipo/Clase NombreMetodoRecursivo(parametro){

if(expresion logia){    <= Ayuda a controlar el autollamado 

//NombreMetodoRecursivo (Parmetro);

}else{

//NomnreMetodoRecursivo(parametro);

}

}Ejemplo Recursividad

n! = n*(n - 1)!

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

 

 
Imagen de Jean Carlos Robles Atencia
de Jean Carlos Robles Atencia - lunes, 9 de junio de 2014, 11:44
Todo el mundo

 

X. vacia                            x.poner('a');                                     

   llena                             x.poner('b');       

   poner                           x.poner('c'); 

   quitar                           x.poner('d'); 

                                      x.poner('e');  Cola llena 

                                      x.poner('f'); cola llena 

                                      x.poner(' ');  ok 

                                      x.poner('g');  cola llena 

 

x.quitar();

x.quitar();

x.poner('h');   col llena 

 

COLA CIRCULA 

Para saber que este llena frente tiene que estar en cero (0)

y que fin sea igual a max-1

llena = frente ==0 && fin== max -1

vacia = frente ==-1

 

PONER

if(fin== max-1){

fin=0;

}else{

fin ++;

}

c[ fin]=dato;

 

QUITAR

dato=c[frente];

if(frente==fn){

frente=fin=-1;

}else{

if(fente ==max-1){

frente=0;

}else{

frente ++;

}

}

 

Ejercicios, funciones de cola para :

condiciones :solo usar colas y variables simples 

1. invertir elementos 

2. eliminar el ultimo elemento 

3. hacer una copia 

4. elimina un elemento especifico

5. intercambiar extremos 

6.eliminar elelmentos repetidos consecutivamente 

 

Public Static Void EliminarRepCons(cola c){

Object dato1 = null;

Object dato2 =null;

cola d =new cola();

while(! c.vacia());{

dato1 =c.quitar();

if(!dato1equals (dato2)){

d.poner(dao1);

dato2=dato1;

}

}

while (! d.vacia ()){

c.poner (d.quitar());

}

}

 

RECURSIVIDAD 

1.UTIILIDAD

2.APLICACIONES

3.RECURSIVIDAD Vs ITERRACION

4. IMPLEMENTACION 

 

* Propiedad de las funciones para autollamarse, es una alternativa a los procesos itertativos

for

while

do while 

1. Cuando la solucion e problemas iterativamente es muy compleja 

2. recorridos de estructuras no lineales, formas matematicas complejas 

3. RECURSIVIDAD 

*Metodos 

*Reduccion de codigos 

*Simplicidad logica 

*Consumo excesivo de materia 

 

ITERACION 

*for, while, do while

* No reduccion de codigos 

*Dependiendo de la solucion la logica puede ser muy compleja 

*Bajo consumo de memoria 

 

 

 

 

 
Todo el mundo

REFLEXION EL PERDON

Entonces se le acercó Pedro y le dijo: Señor, ¿cuántas veces perdonaré a mi hermano que peque contra mí? ¿Hasta siete?

Jesús le dijo: No te digo hasta siete, sino aun hasta setenta veces siete.

Por lo cual el reino de los cielos es semejante a un rey que quiso hacer cuentas con sus siervos.

Y comenzando a hacer cuentas, le fue presentado uno que le debía diez mil talentos.

A éste, como no pudo pagar, ordenó su señor venderle, y a su mujer e hijos, y todo lo que tenía, para que se le pagase la deuda.

Entonces aquel siervo, postrado, le suplicaba, diciendo: Señor, ten paciencia conmigo, y yo te lo pagaré todo.

El señor de aquel siervo, movido a misericordia, le soltó y le perdonó la deuda.

Pero saliendo aquel siervo, halló a uno de sus consiervos, que le debía cien denarios; y asiendo de él, le ahogaba, diciendo: Págame lo que me debes.

Entonces su consiervo, postrándose a sus pies, le rogaba diciendo: Ten paciencia conmigo, y yo te lo pagaré todo.

Mas él no quiso, sino fue y le echó en la cárcel, hasta que pagase la deuda.

Viendo sus consiervos lo que pasaba, se entristecieron mucho, y fueron y refirieron a su señor todo lo que había pasado.

Entonces, llamándole su señor, le dijo: Siervo malvado, toda aquella deuda te perdoné, porque me rogaste.

¿No debías tú también tener misericordia de tu consiervo, como yo tuve misericordia de ti?

Entonces su señor, enojado, le entregó a los verdugos, hasta que pagase todo lo que le debía.

Así también mi Padre celestial hará con vosotros si no perdonáis de todo corazón cada uno a su hermano sus ofensas.

Mateo 18:21-35

Reflexion personal

La lectura hace referencia a que nosotros debemos perdonar a nuestros semejantes todas las veces que sea necesarias, así como lo hace Dios con nosotros cada vez que le fallamos, para los ojos de él no está bien visto que entre hermanos guardemos rencor en nuestro corazón y no seamos capaces de perdonar. Para pedirle perdón a él por nuestros actos debemos mostrar que también perdonamos los actos que cometen las otras personas contra nosotros.

 
Imagen de HEYNIS BARROSO JIMENEZ_12217065
de HEYNIS BARROSO JIMENEZ_12217065 - lunes, 9 de junio de 2014, 10:24
Todo el mundo

Clase 03 de Junio de 2014

Codigo:

public static void main preorden (NodoArbolBin r){

    if (r! = null){

    System.out.print (r.getDato ());   //  raiz

      Preorden (r.getIzq());                  // izq    

      Preorden (r.getDer());                  // der

    }

}

 

 

  

 

 

Preorden (3030)

 P.S.O

 

 

 

 

 

 

 

Nota: Aquí se guardan las copias que quedan pendiente, en la pila.

 

Public class Principal{

    Public static void main (String []arg){

           preorden (raiz);

     }

}

 

Nota: En el Inorden y Posorden se intercambian las funciones de acuerdo a su estructura.

 Tarea de Investigacion 

¿Cuáles son las funciones recursivas e iterativas?

 

Recursividad vs Iteración

Aspectos que hay que considerar al decidir cómo implementar la solución a un problema si es de forma iterativa o de forma recursiva:

  • La carga computacional (tiempo de CPU y espacio en memoria) asociada a las llamadas recursivas.
  • La redundancia (algunas soluciones recursivas resuelven un problema en repetidas ocasiones).
  • La complejidad de la solución (en ocasiones, la solución iterativa es muy difícil de encontrar).
  • La concisión, legibilidad y elegancia del código resultante de la solución recursiva del problema.

 

Recursividad vs. Iteración

1- Ambas realizan una repetición:

a) Solución iterativa repite el cuerpo del bucle.

b) Solución recursiva repite las llamadas al método recursivo.

2- Ambas tienen una condición de terminación.

a) Solución iterativa: termina cuando se incumple la condición de continuación del bucle.

b) Solución recursiva: se termina cuando una llamada alcanza el caso base (inducción) desencadenando una secuencia de vuelta atrás.

 

Backtracking: sucesión de pruebas tentativas.

3- Ambas se deben diseñar para converger a la solución (principio de convergencia, y que no se salten la condición de terminación).

a) Solución iterativa: se llega a cumplir la condición de terminación (esto se debe garantizar).

b) Solución recursiva: se debe garantizar que se llegue al caso base.

 

Principio importante: Toda solución recursiva puede encontrar una solución iterativa equivalente, mientras que lo contrario no siempre es cierto.

 

Ejemplo: Programa que calcula el factorial de un número

 

Nota: Las nuevas funciones consiste básicamente en la combinación de llamadas a otras funciones que resulten adecuadas a los fines que nos proponemos. Un caso particular surge cuando la función se llama a sí misma. Estas funciones suelen llamarse funciones recursivas. Obsérvese que la función recursiva se repite invocándose a sí misma. Esto lo hace desde la llamada inicial al programa. Así que para cada repetición hay una nueva llamada a la función original y cualquier otro procedimiento repetitivo que no implique una recursión es un procedimiento iterativo.

 _________________________________________________________

Arboles de Expresión: Son arboles binarios completos para la evaluación de expresiones aritméticas. En este, las hojas son los operandos y el resto de nodos los operadores.

Expresión: a + b * c

Posibles arboles: Ejemplos: Quiénes son y quiénes no. 

 

 

Criterio de estos dos arboles: 

 

Nota: Los operandos se almacenan en un nodo de la pila y los operandos aparte. 

[ Modificado: jueves, 12 de junio de 2014, 09:00 ]
 
Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...113   ()