ALGORITMOS COMPUTACIONALES I

	La recuperación de información es una de las más importantes aplicaciones de
las computadoras; se nos  da  un nombre y se nos pide un número telefónico asociado. 
Nos  dan  un número o nombre y debemos encontrar los registros  personales  de dicho
nombre o clave.
	
	En estos ejemplos estamos dando un fragmento de información el cual  denominaremos
llave y estamos preguntando para encontrar un registro que contiene  más información asociadacon
la llave. Una regla por simplicidad es  que,  dada  una llave no hay registro en absoluto que lo 
contenga.

La búsqueda de llaves para encontrar registros es aveces la acción que requiere más tiempo en un programa y por lo tanto la manera en que los registros se reacomodan y la selección del método usado en la busqueda puede influir mucho en la ejecución del programa. El problema de la busqueda en forma natural dentro de dos casos: Busqueda interna y Busqueda externa. Un archivo compuesto por un grupo de elementos, cada uno de ellos es un registro. Asociado a cada registro. Una llave que se utiliza para determinarlos de otro registro. Esta asociación a cada registro y su llave puede ser simple o com- puesta (compleja). SIMPLE. Cuando la llave esta contenida en un lugar especifico dentro de un registro. COMPLEJA. Cuando existe una tabla separada de llaves con apuntandor a los registros. REGRESAR AL PRINCIPIO DEL TUTOR

BUSQUEDA INTERNA. Esta se dá cuando los registros se mantienen dentro de los registros de la memoria de la computadora. BUSQUEDA EXTERNA. Se dá cuado hay muchos registros y cada uno quiza bastante grande o extenso y es necesario almacenarlos en archivos o en cintas externas de la computadora. BUSQUEDA POR COMPARACIÓN DE LLAVES. Aqui se tiene la busqueda secuencial, lo cual es una técnica e busqueda que mejora la eficiencia de un archivo ordenado pero requiere mayor espacio. BUSQUEDA POR TRANSFORMACIÓN DE LLAVES. Este tipo de busqueda se dá cuando el valor de la llave se transforma en un índice de una tabla para obtener una dirección, entonces al realizar la busqueda esta se hace de pendiendo de la dirección asignada a cada llave.

LLAVES PRIMARIAS. Para cada archivo existen un conjunto de llaves que es único, es decir, no existen dos registros con la misma llave LLAVES SECUNDARIAS. Es una llave que puede existir en dos o más registros en un mismo archivo.

Tres de los punto más importantes que se deben tomar en cuanta para llevar a cabo el ánalisis de eficiencia son: el tiempo requerido por el programador para codificar algún programa en particular de ordenamiento, el tiempo de máquina necesa- rio para correr el programa y la cantidad de espacio requerido por el programa. Si se tiene un archivo pequeño, las técnicas diseñadas de ordenamiento sofis- tcadas para minimizar espacios y tiempo son generalmen peores o marginalmente un poco mejores en obtener estas deficiencias que los métodos simples, generalmenteme no es ficientes. Igualmente, si un programa en particular de ordenamiento se va a correr solamente una vez y existe sufiente capacidad de espacio y tiempo de máquina para correrlo, sería lógico para el programador gastar días investigando el mejor método para poder poner un poco más de eficenfia. Esto nos lleva a la consideración de los otros dos factores de eficiencia: tiempo y espacio. Al consderar l tiempo requerido para ordenar un archivo de tamaño "n", generalmente no nos preocupamos con respecto a las unidades de tiempo reales, puesto que estas varian de una máquina a otra, de un programador a otro, y aun de un conjunto de datos a otro. En muchos casos, el tiempo requerido para un ordenamiento depende de la secuencia original de los datos. En muchas aplicaciones de prograamción es a veces necesaria sacrificar efi- ciencia por calidad. En caso de ordenamiento la situación es opuesta. Una vez que el programa de ordenamiento se ha escrito y probado, el objetivo básico del programador es de mejorar su velocidad aun si este se vuelve díficil de leer.

PROCEDURE A. SECUENCIAL(llave: integer; var posic:integer); var i,n:integer; begin f:=false; i:=1; while (i<=n) and (not f) do if llave="k[i]" then begin posic:="i;" f:="true;" end else inc(i); if not f then posic:="0;" end;

