Universidad Tecnológica De Panamá

Facultad De Ingeniería De Sistemas Computacionales

Ingeniería en Sistemas y Computación

Estructuras de Datos II

Proyecto # 3

Tema:

Ordenamiento y Búsqueda

Presentado por:

Joan Vásquez 8-893-286

Ángel De León 8-901-2180

Katherine Arauz 8-895-2165

Facilitadora:

Doris Cueto

Grupo

1IL-122

II Semestre

Año

2015

ContenidoIntroducción.......................................................................................................2

Consideraciones de eficiencia de los algoritmos de ordenamiento y búsquedas. Notación de la Gran O (Big O)....................................................3

Algoritmo de ordenamiento y su eficiencia Quicksort..................................5

Algoritmo de ordenamiento y su eficiencia Heapsort...................................8

Algoritmo de búsqueda y su eficiencia de cadena Knuth-Morris-Pratt.......9

Algoritmo de búsqueda y su eficiencia de cadena Boyer-Moore...............11

Transformaciones o técnicas de cálculos de direcciones (residuo) y manejo de colisiones......................................................................................13

Proceso de Comprimir y Descomprimir........................................................16

Árboles Balanceados (B, B+ y B*).................................................................18

Arboles AVL.....................................................................................................20

Árbol Multicamino O Multirama.....................................................................23

Conclusión.......................................................................................................28

Web grafía........................................................................................................29

P á g i n a 1 | 30

Introducción ¿Qué es un Árbol y para qué sirve un árbol a la hora de estructurar datos?

Un árbol es una estructura donde sus elementos también llamados nodos, se organizan de forma jerárquica. Existen distintos tipos de árboles, cada uno diferente a otro, pero con el mismo principio de jerarquía. Los Tipos de Árboles que trataremos en este documento son: Árboles Balanceados (B, B+ y B*), Arboles AVL, Árbol Multicamino O Multirama.

En este documento también se tratará el concepto de rendimiento en los algoritmos a través de la Notación Big O, la cual funciona para medir el tiempo en que un algoritmo demora en ejecutar una tarea y los recursos que ha usado para llevarla a cabo. Y otros algoritmos cuya función es la de buscar y ordenar datos en una estructura. Los algoritmos a describir son los siguientes: Quicksort, Heapsort, Knuth-Morris-PrattBoyer-Moore

Concepto de Hash: A las funciones hash (adopción más o menos directa del término inglés hash function) también se les llama funciones picadillo, funciones resumen o funciones de digest (adopción más o menos directa del término inglés equivalente digest function)1 2 3 Una función hash H es una función computable mediante un algoritmo, que tiene como entrada un conjunto de elementos, que suelen ser cadenas, y los convierte (mapea) en un rango de salida finito, normalmente cadenas de longitud fija. Es decir, la función actúa como una proyección del conjunto U sobre el conjunto M. además se abordará el tema de comprensión y descomprensión de datos , y los algoritmos que son utilizados en el proceso.

P á g i n a 2 | 30

Consideraciones de eficiencia de los algoritmos de ordenamiento y búsquedas. Notación de la Gran O (Big O)Cuando trabajamos con algoritmos, normalmente nos interesa el rendimiento de éste. Nos interesa saber, por ejemplo, de qué forma se comporta el algoritmo dada una cantidad determinada de datos a procesar. Científicos en computación emplean una forma de categorizar y comparar los algoritmos, de tal suerte que se pueda categorizar de forma rápida el rendimiento de un algoritmo. Esta forma de medir se llama la Notación Gran O: Big-O Notation (BON).

Esta notación expresa la ejecución de un algoritmo dado un parámetro de entrada (i.e. el tamaño de datos a procesar). La notación normalmente es O(n). Por ejemplo, si la ejecución crece linealmente con el número de elementos (dado n elementos el proceso aumenta en n complejidad, entonces el algoritmo es O(n). Si el algoritmo es independiente de la cantidad de datos a procesar, entonces el algoritmo es O(1). A continuación presento una tabla con los valores típicos de complejidad, así como su 

Tipo Notación SignificadoConstante O(1) La ejecución es independiente del

número de elementos a procesar.Logarítmica O(log(n)) La ejecución crece logarítmicamente con

respecto al número de elementos a procesar.

Lineal O(n) La ejecución crece linealmente, con el mismo factor, conforme crece el número de elementos a procesar.

N Log N O(n * log(n)) La ejecución crece como un producto de complejidad lineal y logarítmica.

Cuadrática O(n2) La ejecución crece de forma cuadrática con respecto al número de elementos a procesar.

Por supuesto, esta notación tiene sus pormenores. Cuando se calculan, es difícil que el resultado de ejecución coincida plenamente con alguna de estas fórmulas, pero normalmente se les considera buenas aproximaciones. También es importante hacer notar que esta notación oculta (en algunos casos) algunos factores con exponentes pequeños. En particular, no importa cuánto tiempo toma un algoritmo. Cualesquiera dos algoritmos lineales son considerados igualmente aceptables bajo esta medida. Hay incluso algunas situaciones en las que la constante oculta es tan larga en un algoritmo lineal que inclusive un algoritmo exponencial con una constante más pequeña es preferible en la práctica. Por ende, no se debe considerar como regla de oro esta notación, sino más bien como guía.

Para ejemplificar mejor el significado de la notación, a continuación presento una tabla donde se lista el tipo de complejidad, seguido del número de elementos a procesar, lo cual nos da la salida deseada.

Tipo Notación 1 2 5 10 50 100 1000Constante O(1) 1 1 1 1 1 1 1Logarítmica O(log(n)) 1 2 3 4 6 7 10Lineal O(n) 1 2 5 10 50 100 1,000N Log N O(n * log(n)) 1 4 15 40 300 700 10,000

P á g i n a 3 | 30

Cuadrática O(n2) 1 4 25 100 2,500 10,000 1,000,000

Como se puede ver, dado un número de elementos a procesar pequeño, los resultados no cambian mucho (y aquí es donde los factores escondidos tendrían mucha importancia). Pero conforme éstos se incrementan, sí que cambia el resultado.

Para finalizar, solo apuntar que algunos algoritmos se consideran como amortizados, lo cual quiere decir que las operaciones a largo plazo funcionan como se describe en la notación. Es decir, dado un proceso que lleve 20 minutos, posiblemente dentro de los primeros 5 minutos el algoritmo no se comporte como describe la notación, pero pasado este tiempo el resultado se empieza a estabilizar. De hecho, algunos algoritmos implementados en la librería estándar de C++ actúan de esta forma.

Ejemplo:

P á g i n a 4 | 30

Algoritmo de ordenamiento y su eficiencia Quicksort El ordenamiento rápido (quicksort) es un algoritmo creado por el científico británico en computación C. A. R. Hoare, basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Descripción del algoritmo

El algoritmo trabaja de la siguiente forma:

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

La lista queda separada en dos sub listas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

Repetir este proceso de forma recursiva para cada sub lista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sub listas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).

