Algoritmo De Datos.docx

Algoritmo de Datos

Desarrollo Se entiende por colisiones cuando dos o más elementos diferentes se asignan a un mismo índice, es decir cuando el algoritmo empieza a buscar un cierto parámetro o valor entonces el índice está conformado por. Ver Figura N°1 Figura N°1 INDICE. 1 2 3 ARREGLO

4

1

4

2

3

Entonces como un breve ejemplo en el índice existe una colisión cuando se le asigna a dos o más elementos a la misma posición del índice. Ver Figura N°2 Figura N°2 INDICE. 1 2 3 ARREGLO

4

1

4

2

3

Que sucede con esto en simples palabras retarda la búsqueda, ya que no se puede determinar la posición exacta del dato. ¿Cómo podemos dar una solución a las colisiones?; podemos dar una solución con tres posibilidades existentes en el tratamiento de las colisiones. La primera de ella, se puede aplicar cuando se encuentra ocupado el índice correspondiente a un elemento determinado, es decir se procederá a asignar el primer índice libre a partir de esta posición un ejemplo seria. Ver figura N°3 Figura N°3

INDICE. 1 2 3 ARREGLO

4

1

4

2

3

5

6

Como el índice 4 está ocupado se le asignara la primera posición libre en este caso sería en modo ascendente y podríamos decir que es la 5ta del índice la que se encuentra en color verde. Ver Figura N°4 Figura N°4 5

6

Aunque este método es poco eficaz, ya que pudiese que al nuevo elemento se le podría asignar un índice que estuviera ocupado por un elemento anterior y así conformando una nueva colisión y retardando la búsqueda, ya que no se podría encontrar la posición exacta de los elementos buscados. Ahora veremos el segundo en el cual podemos reservar una cantidad determinada de espacios libres al final del arreglo para colocar las colisiones allí pero solamente cuando se produzcan durante el proceso de búsqueda, pero tenemos que pensar lo siguiente ¿Cuántos espacios tenemos que reservar para dejar las nuevas colisiones que se generen?, esto queda en evidencia si aún conocemos N o la cantidad de elementos que se generaran en el arreglo. Pero esto puede aumentar la lentitud o el tiempo de respuesta en la búsqueda. Y el ultimo que revisaremos es probablemente lo más efectivo es crear un arreglo de los punteros, en vez de hacer un arreglo con números, cada uno de estos punteros señalará de esta manera un inicio de una lista cualquiera enlazada. Con esta modalidad cada elemento se enlaza con un determinado índice y este se coloca el último lugar del el índice mencionado. Al aplicar este

tratamiento puede reducir el tiempo de búsqueda considerablemente, obviamente no se aplica considerar las restricciones del tamaño del arreglo (N), ya que se pueden añadir nodos en una forma dinámica al final de la lista. Ahora el tratamiento que le podemos dar a las tablas hash en las cuales el comportamiento puede ser en forma de restas sucesivas, aritmética modular, mitad del cuadrado, truncamiento y plegamiento. Ahora si analizamos brevemente una a una seria de la siguiente manera: Restas sucesivas: En esta función se emplean claves numéricas en las que pueden existir espacios libres y por tamaño conocido, realizando así direcciones consecutivas. Aritmética Modular: Este es un caso particular en donde el índice de un número dentro del arreglo. En este caso particular el índice de un número es el resto de la división entre un factor X que se prefija con un número primo y el número propio. Mitad del Cuadrado: Esta función consiste en elevar al cuadrado cualquier clave y tomar como índice las cifras centrales del producto, pero esta manera es la mayormente presenta problemas de colisión. Truncamiento: Este consiste en desestimar una parte del número que se usa como índice a todos los elementos restantes.

Plegamiento: Simplemente este método consiste en dividir un número en diferentes partes y realizar operaciones entre ellas generalmente suma o multiplicaciones.

a. Búsqueda Secuencial: Este método consiste en recorrer en una forma completa un arreglo, el cual procede a examinar cada uno de los elementos hasta encontrar el que está buscando, o en otro caso hasta que sea examinado todos los elementos que contenga el arreglo. Se representa de la siguiente manera para el caso que sea optimizado para buscar algún elemento dentro del arreglo

For (i=a=0; array[i]==elementobuscado; i++) En el caso que necesitemos de conocer solamente el primer registro se utiliza de esta manera For (i=0; i
b. Búsqueda Binaria: El requisito fundamental de este algoritmo tiene como petición que todo el arreglo haya sido ordenando previamente. Este tipo de algoritmo divide el arreglo, en varios sus arreglos menores para así poder comparar el mismo elemento buscado. Si existiera una coincidencia la búsqueda finaliza ahí, pero en el caso contrario el elemento buscado se seguirá buscando.

La forma que tiene para dividir es separar en dos dejando un elemento central para realizar la comparación. Seria {1, 2, 3,4} -5- {6, 7, 8, 9, 10} Ejemplo tomado de contenido de la semana N°2, IACC 2013

Cuando busca el número por dar un ejemplo el 6 verifica que el numero encontrado sea mayor que el numero central en caso de encontrar el arreglo termina.