PROCEDURE B_S_ENCADENADA(llave:integer; var posic:int); VAR found:=false; BEGIN found:=false; q:=nil; p:=table; while(p<>nill) and (not found) do if k[p]=llave then begin posic:=p; found:=true; end else begin q:=p; p:=next[p]; end; if not found then posic:=0; end; BUSQUEDA SECUENCIAL ENCADENADA. Almacena una tabla o archivo como lista encadenada, tiene la ventaja que el tamaño de la tabla puede ser aumentada únicamente de acuerdo a los requerimientos. Asume que la tabla esta organizada como una lista encadenada lineal apuntada por List y encadenada por un campo puntero denominado Next; se asumen las mismas definiciones de llaves y posición.

PROCEDURE B_S_INDEXADA(llave:integer; var pocis:integer); var i,n:integer; f:boolean; begin f:=false; i:=1; while (i<llave) then f:= true; else inc(i); if i=1 then linf:=1 else linf:=pindex[i-1]; if f then lsup:=pindex[i]-1 else lsup:=n; j:=linf; f:=false; while(j<=lsup) ands (not f) do if k[j]="llave" then f:="true" else inc(j); if f then posic:="j" else posic:="0;" end; KINDEX. Arreglo de llaves en la tabla índice. PINDEX. Arreglo de punteros a los registros actuales del archivo. N. Tamaño del archivo. TAMINDEX. Tamaño de la tabla índice. Primero busca el rango de llaves en el que puede encontrar posiblemente la llave indicada, después busca secuencialmente en cada una de ellas hasta encontrarla o no, en caso de que no exista.

PROCEDURE BÚSQUEDA BINARIA; var f:=boolean; begin found:=false; inf:=1; sup:=N; While (inf <=sup ) and (not Found) Donova begin Mid:="(inf+sup)" div 2; if Key="K[Mid]" then f:="true" else if Key < k[Mid] then sup:=";Mid-1" else inf:="Mid+1;" end; if f then posic:="Mid" else posic:="0;" end; Este método es el más eficiente en un tabla o archivo secuencial. El argumen- to de busqueda es comparado con la llave del elemento central de la tabla, si estos son iguales entonces termina la busqueda, si no, continua la busqueda con la parte superior o inferior de la tabla siguiedo los mismos pasos.

PROCEDURE ARBOL BINARIO (llave:integer; var posic:integer); begin found:=false; p:= tree; While (p<>nil) and (not found)do if Key = K[p] then found:=true else if Key ..etc

Es un árbol de busqueda en el cual se forma un árbol general basado en los valores de las llaves. Por ejemplo, en llaves numéricas enteras de cada dígito que forma a esta llave representa un nodo del árbol y determina uno de los 10 hijos posibles de un nodo cado, a esta estructura completa se le llama bosque. Si las llaves son de letras cada letra del alfabeto determina una rama del árbol. El fin de la llave debe indicarse con una marca especial, además cada nodo hoja debe contener un apuntador al registro almacenado. Cada nodo de éste árbol general contien tres campos: DIGITO. Contiene un símbolo de llave. HIJO. Es un apuntador al hijo más viejo del nodo en el árbol. HERMANO. Es un apuntador al hermano más jóven siguiente en el nodo del árbol. El primer árbol en el bosque es apuntado por un apuntador externo denomi- nado raíz y las raizes de los otros árboles del bosque estan en cada nado en forma conjunta en una lista líneal mediante el campo hermano. El campo hijo de una hoja en un bosque apunta a un registro. La concatenación de todos los dígitos en el bosque original en el camino de los nodos desde la raíz hasta las hojas representa las llaves del registro. Cada lista de hermanos esta organiozada en el árbol en orden ascendente de acuerdo al campo del dígito. El indicador del fin del llave (EOK) End Of Key se considera que es más gran- de que cualquiera otro. RAIZ-->( 1 )-----------( 2 )-----------( 5 )-------------( 8 )-------------(9) / ¦ \ / \ / ¦ \ / ¦ \ ¦ (0)(1)(2) (0) (9) (5)(6)(8) (3)(1)(2) ( 0 ) / ¦ \ / \ / ¦ \ / ¦ \ / ¦ \ (9) (2) (3) (EOK) (EOK) (5) (7) (0) (0) (0) (EOK) (0)(3)(7) / ¦ \ / ¦ \ / ¦ / ¦ \ (EOK) (6) (EOK) (EOK) (EOK) (EOK)(0) (2) (EOK)(EOK)(EOK) ¦ / ¦ (EOK) (EOK) (EOK) PROCEDURE B_DIGITOS(llave: integer; var posic:integer); begin P:=raiz; PAD:=nil; F:=false; I:=1; While ( not F) do begin Q:=nill; Hviejo:=false; While (P<>nill) and (not Hviejo) do if digito(P) >= llave[I] then Hviejo:=true else begin Q:=P; HNO:=(P); end; F:=true; if (P:=nill) or (digito(P)) > (llave[I]) then insertar(posic) else if (llave[I]=EOK) then posic:= HIJO(P) else begin PAD:=P; P:= HIJO(P); F:=false; inc(I); end; end; end; BUSQUEDA DE DIGITOS: Funcionamineto. La representación de una tabla de llaves como un bosque es eficien- te si cada llave consta de pocos dígitos, en cambio a mayor número de dígitos en cada llave e obtendra un bosque más denso dentro del conjunto de todas las llaves. Y la mayoría de los nodos tendría un número muy grande de hijos y el tiempo en el pro- ceso de busqueda sería completamente deficiente.