En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Demostración de un caso particular

Supongamos que el número de elementos a ordenar es una potencia de dos,

es decir,   para algún natural . Inmediatamente , donde k es el número de divisiones que realizará el algoritmo.

P á g i n a 5 | 30

En la primera fase del algoritmo habrá n comparaciones. En la segunda fase el algoritmo instanciará dos sublistas de tamaño aproximadamente n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.

En conclusión, el número total de comparaciones que hace el algoritmo es:

, donde , por tanto el Orden de

Complejidad del algoritmo en el peor caso es .

Técnicas de elección del pivote

El algoritmo básico del método Quicksort consiste en tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la partición en que se elija, el algoritmo será más o menos eficiente.

Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista.

Otra opción puede ser recorrer la lista para saber de antemano qué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n·log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio.

La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote.

Técnicas de reposicionamiento

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la recursividad.

Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:

Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).

Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones.

Repetir esto hasta que se crucen los índices.

El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).

Transición a otro algoritmo

P á g i n a 6 | 30

Como se mencionó anteriormente, el algoritmo quicksort ofrece un orden de ejecución O(n²) para ciertas permutaciones "críticas" de los elementos de la lista, que siempre surgen cuando se elige el pivote «a ciegas». La permutación concreta depende del pivote elegido, pero suele corresponder a secuencias ordenadas. Se tiene que la probabilidad de encontrarse con una de estas secuencias es inversamente proporcional a su tamaño.

Los últimos pases de quicksort son numerosos y ordenan cantidades pequeña de elementos. Un porcentaje medianamente alto de ellos estarán dispuestos de una manera similar al peor caso del algoritmo, volviendo a éste ineficiente. Una solución a este problema consiste en ordenar las secuencias pequeñas usando otro algoritmo. Habitualmente se aplica el algoritmo de inserción para secuencias de tamaño menores de 8-15 elementos.

Pese a que en secuencias largas de elementos la probabilidad de hallarse con una configuración de elementos "crítica" es muy baja, esto no evita que sigan apareciendo (a veces, de manera intencionada). El algoritmo introsort es una extensión del algoritmo quicksort que resuelve este problema utilizando heapsort en vez de quicksort cuando el número de recursiones excede al esperado.

Nota: Los tres parámetros de la llamada inicial a Quicksort serán array[0], 0, numero_elementos -1, es decir, si es un array de 6 elementos array, 0, 5

P á g i n a 7 | 30

Algoritmo de ordenamiento y su eficiencia Heapsort  El ordenamiento por montículos es un algoritmo de ordenamiento no recursivo, no estable, con complejidad computacional 

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él. El algoritmo, después de cada extracción, recoloca en el nodo raíz o cima, la última hoja por la derecha del último nivel. Lo cual destruye la propiedad heap del árbol. Pero, a continuación, realiza un proceso de "descenso" del número insertado de forma que se elige a cada movimiento el mayor de sus dos hijos, con el que se intercambia. Este intercambio, realizado sucesivamente "hunde" el nodo en el árbol restaurando la propiedad montículo del árbol y dejando paso a la siguiente extracción del nodo raíz.

El algoritmo, en su implementación habitual, tiene dos fases. Primero una fase de construcción de un montículo a partir del conjunto de elementos de entrada, y después, una fase de extracción sucesiva de la cima del montículo. La implementación del almacén de datos en el heap, pese a ser conceptualmente un árbol, puede realizarse en un vector de forma fácil. Cada nodo tiene dos hijos y por tanto, un nodo situado en la posición i del vector, tendrá a sus hijos en las posiciones 2 x i, y 2 x i +1 suponiendo que el primer elemento del vector tiene un índice = 1. Es decir, la cima ocupa la posición inicial del vector y sus dos hijos la posición segunda y tercera, y así, sucesivamente. Por tanto, en la fase de ordenación, el intercambio ocurre entre el primer elemento del vector (la raíz o cima del árbol, que es el mayor elemento del mismo) y el último elemento del vector que es la hoja más a la derecha en el último nivel. El árbol pierde una hoja y por tanto reduce su tamaño en un elemento. El vector definitivo y ordenado, empieza a construirse por el final y termina por el principio.

Descripción

He aquí una descripción en pseudocódigo del algoritmo. Se pueden encontrar descripciones de las operaciones insertar en montículo y extraer cima_del_monticulo en el artículo sobre montículos.

function heapsort(array A[0..n]): montículo M integer i; // declaro variable i for i = 0..n: insertar_en_monticulo(M, A[i]) for i = 0..n: A[i] = extraer_cima_del_monticulo(M) return A;

P á g i n a 8 | 30

