Arboles y Grafos: 2015

RECURSIVIDAD

Propiedad de las funciones (métodos) para auto llamarse, son una alternativa a los procesos iterativos. (for, while do while)

Utilidad: cuando las soluciones iterativas son muy complejas.

Aplicaciones:

· Recorrido de estructuras no lineales.

· Formulas matemáticas complejas

TIPOS DE RECURSIVIDAD

Recursividad Directa: Cuando un método P contiene dentro de si un llamado a si mismo.

Recursividad Indirecta: Cuando un método P contiene dentro de si un llamado a otro método que que contiene llamados (directos o indirectos) a P.

Iteración	Recursividad
Ciclos (for, while, do while)	Funciones o métodos
No simplifica sino que pude tener lógica compleja en la solución de algunos problemas.	Simplifica la lógica en la solución de problemas.
Puede aumentar el código en la solución de algunos problemas.	Generalmente se reduce el código de programación.
No reduce codigo	Considerable consumo de memoria
Muy bajo consumo de memoria	Por cada autollamado el sistema operativo hace una copia completa de la función y son guardadas en la pila.

ITERATIVO

public static tipo nombreMetodo (arg){

________________
________________

for ()
________________
________________

while ()
________________
________________

do while ();

Iteractivo implementacion factorial 5! 1x2x3x4x5

public static long factorial (int n){

long f=1;

for (int 1 = 1; 1<= n; 1 ++){

f*= i;

return f;
}
}

______________________________________________________________________________

RECURSIVO

public static tipo nombreMetodo (arg){

if (indicar para autollamado)
________________
________________

nombreMetodo (arg)

}

Recursivo implementacion factorial 5! 1x2x3x4x5

APLICACIONES DE PILAS

Expresiones aritméticas

Notación Expresión Significado

inFija a+b*c Operador Medio

preFija +a*bc Operador Antes

posFija abc*+ Operador Después

PREFIJA

a + b * c

a + * b c

+ a * b c

a + b * c^ (1/2)

__________________________________________________________________________________

ARBOLES

Estructura de datos no lineales para organizar información por niveles.Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las cuales puede extenderse en ramificaciones hasta terminar, finalmente en una hoja

Utilidad: aplican cuando se requiera representar las estructuras con niveles y se pueda distinguir su organización tipo jerárquico, se diferencia entre valores mayores y menores.

Aplicaciones: organigrama, genealogía, representación y evaluación de expresiones aritméticas, ordenamiento y búsqueda.

MAS INFORMACIÓN SOBRE ARBOLES AQUI ---------><---------

Altura: cantidad de niveles 3

Peso: cantidad de hojas 7

Orden: cantidad de nodos del árbol 10

*Una colección de dos o más árboles se llama BOSQUE*

Los árboles constituyen estructuras de datos jerarquizados, y tienen multitud de aplicaciones, como.

• Análisis de circuitos, Representación de estructuras de fórmulas matemáticas

• Organización de datos en bases de datos

• Representación de la estructura sintáctica en compiladores.

• En muchas otras áreas de las ciencias del computador.

Se definen varios conceptos:

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

Posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.

Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

________________________________________________________________________________

ARBOLES BINARIOS

Arboles binarios: cada nodo tiene máximo dos hijos.

Aplicación: representación y evaluación de expresiones aritméticas. Búsqueda y ordenamiento.

Terminología: dos subarboles diferenciados en cada nodo (inclinación).

Completo: cada nodo tiene dos o cero descendientes.

Balanceado: para cada nodo la diferencia entre las alturas del subárbol derecho y del subárbol izquierdo debe ser menor que dos.

Degenerado: cada nodo solo tiene un hijo excepto la hoja.

Lleno: cada nivel tiene el máximo de nodos que soporta.

Arboles	A	B	C	D
Completo	✓	✗	✗	✓
Lleno	✗	✗	✗	✓
Degenerado	✗	✗	✓	✗
Balanceado	✓	✓	✗	✓

Se puede aplicar la formula 2h-1 para saber si un árbol se encuentra lleno. Donde h es igual al número de niveles del árbol.

Como resultado tenemos que el número de nodos de este árbol es 15, por lo tanto el árbol se encuentra lleno.

Implementación:

Podemos visualizar en el siguiente arreglo los subíndices de los descendientes de cada nodo ordenados en dos vectores hijos.

Nodos: el siguiente es un bosquejo de la estructura del nodo utilizado para los arboles binarios.

Clase de la estructura del nodo de árbol binario.

public class NodoArbolBin <T>{

private T dato;

private NodoArbolBin izq;

private NodoArbolBin der;

public NodoArbolBin(T dato) {

this.dato = dato;

izq = der = null;

}

public NodoArbolBin(T dato, NodoArbolBin izq, NodoArbolBin der) {

this.dato = dato;

this.izq = izq;

this.der = der;

}

public T getDato(){

return dato;

}

public NodoArbolBin getIzq(){

return izq;

}

public NodoArbolBin getDer(){

return der;

}

public void setIzq(NodoArbolBin izq){

this.izq=izq;

}

public void setDer(NodoArbolBin der){

this.der=der;

}

Clase principal donde se organiza el árbol binario del esquema.

public class Principal {

public static int n;

public static void main(String[ ] args) {

Recorrido r = new Recorrido();

NodoArbolBin raiz = new NodoArbolBin("A",new NodoArbolBin("B",new NodoArbolBin("D"),null),new NodoArbolBin("C",new NodoArbolBin("E"),new NodoArbolBin("F")));

System.out.print("Preorden: ");

r.preOrden(raiz);

System.out.println();

System.out.print("Inorden: ");

r.inOrden(raiz);

System.out.println();

System.out.print("Posorden: ");

r.posOrden(raiz);

System.out.println();

}

Arboles binarios recorridos

Actividades Recorridos Com.Actividades
1 Visitar raiz (S.O.P()) PreOrden (1), 2, 3
2 Recorrer Arbol (R) InOrden 2, (1), 3
3 Recorrer Subarbol PosOrden 2. 3, (1)

Pre (A), B, D, C, E, F
In D. B, (A), E, C, F
Pos D, B, E, F, C, (A)

_______________________________________________________________________________

Arboles Binarios De Expresión De Búsqueda (A.B.B)

Se utilizan para representar y evaluar expresiones aritmeticas, son arboles binarios completos donde las hojas son operando y el resto de nodos operadores

Expresion: a + b * c

________________________________________________________________________

Arboles binarios Busqueda (A. B. B)

Su estructura permite implementar un algoritmo para ordenamiento y búsqueda mas eficiente que los que se puedan implementar y en las estructuras anterior mente vistas (estructuras lineales, vectores y listas).

Eficiencia: dado por el menor de las composiciones al hacer una búsqueda

Operaciones

Búsqueda para

Insertar: todos los nodos deben tener las claves de mayor valor a la derecha y las claves de menor valor a la izquierda

Eliminar:

Hoja: simplemente se suprime

Nodo con subárbol: se reemplaza con su descendiente insertado

Nodo con dos subárbol: se puede reemplazar con el nodo mas a la izquierda del sub árbol derecho.

Se reemplaza con el nodo mas a la derecha del subárbol derecho

_____________________________________________________________________

Arboles binarios de búsqueda balanceado (A.V.L)

Proponen un algoritmo mejorado para recuperar la eficiencia que se pierda por la tendencia degenrado en los arboles ABB con operaciones de insertar y eliminar

FE: factor de equilibrio

HS: altura del subárbol izquierdo

HSD: altura del subárbol derecho

FE= hsi-hds

Para todos los nodos

FE>=-1 Y FE<=1 entonces árbol balanceado si no árbol NO balanceado

Operaciones

Insercion: inicialmente es el mismo proceso del ABB adicionalmente por cada inserción se calcula el FE para todos los nodos en la rama de la inserción partiendo de la hoja insertada y subiendo hacia la raíz. El proceso se detiene si: uno de los nodos tiene FE=0

Llegamos a la raíz y no se presentó FE que muestran desbalances no FE|>1

FE de un nodo presente |FE|>1 El árbol esta desbalanceado y necesita re estructuración en un proceso llamado rotación que recupera el balance y puede ser de tipos relación

_______________________________________________________________________________

Radix sort

Es un algoritmo de ordenamiento que ordena enteros y cadenas de caracteres procesándolos de manera individual.

Existen dos clasificaciones, el digito menos significativo y el más significativo.

Ejemplo:

Tenemos un vector de números enteros

Ordenamos el vector teniendo en cuenta el número entero por su digito menos significativo

Posteriormente reordenamos los números enteros en el vector teniendo en cuenta el siguiente número menos significativo de izquierda a derecha.

Por último realizamos la misma operación esta vez teniendo en cuenta el digito más significativo, que vendría siendo el digito que representa la centena en este caso.

Nuestra matriz quedaría ordenada definitivamente de la siguiente forma.

Ventajas:

En comparación con otros algoritmos de ordenamiento, Radix Sort es más rápido y fácil de usar.

Implementación:

Address Calculation Sort

Ahora aquí hay diez posibles primeros dígitos del 0 al 9. Así que vamos a crear diez subficheros inicialmente, cada uno de los sub-archivos está vacío.

25 57 48 37 12 92 86 33

DATO 25 SIGUIENTE null

La función debe tener la propiedad de que si x<=y, f(x)<=f(y). Esta función se denomina función preservadora de orden.

Al principio, cada uno de estos sub archivos está vacío. Ahora comenzar a escanear cada número. El primer número es 25. Su primer dígito es 2. Por lo tanto, se colocará en f(2). Así que un nodo almacena los datos y el próximo apunta al siguiente nodo.
A continuación, 57 se almacenarán en f(5) y así sucesivamente. Cuando el número 37 será tomado, obviamente, se almacenará en la ubicación f (3). Pero lo que si conseguimos el número 33 en la lista? Según la regla en la ubicación f(3), se almacena el 37. Este problema se resuelve mediante el mantenimiento de una lista enlazada que en realidad es una lista ordenada en f(3).

Y por lo tanto después de que el cálculo de la address calculation sort se realice el archivo se verá así.

Implementación:

/ * Dirección Cálculo Ordenar * /
/ * Se utiliza una función hash que ordenar sólo 2 puede nn dígitos. * /

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 5

lista struct
{Int información;
struct lista * siguiente;
} * Nodo [10] = {NULL};

struct lista * create ()
{
struct lista * temp = (struct lista *) malloc (sizeof (struct lista));
si (temp == NULL)
{Printf ("\ Error de asignación nMemory!");
exit (1);
}
volver temp;
}

struct lista * makenode (int num)
{
struct lista * temp;
temp = create ();
TEMP-> info = num;
TEMP-> siguiente = NULL;
volver temp;
}

struct lista * inserte (struct lista * s, int num)
{
struct lista * ptr, * temp;
ptr = s;
temp = makenode (num);
si (s == NULL)
s = temp;
más
{
/ * Código para la colocación de nuevo nodo en su caso
posición en el subarchivo * /
while ((ptr-> next-> info <= num) && (ptr-> siguiente! = NULL))
{Ptr = ptr-> siguiente;
}
si (TEMP-> info <ptr-> info)
{TEMP-> siguiente = ptr;
s = temp;
}
más
{TEMP-> siguiente = ptr-> siguiente;
ptr-> siguiente = temp;
}
}
volver s;
}

/ * Una función hash que opera sobre dos dígitos
sólo números * /

int hashfun (int n)
{Return (n / 10);
}

vacío addr_calc (int arr [], int size)
{
int i, j = 0, pos;
for (i = 0; i <tamaño; i ++)
{Pos = hashfun (arr [i]);
nodo [pos] = insertar (nodo [pos], arr [i]);
}
for (i = 0; i <10; i ++)
{While (nodo [i]! = NULL)
{Arr [j ++] = nodo [i] -> Información;
nodo [i] = nodo [i] -> siguiente;
}
}
printf ("salida \ nSorted es:");
for (i = 0; i <tamaño; i ++)
printf ("% d \ t", arr [i]);
getch ();
}

void main ()
{
int arr [MAX], i, n;
clrscr ();
printf ("Introduzca el número total de resolver?");
scanf ("% d", y n);
printf ("Introduzca los números?");
for (i = 0; i <n; i ++)
scanf ("% d", y arr [i]);
addr_calc (arr, n);
}

_________________________________________________________________________________

Método Quicksort

Sin duda, este algoritmo es uno de los mas eficientes. Este metodo es el mas rápido gracias a sus llamadas recursivas, basandose en la teoria de divide y vencerás.

Lo que hace este algoritmo es dividir recurvisamente el vector en partes iguales, indicando un elemento de inicio, fin y un pivote (o comodin) que nos permitirá segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los mayores que el pivote a su derecha y todos los menores a su izq. Al finalizar el algoritmo, nuestros elementos estan ordenados.

En esta figura se ilustra de mejor manera un vector con mas elementos, usando como

pivote el primer elemento:

Programa Quicksort

public class Ordenador {

public int[] quicksort(int numeros[])
//El metodo recibe los datos del arreglo
{
return quicksort(numeros,0,numeros.length-1);
//Llama al metodo quicksort para ordenar los datos
}
public int[] quicksort(int numeros[],int izq,int der)
//Recibe los valores del arreglo, el valor 0, y el tamano del arreglo
{
if(izq>=der)
return numeros;
/*Si izq que es igual a cero es mayor o igual a der que es el tamano del arreglo,
* el metodo regresa el arreglo.
*/
int i=izq,d=der;
//Se le asignan los valores de izq (0) & der(tamano del arreglo) a las variables i & d.
if(izq!=der)
//Si izq es diferente a der entonces se realiza lo siguiente
{
int pivote;
int aux;
pivote = izq;
while(izq!=der)
{imprimeArreglo(numeros);
while(numeros[der]>=numeros[pivote] && izq<der)
der--;
while(numeros[izq]<numeros[pivote] && izq<der)
izq++;
if(der!=izq)
{
aux = numeros[der];
numeros[der]= numeros[izq];
numeros[izq]=aux;}
}
if(izq==der){
quicksort(numeros,i,izq-1);
quicksort(numeros,izq+1,d);
}
}
else
return numeros;
return numeros;
}

public void imprimeArreglo(int arreglo[])
{
String imp="";
for(int i=0;i<arreglo.length;i++)
{
if(i!=arreglo.length-1)
imp=imp+arreglo[i]+",";
else
imp=imp+arreglo[i]+"";
}
System.out.println(imp);
}
public static void main(String[] args) {
int array[] ={4,2,5,7,6,1,3}; //Declaracion del arreglo
Ordenador a = new Ordenador();//Crea un objeto de la clase ordenador
a.quicksort(array);//Llama al metodo quicksort, con los datos del arreglo
}
}

__________________________________________________________________________________

Método ShellSort

Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.
Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
"Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos."
Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.

Programa ShellSort

public class ShellSort

{

private long[] data;

private int len;

public ShellSort(int max) {

data = new long[max];

len = 0;

}

public void insert(long value)

{

data[len] = value;

len++;

}

public void display()

{

System.out.print("Datos:");

for (int j = 0; j < len; j++)

System.out.print(data[j] + " ");

System.out.println("");

}

public void shellSort()

{

int inner, outer;

long temp;

//find initial value of h

int h = 1;

while (h <= len / 3)

h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)

while (h > 0) // decreasing h, until h=1

{

// h-sort the file

for (outer = h; outer < len; outer++)

{

temp = data[outer];

inner = outer;

// one subpass (eg 0, 4, 8)

while (inner > h - 1 && data[inner - h] >= temp)

{

data[inner] = data[inner - h];

inner -= h;

}

data[inner] = temp;

}

h = (h - 1) / 3; // decrease h

}

public static void main(String[] args)

{

int maxSize = 10;

ShellSort arr = new ShellSort(maxSize);

for (int j = 0; j < maxSize; j++)

{

long n = (int) (java.lang.Math.random() * 99);

arr.insert(n);

}

System.out.println("Datos no Ordenados");

arr.display();

arr.shellSort();

arr.display();

}

__________________________________________________________________________________

Búsqueda Secuencial

Definición:

Está diseñada para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La búsqueda secuencial busca un elemento de una lista utilizando un valor destino llamado clave.

En una búsqueda secuencial (a veces llamada búsqueda lineal), los elementos de una lista o vector

se exploran (se examinan) en secuencia, uno después de otro. La búsqueda secuencial es necesaria,

por ejemplo, si se desea encontrar la persona cuyo número de teléfono es 958-220000 en un directorio o listado telefónico de su ciudad. Los directorios de teléfonos están organizados alfabéticamente

por el nombre del abonado en lugar de por números de teléfono, de modo que deben explorarse

todos los números, uno después de otro, esperando encontrar el número 958-220000.

El algoritmo de búsqueda secuencial compara cada elemento del array con la clave de búsqueda

Programa

public class BSecuencial {

public static void main(String[] args) throwsIOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ",
"Abril"};

System.out.print("Digite el nombre que desea buscar: ");
String nombre = entrada.readLine();
// entrada de dato a buscar

for (int i=0; i<VectorNombres.length;i++){

if(nombre.equalsIgnoreCase(VectorNombres[i])){

JOptionPane.showMessageDialog(null,"Elemento encontrado "+VectorNombres[i],"Encontrado",
JOptionPane.INFORMATION_MESSAGE);
encontrados++;
continue;
}
}

if(encontrados == 1 ){
System.out.println("Fin de busqueda, encontrado "+encontrados+" elemento igual");
}else{
System.out.println("Fin de búsqueda, encontrados "+encontrados+" elementos iguales");

Búsqueda Hash

Función Hash

En informática, hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo

Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.

jueves, 4 de junio de 2015