ALGORITMOS COMPUTACIONALES I
Make your own free website on Tripod.com

TUTORIAL DE ALGORITMOS COMPUTACIONALES  I

UNIDAD I

REGRESAR A LA PAGINA PRINCIPAL



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

REGRESAR AL PRINCIPIO DEL TUTOR

1.1. IMPORTANCIA DEL PROCESO DE BUSQUEDA.
	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.

1.2.- INTERPRETACIÓN DE LAS TÉCNICAS DE BUSQUEDA.

	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

1.3.- CLASIFICACIÓN DE LAS TECNICAS DE BUSQUEDA.

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.

REGRESAR AL PRINCIPIO DEL TUTOR REGRESAR A LA PAGINA PRINCIPAL

1.4.- CLASFICACION DE TIPOS DE LLAVES.
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.
1.5.- ANALISIS DE EFICIENCIA.
	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.

REGRESAR AL PRINCIPIO DEL TUTOR







UNIDAD II

BUSQUEDA POR COMPARACIÓN DE LLAVES

2.1.- ALGORITMOS DE ARBOL SECUENCIAL.
2.1.1.- BUSQUEDA SECUENCIAL DEE ARREGLOS.
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; 
REGRESAR AL PRINCIPIO DEL TUTOR
1.2.2.- BUSQUEDA SECUENCIAL ENCADENADA.
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.
REGRESAR AL PRINCIPIO DEL TUTOR
 
2.2.- ALGORITMO DE BUSQUEDA SECUENCIAL INDEXADA.
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. 
REGRESAR AL PRINCIPIO DEL TUTOR
2.3.- ALGORITMO DE BUSQUEDA SECUENCIAL BINARIA.
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. 
REGRESAR AL PRINCIPIO DEL TUTOR
2.4.- ALGORITMO DE ÁRBOL BINARIO DE BUSQUEDA.
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

 

 
REGRESAR AL PRINCIPIO DEL TUTOR


2.5.- ALGORITMO DE ARBOLES DIGITALES DE BUSQUEDA:
	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.
REGRESAR AL PRINCIPIO DEL TUTOR

2.6.- ALGORITMO FIBONACCI:
	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.
REGRESAR AL PRINCIPIO DEL TUTOR









UNIDAD III

BUSQUEDA POR TRANSFORMACION DE LLAVES
3.1.- FUNCIONES HASH MAS COMUNES:
Residuo de la división.
Medio del cuadrado.
Pliegue.
3.1.1.- HASHING POR RESIDUO DE LA DIVISIÓ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.
3.1.2.-HASHING POR MEDIO DEL CUADRADO.
	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.
3.1.3.-HASHING POR PLIEGUE.
	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.
REGRESAR AL PRINCIPIO DEL TUTOR