Algoritmo de búsqueda y su eficiencia de cadena Knuth-Morris-Pratt

El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella se pre calcula una tabla de valores), para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca.

El algoritmo originalmente fue elaborado por Donald Knuth y Vaughan Pratt y de modo independiente por James H. Morris en 1977, pero lo publicaron juntos los tres.

Descripción del algoritmo KMP

El algoritmo KMP, trata de localizar la posición de comienzo de una cadena, dentro de otra. Antes que nada, con la cadena a localizar se pre calcula una tabla de saltos (conocida como tabla de fallos) que después al examinar entre si las cadenas se utiliza para hacer saltos cuando se localiza un fallo.

Supongamos una tabla 'F' ya pre calculada, y supongamos que la cadena a buscar esté contenida en el array 'P()', y la cadena donde buscamos esté contenida en un array 'T()'. Entonces ambas cadenas comienzan a compararse usando un puntero de avance para la cadena a buscar, si ocurre un fallo en vez de volver a la posición siguiente a la primera coincidencia, se salta hacia donde sobre la tabla, indica el puntero actual de avance de la tabla. El array 'T' utiliza un puntero de avance absoluto que considera donde se compara el primer carácter de ambas cadenas, y utiliza como un puntero relativo (sumado al absoluto) el que utiliza para su recorrido el array 'P'. Se dan 2 situaciones:

Mientras existan coincidencias el puntero de avance de 'P', se va incrementando y si alcanza el final se devuelve la posición actual del puntero del array 'T'

Si se da un fallo, el puntero de avance de 'T' se actualiza hasta, con la suma actual del puntero de 'P' + el valor de la tabla 'F' apuntado por el mismo que 'P'. A continuación, se actualiza el puntero de 'P', bajo una de 2 circunstancias; Si el valor de 'F' es mayor que -1 el puntero de 'P', toma el valor que indica la tabla de salto 'F', en caso contrario vuelve a recomenzar su valor en 0.

Descripción de la tabla adicional (conocida como 'función de fallo')

El objetivo de la tabla (precalculada) de fallo 'F' es no permitir que cada carácter del array 'T()' sea examinado más de 1 vez. El método clave para lograr esto, consiste en haber comprobado algún trozo de la cadena donde se busca con algún trozo de la cadena que se busca, lo que nos proporciona en qué sitios potenciales puede existir una nueva coincidencia, sobre el sector analizado que indica fallo.

P á g i n a 9 | 30

Dicho de otro modo, partiendo del texto a buscar, elaboramos una lista con todas las posiciones, de salto atrás que señalen cuanto se retrocede desde la posición actual del texto a buscar. Por ejemplo, si el texto a buscar es 'esconderse' y estamos examinando un texto como 'se esconden tras la mesa', cuando llegamos a la 2ª 'n' de 'esconden' (posición 7 en el texto a buscar es una 'r'), falla, la pregunta lógica sería ¿Dónde se encuentra de nuevo (si existe) la primera letra en el texto 'esconderse'(antes del fallo), y hasta donde logra repetirse? La respuesta a esta pregunta será el punto de salto, en el caso propuesto ('esconderse'). Dicho punto se encuentra en la posición 6 (antes de la 'r'), luego para la tabla en la siguiente posición debería de haber un 1.

Por tanto, esta tabla se confecciona con la distancia que existe desde un punto en la palabra a la última ocurrencia (de la 0ª letra de la palabra) distinta de la primera vez que aparece, y mientras sigan coincidiendo, se marca la distancia, cuando haya una ruptura de coincidencia se marca 0 o un valor previo ya calculado anteriormente, y así sucesivamente hasta terminar con el texto.

La tabla tiene sus 2 primeros valores fijados, de modo que la función de fallo empieza siempre examinando el 3 carácter del texto. La razón por la que dichos valores están fijados es obvia: si para el 2º carácter se marcara 1, nunca se lograría un salto, pues siempre retornaría a dicho punto. En cuanto al primero, por necesidad se marca -1, pues de ese modo le es imposible regresar más atrás, sino siempre adelante.

Pseudocódigo del algoritmo Pseudocódigo no se incluye la verificación de las cadenas vacías. Algoritmo BúsquedaKMP: Entrada: Un array de caracteres, T (el texto donde se busca) Un array de caracteres, P (la palabra/s que se busca) Salida: Un entero que expresa la posición en T en la cual se encontró P. (nota: opcionalmente puede convenir devolver un entero con signo).

Definición de variables: Un entero, k ← 0 (puntero de examen en T) Un entero, i ← 0 (la posición del carácter actual en P, y avance relativo respecto de k, para T) Un array de enteros, F (la tabla de fallo, calculada a continuación, o en otra parte) Si tamaño de T es mayor o igual que tamaño de P entonces Precalcular TablaKMP(P, F) Mientras k + i es menor que la longitud de T, hacer Si P[i] = T[k + i] entonces Si i es igual a la longitud de P - 1 entonces Devolver k Fin si Asignar i ← i + 1 Si no entonces Asignar k ← k + i - F[i] Si i es mayor que 0 entonces Asignar i ← F[i] Fin si Fin si Repetir

P á g i n a 10 | 30

Fin si (Si se alcanza este punto, se buscó en todas las T sin éxito) Devolver longitud de T, o si se usa una variable con signo, devolver -1)

Algoritmo de búsqueda y su eficiencia de cadena Boyer-Moore

El algoritmo de Boyer-Moore, considerado el algoritmo más eficiente en la búsqueda de patrones en cadena de caracteres, se basa en desplazar la ventana de comparación lo máximo posible.

El algoritmo se desplaza dentro de la cadena de búsqueda de izquierda a derecha, y dentro del patrón de derecha a izquierda. La mayor eficiencia se consigue minimizando el número de comparaciones entre caracteres, desplazando lo máximo posible la venta de comparación, a costa de una computación previa.

