Flashcards
Untitled
Cards in this deck (24)
- 1Tabla de símbolosLa tabla de símbolos es la componente del compilador que se encarga de todos los aspectos dependientes del contexto relacionados con las restricciones impuestas a los nombres que puedan
aparecer en los programas.
Estas restricciones obligan a llevar la cuenta, durante todo el proceso de la compilación, de los
nombres utilizados, para poder realizar las comprobaciones e imponer las restricciones
necesarias - 2Complejidad de los algoritmosLa complejidad de los algoritmos se puede estudiar estimando la dependencia entre el tiempo que necesitan para procesar su entrada y el tamaño de ésta. El mejor rendimiento se
obtiene si ambos son independientes: el tiempo es constante. En orden decreciente de eficiencia,
otros algoritmos presentan dependencia logarítmica, polinómica (lineal, cuadrática, etc.) o exponencial. - 3Búsqueda LinealLa búsqueda lineal supone que los datos entre los que puede estar el buscado se guardan en una
lista o vector, no necesariamente ordenados. El algoritmo (2.1) recorre la estructura desde la primera posición, comparando (comparación de clave) cada uno de los elementos que encuentra con el buscado.
Termina por una de las dos situaciones siguientes: o se llega al final de la estructura o se encuentra el dato buscado. En la primera situación, el dato no se ha encontrado y el algoritmo no
termina con éxito.
- 4Búsqueda BinariaLa búsqueda binaria supone que los datos, entre los que puede estar el buscado, se guardan en
una lista o vector ordenados.
El algoritmo (2.2) aprovecha el orden propio de la estructura para descartar, en
cada iteración, la mitad de la tabla donde, con seguridad, no se encuentra el dato buscado. En la siguiente iteración sólo queda por estudiar la otra mitad, en la que sí puede encontrarse. Para ello se compara el elemento buscado con el que ocupa la posición central de la estructura (comparación de clave).
- 5Búsqueda con árboles AVLLos árboles de Adelson-Velskii y Landis (AVL) son un subconjunto de los árboles binarios ordenados. Un árbol binario ordenado es un árbol AVL si y sólo si las profundidades de los hijos de
cualquier nodo no difieren en más de una unidad. Por tanto, aunque pueda haber muchos árboles
AVL para el mismo conjunto de datos, se tiene la garantía de que la profundidad es siempre más
o menos la del árbol binario menos profundo posible. - 6Estructura de datos y operacionesLa teoría de estructuras de datos define el diccionario como una colección ordenada de información organizada de forma que una parte de ella se considera su clave. La clave se utiliza para
localizar la información en el diccionario, de la misma manera en que, en un diccionario de la
lengua, las palabras se utilizan como clave para encontrar su significado. - 7Implementación con vectores ordenadosCuando las claves del diccionario se almacenan en un vector ordenado, la operación de búsqueda puede realizarse con el algoritmo de búsqueda binaria descrito en secciones anteriores. Tanto
su tiempo medio como su tiempo peor suponen un rendimiento aceptable.
- 8InserciónLa inserción de la clave k en el árbol binario ordenado T comienza con su búsqueda. Si suponemos que el algoritmo de búsqueda devuelve un puntero al nodo padre donde debería insertarse el
nuevo elemento, lo único que quedaría por hacer es crear un nodo nuevo y asignarlo como hijo izquierdo (derecho) al retorno de la búsqueda, si k es anterior (posterior) a la clave del árbol.
- 9BorradoEl borrado de la clave k del árbol binario ordenado T presenta la dificultad de asegurar que el árbol sigue ordenado tras eliminar el nodo que contiene a k. La disposición de los nodos en estos
árboles permite, sin embargo, simplificar el proceso gracias a los dos resultados siguientes:
1. Para cualquier árbol binario ordenado T y cualquier nodo b del
mismo, se pueden demostrar afirmaciones relacionadas con el nodo b’,
que contiene el antecesor inmediato del nodo b en el árbol.
2. Se puede demostrar que, para cualquier árbol binario ordenado T
y cualquier nodo b del mismo, el árbol T’ construido mediante el siguiente proceso corresponde al resultado de eliminar el nodo b de T. - 10Tablas HashUna tabla hash es un tipo de datos que consta de un vector (para almacenar los datos) y una función (hash o de dispersión, que es su significado en inglés), que garantiza (idealmente) que a cada dato se le asocie una posición única en el vector. La tabla hash se usa de la
siguiente manera:
• Se elige una parte de los datos para considerarla clave de los mismos (por ejemplo, si se
está almacenando información sobre personas, la clave podría ser su DNI).
• Se diseña una función hash que asocie (idealmente) a cada valor de la clave una posición
única en el vector.
• Cuando se desea localizar un dato en el vector (ya sea para añadirlo a la tabla, para recuperarlo o para eliminarlo) se aplica a su clave la función hash, que proporciona el índice en
el vector que corresponde al dato. - 11Funciones hashSe usará la siguiente notación para las funciones hash: sea K el conjunto de claves, sean 11 y m
respectivamente las posiciones mínima y máxima de la tabla, y sea N el conjunto de los números
naturales. Cualquier función hash h se define de la siguiente forma:
h:K → [ 1, m] - 12Funciones hash inyectivasLo ideal es que h fuese al menos inyectiva, ya que de esta forma se garantiza que a dos claves
distintas les corresponden siempre posiciones distintas del vector.
Lo que se pierde al no obligar a h a ser biyectiva es que no se garantiza que se ocupen todas
las posiciones del vector. En la práctica, es muy difícil diseñar funciones hash inyectivas, por lo
que hay que conformarse con funciones no inyectivas razonablemente buenas.
La no inyectividad causa un problema importante: las colisiones. Se llama colisión a la situación en la que h asigna la misma posición en el vector a dos o más claves distintas. - 13Funciones hash pseudoaleatoriasEl siguiente mecanismo para la inserción de la clave k, que recibe el nombre de aleatorio o pseudoaleatorio, permitiría alcanzar este objetivo:
1. Se tira un dado con m caras.
2. Se anota el valor de la cara superior (i).
3. Se toma i como el valor hash para la clave k: h(k)=i.
3. Se accede a la posición i de la tabla y se le asigna la información de la clave k.
Resulta claro que este esquema no es válido para implementar las tablas hash, ya que el mecanismo de recuperación de la información asociada a la clave k’ tendría los siguientes pasos:
1. Se tira un dado con m caras.
2. Se anota el valor de la cara superior (j)
3. Se define j como el valor hash para la clave k: h(k)=j.
4. Se accede a la posición j de la tabla y se recupera la información almacenada en ella. - 14Funciones hash uniformesSe pedirá a las funciones hash que sean relativamente uniformes, es decir, que distribuyan las claves de manera uniforme por la tabla, sin que queden muchas posiciones libres cuando comiencen
a aparecer colisiones. En este contexto, resulta esencial encontrar un mecanismo que genere elementos de un subconjunto de los números naturales [1,m] sin repeticiones. El álgebra y la teoría de números definen la operación módulo para el cálculo del resto de la división entre dos
números enteros, los grupos cíclicos, su estructura y las condiciones para su existencia. Estos resultados, que quedan fuera del ámbito de este libro, pueden utilizarse para definir funciones hash
relativamente uniformes. Pueden ser de multiplicación y de división. - 15Factor de cargaUn concepto muy importante en el estudio de la eficiencia es el factor de carga. Dada una tabla
hash con espacio para m claves, en la que ya se han insertado n, se llama factor de carga y se representa mediante la letra λ, al cociente entre n y m.
λ = n/m - 16Hash con direccionamiento abiertoEsta técnica recibe su nombre del hecho de que la posición final que se asigna a una clave no está
totalmente determinada por la función hash. Lo más característico de este método es que las colisiones se solucionan dentro del mismo espacio utilizado por la tabla, es decir, no se usa ninguna estructura de datos auxiliar para ello. De aquí se deduce la necesidad de que haya siempre
posiciones libres en la tabla, es decir, que el tamaño reservado para ella sea siempre mayor que
el número de claves que se va a insertar. - 17Sondeo linealEl sondeo lineal busca sitio en las posiciones siguientes, en la misma secuencia en que están en la
tabla. Si se supone que posición=h(k) y que no está libre, el sondeo lineal mirará en la secuencia de posiciones {posición+1, posición+2, ...} = {posición+i}1≤i≤m-posición.
Por lo tanto, todas las claves que colisionen estarán agrupadas en posiciones contiguas a la que les
asigna la función hash. (2.16)
- 18Sondeo multiplicativoEl sondeo multiplicativo intenta superar el inconveniente que suponen las bandas de claves que
colisionan en la tabla hash. Para ello se articula un mecanismo poco costoso para dispersar los
reintentos por la tabla, impidiendo la formación de bandas al espaciarlos uniformemente.
Intuitivamente, se usa como incremento el valor devuelvo por la función hash, de forma que, en
el primer reintento, se saltan h(k) posiciones; en el segundo, 2*h(k) posiciones, etc:
int delta(int numero_reintento, indice posicion_inicial)
{
return (posicion_inicial*numero_reintento);
} - 19Otros sondeosUna variante es el sondeo cuadrático, que generaliza el
sondeo multiplicativo de la siguiente manera: el sondeo multiplicativo realmente evalúa una función lineal, f(x)=posición_inicial*x (donde x es el número de reintentos). El sondeo
cuadrático utiliza un polinomio de segundo grado g(x)=a*x2+b*x+c, en el que hay que determinar las constantes a, b y c:
int delta(int numero_reintento)
{
return (a*numero_reintento2+b*numero_reintento+c);
} - 20Hash con encadenamientoEsta técnica se diferencia de la anterior en el uso de listas para contener las claves que colisionan
en la misma posición de la tabla hash. De esta forma, la tabla está formada por un vector de listas de claves. La función hash proporciona acceso a la lista en la que se encuentran todas las claves a las que les corresponde el mismo valor de función hash. (2.21)
- 21Lenguajes con estructuras de bloquesLos lenguajes de programación con estructura de bloques tienen mecanismos para definir el alcance de los nombres e identificadores (las secciones del código donde estarán definidos). Es decir, en los lenguajes de programación con estructura de bloques, en cada bloque sólo están
definidos algunos identificadores. Los bloques más frecuentes son las subrutinas (funciones o
procedimientos), aunque también hay lenguajes de programación que permiten definir bloques
que no corresponden a subrutinas.
- 22Compiladores de un pasoLos ámbitos no se consultan una vez que se cierran, por
lo que pueden descartarse sus tablas hash. En esta circunstancia, se puede utilizar una pila de ámbitos abiertos. Esta estructura de datos devuelve primero los elementos insertados en ella más recientemente, por lo que se mantiene automáticamente el orden de apertura de los
- 23Compiladores de más de un pasoUn esquema fácil de describir consiste en modificar la pila del apartado anterior para convertirla en una lista, que conserve juntas, por encima de los ámbitos abiertos, las tablas hash de los
ámbitos cerrados. De esta manera, el ámbito actual estará siempre por debajo de los cerrados. Por
debajo de él, se encontrará la misma pila descrita anteriormente. Es necesario añadir la información necesaria para marcar los bloques como abiertos o cerrados. - 24Identificadores en las tablas de símbolosDe la definición del lenguaje de programación utilizado depende la información que hay que almacenar en la tabla de símbolos para el tratamiento correcto del programa:
• Clase del identificador, para indicar a qué tipo de objeto se refiere el identificador. Por ejemplo, podría ser una variable, función o procedimiento, una etiqueta, la definición de un tipo
de dato, el valor concreto de una enumeración, etc.
• Tipo, para indicar el tipo de dato. Por ejemplo: entero, real, lógico, complejo, carácter, cadena de caracteres, tipo estructurado, tipo declarado por el programador, subrutina que devuelve un dato, subrutina que no devuelve dato alguno, operador, etc.
Information
- Description
- Flashcards on Untitled, created by German Alejandro Ordoñez Calderon on 26/07/2021.
- Created by
- German Alejandro Ordoñez Calderon
- Views
- 0
- Rating