Este algoritmo de busqueda es para un arreglo ordenado en donde se utilizan la secuencia numérica de Fibonacci como parte del proceso. Se utiliza un arreglo que contiene los números Fibonacci. La secuencia Fibonacci consiste en que cada elemento es la suma de los dos elementos anteriores. PROCEDURE FIBONACCI(llave:integer; var pocis:integer); begin J:=1; While(FIB[J] K[mitad]) and (not fin) do if (mitad <= 0) or (llave> K[mitad]) then if F1 = 1 then FIN:= true else begin MITAD:= MITAD+F2; F1:=F1-F2; F2:= F2-F1; end else if F2:=0 then FIN:= true; else begin MITAD:= MITAD-F2; T:= F1-F2; F2:= T; end; if FIN then posic:=0 else posic:=MITAD; end; BUSQUEDA POR TRANSFORMACIÓN DE LLAVES: Es el cálculo aplicado al valor de una llave para obtener una dirección. Transforma una llave en un índice de una tabla. También se llama función de randomi- zación. Una buena función Hash o asignación es aquella que minimiza los choques o coliciones y distribuye los registros uniformemente a través de la tabla, esta es la razón por la cual es mejor tener una regla con tamaño un poco mayor con el número real de registros entre más grande sea el rango de la función de randomización es menos posible que dos llaves generen el mismo valor de asignación.

La idea básica de este método es la de dividir el valor de la llave entre un número apropiado y después utilizar el resultado de la división como dirección relativa para el regitro. EJEMPLO: Considerar un archivo que en el cual las llaves son números de cinco dígitos y el número aproximado de registros es 900 sin repeticiones de llave. Se tendría que manejar un arreglo de 1000 elementos como suficiente para manejar todo el archivo. El arreglo es accesado mediante un entero entre 0 y 999 (índice). Los tres últimos dígitos de la llave son utilizados como índice para el registro en el arreglo.

En esta técnica la llave elevada al cuadrado y después algunos dígitos especificos se extraen de la mitad del resultado para constituir la dirección rala- tiva de dígitos, entonces los dígitos se truncan en ambos extremos de la llave alevada al cuadrado tomando "n" dígitos para cada llave. Para este ejemplo se tomarón los dígitos de 4 a 6 derecho a izquierdo para dar una dirección relativa de tres dígitos. FACTORES A TOMAR EN CUENTA 1. Para mayor seguiridad empezar a extraer dígitos de la mitad de la llave elevada al cuadrado a la izquierda. 2. Extraer el mismo número de dígitos para cada llave y de las mismas posiciones. Aquí hay que tomar en cuanta el número de registros que s etiene en el archivo.