Notación

y: cadena dónde se busca.x: patrón de búsqueda.| y | = n, longitud de y.| x | = m, longitud de x.j: posición en y desde dónde se prueba la coincidencia.i: posición en x de comparación, dónde se produce una no coincidencia , y[j+i] <> x[i], y[j+i] = b, x[i] = a.u: coincidencia en la comparación, sufijo de x, u = y[j+i+..j+m] = x[i+1..m-1].v: prefijo de x.s: salto del patrón para la siguiente comparación.

Al producirse una ocurrencia del patrón, o un error en la comparación de un carácter, se calcula el desplazamiento máximo del patrón a lo largo de la cadena de búsqueda.

Partimos de una situación en que no hay coincidencia, existe diferencia entre y[j+i] y x[i], pero las posiciones de x siguientes a i sí coinciden con sus asociadas en y, u = y[j+i+..j+m] = x[i+1..m-1]; hacer notar que u es sufijo de x.

El desplazamiento de x a lo largo de y se limita a causa del carácter en y que produjo la no coincidencia, y[i+j] (1), y los caracteres de x posteriores a i (2), sufijo de x que tenía coincidencia parcial con y.

(1) Teniendo en cuenta el carácter que produjo la no coincidencia en y, y[i+j] = b, el desplazamiento máximo, s, será la distancia entre la aparición más a la derecha de b en x[0..m-2] y la longitud de x, m. La nueva j sería j’=j+s, lo que se consigue es alinear las dos coincidencias de b en x e y, desde dónde es

P á g i n a 11 | 30

posible que se produzca una coincidencia del patrón. Se considera el intervalo 0..m-2, porque si se da el caso de que b es igual al último carácter de x, el desplazamiento sería 0, y podría provocar un bucle infinito debido a que el patrón no varía su posición.

(1)

(2) Teniendo en cuenta los caracteres posteriores a i en x (u, sufijo de x), que coinciden de forma parcial con y, hay que alinear u lo más a la derecha posible de x, sin que esté precedido por x[i] = a (2.a); al no estar u ya precedido por x[i] = a <> x[i-s] = c, en la nueva posición de x respecto de y, sabemos que existe la coincidencia u precedida por c, es posible que se produzca una ocurrencia en y. Si no se encuentra la situación anterior, se tratará de alinear el mayor sufijo posible de x con un prefijo v también de x (2.b); como u coincide parcialmente en y, al buscar el prefijo v de x que también es sufijo de x, v también está en y. Si no se producen ninguno de los dos casos anteriores, el patrón se podrá desplazar toda su longitud.

(2.a)

(2.b)

El desplazamiento de x a lo largo de y será el máximo desplazamiento entre los dos anteriores, (1) y (2).

P á g i n a 12 | 30

Transformaciones o técnicas de cálculos de direcciones (residuo) y manejo de colisiones.Transformaciones De Llaves (Hashing)El método de transformación de claves consiste en convertir la clave dada (numérica o alfanumérica) en una dirección (índice) dentro del array. La correspondencia entre las claves y la dirección en el medio de almacenamiento o en el array se establece por una función de conversión (función o hash).Así, por ejemplo, en el caso de una lista de empleados (100) de una pequeña empresa. Si cada uno de los cien empleados tiene un número de identificación (clave) del 1 al 100, evidentemente puede existir una correspondencia directa entre la clave y la dirección definida en un vector o array de 100 elementos.Supongamos ahora que el campo clave de estos registros o elementos es el número del DNI o de la Seguridad Social, que contenga nueve dígitos. Si se desea mantener en un array todo el rango posible de valores, se necesitarán 10ˆ10 elementos en la tabla de almacenamiento, cantidad difícil de tener disponibles en memoria central, aproximadamente1.000.000.000 de registros o elementos. Si el vector o archivo sólo tiene 100, 200 o 1.000 empleados, cómo hacer para introducirlos en memoria por el campo clave DNI. Para hacer uso de la clave DNI como un índice en la tabla de búsqueda, se necesita un medio para convertir el campo clave en una dirección o índice más pequeño. En la figura se presentaun diagrama de cómo realizar la operación de conversión de una clave grande en una tabla pequeña.Los registros o elementos del campo clave no tienen por qué estar ordenados de acuerdo con los valores del campo clave, como estaban en la búsqueda binaria.Por ejemplo, el registro del campo clave 345671234 estará almacenado en la tabla de transformación de claves (array) en una posición determinada; por ejemplo, 75.La función de transformación de clave, H(k) convierte la clave (k) en una dirección (d).Imaginemos que las claves fueran nombres o frases de hasta dieciséis letras, que identifican a un conjunto de un millar de personas. Existirán 26ˆ16 combinaciones posibles de claves que se deben transformar en 103 direcciones o índices posibles. La función H es, por consiguiente, evidentemente una función de paso o conversión de múltiplesclaves a direcciones. Dada una clave k, el primer paso en la operación de búsqueda es calcular su índice asociado d ← H(k) y el segundo paso —evidentemente necesario— es verificar sí o no el elemento con la clave k es identificado verdaderamente por d en el array T; es decir, para verificar si la clave T[H(K)] = K se deben considerar dos preguntas:• ¿Qué clase de función H se utilizará?• ¿Cómo resolver la situación de que H no produzca la posición del elemento asociado?La respuesta a la segunda cuestión es que se debe utilizar algún método para producir una posición alternativa, es decir, el índice d', y si ésta no es aún la posición del elemento deseado, se produce un tercer índice d", y así sucesivamente.

P á g i n a 13 | 30

