martes, 26 de mayo de 2009
METODO DE ORDENACION QUICKSORT
METODO DE QUICK SORT*
Es uno de los métodos mas rápidos y mas utilizados en la ordenación de arreglos y fue inventado por C. Horre.
La cantidad de código necesario es pequeña con la velocidad que proporciona.
La idea básica de la ordenación de un arreglo consiste:
1.- elegir el elemento pivote
2.- dividir a partir del arreglo original en 2 subarreglos de modo que un subarreglo o sublista están todos los elementos menores del pivote y en la otra sublista todos los elementos mayores del pivote, las sublistas deben ser ordenadas del mismo modo, lo que conduce a un algoritmo recursivo.
La elección del pivote es arbitraria aunque por comodidad es usual utilizar el termino central de la lista original aunque se puede utilizar el primero o el ultimo elemento de la misma, para ello se establecen 2 punteros; por ejemplo: i y j.... I apuntara al 1er elemento y j apuntara al último.
El siguiente paso es comparar si el elemento de i es menor que el pivote, si es menor se deberá ir incrementando i cuantas veces sea necesario, lo mismo sucederá para j, si el elemento es mayor que el pivote se deberá ir decrementando.
En caso de que el elemento de j sea menor que el pivote se hará un intercambio entre i y j y se incrementara a i y se decrementara a j.
En el momento en el que j sea menor que i se ha terminado la partición y se han generado 2 sublistas, en la 1ra sublista todos los elementos menores o igual al pivote y en la 2da todos los elementos mayores que el pivote.
Se repetirá la misma partición hasta que los elementos hayan quedado ordenados. Este método es conocido como: "DIVIDE Y VENCERÁS".
Ejemplo:
Es uno de los métodos mas rápidos y mas utilizados en la ordenación de arreglos y fue inventado por C. Horre.
La cantidad de código necesario es pequeña con la velocidad que proporciona.
La idea básica de la ordenación de un arreglo consiste:
1.- elegir el elemento pivote
2.- dividir a partir del arreglo original en 2 subarreglos de modo que un subarreglo o sublista están todos los elementos menores del pivote y en la otra sublista todos los elementos mayores del pivote, las sublistas deben ser ordenadas del mismo modo, lo que conduce a un algoritmo recursivo.
La elección del pivote es arbitraria aunque por comodidad es usual utilizar el termino central de la lista original aunque se puede utilizar el primero o el ultimo elemento de la misma, para ello se establecen 2 punteros; por ejemplo: i y j.... I apuntara al 1er elemento y j apuntara al último.
El siguiente paso es comparar si el elemento de i es menor que el pivote, si es menor se deberá ir incrementando i cuantas veces sea necesario, lo mismo sucederá para j, si el elemento es mayor que el pivote se deberá ir decrementando.
En caso de que el elemento de j sea menor que el pivote se hará un intercambio entre i y j y se incrementara a i y se decrementara a j.
En el momento en el que j sea menor que i se ha terminado la partición y se han generado 2 sublistas, en la 1ra sublista todos los elementos menores o igual al pivote y en la 2da todos los elementos mayores que el pivote.
Se repetirá la misma partición hasta que los elementos hayan quedado ordenados. Este método es conocido como: "DIVIDE Y VENCERÁS".
Ejemplo:
IMPLEMENTACION DE UNA MATRIZ EN UN ARBOL
Introducción
La matriz binaria, en la que el valor ‘1’ representará al color NEGRO y el valor ‘0’ al color BLANCO.
Otra posible representación de la misma imagen consiste en emplear árboles binarios.
Para realizar la conversión entre una representación de la imagen a su equivalente en árbol binario
debemos suponer que la matriz binaria es cuadrada y el rango de la misma es potencia de 2.
En esta representación obtendremos un árbol por cada fila de la matriz binaria, que almacenaremos en una estructura para poder trabajar posteriormente sobre esta representación en futuras operaciones.
El proceso principal de obtención de un árbol binario consiste en ir dividiendo la fila en dos mitades cuando ésta no tenga un valor constante, hasta que lleguemos al caso de encontrar un trozo de tal fila cuyos elementos tengan el mismo valor o bien tengamos únicamente una fila con un único elemento, guandándose en ese caso información pictórica.
Ejemplo representaciones Matriz binaria y Árbol binario
1.Descripción de tipos de datos usados en el programa
1.1.Tipo IMAGEN.
1.2.Tipo NODO.
1.3.TABLAS.
1.3.1.Ejemplo.
2.Conversión Matriz binaria a Árbol binario.
2.1.Pseudocodigo.
2.2.Ejemplo.
3.Conversión Árbol binario a Matriz binaria.
3.1.Pseudocodigo.
3.2.Ejemplos.
1.Descripción de tipos de datos usados en el programa.
1.1.Tipo IMAGEN.
1.2.Tipo NODO.
1.3.TABLAS.
1.3.1.Ejemplo estructura ConjuntoArbolBinario
CONVERSIÓN ÁRBOL BINARIO A MATRIZ BINARIA
3.1.Pseudocodigo.
3.2.Ejemplo conversión Árbol binario en Matriz binaria.
3.2.Ejemplo conversión Árbol binario en Matriz binaria.
La matriz binaria, en la que el valor ‘1’ representará al color NEGRO y el valor ‘0’ al color BLANCO.
Otra posible representación de la misma imagen consiste en emplear árboles binarios.
Para realizar la conversión entre una representación de la imagen a su equivalente en árbol binario
debemos suponer que la matriz binaria es cuadrada y el rango de la misma es potencia de 2.
En esta representación obtendremos un árbol por cada fila de la matriz binaria, que almacenaremos en una estructura para poder trabajar posteriormente sobre esta representación en futuras operaciones.
El proceso principal de obtención de un árbol binario consiste en ir dividiendo la fila en dos mitades cuando ésta no tenga un valor constante, hasta que lleguemos al caso de encontrar un trozo de tal fila cuyos elementos tengan el mismo valor o bien tengamos únicamente una fila con un único elemento, guandándose en ese caso información pictórica.
Ejemplo representaciones Matriz binaria y Árbol binario
1.Descripción de tipos de datos usados en el programa
1.1.Tipo IMAGEN.
1.2.Tipo NODO.
1.3.TABLAS.
1.3.1.Ejemplo.
2.Conversión Matriz binaria a Árbol binario.
2.1.Pseudocodigo.
2.2.Ejemplo.
3.Conversión Árbol binario a Matriz binaria.
3.1.Pseudocodigo.
3.2.Ejemplos.
1.Descripción de tipos de datos usados en el programa.
1.1.Tipo IMAGEN.
1.2.Tipo NODO.
1.3.TABLAS.
1.3.1.Ejemplo estructura ConjuntoArbolBinario
CONVERSIÓN ÁRBOL BINARIO A MATRIZ BINARIA
3.1.Pseudocodigo.
3.2.Ejemplo conversión Árbol binario en Matriz binaria.
3.2.Ejemplo conversión Árbol binario en Matriz binaria.
FUNCION HASH
FUNCION DE DISPERSION HASH
Una función hash es un algoritmo matemático que nos da un resultado B al aplicarlo a un valor inicial A.
Es como cualquier función matemática, por ejemplo la función raíz cuadrada nos daría como resultado 2 si se la aplicamos al número 4.
Al igual que cualquier función matemática tiene que actuar de tal forma y tiene que cumplir con ciertos criterios. No nos puede devolver cualquier cosa, lo que nos devuelva requiere que tenga ciertas propiedades para que podamos usarlo.
Una función de Hash es una caja negra que tiene como entrada una llave y como salida una dirección
h(K)=address
Ejemplo: h(LOWELL)=4
El hashing es similar al indexamiento en el sentido de asociación entre llaves y direcciones relativas de registros
Pero difiere de los índices en 2 cosas:
1. La dirección generada por Hash suele ser aleatoria (random).
No hay una relación aparente entre la llave y la localización del registro correspondiente
2. El Hash permite que 2 llaves puedan producir la misma salida --> direcciones iguales, a esto se le conoce como "colisión".
PROPIEDADES BASICAS PARA CUMPLIR POR LAS FUNCIONES HASH
1. Sea cual sea la longitud del texto base A, la longitud de su hash resultante B siempre va a ser la misma.
Si la longitud de la salida B esta defiinida en 128 bits, si aplicamos una función hash a un A de 5 bits nos dará un B de 128 bits, y si se la aplicamos a un A de 380 millones de bits, nos dará un B de 128 bits igualmente.
2. Para cada entrada A, la función generará una salida B única. O lo que es lo mismo, es imposible que dos textos bases A y A' tengan un mismo hash B.
3. Dado un texto base, es fácil y rápido (para un ordenador) calcular su número resumen.
Una función hash es un algoritmo matemático que nos da un resultado B al aplicarlo a un valor inicial A.
Es como cualquier función matemática, por ejemplo la función raíz cuadrada nos daría como resultado 2 si se la aplicamos al número 4.
Al igual que cualquier función matemática tiene que actuar de tal forma y tiene que cumplir con ciertos criterios. No nos puede devolver cualquier cosa, lo que nos devuelva requiere que tenga ciertas propiedades para que podamos usarlo.
Una función de Hash es una caja negra que tiene como entrada una llave y como salida una dirección
h(K)=address
Ejemplo: h(LOWELL)=4
El hashing es similar al indexamiento en el sentido de asociación entre llaves y direcciones relativas de registros
Pero difiere de los índices en 2 cosas:
1. La dirección generada por Hash suele ser aleatoria (random).
No hay una relación aparente entre la llave y la localización del registro correspondiente
2. El Hash permite que 2 llaves puedan producir la misma salida --> direcciones iguales, a esto se le conoce como "colisión".
PROPIEDADES BASICAS PARA CUMPLIR POR LAS FUNCIONES HASH
1. Sea cual sea la longitud del texto base A, la longitud de su hash resultante B siempre va a ser la misma.
Si la longitud de la salida B esta defiinida en 128 bits, si aplicamos una función hash a un A de 5 bits nos dará un B de 128 bits, y si se la aplicamos a un A de 380 millones de bits, nos dará un B de 128 bits igualmente.
2. Para cada entrada A, la función generará una salida B única. O lo que es lo mismo, es imposible que dos textos bases A y A' tengan un mismo hash B.
3. Dado un texto base, es fácil y rápido (para un ordenador) calcular su número resumen.
METODO DE ORDENAMIENTO POR INSERCION BINARIA
DEFINICION
El algoritmo de inserción directa se mejora fácilmente al notar que la secuencia destino aj..ai-1, donde debe insertarse el nuevo elemento, ya está ordenada . Por eso puede ser empleado un método más rápido para determinar el punto de inserción . La elección obvia es una búsqueda binaria que prueba la secuencia destino en la mitad y continúa buscando hasta encontrar el punto de inserción. El algoritmo de clasificación modificado recibe el nombre de inserción binaria.
Carácteristicas fundamentales:
1.- La secuencia destino donde debe insertarse el nuevo elemento ya esta ordenada.
2.-Búsqueda Binaria para localizar el lugar de inserción.
3.-Desplazar elementos.
4.-Insertar.
Análisis:
Al realizar la búsqueda binaria se divide una longitud L por la mitad un número determinado de veces.
Algoritmo
para (i=2 hasta N)
{
aux = A[i];
izq=1;
der=i-1;
mientras (izq<=der)
{
m=[parte entera ((izq+der)/2)];
si (aux
der=m-1;
}
si no
{
izq=m+1;
}
}
j=i-1;
mientras (j>=izq)
{
A[j+1]=A[j];
j=j-11;
}
A[izq]=auz;
}
Procedimiento
El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo.
Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
El algoritmo de inserción directa se mejora fácilmente al notar que la secuencia destino aj..ai-1, donde debe insertarse el nuevo elemento, ya está ordenada . Por eso puede ser empleado un método más rápido para determinar el punto de inserción . La elección obvia es una búsqueda binaria que prueba la secuencia destino en la mitad y continúa buscando hasta encontrar el punto de inserción. El algoritmo de clasificación modificado recibe el nombre de inserción binaria.
Carácteristicas fundamentales:
1.- La secuencia destino donde debe insertarse el nuevo elemento ya esta ordenada.
2.-Búsqueda Binaria para localizar el lugar de inserción.
3.-Desplazar elementos.
4.-Insertar.
Análisis:
Al realizar la búsqueda binaria se divide una longitud L por la mitad un número determinado de veces.
Algoritmo
para (i=2 hasta N)
{
aux = A[i];
izq=1;
der=i-1;
mientras (izq<=der)
{
m=[parte entera ((izq+der)/2)];
si (aux
der=m-1;
}
si no
{
izq=m+1;
}
}
j=i-1;
mientras (j>=izq)
{
A[j+1]=A[j];
j=j-11;
}
A[izq]=auz;
}
Procedimiento
El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo.
Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
ORDENACION POR EL METODO SHELL
Ordenación por el método de Shell (ShellSort)
El método se denomina Shell en honor de su inventor Donald Shell.
Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.
Esto quedaría así:
13. 14 94 33 82
14. 59 94 65 23
15. 27 73 25 39
10
10. 14 73 25 23
11. 27 94 33 39
12. 59 94 65 82
45
Entonces ordenamos cada columna, lo que nos da
Cuando lo leemos de nuevo como una única lista de números, obtenemos
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].
SECUENCIA DE ESPACIOS
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción. se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
El método se denomina Shell en honor de su inventor Donald Shell.
Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.
Esto quedaría así:
13. 14 94 33 82
14. 59 94 65 23
15. 27 73 25 39
10
10. 14 73 25 23
11. 27 94 33 39
12. 59 94 65 82
45
Entonces ordenamos cada columna, lo que nos da
Cuando lo leemos de nuevo como una única lista de números, obtenemos
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].
SECUENCIA DE ESPACIOS
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción. se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
METODOS DE BUSQUEDA
METODOS DE BUSQUEDA
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
• Métodos de Búsqueda Interna
• Métodos de Búsqueda Externa.
METODOS DE BUSQUEDA INTERNA
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
• Secuencial o lineal
• Binaria
• Por transformación de claves
• Arboles de búsqueda
•
METODOS DE BUSQUEDA EXTERNA
• Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).
BUSQUEDA SECUENCIAL
• Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
• CARACTERISTICAS
• La búsqueda se puede realizar en arreglos desordenados.
• El método es totalmente confiable.
• El numero de comparaciones es significativa si el arreglo es muy grande.
• En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+N)/2.
• Cantidad máxima de comparaciones es N.
DIAGRAMA DE FLUJO
(BUSQUEDA SECUENCIAL)
BUSQUEDA BINARIA
• La búsqueda binaria utiliza un método de `divide y vencerás' para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.
• En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
CARACTERISTICAS
• Sirve únicamente para arreglos ordenados.
• Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+log₂(N))/2.
• Cantidad máxima de comparaciones es log₂(N).
ALGORITMO
• Se compara la llave buscada con la llave localizada al centro del arreglo.
• Si la llave analizada corresponde a la buscada fin de búsqueda si no.
• Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
• El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero, lo cual implica que el valor de la llave buscada no está en la lista.
BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
• Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
• El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
• La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
FUNCIONES HASH
• Las Funciones HASH (H) mas aplicadas son:
• Función Modulo (Por división).
• Función Cuadrado.
• Función Plegamiento.
• Función Truncamiento.
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
• Métodos de Búsqueda Interna
• Métodos de Búsqueda Externa.
METODOS DE BUSQUEDA INTERNA
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
• Secuencial o lineal
• Binaria
• Por transformación de claves
• Arboles de búsqueda
•
METODOS DE BUSQUEDA EXTERNA
• Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).
BUSQUEDA SECUENCIAL
• Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
• CARACTERISTICAS
• La búsqueda se puede realizar en arreglos desordenados.
• El método es totalmente confiable.
• El numero de comparaciones es significativa si el arreglo es muy grande.
• En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+N)/2.
• Cantidad máxima de comparaciones es N.
DIAGRAMA DE FLUJO
(BUSQUEDA SECUENCIAL)
BUSQUEDA BINARIA
• La búsqueda binaria utiliza un método de `divide y vencerás' para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.
• En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
CARACTERISTICAS
• Sirve únicamente para arreglos ordenados.
• Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+log₂(N))/2.
• Cantidad máxima de comparaciones es log₂(N).
ALGORITMO
• Se compara la llave buscada con la llave localizada al centro del arreglo.
• Si la llave analizada corresponde a la buscada fin de búsqueda si no.
• Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
• El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero, lo cual implica que el valor de la llave buscada no está en la lista.
BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
• Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
• El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
• La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
FUNCIONES HASH
• Las Funciones HASH (H) mas aplicadas son:
• Función Modulo (Por división).
• Función Cuadrado.
• Función Plegamiento.
• Función Truncamiento.
ORDENACION POR METODO HEAPSORT
HEAPSORT
• El ordenamiento por heapsort es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional
• El Heapsort está basado en el uso de un tipo especial de árbol binario (llamado apilamiento) para estructurar el proceso de ordenamiento. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en O(n log n).
Caracteristicas
¨ Las llaves están acomodadas en los nodos de tal manera que, para cada nodo i,
Ki <= Kj donde el nodo j es el padre del nodo i. Es decir, al recorrer el camino desde la raíz hacia abajo, las claves se encuentran en orden descendente.
¨ El árbol se llena de izquierda a derecha, lo que implica que si algún(os) nodo(s) no está(n) en el mismo nivel que el resto, éste(os) estará(n) entonces lo más a la izquierda posible del árbol.
Pasos del Heap
1º. Saca el valor máximo del Heap. (El de la posición 1).
2º. Pone el valor sacado en el arreglo ordenado.
3º. Reconstruir el Heap con un elemento menos.
Ejemplo
Ordenamiento : 73 - 50 - 36 - 21 - 46 - 27 - 9 - 18 - 10 - 30
lunes, 25 de mayo de 2009
BUSQUEDA POR EL METODO HASH
Procedimiento
Método consistente en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas
Casos de Colision
soluciones para reducir el número de colisiones
Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones
Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.
Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.
9.3.1 Un Algoritmo de Hash
No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos: 1) Representar la llave de manera numérica (siempre que no sea de por sí un número) Una buena opción es usar los valores ASCII o bien los Unicode de las letras LOWELL= L O W E L L _ _ _ _ _ _ 76 79 87 69 76 76 32 32 32 32 32 32 2) Plegar y Agregar Combinar algunos de estos números para generar pequeños trozos con los que podamos trabajar 76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32 De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección 7679 + 8769 + 7676 + 3232 + 3232 = 30 588 Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema. 3) Dividir por un número primo y usar el resultado como dirección Los archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula:
o a= s mod n
o donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal), etc...
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
No pueden usarse registros de longitud variable
El archivo no esta clasificado
No permite llaves repetidas
Solo permite acceso por una sola llave
Costos
o Tiempo de procesamiento requerido para la aplicación de la función hash
o Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.
Factores de Eficiencia
o La distribución de los valores de llave que realmente se usan
o El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones
o El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión
o La técnica usada para resolver el problema de las colisiones
Tipos de Funcion Hash
o Residuo de la división
o Medio del cuadrado
o Pliegue
Hashing por residuo de división
o 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).
Consideraciones
· Independientemente de que tan bueno sea el divisor, cuando el espacio de direcciones de un archivo esta completamente lleno, la probabilidad de colisión crece dramáticamente. La saturación de archivo de mide mediante su factor de carga, el cual se define como la relación del numero de registros en el archivo contra el numero de registros que el archivo podría contener si estuviese completamente lleno.
Factor de Carga
Todas las funciones hash comienzan a trabajar probablemente cuando el archivo esta casi lleno. Por lo general el máximo factor de carga que puede tolerarse en un archivo para un rendimiento razonable es de entre el 70 % y 80 %.
Hashing por Elevacion al 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.
· Utilizando esta función hashing el tamaño del archivo resultante es de 10n donde n es el numero de dígitos extraídos de los valores de la llave elevada al cuadrado.
Hashing por Pliegue
o En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales (excepto la ultima) tiene el mismo numero de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa. Igual que para el método del medio del cuadrado, el tamaño del espacio de direcciones relativas es una potencia de 10.
Método consistente en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas
Casos de Colision
soluciones para reducir el número de colisiones
Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones
Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.
Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.
9.3.1 Un Algoritmo de Hash
No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos: 1) Representar la llave de manera numérica (siempre que no sea de por sí un número) Una buena opción es usar los valores ASCII o bien los Unicode de las letras LOWELL= L O W E L L _ _ _ _ _ _ 76 79 87 69 76 76 32 32 32 32 32 32 2) Plegar y Agregar Combinar algunos de estos números para generar pequeños trozos con los que podamos trabajar 76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32 De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección 7679 + 8769 + 7676 + 3232 + 3232 = 30 588 Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema. 3) Dividir por un número primo y usar el resultado como dirección Los archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula:
o a= s mod n
o donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal), etc...
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
No pueden usarse registros de longitud variable
El archivo no esta clasificado
No permite llaves repetidas
Solo permite acceso por una sola llave
Costos
o Tiempo de procesamiento requerido para la aplicación de la función hash
o Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.
Factores de Eficiencia
o La distribución de los valores de llave que realmente se usan
o El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones
o El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión
o La técnica usada para resolver el problema de las colisiones
Tipos de Funcion Hash
o Residuo de la división
o Medio del cuadrado
o Pliegue
Hashing por residuo de división
o 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).
Consideraciones
· Independientemente de que tan bueno sea el divisor, cuando el espacio de direcciones de un archivo esta completamente lleno, la probabilidad de colisión crece dramáticamente. La saturación de archivo de mide mediante su factor de carga, el cual se define como la relación del numero de registros en el archivo contra el numero de registros que el archivo podría contener si estuviese completamente lleno.
Factor de Carga
Todas las funciones hash comienzan a trabajar probablemente cuando el archivo esta casi lleno. Por lo general el máximo factor de carga que puede tolerarse en un archivo para un rendimiento razonable es de entre el 70 % y 80 %.
Hashing por Elevacion al 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.
· Utilizando esta función hashing el tamaño del archivo resultante es de 10n donde n es el numero de dígitos extraídos de los valores de la llave elevada al cuadrado.
Hashing por Pliegue
o En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales (excepto la ultima) tiene el mismo numero de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa. Igual que para el método del medio del cuadrado, el tamaño del espacio de direcciones relativas es una potencia de 10.
TEORIA DE GRAFOS
GRAFOS 
la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos(también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas(arcs en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.Estructura de listalista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra. En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si V=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.Ejemplo de lista de adyacencia Estructuras matricialesMatriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado) Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de lo contrario, es 0.
ALGORITMO DE CREACION.
repite
si top=NIL entonces
new(top)
top(la)<--NIL top(ld)<--NIL lee(top(dato)) q<--top en caso contrario new(p) p(ld)<--NIL p(la)<--NIL q(la)<--p lee(p(dato)) q<--p mensaje(otro vertice ?) lee(respuesta) hasta repuesta=no p<--top mientras p<>NIL haz
mensaje(tiene vértices adyacentes p(dato) ?)
lee(respuesta)
si respueta=si entonces
repite
new(q)
lee(q(dato))
q(ld)<--p(ld) p(ld)<--q mensaje(otro vértice ?) lee(respuesta2) hasta respuesta2=no p<--p(la) ALGORITMO DE INSERCION mensaje(valor a insertar ?) lee(valor_a_insertar) si top<>NIL entonces
p<--top mientras p(la)<>NIL haz
p<--p(la) new(q) lee(q(dato)) p(la)<--q q(la)<--NIL mensaje(Hay vértices adyacentes?) lee(respuesta) si respuesta=si entonces mensaje(Cuantos vértices?) lee(número_vértices) desde i=1 hasta número_vértices haz new(p) lee(p(dato)) q(ld)<--p q<--q(ld) en caso contrario mensaje(no existe lista) ALGORITMO DE BUSQUEDA mensaje(vértice a buscar) lee(vértice_a_buscar) p<--top repite si p(dato)=vértice_a_buscar entonces repite p<--p(ld) escribe(p(dato)) hasta p(ld)=NIL en caso contrario p<--(la) hasta p=NIL ALGORITMO DE BORRADO mensaje(vértice a borrar ?) lee(vértice_a_borrar) p&Lt--top r<--p q<--p sw<--falso repite si p(dato)=vértice_a_borrar entonces si p=top entonces top<--top(la) r<--top sw<--verdadero en caso contrario r(la)<--p(la) repite p<--p(ld) dispose(q) q<--p hasta p=NIL si sw=verdadero entonces p<--r q<--p en caso contrario p<--r(la) q<--p en caso contrario r<--p repite q<--p(ld) si q(dato)=vértice_a_borrar entonces p(ld)<--q(ld) dispose(q) q<--p en caso contrario p<--p(ld) hasta p=NIL
repite
si top=NIL entonces
new(top)
top(la)<--NIL top(ld)<--NIL lee(top(dato)) q<--top en caso contrario new(p) p(ld)<--NIL p(la)<--NIL q(la)<--p lee(p(dato)) q<--p mensaje(otro vertice ?) lee(respuesta) hasta repuesta=no p<--top mientras p<>NIL haz
mensaje(tiene vértices adyacentes p(dato) ?)
lee(respuesta)
si respueta=si entonces
repite
new(q)
lee(q(dato))
q(ld)<--p(ld) p(ld)<--q mensaje(otro vértice ?) lee(respuesta2) hasta respuesta2=no p<--p(la) ALGORITMO DE INSERCION mensaje(valor a insertar ?) lee(valor_a_insertar) si top<>NIL entonces
p<--top mientras p(la)<>NIL haz
p<--p(la) new(q) lee(q(dato)) p(la)<--q q(la)<--NIL mensaje(Hay vértices adyacentes?) lee(respuesta) si respuesta=si entonces mensaje(Cuantos vértices?) lee(número_vértices) desde i=1 hasta número_vértices haz new(p) lee(p(dato)) q(ld)<--p q<--q(ld) en caso contrario mensaje(no existe lista) ALGORITMO DE BUSQUEDA mensaje(vértice a buscar) lee(vértice_a_buscar) p<--top repite si p(dato)=vértice_a_buscar entonces repite p<--p(ld) escribe(p(dato)) hasta p(ld)=NIL en caso contrario p<--(la) hasta p=NIL ALGORITMO DE BORRADO mensaje(vértice a borrar ?) lee(vértice_a_borrar) p&Lt--top r<--p q<--p sw<--falso repite si p(dato)=vértice_a_borrar entonces si p=top entonces top<--top(la) r<--top sw<--verdadero en caso contrario r(la)<--p(la) repite p<--p(ld) dispose(q) q<--p hasta p=NIL si sw=verdadero entonces p<--r q<--p en caso contrario p<--r(la) q<--p en caso contrario r<--p repite q<--p(ld) si q(dato)=vértice_a_borrar entonces p(ld)<--q(ld) dispose(q) q<--p en caso contrario p<--p(ld) hasta p=NIL
Suscribirse a:
Entradas (Atom)