hash mitad al cuadrado pdf
TRANSCRIPT
Informe de Análisis de Algoritmos “Hash Mitad al Cuadrado”
Integrantes: Carlos Delgado Carriel Franco Guajardo Fernández
Luis Riquelme Burgos Sebastián Morales Bustamante
Docente: Pilar Pardo
Concepción, abril 2014
Ingeniería en Informática
INDICE
Introducción ....................................................................................................................... 3
1. Búsqueda Lineal ....................................................................................................... 4
1.2 Ejemplo ...................................................................................................................... 4
2. Búsqueda Binaria ..................................................................................................... 5
2.1 Ejemplo ...................................................................................................................... 5
3. Hash Truncamiento .................................................................................................. 6
3.1. Ejemplo ................................................................................................................... 6
4. Hash Plegamiento .................................................................................................... 7
4.1. Ejemplo ................................................................................................................... 7
5. Hash Aritmética Modular ......................................................................................... 8
5.1. Ejemplo ................................................................................................................... 8
6. Hash Mitad del Cuadrado ........................................................................................ 9
6.1. Factores a tomar en cuenta ................................................................................. 9
6.2. Ejemplos ............................................................................................................... 10
Conclusión ....................................................................................................................... 11
Página 3
Introducción
El presente informe busca dar a conocer mas información sobre los algoritmos de
búsqueda, en donde se verán los siguientes puntos, búsqueda lineal, búsqueda
binaria, hash truncamiento, hash de plegamiento, hash de aritmética modular, y
hash mitad dl cuadrado, siendo esta última en la cual se profundizara en este
informe mostrando el método de funcionamiento que este posee atreves de sus
métodos, funcionamiento, descripción y ejemplos.
Página 4
1. Búsqueda Lineal
Se utiliza en vectores no ordenados. El dato que se requiere buscar, se va comparando uno por uno (secuencialmente) con los contenidos en el vector hasta encontrarlo, o en caso contrario, recorrerlo por completo.
Mejor Caso Se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O(1). Peor Caso Se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n). Caso Promedio Requiere un poco de razonamiento probabilista. Para el caso de una lista aleatoria es probable que una coincidencia ocurra en cualquier posición.
1.2 Ejemplo
Si tenemos una estructura con los elementos 5, 8, 3, 2, 9, 5, 7, 0, 5, 1 y estamos
buscando el número 5, el resultado de la búsqueda nos mostraría las posiciones 0,
5 y 8 y el proceso terminaría al llegar al número 1 que es el último de la lista de
elementos.
Elementos 5 8 3 2 9 5 7 0 5 1
Posiciones 0 1 2 3 4 5 6 7 8 9
Posiciones donde
encontró el número 5
√ × × × × √ × × √ ×
Página 5
2. Búsqueda Binaria
Se utiliza solamente cuando el vector está ordenado. Para ello, se selecciona un elemento cualquiera del vector, preferentemente central, y se compara con el elemento a buscar; si el valor tomado es mayor, se continúa realizando el procedimiento por la sección a la izquierda de éste ignorando la otra parte; si es menor se procede con la sección a la derecha hasta encontrar el valor o, en el peor de los casos, no encontrarlo. Mejor Caso Se presenta cuando una coincidencia se encuentra en el punto central de la lista. En este caso la complejidad es O (1) dado que sólo se realiza una prueba de comparación de igualdad. Peor Caso La complejidad del caso peor es O (log2 n) que se produce cuando el elemento no está en la lista o el elemento se encuentra en la última comparación. Se puede deducir intuitivamente esta complejidad Caso Promedio ½ log2n comparaciones.
2.1 Ejemplo
Para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos: Se toma el elemento central y se divide el array en dos: {1,2,3,4}−5-{6,7,8,9} Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4} Se vuelve a dividir el array en dos: {1}−2-{3,4} Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4} Se vuelve a dividir en dos: {}−3-{4} Como el elemento buscado coincide con el central, lo hemos encontrado.
Página 6
3. Hash Truncamiento
La función truncamiento toma algunos de los dígitos de las claves y forma con
ellos una dirección. La elección de los dígitos es arbitraria, podrían tomarse los de
las posiciones pares o impares para con ellos generar la dirección donde se
almacenara la clave, uniendo los dígitos de izquierda a derecha o de derecha a
izquierda, su fórmula es la siguiente:
Dirección = elegir dígitos (unión dígitos)
3.1. Ejemplo
Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las
direcciones generadas son las siguientes:
Dirección = elegir dígitos (7, 5) = 75
Dirección = elegir dígitos (9, 5) = 95
Para este caso se tomaron los dígitos impares y se unieron de izquierda a
derecha.
Página 7
4. Hash Plegamiento
La función plegamiento divide la clave en partes de igual número de dígitos (la
última puede tener menos dígitos), tomando como dirección los dígitos menos
significativos, después de realizar una operación entre las partes, ya sea una serie
de sumas o de multiplicaciones. La fórmula sería la siguiente:
Dirección = dígitos menos significativos (suma de partes)
Dirección = dígitos menos significativos (multiplicación de partes)
4.1. Ejemplo
Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las
direcciones generadas son las siguientes:
Dirección = dígitos menos significativos (72 + 59) =
dígitos menos significativos (131) = 31
Dirección = dígitos menos significativos (93 + 59) =
Dígitos menos significativos (152) = 52
Como el rango de claves es de 1 a 100 se toman dos dígitos para las particiones y
para la dirección.
Página 8
5. Hash Aritmética Modular
La función módulo o por división toma el residuo de la división entre la clave y el
total de elementos de la estructura, generando la siguiente fórmula:
Dirección = (clave % total elementos)
Para lograr una mayor uniformidad en la distribución de los elementos, se debe
buscar que el valor que se usa en el total de elementos sea un número primo más
cercano al tamaño de la estructura.
5.1. Ejemplo
Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las
direcciones generadas son las siguientes:
Dirección = (7259%100) = 59
Dirección = (9359%100) = 59
Estos dos casos generan una colisión, ya que los dos números no se pueden
asignar dentro de la misma dirección en la estructura, para evitar la colisión, se
cambia el valor de 100 por el numero primo más cercano a él, en este caso seria
un 97, lo que generaría las siguientes direcciones:
Dirección = (7259%97) = 81
Dirección = (9359%97) = 47
Página 9
6. Hash Mitad del Cuadrado
La función cuadrada como su nombre lo indica eleva al cuadrado la clave y del
resultado, se toman los dígitos centrales como la dirección. El número de dígitos a
tomar se determina del por el rango del índice de toda la estructura. Las fórmulas
hash son las siguientes:
Dirección = dígitos centrales (clave2)
Dirección = dígitos centrales (clave2) +1
6.1. Factores a tomar en cuenta
1. Para mayor seguridad empezar a extraer dígitos de la mitad de la llave elevada al cuadrado a la izquierda.
2. Extraer el mismo número de dígitos para cada llave y de las mismas posiciones. Aquí hay que tomar en cuenta el número de registros que se tiene en el archivo
Página 10
6.2. Ejemplos
Utilizando la formula Dirección = dígitos centrales (clave2) +1
Sea N=100 el tamaño del arreglo y sean sus direcciones entre 1 y 100. Sean
K1=7259 y K2=9359 dos claves que deban almacenarse en el arreglo. Si se aplica
la fórmula queda:
H(K1)= (72592) + 1= (72592^2)=(52693081)+1=93 + 1= 94
Utilizando la formula Dirección = dígitos centrales (clave2)
Se escogen el 4º y el 5º dígitos por la derecha para obtener la dirección Hash. K: 3205 7148 2345 K2: 10272025 51093904 5499025
Página 11
Conclusión Se concluye hay distintos métodos de búsqueda, estos se aplican según la problemática, esto dependerá de su tiempo de ejecución (tiempo y espacio). En resumen no existe un algoritmo mejor que otro ya que dependerá todo del problema que se encuentre.