El caso en el que una clave distinta de la deseada está en la posición identificada se denomina colisión; la tarea de generación de índices alternativos se denomina tratamiento de colisiones.Métodos De Transformación De ClavesExisten numerosos métodos de transformación de claves.Todos ellos tienen en común la necesidad de convertir claves en direcciones. En esencia, la función de conversión equivale a una caja negra que podríamos llamar calculador de direcciones. Cuando se desea localizar un elemento de clave x, el indicador de direcciones indicará en qué posición del array estará situado el elemento.TruncamientoIgnora parte de la clave y se utiliza la parte restante directamente como índice (considerando campos no numéricos y sus códigos numéricos). Si las claves, por ejemplo, son enteros de ocho dígitos y la tabla de transformación tienemil posiciones, entonces el primero, segundo y quinto dígitos desde la derecha pueden formar la función de conversión.Por ejemplo, 72588495 se convierte en 895. El truncamiento es un método muy rápido, pero falla para distribuir las claves de modo uniforme.PlegamientoLa técnica del plegamiento consiste en la partición de la clave en diferentes partes y la combinación de las partes en un modo conveniente (a menudo utilizando suma o multiplicación) para obtener el índice.La clave x se divide en varias partes, x1, x2, ..., xn, donde cada parte, con la única posible excepción de la última parte, tiene el mismo número de dígitos que la dirección más alta que podría ser utilizada.A continuación, se suman todas las partesh(x) = x1 + x2 + ... + xnEn esta operación se desprecian los dígitos más significativos que se obtengan de arrastre o acarreo.

ColisionesLa función de conversión h(x) no siempre proporciona valores distintos, puede suceder que para dos claves diferentes x1 y x2 se obtenga la misma dirección. Esta situación se denomina colisión y se deben encontrar métodos para sucorrecta resolución.Los ejemplos vistos anteriormente de las claves DNI correspondientes al archivo de empleados, en el caso de cien posibles direcciones. Si se considera el método del módulo en el caso de las claves, y se considera el número primero 101123445678 123445880proporcionarían las direcciones:h (123445678) = 123445678 mod 101 = 44h (123445880) = 123445880 mod 101 = 44Es decir, se tienen dos elementos en la misma posición del vector o array, [44]. En terminología de claves se dice que las claves 123445678 y 123445880 han colisionado.El único medio para evitar el problema de las colisiones totalmente es tener una posición del array para cada posible número de DNI. Si, por ejemplo, los números de DNI son las claves y el DNI se representa con nueve dígitos, se necesitaría una posición del array para cada entero en el rango 000000000 a

P á g i n a 14 | 30

999999999. Evidentemente, sería necesario una gran cantidad de almacenamiento. En general, el único método para evitar colisiones totalmente es que el array sea lo bastante grande para que cada posible valor de la clave de búsqueda pueda tener su propia posición.Ya que esto normalmente no es práctico ni posible, se necesitará un medio para tratar o resolver las colisiones cuando sucedan.

Resolución de colisionesConsideremos el problema producido por una colisión. Supongamos que desea insertar un elemento con número nacional de identidad DNI 12345678, en un array T. Se aplica la función de conversión del módulo y se determina que el nuevo elemento se situará en la posición T[44]. Sin embargo, se observa que T[44] ya contiene un elemento con DNI 123445779.

Método de DivisiónLa función de este método es 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 F(hash)= llave% divisor.Factores que deben considerarse al seleccionar el divisor:Divisor >n: suponiendo que solamente un registro puede ser almacenado en una dirección relativa dadaSeleccionarse el divisor de tal forma que la probabilidad de colisión sea minimizada.Uso:Cuando la distribución de los valores de llaves no es conocida.

Método de medio cuadrado:Consiste en elevar al cuadrado la clave y tomar los dígitos centrales como dirección. El número de dígitos a tomar queda determinado por el rango del índice. Sea K la clave del dato a buscar, la función hash queda definida por la siguiente formula: H(K)=dígitos_centrales(K^2)+1.Las suma de los dos dígitos centrales de la clave K (elevada al cuadrado) más 1, debe obtener valor entre 1 y N (N, tamaño del arreglo).Uso:Puede aplicarse en archivos con factores de cargas bastantes bajas.

La eficiencia de una función hash depende:1. La distribución de los valores de llave que se usaran realmente.2. El número de valores de llave que realmente están en uso con respecto

al tamaño del espacio de direcciones.3. El número de registros que pueden almacenarse en una dirección dada

sin causar una colisión.4. La técnica usada para resolver el problema de las colisiones.

Técnicas de cálculo de direcciones

P á g i n a 15 | 30

Proceso de Comprimir y Descomprimir En ciencias de la computación la compresión de datos es la reducción del volumen de datos tratables para representar una determinada información empleando una menor cantidad de espacio. Al acto de compresión de datos se denomina compresión, y al contrario descompresión.

El espacio que ocupa una información codificada (datos, señal digital, etc.) sin compresión es el cociente entre la frecuencia de muestreo y la resolución. Por tanto, cuantos más bits se empleen mayor será el tamaño del archivo. No obstante, la resolución viene impuesta por el sistema digital con que se trabaja y no se puede alterar el número de bits a voluntad; por ello, se utiliza la compresión, para transmitir la misma cantidad de información que ocuparía una gran resolución en un número inferior de bits.

La compresión es un caso particular de la codificación, cuya característica principal es que el código resultante tiene menor tamaño que el original.

La compresión de datos se basa fundamentalmente en buscar repeticiones en series de datos para después almacenar solo el dato junto al número de veces que se repite. Así, por ejemplo, si en un fichero aparece una secuencia como "AAAAAA", ocupando 6 bytes se podría almacenar simplemente "6A" que ocupa solo 2 bytes, en algoritmo RLE.

En realidad, el proceso es mucho más complejo, ya que raramente se consigue encontrar patrones de repetición tan exactos (salvo en algunas imágenes). Se utilizan algoritmos de compresión:

Por un lado, algunos buscan series largas que luego codifican en formas más breves.

