Materia: Laboratorio de lenguajes de programación
Hora: Jueves v1
Hola a todos aquí les dejo una pequeña entrada sobre el lenguaje Algol.
Su nombre proviene del término Algorithmic Language (Lenguaje Algorítmico). Fue muy popular durante los años 60 e influyó en varios lenguajes como Pascarl, C y Ada.
Durante 1965 aparecieron dos lenguajes: el Algol W que es un lenguaje minimalista, rápidamente implementado y distribiudo. Y también apareció el Algol 68.
Algol W
Es un lenguaje elaborado por Niklaus Wirth y Tony Hoare, es un lenguaje conciso, simple de implementar, evita todos los defectos conocidos del lenguaje Algol e incluye sus propias características. Fue utilizado por muchos usuarios y abrió el camino para el nacimiento del lenguaje Pascal.
Algunas características sobre este lenguaje son:
Aritmética de doble precisión, números complejos, Strings y estructuras de datos dinámicas, evaluación por valor, pasaje de parámetros por valor, valor resultado o resultado.
Algol 68
Su creador es Adriaan van Wijingaarden, los objetivos principales de este lenguaje son: permitir comunicar algoritmos, permitir una eficiente ejecución de los mismos en diferentes arquitecturas y el de servir como herramienta para la enseñanza.
Una interesante característica de este lenguaje esque su semántica fue definida formalmente antes de ser implementado en base al formalismo llamado: gramáticas de dos niveles.
Esto es todo sobre Algol, espero les ayude de algo :)
Saludos :)
domingo, 14 de noviembre de 2010
*Lenguaje Fortran
Materia: Laboratorio de lenguajes de programación
Hora: Jueves v1
Hola a todos, aquí les dejo una pequeña entrada sobre el lenguaje Fortran.
El lenguaje Fortran que significa Formula Translating System es un lenguaje de programación de alto nivel de propósito general, procedimental e imperativo que está adaptado al cálculo numérico y a la computación científica. Fue desarrollado por IBM en 1957 para el equipo IBM 704.
Este lenguaje se utiliza para programas que evalúan el desempeño y el ranking de los supercomputadores más rápidos del mundo.
Algunas versiones de Fortran son :
- Las líneas tenian que ser numeradas.
- La única alteración posible en el orden de ejecución era producida con la instrucción goto.
- Utilizan subprogramas, recursión y diferentes estructuras de control.
El lenguaje Fortran tiene unos números y signos que utiliza y que
funcionan como caracteres o letras, siendo los caracteres permitidos
por este lenguaje los siguientes:
-Letras de la A a la Z (Tanto mayúsculas como minúsculas).
-Números del 0 al 9.
-Caracteres de puntuación ., ;.
-Caracteres matem ticos +, *, /, -.
-Caracteres especiales $, , =, <, >, (), :, ´, y el blanco.
-El lenguaje Fortran no distingue en la sintaxis las letras mayúsculas
y minúsculas, solo en el caso de los literales, y los signos de la
comparación que casi no los utiliza.
Bueno esto es todo sobre Fortran. Espero les ayude :)
Aquí les dejo un Tutorial de Fortran, un Manual de Fortran y una Tarjeta de referencia de Fortran. Saludos :)
Hora: Jueves v1
Hola a todos, aquí les dejo una pequeña entrada sobre el lenguaje Fortran.
El lenguaje Fortran que significa Formula Translating System es un lenguaje de programación de alto nivel de propósito general, procedimental e imperativo que está adaptado al cálculo numérico y a la computación científica. Fue desarrollado por IBM en 1957 para el equipo IBM 704.
Este lenguaje se utiliza para programas que evalúan el desempeño y el ranking de los supercomputadores más rápidos del mundo.
Algunas versiones de Fortran son :
- FORTRAN IV
- FORTRAN 77
- FORTRAN 90
- FORTRAN 95
- FORTRAN 2003
- FORTRAN 2008
- FORTRAN 2010
- Las líneas tenian que ser numeradas.
- La única alteración posible en el orden de ejecución era producida con la instrucción goto.
- Utilizan subprogramas, recursión y diferentes estructuras de control.
El lenguaje Fortran tiene unos números y signos que utiliza y que
funcionan como caracteres o letras, siendo los caracteres permitidos
por este lenguaje los siguientes:
-Letras de la A a la Z (Tanto mayúsculas como minúsculas).
-Números del 0 al 9.
-Caracteres de puntuación ., ;.
-Caracteres matem ticos +, *, /, -.
-Caracteres especiales $, , =, <, >, (), :, ´, y el blanco.
-El lenguaje Fortran no distingue en la sintaxis las letras mayúsculas
y minúsculas, solo en el caso de los literales, y los signos de la
comparación que casi no los utiliza.
Bueno esto es todo sobre Fortran. Espero les ayude :)
Aquí les dejo un Tutorial de Fortran, un Manual de Fortran y una Tarjeta de referencia de Fortran. Saludos :)
*Iteración
Materia: Laboratorio de Lenguajes de Programación
Hora: Jueves v1
Hola a todos, aquí les dejo una pequeña entrada sobre Iteración.
Se dice que Iteración es la repetición de una serie de instrucciones en un programa. Un ejemplo de Iteración en pseudocódigo:
var i=0, a := 0 // inicializo a antes de comenzar la iteración
for i from 1 to 3 { // ciclo 3 veces
a := a + i // incremento a con el valor actual de i
print a // se imprime el número 6
}
En este ejemplo el valor de la variable i cambia a medida que la ejecución del programa avanza, tomando los valores 1, 2 y 3. Y a este cambio de valor o estado mutable es característico de una iteración.
Existen Sentencias de Iteración o Ciclos que son estructuras de control que repiten la ejecución de un grupo de instrucciones, es una estructura de control condicional, ya que dentro de la misma se repite la ejecución de una o mas instrucciones mientras o hasta que una condición específica se cumpla.
Y algunas de ellas son:
Sentencias For
for(contador; final; incremento)
{
Codigo a Repetir;
}
donde: contador es una variable numérica.
final es el valor final para contador.
incremento es el valor que se suma o se resta al contador.
Sentencia while
while(condicion)
{
codigo a Repetir
}
Sentencia do-while
int contador = 0;
do
{
contador ++;
}
while(contador > 10);
Bueno esto es todo de mi entrada, aquí les dejo un video en donde muestran una explicación sobre la estructura de Iteración. Espero les sirva :) cualquier cosa hagánmelo saber.
Saludos :)
Hora: Jueves v1
Hola a todos, aquí les dejo una pequeña entrada sobre Iteración.
Se dice que Iteración es la repetición de una serie de instrucciones en un programa. Un ejemplo de Iteración en pseudocódigo:
var i=0, a := 0 // inicializo a antes de comenzar la iteración
for i from 1 to 3 { // ciclo 3 veces
a := a + i // incremento a con el valor actual de i
print a // se imprime el número 6
}
En este ejemplo el valor de la variable i cambia a medida que la ejecución del programa avanza, tomando los valores 1, 2 y 3. Y a este cambio de valor o estado mutable es característico de una iteración.
Existen Sentencias de Iteración o Ciclos que son estructuras de control que repiten la ejecución de un grupo de instrucciones, es una estructura de control condicional, ya que dentro de la misma se repite la ejecución de una o mas instrucciones mientras o hasta que una condición específica se cumpla.
Y algunas de ellas son:
Sentencias For
for(contador; final; incremento)
{
Codigo a Repetir;
}
donde: contador es una variable numérica.
final es el valor final para contador.
incremento es el valor que se suma o se resta al contador.
Sentencia while
while(condicion)
{
codigo a Repetir
}
Sentencia do-while
int contador = 0;
do
{
contador ++;
}
while(contador > 10);
Bueno esto es todo de mi entrada, aquí les dejo un video en donde muestran una explicación sobre la estructura de Iteración. Espero les sirva :) cualquier cosa hagánmelo saber.
Saludos :)
domingo, 7 de noviembre de 2010
*Prolog
Materia: Laboratorio de Lenguajes de Programación
Hora: Jueves v1
Hola a todos, aquí les dejo otro pequeño problema lógico que hice :)
Y el problema dice lo siguiente:
En la escuela de Laura estan vendiendo boletos para unos conciertos de Rock,Balada,Pop y Rap que va a ver en su ciudad, Laura y sus amigos quieren ir, pero todos tienen diferentes gustos de música. Entonces cada quien empezó a decir que tipo de música le gustaba. A Paco y a Alex le gusta el Pop, a Liz la Balada, a Jorge el Rock, a Luis y Brandon el Rap, a Daniela y Juan el Rock, a Laura el Pop, a Neto la Balada y a Carmen el Rock. Entonces ya con esto tenemos que resolver ¿Quién va a ir con quién al concierto ?.
Entonces basándonos en la redacción podemos deducir lo siguiente:
Entonces teniendo esto ya sabemos quienes iran juntos al concierto de cada tipo de música.
Y ahora el problema en Prolog queda así:
Bueno este fue mi problema espero les haya quedado claro cualquier comentario hagánmelo saber . Saludos :)
Hora: Jueves v1
Hola a todos, aquí les dejo otro pequeño problema lógico que hice :)
Y el problema dice lo siguiente:
En la escuela de Laura estan vendiendo boletos para unos conciertos de Rock,Balada,Pop y Rap que va a ver en su ciudad, Laura y sus amigos quieren ir, pero todos tienen diferentes gustos de música. Entonces cada quien empezó a decir que tipo de música le gustaba. A Paco y a Alex le gusta el Pop, a Liz la Balada, a Jorge el Rock, a Luis y Brandon el Rap, a Daniela y Juan el Rock, a Laura el Pop, a Neto la Balada y a Carmen el Rock. Entonces ya con esto tenemos que resolver ¿Quién va a ir con quién al concierto ?.
Entonces basándonos en la redacción podemos deducir lo siguiente:
- Les gusta el Rock a: Carmen, Jorge, Daniela, y Juan
- Les gusta el Pop a: Paco, Alex y Laura
- Les gusta la Balada a: Liz y Neto
- Les gusta el rap a: Luis y Brandon
Entonces teniendo esto ya sabemos quienes iran juntos al concierto de cada tipo de música.
Y ahora el problema en Prolog queda así:
Bueno este fue mi problema espero les haya quedado claro cualquier comentario hagánmelo saber . Saludos :)
*Prolog
Materia: Lenguajes de programación - puntos extra
Hora: Martes m1 - m3
Hola a todos, aquí les dejo otro sencillito problema lógico que implemente en Prolog.
Y el problema es el siguiente:
Un maestro de deportes necesita un alumno para una carrera, son 3 niños los que tiene en mente Eduardo, Paco y Omar. Pero necesita saber cual de ellos es más rápido, si sabemos que Paco es más lento que Eduardo pero Eduardo es más lento que Omar y éste más lento que Paco. Entonces ¿Cuál de ellos será el más rápido?.
De acuerdo con la redacción podemos sacar lo siguiente :
- Paco es más lento que Eduardo
- Eduardo es más lento que Omar
- Omar es más lento que Paco
Entonces con esto nosotros ya podemos deducir que Paco es el más rápido.
Ahora se los mostrare en Prolog:
Hora: Martes m1 - m3
Hola a todos, aquí les dejo otro sencillito problema lógico que implemente en Prolog.
Y el problema es el siguiente:
Un maestro de deportes necesita un alumno para una carrera, son 3 niños los que tiene en mente Eduardo, Paco y Omar. Pero necesita saber cual de ellos es más rápido, si sabemos que Paco es más lento que Eduardo pero Eduardo es más lento que Omar y éste más lento que Paco. Entonces ¿Cuál de ellos será el más rápido?.
De acuerdo con la redacción podemos sacar lo siguiente :
- Paco es más lento que Eduardo
- Eduardo es más lento que Omar
- Omar es más lento que Paco
Entonces con esto nosotros ya podemos deducir que Paco es el más rápido.
Ahora se los mostrare en Prolog:
Entonces como ven en Prolog también resultó que Paco es el más rapido.
Este fue mi problema espero les haya quedado claro cualquier comentario hagánmelo saber. Saludos :)
*Arreglos
Materia: Lenguajes de Programación - puntos extra
Hora: Martes m1 - m3
Hola a todos aquí les dejo una pequeña entrada sobre Arreglos :)
Un vector o arreglo unidimensional consta de n elementos que pueden representarse como:
Al número de elementos de un vector se le denomina rango del vector. Los vectores se almacenan en la memoria central del computador en un orden adyacente de posiciones de memoria sucesivas. Cada elemento de un vector se puede procesar como si fuera una variable simple que ocupa una posición de memoria dada, de manera tal que cada elemento del vector es accesible directamente.
Por ejemplo: el vector X[6] está compuesto por seis elementos. Su identificador (nombre del vector) es X y cada elemento se individualiza por su subíndice.
Para definir un arreglo se utilizan las variables char, int y float. Y la deficinión de un arreglo se realiza de la siguiente manera:nombre_variable[longitud];. Con esto vemos que nombre_variable es un arreglo de cierta longitud de elementos del tipo , hay que recordar que longitud debe ser cualquier expresión entera constante mayor que cero.
La asignación de un arreglo quedaría de la siguiente manera:
nombre_variable[índice] = expresión del tipo. Esta instrucción asigna el valor asociado de la expresión a la posición índice del arreglo nombre_variable. El índice debe ser una expresión del tipo entero en el rango [0, longitud-1].
Los arreglos se clasifican de acuerdo con el número de dimensiones que tienen. Y son:
- Unidimensionales (vectores)
- Bidimensionales (tablas o matrices)
- Multidimensionales (tres o más dimensiones)
Bueno esto es todo de mi entrada, espero les sea útil. Saludos :)
Hora: Martes m1 - m3
Hola a todos aquí les dejo una pequeña entrada sobre Arreglos :)
Un arreglo es un conjunto finito y ordenado de elementos homogéneos. Cuando decimos que está ordenado significa que el primer elemento, el segundo, el tercero,..., el enésimo puede ser identificado. La homogeneidad implica que todos los elementos del arreglo son datos del mismo tipo.
Un vector o arreglo unidimensional consta de n elementos que pueden representarse como:
Al número de elementos de un vector se le denomina rango del vector. Los vectores se almacenan en la memoria central del computador en un orden adyacente de posiciones de memoria sucesivas. Cada elemento de un vector se puede procesar como si fuera una variable simple que ocupa una posición de memoria dada, de manera tal que cada elemento del vector es accesible directamente.
Por ejemplo: el vector X[6] está compuesto por seis elementos. Su identificador (nombre del vector) es X y cada elemento se individualiza por su subíndice.
Para definir un arreglo se utilizan las variables char, int y float. Y la deficinión de un arreglo se realiza de la siguiente manera:
La asignación de un arreglo quedaría de la siguiente manera:
nombre_variable[índice] = expresión del tipo
Los arreglos se clasifican de acuerdo con el número de dimensiones que tienen. Y son:
- Unidimensionales (vectores)
- Bidimensionales (tablas o matrices)
- Multidimensionales (tres o más dimensiones)
Arreglo Unidimensional
Arreglo Bidimensionales
Arreglo Multidimensional
Bueno esto es todo de mi entrada, espero les sea útil. Saludos :)
*Tablas de dispersión
Materia: Laboratorio de lenguajes de programación
Hora: Jueves V1
Hola a todos, aquí les dejo mi entrada sobre Tablas de Dispersión :)
Las tablas de dispersión o también llamadas hashing tables son una técnica que se utiliza para realizar inserciones, eliminaciones y búsquedas en un tiempo constante.
La estructura de datos ideal para la tabla de dispersión es un arreglo de tamaño fijo que contiene una clave que son los elementos de tabla, una clave es una cadena de caracteres con un valor asociado. Por ejemplo: Si el tamaño de la tabla es MAX_T, la tabla se declara entre 0 y MAX_T-1, a cada clave se le asignará un número entre 0 y MAX_T-1 y se colocará en la celda que le corresponde.
La relación entre la llave y la posición en la tabla es lo que se llama función de dispersión.
La función de las tablas de dispersión es la correspondencia entre la clave y un índice del arreglo.
Cuando las claves son números enteros la función de dispersión toma la forma:
h(x) = clave MOD MAX_T
Existen 2 tipos de dispersiones, la dispersión abierta y cerrada, las cuales se utilizan para solucionar colisiones, que es cuando dos elementos distintos toman el mismo valor.
*Dispersión abierta
Es también llamada encadenamiento separado y consiste en tener una lista de los elementos que se dispersan en el mismo valor de la tabla. Por ejemplo si tenemos una tabla de tamaño 10 de números enteros y con la función de dispersión: dispersión(x) = x MOD 10, nos quedaría una tabla de dispersión abierta de la siguiente manera:
Por ejemplo las declaraciones para esta dispersión abierta quedarian de la siguiente manera:
TYPEPROCEDURE IniciaTabla (VAR D: TablaDisp);
posicion =POINTER TO nodo;
nodo = RECORD
elem : TipoElemento;
sig : posicion;
END;
TablaDisp = ARRAY INDICE OF posicion;
Primero debemos iniciar la tabla asignando a cada celda el valor NILL:
VAR
i : integer;
BEGIN
FOR i:=0 TO MAX_T-1 DO
D[i]:= NIL;
END;
Para realizar una búsqueda en una tabla, primero se utiliza la función de dispersión para determinar la lista a recorrer. Y ya cuando se recorre la lista hasta encontrar la clave y se devuelve un puntero a la posición de la celda que contiene la clave.
FUNCTION Buscar (llave: TipoElemento; D: TablaDisp): posicion;
VAR
res, p: posicion;
BEGIN
p := D[hashing(llave)];
res:= NIL;
WHILE p <> NIL DO
IF p^.elemento = llave THEN BEGIN
res:= p; BREAK;
END;
p := p^.sig;
END;
Buscar:= res;
END;
Para insertar un elemento en una tabla, primero buscamos en la lista que le corresponde para ver si ya está insertado; si es nuevo, se inserta al principio de la lista:
PROCEDURE Insertar (llave:TipoElemento; VAR D: TablaDisp);
VAR
h: INTEGER;
pos, lista : posicion;
nuevo : posicion;
BEGIN
pos := Buscar (llave, D);
IF pos = NIL THEN BEGIN (* no encontrado *)
h:= hashing(llave);
NEW (nuevo);
nuevo^.elem := llave;
nuevo^.sig := D[h];
D[h]:= nuevo;
END;
END;
Se le llama factor de carga de una tabla de dispersión, λ, a la razón entre el número de elementos en la tabla y el tamaño de la misma:
La longitud media de una lista es λ. El tiempo que se tarda en realizar una búsqueda será el tiempo en que se cálcula la función de dispersión más el tiempo necesario para recorrer la lista, si la búsqueda es infructuosa, el número medio de enlaces por recorrer es λ, pero si la búsqueda tiene éxito los enlaces por recorrer son, por término medio, 1 + λ /2.
No debemos olvidar que el tamaño de la tabla debe ser
*Dispersión cerrada
La dispersión cerrada o direccionamiento abierto, soluciona las colisiones buscando celdas alternativas hasta encontrar una vacía.
Se va buscando en las celdas: d0(x), d1(x), d2(x), ..., donde
di(x) = (hashing(x) + f(i)) MOD MAX_T.
La función f( ) es la estrategia de resolución de las colisiones, y se debe cumplir que:
f(i)= { 0 si i=0
< >0 si i<>0
Dentro de la dispersión cerrada hay tres estrategias distintas: la exploración lineal, la exploración cuadrática y la dispersión doble.
Exploración lineal
En este tipo de estrategia la función f() es una función lineal de i, por ejemplo: f(i) = i. Esto significa que las celdas se recorren en secuencia buscando una celda vacía; es decir, si hay una colisión se prueba en la celda siguiente y así sucesivamente hasta encontrar una vacía.
Lo veremos en un ejemplo: tenemos una tabla con MAX_T = 10 y la función de dispersión h(x)= x MOD 10. En este ejemplo, la primera colisión ocurre cuando queremos insertar el 49. Como la celda 9 está ocupada se pone en la siguiente celda desocupada. Cuando el 58 entra en colisión con el 18 va a la siguiente celda y entra en colisión con el 89, y después con el 49 antes de encontrar su posición. Con el 69 pasa algo parecido.
Algunas de las desventajas que tiene este método son: el tiempo que se tarda en encontrar una celda vacía y la formación de bloques de celdas ocupadas, llamada efecto agrupamiento primario. Para inserciones y búsquedas no exitosas el número de intentos aproximado sería: 1/2(1 + 1/(1 - λ)2). Mientras que para búsquedas exitosas sería: 1/2(1 + 1/(1 - λ)), un número menor que el anterior.
Exploración cuadrática
Este método elimina el problema del agrupamiento primario, la función de colisiones cuadrática:
f(i) = i2.
Si se usa la exploración cuadrática, y el tamaño de la tabla es primo, entonces siempre se puede insertar un elemento nuevo si la tabla está, al menos, medio vacía.
Aunque la exploración cuadrática elimina el agrupamiento primario, se produce otro fenómeno llamado agrupamiento secundario, ya que las claves que se dispersan a la misma posición intentarán las mismas celdas.
_
*Dispersión doble
La función para la dispersión doble es: f (i) = i * h2 (x). Lo que se hace es aplicar una segunda función de dispersión a x, y luego se prueba a distancias h2(x), 2h2(x), ...
Es muy importante la buena elección de h2(x) y, además, nunca debe ser cero. Si elegimos la función:
h2(x) = R - (x MOD R) con R un número primo menor que MAX_T, funcionará bien.
La siguiente tabla aparece como quedaría la dispersión cerrada con dispersión doble y cuando insertamos las mismas claves que en los ejemplos anteriores y para R = 7.
Las declaraciones de los tipos para implantar la dispersión cerrada son las siguientes:
TYPE
ClaseEntrada = (legal, vacia, eliminada);
Entrada_disp = RECORD
elem : TipoElemento;
info : ClaseEntrada;
END;
posicion = INDICE;
TablaDisp = ARRAY [INDICE] OF Entrada_disp;
La puesta a valores iniciales de la tabla se realiza poniendo el campo info a vacío.
PROCEDURE IniciarTabla (VAR D: TablaDisp);
VAR
i: integer;
BEGIN
FOR i:=0 TO MAX_T-1 DO
D[i].info := vacia;
END;
La búsqueda para dispersión cerrada con exploración cuadrática devolverá la posición de la llave en la tabla de dispersión. Si no se encuentra, devuelve la celda donde estaría insertada la llave, que estará marcada como vacía. Y quedaría algo asi :
FUNCTION Buscar (llave: TipoElemento; D:TablaDisp): INDICE;
VAR
i, pos : posicion;
BEGIN
i := 0;
pos := hashing (llave);
WHILE D[pos].info <> vacia DO BEGIN
IF D[pos].elem = llave THEN (* encontrado *)
BREAK;
END;
INC (i);
pos := (pos + 2 * i - 1);
IF pos > MAX_T THEN
pos := pos - MAX_T;
END;
Buscar:= pos;
END;
Aquí se utiliza la forma rápida de hacer la resolución cuadrática. Siendo la definición de la función cuadrática: f(i) = f(i-1) + 2i - 1, se deduce que se puede implementar con una multiplicación por dos y un decremento. Si la posición resultante se sale del array, se le resta el tamaño de la tabla.
Por otro lado, es trivial modificar esta función para que reaproveche huecos eliminados en caso de no encontrar el elemento:
FUNCTION BuscarMejor (llave: TipoElemento; D:TablaDisp): INDICE;
VAR
i, pos, hueco : posicion;
BEGIN
i := 0;
hueco := -1; (* todavia no hay hueco *)
pos := hashing (llave);
WHILE D[pos].info <> vacia DO BEGIN
IF D[pos].info = eliminada THEN BEGIN (* hay hueco *)
hueco := pos; (* no acabamos porque quizá "llave" este más adelante *)
END;
IF D[pos].elem = llave THEN (* encontrado *)
BREAK;
END;
INC (i);
pos := (pos + 2 * i - 1);
IF pos > MAX_T THEN
pos := pos - MAX_T;
END;
Buscar:= pos;
END;
En el caso de la inserción de tablas en la dispersión cerrada, cuando la clave está ya en la tabla no se hace nada; si no, se coloca en la posición que resulte de la rutina buscar:
PROCEDURE Insertar (llave: TipoElemento; VAR D: TablaDisp);
VAR
p; pos: INDICE;
BEGIN
pos := Buscar (llave, D);
IF D[pos].info <> legal THEN BEGIN (* celda apropiada para insertar *)
D[pos].elem := llave;
D[pos].info := legal;
END;
END;
Bueno está fue mi entrada sobre Tablas de Dispersión, espero les sea útil cualquier comentario hagánmelo saber. Saludos :) primo.
Hora: Jueves V1
Hola a todos, aquí les dejo mi entrada sobre Tablas de Dispersión :)
Las tablas de dispersión o también llamadas hashing tables son una técnica que se utiliza para realizar inserciones, eliminaciones y búsquedas en un tiempo constante.
La estructura de datos ideal para la tabla de dispersión es un arreglo de tamaño fijo que contiene una clave que son los elementos de tabla, una clave es una cadena de caracteres con un valor asociado. Por ejemplo: Si el tamaño de la tabla es MAX_T, la tabla se declara entre 0 y MAX_T-1, a cada clave se le asignará un número entre 0 y MAX_T-1 y se colocará en la celda que le corresponde.
La relación entre la llave y la posición en la tabla es lo que se llama función de dispersión.
La función de las tablas de dispersión es la correspondencia entre la clave y un índice del arreglo.
Cuando las claves son números enteros la función de dispersión toma la forma:
h(x) = clave MOD MAX_T
Existen 2 tipos de dispersiones, la dispersión abierta y cerrada, las cuales se utilizan para solucionar colisiones, que es cuando dos elementos distintos toman el mismo valor.
*Dispersión abierta
Es también llamada encadenamiento separado y consiste en tener una lista de los elementos que se dispersan en el mismo valor de la tabla. Por ejemplo si tenemos una tabla de tamaño 10 de números enteros y con la función de dispersión: dispersión(x) = x MOD 10, nos quedaría una tabla de dispersión abierta de la siguiente manera:
Por ejemplo las declaraciones para esta dispersión abierta quedarian de la siguiente manera:
TYPEPROCEDURE IniciaTabla (VAR D: TablaDisp);
posicion =POINTER TO nodo;
nodo = RECORD
elem : TipoElemento;
sig : posicion;
END;
TablaDisp = ARRAY INDICE OF posicion;
Primero debemos iniciar la tabla asignando a cada celda el valor NILL:
VAR
i : integer;
BEGIN
FOR i:=0 TO MAX_T-1 DO
D[i]:= NIL;
END;
Para realizar una búsqueda en una tabla, primero se utiliza la función de dispersión para determinar la lista a recorrer. Y ya cuando se recorre la lista hasta encontrar la clave y se devuelve un puntero a la posición de la celda que contiene la clave.
FUNCTION Buscar (llave: TipoElemento; D: TablaDisp): posicion;
VAR
res, p: posicion;
BEGIN
p := D[hashing(llave)];
res:= NIL;
WHILE p <> NIL DO
IF p^.elemento = llave THEN BEGIN
res:= p; BREAK;
END;
p := p^.sig;
END;
Buscar:= res;
END;
Para insertar un elemento en una tabla, primero buscamos en la lista que le corresponde para ver si ya está insertado; si es nuevo, se inserta al principio de la lista:
PROCEDURE Insertar (llave:TipoElemento; VAR D: TablaDisp);
VAR
h: INTEGER;
pos, lista : posicion;
nuevo : posicion;
BEGIN
pos := Buscar (llave, D);
IF pos = NIL THEN BEGIN (* no encontrado *)
h:= hashing(llave);
NEW (nuevo);
nuevo^.elem := llave;
nuevo^.sig := D[h];
D[h]:= nuevo;
END;
END;
Se le llama factor de carga de una tabla de dispersión, λ, a la razón entre el número de elementos en la tabla y el tamaño de la misma:
La longitud media de una lista es λ. El tiempo que se tarda en realizar una búsqueda será el tiempo en que se cálcula la función de dispersión más el tiempo necesario para recorrer la lista, si la búsqueda es infructuosa, el número medio de enlaces por recorrer es λ, pero si la búsqueda tiene éxito los enlaces por recorrer son, por término medio, 1 + λ /2.
No debemos olvidar que el tamaño de la tabla debe ser
*Dispersión cerrada
La dispersión cerrada o direccionamiento abierto, soluciona las colisiones buscando celdas alternativas hasta encontrar una vacía.
Se va buscando en las celdas: d0(x), d1(x), d2(x), ..., donde
di(x) = (hashing(x) + f(i)) MOD MAX_T.
La función f( ) es la estrategia de resolución de las colisiones, y se debe cumplir que:
f(i)= { 0 si i=0
< >0 si i<>0
Dentro de la dispersión cerrada hay tres estrategias distintas: la exploración lineal, la exploración cuadrática y la dispersión doble.
Exploración lineal
En este tipo de estrategia la función f() es una función lineal de i, por ejemplo: f(i) = i. Esto significa que las celdas se recorren en secuencia buscando una celda vacía; es decir, si hay una colisión se prueba en la celda siguiente y así sucesivamente hasta encontrar una vacía.
Lo veremos en un ejemplo: tenemos una tabla con MAX_T = 10 y la función de dispersión h(x)= x MOD 10. En este ejemplo, la primera colisión ocurre cuando queremos insertar el 49. Como la celda 9 está ocupada se pone en la siguiente celda desocupada. Cuando el 58 entra en colisión con el 18 va a la siguiente celda y entra en colisión con el 89, y después con el 49 antes de encontrar su posición. Con el 69 pasa algo parecido.
Algunas de las desventajas que tiene este método son: el tiempo que se tarda en encontrar una celda vacía y la formación de bloques de celdas ocupadas, llamada efecto agrupamiento primario. Para inserciones y búsquedas no exitosas el número de intentos aproximado sería: 1/2(1 + 1/(1 - λ)2). Mientras que para búsquedas exitosas sería: 1/2(1 + 1/(1 - λ)), un número menor que el anterior.
Exploración cuadrática
Este método elimina el problema del agrupamiento primario, la función de colisiones cuadrática:
f(i) = i2.
En este caso, cuando el 49 entra en colisión con el 89, la siguiente posición es la celda siguiente
(f(1) = 12 = 1). Después, cuando el 58 entra en colisión también intenta la celda siguiente, pero está ocupada. En su segunda colisión, el 58 intenta la celda que está 4 posiciones más allá ( 22 = 4), y como está libre se coloca en ella (en la celda 2). Con el 69 ocurre lo mismo.
Con este tipo de método no hay garantía de encontrar una celda vacía si la tabla se llena a más de la mitad, o si el tamaño de la tabla no es primo.
Aunque la exploración cuadrática elimina el agrupamiento primario, se produce otro fenómeno llamado agrupamiento secundario, ya que las claves que se dispersan a la misma posición intentarán las mismas celdas.
_
*Dispersión doble
La función para la dispersión doble es: f (i) = i * h2 (x). Lo que se hace es aplicar una segunda función de dispersión a x, y luego se prueba a distancias h2(x), 2h2(x), ...
Es muy importante la buena elección de h2(x) y, además, nunca debe ser cero. Si elegimos la función:
h2(x) = R - (x MOD R) con R un número primo menor que MAX_T, funcionará bien.
La siguiente tabla aparece como quedaría la dispersión cerrada con dispersión doble y cuando insertamos las mismas claves que en los ejemplos anteriores y para R = 7.
En este caso la primera colisión ocurre al insertar el 49; calculando la función de dispersión nos quedaría: h2(49) = 7 - (49 MOD7), que es igual a: h2(49) = 7 - 0 = 7; luego el 49 se insertará en la posición 6. La segunda colisión ocurrirá al insertar el 58, la función será: h2(58) = 7 - 2 = 5, por lo tanto el 58 se colocará en la posición 3. Finalmente intentamos insertar el 69, que con la función de dispersión iría en la posición: h2(69) = 7 - 6 = 1, por lo que la celda resultante es la cero.
Las declaraciones de los tipos para implantar la dispersión cerrada son las siguientes:
TYPE
ClaseEntrada = (legal, vacia, eliminada);
Entrada_disp = RECORD
elem : TipoElemento;
info : ClaseEntrada;
END;
posicion = INDICE;
TablaDisp = ARRAY [INDICE] OF Entrada_disp;
La puesta a valores iniciales de la tabla se realiza poniendo el campo info a vacío.
PROCEDURE IniciarTabla (VAR D: TablaDisp);
VAR
i: integer;
BEGIN
FOR i:=0 TO MAX_T-1 DO
D[i].info := vacia;
END;
La búsqueda para dispersión cerrada con exploración cuadrática devolverá la posición de la llave en la tabla de dispersión. Si no se encuentra, devuelve la celda donde estaría insertada la llave, que estará marcada como vacía. Y quedaría algo asi :
FUNCTION Buscar (llave: TipoElemento; D:TablaDisp): INDICE;
VAR
i, pos : posicion;
BEGIN
i := 0;
pos := hashing (llave);
WHILE D[pos].info <> vacia DO BEGIN
IF D[pos].elem = llave THEN (* encontrado *)
BREAK;
END;
INC (i);
pos := (pos + 2 * i - 1);
IF pos > MAX_T THEN
pos := pos - MAX_T;
END;
Buscar:= pos;
END;
Aquí se utiliza la forma rápida de hacer la resolución cuadrática. Siendo la definición de la función cuadrática: f(i) = f(i-1) + 2i - 1, se deduce que se puede implementar con una multiplicación por dos y un decremento. Si la posición resultante se sale del array, se le resta el tamaño de la tabla.
Por otro lado, es trivial modificar esta función para que reaproveche huecos eliminados en caso de no encontrar el elemento:
FUNCTION BuscarMejor (llave: TipoElemento; D:TablaDisp): INDICE;
VAR
i, pos, hueco : posicion;
BEGIN
i := 0;
hueco := -1; (* todavia no hay hueco *)
pos := hashing (llave);
WHILE D[pos].info <> vacia DO BEGIN
IF D[pos].info = eliminada THEN BEGIN (* hay hueco *)
hueco := pos; (* no acabamos porque quizá "llave" este más adelante *)
END;
IF D[pos].elem = llave THEN (* encontrado *)
BREAK;
END;
INC (i);
pos := (pos + 2 * i - 1);
IF pos > MAX_T THEN
pos := pos - MAX_T;
END;
Buscar:= pos;
END;
En el caso de la inserción de tablas en la dispersión cerrada, cuando la clave está ya en la tabla no se hace nada; si no, se coloca en la posición que resulte de la rutina buscar:
PROCEDURE Insertar (llave: TipoElemento; VAR D: TablaDisp);
VAR
p; pos: INDICE;
BEGIN
pos := Buscar (llave, D);
IF D[pos].info <> legal THEN BEGIN (* celda apropiada para insertar *)
D[pos].elem := llave;
D[pos].info := legal;
END;
END;
Bueno está fue mi entrada sobre Tablas de Dispersión, espero les sea útil cualquier comentario hagánmelo saber. Saludos :) primo.
Suscribirse a:
Entradas (Atom)