| Búsqueda Binaria |
Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes:
 Debido a que el vector se encuentra ordenado si el dato que buscamos es mayor a la posición central se descartan todos los datos que se encuentren en la parte inferior, de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector. Una vez que encuentre el dato el método regresara la posición en que lo encontró (linea 12), en caso de no encontrar el dato en el vector regresara el valor -1  La implementación de este ejemplo del algoritmo de búsqueda binaria se encuentra en el lenguaje de programación Java. |
Busqueda Secuencial
En este ocasion voy a explicar los algoritmos de busquedas secuenciales , este tipo de algoritmos nos facilita la forma de hacer consultas ya sea en una tabla de una base de datos como en un vector o matriz de datos (que al final viene siendo lo mismo que en una base de datos; xD ).
Este tipo de busqueda tiene mas puntos en contra que a favor porque en un vector de N posicioneseste algoritmo va a buscar posicion a posicion hasta dar con el dato solicitado y en el caso de que no exista pues tambien va a recorrer todo el arreglo.
Lo bueno de este tipo de busqueda es que es muy sencillo de implementar y no se tiene que ordenar el vector si tomamos el ejemplo anterior todavia como valido.
Bueno mucha explicacion vamos a la practica...
Si tenemos un vector ya definido con los siguientes datos:
["aarona","aashta","abelarda","abelia","abigail","a bril"] , todos de
tipo String y queremos saber si ya existe el nombre : "Abigail" en nuestro vector entonces tenemos que hacer lo siguiente:
public class BSecuencial {
public static void main(String[] args)throws IOException {
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 busqueda, encontrados "+encontrados+" elementos iguales");
}
}
}
METODO DE BUSQUEDA HASHING
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.
FUNCION 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. Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada
VENTAJAS:
Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar
Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones
No se requiere almacenamiento adicional para los índices.
DESVENTAJAS:
El archivo no esta clasificado
No permite llaves repetidas
Solo permite acceso por una sola llave
Costos
Tiempo de procesamiento requerido para la aplicación de la función hash
ALGORITMO HASHING
Algoritmo que se utiliza para generar un valor de hash para algún dato, como por ejemplo claves. Un algoritmo de hash hace que los cambios que se produzcan en los datos de entrada provoquen cambios en los bits del hash. Gracias a esto, los hash permiten detectar si un dato ha sido modificado.
ALGORITMOS DE HASH MAS COMUNES
SHA-1: algoritmo de hash seguro Algoritmo de síntesis que genera un hash de 160 bits. Se utiliza, por ejemplo, como algoritmo para la firma digital.
MD2 y MD4 Algoritmos de hash que generan un valor de 128 bits.
MD5 Esquema de hash de hash de 128 bits muy utilizado para autenticación cifrada. Gracias al MD5 se consigue, por ejemplo, que un usuario demuestre que conoce una contraseña sin necesidad de enviar la contraseña a través de la red.
FUNCIONES DE HASH
Residuo de la división
Medio del cuadrado
Pliegue
RESIDUO DE LA DIVISIÓN
La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor). Mientras que el valor calculado real de una dirección relativa, dados tanto un valor de llave como el divisor, es directo; la elección del divisor apropiado puede no ser tan simple. Existen varios factores que deben considerarse para seleccionar el divisor:
RESIDUO DE LA DIVISIÓN
El rango de valores que resultan de la operación "llave % divisor", va desde cero hasta el divisor 1. Luego, el divisor determina el tamaño del espacio de direcciones relativas. Si se sabe que el archivo va a contener por lo menos n registros, entonces tendremos que hacer que divisor > n, suponiendo que solamente un registro puede ser almacenado en una dirección relativa dada.
El divisor deberá seleccionarse de tal forma que la probabilidad de colisión sea minimizada. ¿Como escoger este numero? Mediante investigaciones se ha demostrado que los divisores que son números pares tienden a comportase pobremente, especialmente con los conjuntos de valores de llave que son predominantemente impares. Algunas investigaciones sugieren que el divisor deberá ser un numero primo. Sin embargo, otras sugieren que los divisores no primos trabajan también como los divisores primos, siempre y cuando los divisores no primos no contengan ningún factor primo menor de 20. Lo mas común es elegir el número primo mas próximo al total de direcciones.
RESIDUO DE LA DIVISIÓN
Ejemplo:
Numero de direcciones 996. La eleccion de m sera 997, que es el primo mas cercano. Se aplica esta función hash cuyo número es:
245643
h(245643) = 245643 mod 997 = 381
MEDIO DEL CUADRADO
FUNCION 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. Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada
VENTAJAS:
Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar
Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones
No se requiere almacenamiento adicional para los índices.
DESVENTAJAS:
El archivo no esta clasificado
No permite llaves repetidas
Solo permite acceso por una sola llave
Costos
Tiempo de procesamiento requerido para la aplicación de la función hash
ALGORITMO HASHING
Algoritmo que se utiliza para generar un valor de hash para algún dato, como por ejemplo claves. Un algoritmo de hash hace que los cambios que se produzcan en los datos de entrada provoquen cambios en los bits del hash. Gracias a esto, los hash permiten detectar si un dato ha sido modificado.
ALGORITMOS DE HASH MAS COMUNES
SHA-1: algoritmo de hash seguro Algoritmo de síntesis que genera un hash de 160 bits. Se utiliza, por ejemplo, como algoritmo para la firma digital.
MD2 y MD4 Algoritmos de hash que generan un valor de 128 bits.
MD5 Esquema de hash de hash de 128 bits muy utilizado para autenticación cifrada. Gracias al MD5 se consigue, por ejemplo, que un usuario demuestre que conoce una contraseña sin necesidad de enviar la contraseña a través de la red.
FUNCIONES DE HASH
Residuo de la división
Medio del cuadrado
Pliegue
RESIDUO DE LA DIVISIÓN
La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor). Mientras que el valor calculado real de una dirección relativa, dados tanto un valor de llave como el divisor, es directo; la elección del divisor apropiado puede no ser tan simple. Existen varios factores que deben considerarse para seleccionar el divisor:
RESIDUO DE LA DIVISIÓN
El rango de valores que resultan de la operación "llave % divisor", va desde cero hasta el divisor 1. Luego, el divisor determina el tamaño del espacio de direcciones relativas. Si se sabe que el archivo va a contener por lo menos n registros, entonces tendremos que hacer que divisor > n, suponiendo que solamente un registro puede ser almacenado en una dirección relativa dada.
El divisor deberá seleccionarse de tal forma que la probabilidad de colisión sea minimizada. ¿Como escoger este numero? Mediante investigaciones se ha demostrado que los divisores que son números pares tienden a comportase pobremente, especialmente con los conjuntos de valores de llave que son predominantemente impares. Algunas investigaciones sugieren que el divisor deberá ser un numero primo. Sin embargo, otras sugieren que los divisores no primos trabajan también como los divisores primos, siempre y cuando los divisores no primos no contengan ningún factor primo menor de 20. Lo mas común es elegir el número primo mas próximo al total de direcciones.
RESIDUO DE LA DIVISIÓN
Ejemplo:
Numero de direcciones 996. La eleccion de m sera 997, que es el primo mas cercano. Se aplica esta función hash cuyo número es:
245643
h(245643) = 245643 mod 997 = 381
MEDIO DEL CUADRADO
En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n dígitos deben extraerse para cada llave.
MEDIO DEL CUADRADO
RADIX
En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los entero.
La mayor parte de los ordenadores digitales representan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente. Existen dos clasificaciones de radix sort: el de dígito menos significativo (LSD) y el de dígito más significativo (MSD). Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo.Radix sort MSD trabaja en sentido contrario.Descripción
Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos.Radix sort LSD usa típicamente el siguiente orden: claves cortas aparecen antes que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija. Una secuencia como "b, c, d, e, f, g, h, i, j, ba" será ordenada léxicamente como "b, ba, c, d, e, f, g, h, i, j". Si se usa orden léxico para ordenar representaciones de enteros de longitud variable, entonces la ordenación de las representaciones de los números del 1 al 10 será "1, 10, 2, 3, 4, 5, 6, 7, 8, 9", como si las claves más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con espacios en blanco, para hacerlas tan largas como la clave más larga, para el propósito de este ordenamiento.
No hay comentarios:
Publicar un comentario