Por otro lado, algunos algoritmos, como el algoritmo de Huffman, examinan los caracteres más repetidos para luego codificar de forma más corta los que más se repiten.

Otros, como el LZW, construyen un diccionario con los patrones encontrados, a los cuales se hace referencia de manera posterior.

La codificación de los bytes pares es otro sencillo algoritmo de compresión muy fácil de entender.

A la hora de hablar de compresión hay que tener presentes dos conceptos:

Redundancia: Datos que son repetitivos o previsibles

Entropía: La información nueva o esencial que se define como la diferencia entre la cantidad total de datos de un mensaje y su redundancia.

La información que transmiten los datos puede ser de tres tipos:

Redundante: información repetitiva o predecible.

Irrelevante: información que no podemos apreciar y cuya eliminación por tanto no afecta al contenido del mensaje. Por ejemplo, si las frecuencias que es capaz de captar el oído humano están entre 16/20 Hz y 16.000/20.000 Hz,

P á g i n a 16 | 30

serían irrelevantes aquellas frecuencias que estuvieran por debajo o por encima de estos valores.

Básica: la relevante. La que no es ni redundante ni irrelevante. La que debe ser transmitida para que se pueda reconstruir la señal.

Teniendo en cuenta estos tres tipos de información, se establecen tres tipologías de compresión de la información:

Sin pérdidas reales: es decir, transmitiendo toda la entropía del mensaje (toda la información básica e irrelevante, pero eliminando la redundante).

Subjetivamente sin pérdidas: es decir, además de eliminar la información redundante se elimina también la irrelevante.

Subjetivamente con pérdidas: se elimina cierta cantidad de información básica, por lo que el mensaje se reconstruirá con errores perceptibles pero tolerables (por ejemplo: la videoconferencia).

Diferencias entre compresión con y sin pérdida

El objetivo de la compresión es siempre reducir el tamaño de la información, intentando que esta reducción de tamaño no afecte al contenido. No obstante, la reducción de datos puede afectar o no a la calidad de la información:

Compresión sin pérdida: los datos antes y después de comprimirlos son exactos en la compresión sin pérdida. En el caso de la compresión sin pérdida una mayor compresión solo implica más tiempo de proceso. El bit rate siempre es variable en la compresión sin pérdida. Se utiliza principalmente en la compresión de texto.

Un algoritmo de compresión con pérdida puede eliminar datos para disminuir aún más el tamaño, con lo que reduce la calidad. En la compresión con pérdida el bit rate puede ser constante (CBR) o variable (VBR). Una vez realizada la compresión, no se puede obtener la señal original, aunque sí una aproximación cuya semejanza con la original dependerá del tipo de compresión. Este tipo de compresión se da principalmente en imágenes, vídeos y sonidos. Además de estas funciones la compresión permite que los algoritmos usados para reducir las cadenas del código desechen información redundante de la imagen. Uno de los formatos que permite compensar esta pérdida es el JPG, que emplea técnicas que suavizan los bordes y áreas que tienen un color similar permitiendo que la falta de información sea invisible a simple vista. Este método permite un alto grado de compresión con pérdidas en la imagen que, muchas veces, sólo es visible mediante el zoom.

P á g i n a 17 | 30

Árboles Balanceados (B, B+ y B*)Los árboles B constituyen una categoría muy importante de estructuras de datos, que permiten una implementación eficiente de conjuntos y diccionarios, para operaciones de consulta y acceso secuencial. Existe una gran variedad de árboles B: los arboles B, B+ y B*; pero todas ellas están basadas en la misma idea, la utilización de árboles de búsqueda no binarios y con condición de balanceo.En concreto, los árboles B+ son ampliamente utilizados en la representación de índices en bases de datos. De hecho, este tipo de árboles están diseñados específicamente para aplicaciones de bases de datos, donde la característica fundamental es la predominancia del tiempo de las operaciones de entrada/salida de disco en el tiempo de ejecución total. En consecuencia, se busca minimizar el número de operaciones de lectura o escritura de bloques de datos del disco duro o soporte físico.Árboles De Búsqueda No BinariosEn cierto sentido, los arboles B se pueden ver como una generalización de la idea de árbol binario de búsqueda a árboles de búsqueda no binarios. Consideremos la representación de árboles de búsqueda binarios y n-arios En un ABB si un nodo x tiene dos hijos, los nodos del subárbolizquierdo contienen claves menores que x y los del derecho contienen claves mayores que x. En un árbol de búsqueda no binario (figura 4.23b), cada nodo interno puede contener q claves x1, x2, . . ., xq, y q+1 punteros a hijos que están “situados” entre cada par de claves y en los dos extremos. Las claves estarán ordenadas de menor a mayor: x1 < x2 < ... < xq.Además, el hijo más a la izquierda contiene claves menores que x1; el hijo entre x1 y x2 contiene claves mayores que x1 y menores que x2; y así sucesivamente hasta el hijo más a la derecha que contiene claves mayores que xq.

Definición de árbol BUn árbol B de orden p es básicamente un árbol de búsqueda n-ario donde losnodos tienen p hijos como máximo, y en el cual se añade la condición de balanceo de que todas las hojas estén al mismo nivel. La definición formal de árbol B es la siguiente.Un árbol B de orden p, siendo p un entero mayor que 2, es un árbol

P á g i n a 18 | 30

con las siguientes características:1. Los nodos internos son de la forma (p1, x1, p2, x2, . . ., xq−1, pq), siendo pi punteros a nodos hijos y xi claves, o pares (clave, valor) en caso de representar diccionarios.2. Si un nodo tiene q punteros a hijos, entonces tiene q − 1 claves.

Árbol B+En un árbol B+, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo nivel, que corresponde al más bajo. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir principalmente recuperación en rango mediante búsqueda secuencial.