En esta técnica el valor de la llave es particionado en varias partes, cada una de los cuales excepto el último tiene el mismo número de dígitos. Estas parti- ciones son plegadas unas sobre otras y sumadas. El resultado es la irección relativa y si es necesario el dígito más a la izquierda es truncado. FACTORES A TOMAR EN CUENTA 1. Sólo utilizar este método cuando el valor de la llave es de muchos dígitos. 2. Empezar a tomar valores de la llave de izquierda a derecha. 3. Tomar la primera parte de la llave con los dígitos que queremos que nos de la dirección y se ponen inversamente, posteriormente se toman otros dígitos que iran en el mismo orden luego inversos y así sucesivamente. Al final se suman las can- tidades y se trunca de la izquierda el valor sobrante.

TUTORIAL DE ALGORITMOS COMPUTACIONALES I

UNIDAD I

INTRODUCCION

1.1.- IMPORTANCIA DEL PROCESO DE BUSQUEDA

1.2.- INTERPRETACION DE LAS TECNICAS DE BUSQUEDA

1.3.- CLASIFICACION DE LAS TECNICAS DE BUSQUEDA

1.3.1.- BUSQUEDAS INTERNAS

1.3.2.- BUSQUEDAS EXTERNAS

1.3.3.- POR COMPARACION DE LLAVES

1.3.4.- POR TRANSFORMACION DE LLAVES

1.4.- CLASIFICACION DE LOS TIPOS DE LLAVES

1.4.1.- LLAVES PRIMARIAS

1.4.2.- LLAVES SECUNDARIAS

1.5.- ANALISIS DE EFICIENCIA

1.5.1.- NUMERO DE COMPARACIONES

1.5.2.- TIEMPO DE PROCESO

1.5.3.- ESPACIO REQUERIDO

UNIDAD II

BUSQUEDA POR COMPARACION DE LLAVES

2.1.-ALGORITMOS DE ARBOL SECUENCIAL

2.1.1.- BUSQUEDA SECUENCIAL DE ARREGLOS

2.1.2.- BUSQUEDA SECUENCIAL ENCADENADA

2.2.- ALGORITMO DE BUSQUEDA SECUENCIAL INDEXADA

2.3.- ALGORITMO DE BUSQUEDA BINARIA

2.4.- ALGORITMO DE ARBOLES BINARIOS DE BUSQUEDA

2.5.- ALGORITMO DE ARBOLES DIGITALES DE BUSQUEDA

2.6.- ALGORITMO DE FIBONACCI

UNIDAD III

BUSQUEDA POR TRANSFORMACION DE LLAVES

3.1.- FUNCIONES HASH

3.1.1- FUNCION HASH POR EL METODO DE LA DIVISION

3.1.2- FUNCION HASH POR EL METODO DEL CUADRADO

3.1.3- FUNCION HASH POR EL METODO DE PLIEGUE

1.1. IMPORTANCIA DEL PROCESO DE BUSQUEDA.

1.4.- CLASFICACION DE TIPOS DE LLAVES.

1.5.- ANALISIS DE EFICIENCIA.

UNIDAD II

BUSQUEDA POR COMPARACIÓN DE LLAVES

2.1.- ALGORITMOS DE ARBOL SECUENCIAL.

2.1.1.- BUSQUEDA SECUENCIAL DEE ARREGLOS.

1.2.2.- BUSQUEDA SECUENCIAL ENCADENADA.

2.2.- ALGORITMO DE BUSQUEDA SECUENCIAL INDEXADA.

2.3.- ALGORITMO DE BUSQUEDA SECUENCIAL BINARIA.

2.4.- ALGORITMO DE ÁRBOL BINARIO DE BUSQUEDA.

2.5.- ALGORITMO DE ARBOLES DIGITALES DE BUSQUEDA:

2.6.- ALGORITMO FIBONACCI:

UNIDAD III

BUSQUEDA POR TRANSFORMACION DE LLAVES

3.1.- FUNCIONES HASH MAS COMUNES:

3.1.1.- HASHING POR RESIDUO DE LA DIVISIÓN:

3.1.2.-HASHING POR MEDIO DEL CUADRADO.

3.1.3.-HASHING POR PLIEGUE.