Apuntes algebra

EDA
Apuntes
UNED
Curso 2000 – 2001

©José Manuel Carrillo

Nota:
Los apuntes que tienes ahora en tus manos son los que he confeccionado para el
estudio de la asignatura durante el curso 2000-2001. Son resúmenes de los temas de
las Unidades Didácticas. He omitido aquellas partes del temario que, bien por su
complejidad, bien porque no he visto que en los exámenes anteriores que hetenido en
mis manos se preguntara nada sobre los mismos, he considerado que no valía la pena
estudiar. Por supuesto esta es una valoración completamente subjetiva y en algunas
cuestiones probablemente muy equivocada. Por eso quiero advertirte de tal extremo.
Por otra parte he procurado en todo momento ser fiel en la transcripción, no obstante
en algunos temas puntuales hay razonamientos propios yligeras modificaciones
respecto al texto base. En todos estos casos lo he mencionado convenientemente.
Espero que te sirvan de ayuda.
Un saludo, José Manuel.

Introducción y conceptos fundamentales / 1

1.- INTRODUCCIÓN Y CONCEPTOS FUNDAMENTALES

1.1.- Estructuras de datos y tipos de datos abstractos (TDA)
Un tipo de datos es una colección de valores
Un tipo de datos abstracto (TDA)es un tipo de datos definido de forma única mediante un tipo y
un conjunto dado de operaciones definidas sobre el tipo.
Una estructura de datos es la implementación física de un tipo de datos abstracto.
Debido al proceso de abstracción, el diseño deberá realizarse siguiendo tres pasos
fundamentales:
1.- Análisis de datos y operaciones
2.- Elección del Tipo de Datos Abstracto
3.- Elección dela implementación

1.2.- Tipos de datos básicos
TDA Entero : tiene como tipo el conjunto de números enteros, y como operaciones la suma,
resta, multiplicación y división entera
TDA Real: tiene como tipo el conjunto de números reales y como operaciones la suma, resta
multiplicación y división
TDA Booleano : tiene como tipo el conjunto de valores booleanos True, False y como
operaciones lasdefinidas en el álgebra de Boole (AND, OR, NOT)
TDA Carácter: tiene como tipo el conjunto de caracteres definido por un alfabeto dado y como
operaciones todos los operadores relacionales (, =, >=,

102

102
252
74
34

75

Clasificación en Memoria Secundaria / 9

3.3.2.- Manejo de desbordamiento o sobrecarga
Cuando se ha de insertar una nueva llave, si la celda que le correspondeestá ocupada se produce
una colisión y si todo el bloque está lleno, se ha producido un desbordamiento o sobrecarga.
El método de manejo de sobrecargas más evidente es la exploración lineal. Consiste en buscar
en el bloque siguiente. Se distinguen dos acciones: inserción y búsqueda. Para la inserción se
busca en el bloque siguiente una celda libre, si vuelve a producirse sobrecarga se busca enel
siguiente y así sucesivamente. Para la búsqueda de una llave se busca en la dirección siguiente y
así sucesivamente hasta encontrar la llave, o encontrar que la celda del bloque está vacía o la
tabla está llena.
En general la exploración puede expresarse como: dirección = f(x) + g(x); conde f(x) es la
función de dispersión y g(x) es la función de tratamiento de sobrecargas. Considerandola tabla
circular, la dirección vendrá dada por: dirección = (f(x) + g(x)) mod TamañoTabla
En el caso de exploración lineal:

g(x) = i , i = 1 ... TamañoTabla

La exploración lineal tiende a colocar las llaves poco uniformemente de manera que las
sobrecargas producidas irán llenando los bloques cercanos a los ocupados.
Una técnica que mejora este comportamiento es la exploración cuadrática,definida por:
g(x) = i2 , i = 1 … TamañoTabla
Con esta función de exploración la búsqueda se realiza examinando los bloques:
f(x) ,

(f(x) + i2 ) mod TamañoTabla ,

(f(x) – i2 ) mod TamañoTabla,

con 1 ≤ i ≤ (TamañoTabla-1) / 2
Cuando TamañoTabla es un número primo de la forma 4j+3, j entero, la exploración cuadrática
puede recorrer todos los bloques de la tabla.
La técnica de...