Las estructuras de árbol B+ reúnen las siguientes características:El número máximo de claves en un registro es llamado el orden del árbol B+.El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.El número de claves que pueden ser indexadas usando un árbol B+ está en función del orden del árbol y su altura.Altura: El mejor y el peor casoDado un M, el cual corresponde al número máximo de hijos que un nodo puede contener se define por:La altura h de un árbol B+ (El peor caso):La altura h de un árbol B+ (Mejor caso):Este caso se debe a que, si guardamos menos hijos en los nodos, se necesitarán más niveles para almacenar todo.Cantidad de clavesPara un árbol B+ de orden n, con una altura h:El número máximo de claves es: 

El número mínimo de claves es: 

Árbol-B* Un árbol-B* es una estructura de datos de árbol, una variante de Árbol-B utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los

P á g i n a 19 | 30

nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2. Para mantener esto los nodos, en lugar de generar inmediatamente un nodo cuando se llenan, comparten sus claves con el nodo adyacente. Cuando ambos están llenos, entonces los dos nodos se transforman en tres. También requiere que la clave más a la izquierda no sea usada nunca.No se debe confundir un árbol-B* con un árbol-B+, en el que los nodos hoja del árbol están conectados entre sí a través de una lista enlazada, aumentando el coste de inserción para mejorar la eficiencia en la búsqueda.

Análisis de eficiencia de los arboles BEn el análisis de eficiencia del árbol B, el recurso critico es el número de lecturas/ escrituras de bloques del disco duro. Típicamente, las operaciones de acceso a disco son varios ordenes de magnitud más lentas que las que se realizan en memoria. En las implementaciones reales y eficientes de árboles B, se hace que cada nodo del árbol ocupe exactamente un bloque de disco, lo cual se consigue ajustando el parámetro p. Por lo tanto, hasta cierto límite, el tiempo de las instrucciones que se ejecutan dentro de cada nodo es despreciable y el factor importante es el número de nodos tratados.

Arboles AVL Un árbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.

Los árboles AVL están siempre equilibrados de tal modo que, para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O (log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.

Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Los árboles AVL más profundos son los árboles de Fibonacci.

Definición de árbol AVLUn árbol vacío es un árbol AVLSi   es un árbol no vacío y   y   sus subárboles, entonces   es AVL si y solo si:

 es AVL  es AVL

P á g i n a 20 | 30

Factor de equilibrio

Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los árboles binarios de búsqueda(ABB), y además el dato que controla el factor de equilibrio.El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:FE = altura subárbol derecho - altura subárbol izquierdo;Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.Si el factor de equilibrio de un nodo es:0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.1 -> el nodo está equilibrado y su subárbol derecho es un nivel más alto.-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.

Si el factor de equilibrio   es necesario reequilibrar.

Operaciones

Las operaciones básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos que serían realizados en un árbol binario de búsqueda desequilibrado, pero precedido o seguido por una o más de las llamadas "rotaciones AVL".

Rotaciones

El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda

Las rotaciones internas en árboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto (o casi perfecto del árbol binario. Un árbol balanceado permite operaciones en tiempo logarítmico

Rotación simple a la derecha

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).

P á g i n a 21 | 30

Rotación simple a la izquierda

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).

Precondición: Tiene que tener hijo derecho no vacío.

Rotación doble a la derecha

La Rotación doble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación simple derecha.

Rotación doble a la izquierda

La Rotación doble a la Izquierda son dos rotaciones simples, primero rotación simple derecha y luego rotación simple izquierda.

Inserción

La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.

Proceso de inserción:

P á g i n a 22 | 30

1 Buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda)

2 Insertar el nuevo nodo con factor de equilibrio “equilibrado”

3 Desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario

Extracción

El procedimiento de borrado es el mismo que en el caso de árbol binario de búsqueda. La diferencia se encuentra en el proceso de reequilibrado posterior. El problema de la extracción puede resolverse en O (log(n)) pasos. Una extracción trae consigo una disminución de la altura de la rama donde se extrajo y tendrá como efecto un cambio en el factor de equilibrio del nodo padre de la rama en cuestión, pudiendo necesitarse una rotación.

Esta disminución de la altura y la corrección de los factores de equilibrio con sus posibles rotaciones asociadas pueden propagarse hasta la raíz.

Árbol Multicamino O MultiramaComo hemos visto un árbol AVL es un árbol binario de búsqueda que permite búsqueda, inserción y borrado rápido a expensas de tener que mantener el árbol equilibrado, excepto que para bajar costes lo manteníamos "bastante equilibrado".

Otra posible concesión en vez de equilibrio perfecto es permitir almacenar más de un elemento en cada nodo.

En este caso es posible hacer que todos los subárboles estén perfectamente equilibrados.

Un árbol m-ario ó multicamino cumple:

1. Cada nodo tiene hasta m hijos y guarda hasta m-1 elementos (número de hijos <= (número de elementos +1)).

2. Los valores guardados en un nodo están en orden ascendente.3. Los valores de los primeros i hijos de A son menores que el elemento

iésimo guardado en A.4. Los valores de los últimos m-i hijos de A son mayores que el elemento

iésimo guardado en A…

Ejemplo de árbol 4-ario:

P á g i n a 23 | 30

La búsqueda es sencilla.

Un árbol m-ario equilibrado sencillo es el árbol 2-3:

Es un árbol 3-ario con 0, 2 ó 3 hijos por nodo. Todas las hojas están al mismo nivel.

Ejemplo de árbol 2-3:

Como un árbol 2-3 de altura h tiene al menos tantos nodos como un árbol binario completo de altura h:

N >= 2h+1-1

por tanto

h <= ceiling(log_2 (N+1) -1)

Otro árbol m-ario equilibrado sencillo es el árbol 2-3-4 (4-ario, 0,2,3 ó 4 hijos por nodo, todas las hojas al mismo nivel):

Vamos a ver los 2-3-4 que son una buena introducción a los árboles B.

Arboles 2-3-4

La altura de un 2-3-4 de N nodos es como mucho la altura de un 2-3 de N nodos, luego

h<=log(N+1)

Para buscar hay que examinar hasta 3 elementos en cada nodo, luego la búsqueda tarda

O (3 h) = O(3 log(N+1))=O(log N)

P á g i n a 24 | 30

Inserción en un árbol 2-3-4

Los nuevos elementos se insertan siempre en las hojas.

Se atraviesa el árbol hacia abajo hasta encontrar la hoja donde insertar.

Dependiendo de si encontramos nodos llenos tenemos 3 casos:

inserción sin subdividir nodos inserción subdividiendo nodos inserción subdividiendo la raíz

Queremos insertar de una sola pasada, por tanto, cada nodo que encontremos lleno lo subdividimos.

Inserción sin subdividir nodos:

No encontramos nodos llenos en el camino de la raíz a la hoja:

Inserción subdividiendo nodos:

Cuando encontramos un nodo lleno en el camino de la raíz a la hoja:

P á g i n a 25 | 30

Podemos necesitar varias divisiones si nos encontramos con más de un nodo lleno en el camino de la raíz a la hoja.

El proceso de subdivisión mantiene el árbol equilibrado.

Inserción subdividiendo la raíz:

Esto ocurre cuando nos encontramos la raíz llena. Dividimos la raíz (cuatro hijos) en 3 nodos de dos hijos cada uno.

Ejemplo: Generar un árbol 2-3-4 con la secuencia:

70, 50, 30, 40, 20, 80, 25, 90, 75, 10

Resultado:

P á g i n a 26 | 30

Ventajas E Inconvenientes

La principal ventaja de este tipo de árboles consiste en que existen más nodos en un mismo nivel que en los árboles binarios con lo que se consigue que, si el árbol es de búsqueda, los accesos a los nodos sean más rápidos.

El inconveniente más importante que tienen es la mayor ocupación de memoria, pudiendo ocurrir que en ocasiones la mayoría de los nodos no tengan descendientes o al menos no todos los que podrían tener desaprovechándose por tanto gran cantidad de memoria. Cuando esto ocurre lo más frecuente es transformar el árbol multicamino en su binario de búsqueda equivalente.

Un tipo especial de árboles multicamino utilizado para solucionar el problema de la ocupación de memoria son los árboles B o árboles Bayer.

P á g i n a 27 | 30

ConclusiónCon uno de los algoritmos previamente tratados, algunos nos permiten medir el rendimiento de los programas que hayamos realizado como es en caso de que hagamos uso de la notación Big O, el mismo permite el tiempo y la cantidad de recursos que se usan en el proceso de ejecutar el programa. También se puede hacer uso de otros algoritmos que nos permiten realizar un ordenamiento dentro de un arreglo como lo son quicksort, headsort. Cada algoritmo es óptimo en ciertas instancias y teniendo en cuenta la cantidad de elementos que se quieren ordenar. Entre los algoritmos que nos permite realizar búsqueda encontramos: Knuth-Morris-Pratt y Boyer-Moore, entre estos dos algoritmos encontramos el que se considera más óptimo en la búsqueda y esto se debe a su funcionamiento eficiente. El manejo de hash, el hash era una palabra un poco conocida, ya que la misma se encuentra muchas veces vinculas con el manejo de archivos, el hash normalmente se le usaba para verificar que un archivo fuera integro o el original. Aunque se desconocía mucho como en realidad realiza esa función y como generaba dichas claves para cada archivo, en el uso diario nunca se había visto dos archivos con las mismas claves, aunque con la teoría se sabe que puede suceder que se encuentren más de dos archivos que hagan uso de la misma clave, esto se debe a la forma en que las claves se generan determinada y no de forma aleatoria. Comprensión y descompresión son terminados que aplicamos a diarios cuando descomprimimos un archivo, convertimos a otro formato una canción para que ocupe menor tamaño, o usamos el formato jpg en vez de RAW para guardar las fotos que tomamos, aunque no sabemos cómo en realidad se lleva a cabo el proceso y de qué manera se realiza la optimización.

El concepto de hash es conocido grandemente en el mundo de las descargas de softwares, en su mayoría las claves hash se usan para verificar la integridad de los archivos o si son los originales. Aunque sin saber en realidad como es que funciona y como se generan las claves. Teniendo en cuesta esto, varios archivos en circunstancias distintas pueden tener una misma clave hash, a esto se le denomina colisiones.

P á g i n a 28 | 30

Web grafía https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Boyer-Moore

https://es.wikipedia.org/wiki/Algoritmo_Knuth-Morris-Pratt

https://es.wikipedia.org/wiki/Quicksort

https://es.wikipedia.org/wiki/Heapsort

http://www.lnds.net/blog/2013/11/la-notacion-big-o.html

http://debianhackers.net/big-o-notation-evalua-el-rendimiento-de-tus-algoritmos/

https://en.wikipedia.org/wiki/Big_O_notation

http://www6.uniovi.es/usr/cesar/Uned/EDA/Apuntes/EsDA_apTW_05.pdf

https://es.wikipedia.org/wiki/Compresi%C3%B3n_de_datos

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&cad=rja&uact=8&ved=0CDgQFjAFahUKEwiZlIHUjpbIAhXMJB4KHeQwDeg&url=http%3A%2F%2Fdis.um.es%2F~ginesgm%2Ffiles%2Fdoc%2Faed%2Fsec4.4.pdf&usg=AFQjCNGYFhOvjc60U9XO0PLkXHPFwwZLqQ&sig2=yfCMKsEdPQbpgG6Kg5jJaA

http://equipo1arboles.blogspot.com/2006/04/rbol-multicamino-o-multirama.html

P á g i n a 29 | 30