Download Tema 3. Representación de Conjuntos
Document related concepts
Transcript
Tema 3. Representación de Conjuntos 1 OBJETIVOS • Estudiar los conjuntos desde un punto de vista algorítmico (conjuntos dinámicos). • Estudiar técnicas de representación de conjuntos (algoritmos de manipulación). • Estudiar los tipos de datos: diccionario, cola de prioridad. • Aprender a seleccionar el tipo de datos y la implementación más adecuados al problema 2 a resolver. ÍNDICE 1. Conceptos Generales 2. Representaciones básicas:listas 3. Árboles Binarios de Búsqueda 4.Tablas de Dispersión 5. Árboles Parcialmente Ordenados (Heaps) 6. Conjuntos Disjuntos (Mfsets) 3 BIBLIOGRAFÍA • T.H. Cormen, C.E. Leiserson, R.L. Rivest Introduction to Algorithms. MIT Press, 1990. – Parte III: Introducción y capítulos 12 y 13 – Parte V: Capítulos 19 y 22 • G. Brassard, P. Bratley. Fundamentos de Algoritmia. Prentice Hall, 1997. Sección 1.9. • Aho A.V., Hopcroft J.E., Ullman J.E. Estructuras de datos y Algoritmos. Addison-Wesley, 1988. Capítulos 4 y 5 4 1. CONCEPTOS GENERALES • Elementos de un conjunto (dinámico). Típicamente: – clave: campo de identificación – información satélite: asociada al objeto • Algunos conjuntos se caracterizan porque en el conjunto de claves se puede establecer una relación de orden total. – En este caso se puede definir el elemento mínimo de un conjunto, o el sucesor. 5 Operaciones sobre conjuntos • Consultoras: – Buscar, Mínimo, Máximo, Predecesor, Sucesor • Modificadoras: – Insertar, Borrar 6 Operaciones sobre conjuntos (cont.) – BUSCA(S,k): dado un cjto S y una clave k devuelve la posición x tal que clave[x]=k, o un valor especial si x∉S. – INSERTA(S,x): añade a S el elemento apuntado por x. – BORRA(S,x): borra el elemento apuntado por x de S 7 Operaciones sobre conjuntos (cont.) – MÍNIMO(S): devuelve el elemento de S con la clave más pequeña – MÁXIMO(S): devuelve el elemento de S con la clave más grande. – SUCESOR(S,x): devuelve el elemento de clave inmediatamente superior a la de x o un valor especial si x es el máximo – PREDECESOR(S,x): devuelve el elemento de clave inmediatamente inferior a la de x o un 8 valor especial si x es el mínimo Algunos tipos de conjuntos dinámicos • Pilas y Colas – Se inserta y se borra un elemento predeterminado – Pila: política LIFO – Cola: política FIFO • Diccionarios – Operaciones Inserta, Borra y Busca • Colas de prioridad – Operaciones Inserta, Elimina_Max 9 2. Implementaciones básicas • Vector de bits • Listas enlazadas – – – – doblemente enlazadas ordenadas circulares otras... 10 Ejemplo. • Lista doblemente enlazada. Notación – Una lista L tiene el atributo primero para acceder al principio de la misma (primero[L]) – Si x es un elemento de la lista: • clave[x] es la clave • suc[x] apunta a su sucesor • pred[x] apunta a su predecesor – Si pred[x]=NIL x no tiene predecesor, es el primer elemento de la lista – Si suc[x]=NIL x no tiene sucesor, es el último elemento de la lista 11 Ejemplo. Buscar Buscar(L,k) /* Encuentra el primer elemento con clave k en L y devuelve su posición. Si no lo encuentra devuelve NIL*/ x:=primero[L]; mientras x<>NIL y clave[x]<>k x:=suc[x] devuelve x El coste es O(n), con n=|L| (en el peor caso hay que recorrer toda la lista). 12 Ejemplo. Insertar Inserta(L,x) /* Dado un elemento x lo inserta en cabeza de lista L*/ suc[x]:=primero[L]; Si primero[L]<>NIL entonces pred[primero[L]]:=x primero[L]:=x pred[x]:=NIL El coste es O(1). 13 Ejercicio. Borrar Borra(L,x) /* Dado un elemento x lo borra de la lista L */ Si pred[x]<>NIL entonces suc[pred[x]]:=suc[x] sino primero[L]:=suc[x] Si suc[x]<>NIL entonces pred[suc[x]]:=pred[x] El coste es O(1). Si queremos borrar un elemento con una clave determinada primero hay que Buscar. Coste O(n) 14 Estudio comparativo de costes Operación Lista BUSCA(S,k) O(|S|) Lista ordenada O(|S|) INSERTA(S,x) O(1) O(|S|) BORRA(S,x) O(|1|) O(|1|) MÍNIMO(S) / MÁXIMO(S) O(|S|) O(1) PREDECESOR(S,x) / SUCESOR(S,x) O(|S|) O(|S|) 15 3) ÁRBOLES BINARIOS DE BÚSQUEDA Un árbol binario es de búsqueda si: • Todos los elementos del subárbol izquierdo son menores que el de la raíz • Todos los elementos del subárbol derecho son mayores que el de la raíz • Propiedad: Si se listan los elementos según recorrido en inorden resulta una secuencia ordenada. Ejercicio: ¿Cuál es la diferencia entre la propiedad de los ABB y la de Heaps?, ¿Puede utilizarse la propiedad de Heaps para listar de forma ordenada las claves de un árbol con n nodos en tiempo O(n)? 16 EJEMPLOS Ejemplos: Representación del conjunto S={5,2,7,4,8,3} 5 3 2 2 7 4 3 8 7 5 8 4 Ejercicio: Dibujar árboles binarios de búsqueda de alturas 2,3,4,5,6 para el conjunto de claves {1,4,5,10,16,17,21} 17 IMPLEMENTACIÓN x Der[x] 5 Izq[x] 3 2 7 4 8 18 IMPLEMENTACIÓN DE OPERACIONES SOBRE CONJUNTOS • • • • • Busca (S,k) Mínimo(S) y Máximo(S) Sucesor(S,x) y Predecesor(S,x) Inserta(S,x) Borra(S,x) 19 BÚSQUEDA DE UNA CLAVE EN UN ABB {x es un puntero a la raíz de un ABB y k es una clave} ABB_BUSCAR(x,k) {Devuelve un puntero al nodo con clave k si existe o Nil si no existe} Si x=nil ∨ k=clave[x] Coste O(h) entonces devuelve x Si k<clave[x] entonces devuelve ABB_BUSCAR(izq[x],k) sino devuelve ABB_BUSCAR(der[x],k) ABB_BUSCAR(T,k) 20 BÚSQUEDA DE UNA CLAVE EN UN ABB(cont) {x es un puntero a la raíz de un ABB y k es una clave} ABB_BUSCAR_I(x,k) {Devuelve un puntero al nodo con clave k si existe o Nil si no existe} mientras x≠nil ∧ k≠clave[x] hacer si k<clave[x] entonces x:=izq[x] sino x:=der[x] fsi devuelve x ABB_BUSCAR(T,k) 21 MÍNIMO Y MÁXIMO EN UN ABB ABB_MÍNIMO (x) {Devuelve un puntero al nodo con la clave más pequeña del árbol x, x <> nil} mientras izq[x]≠nil hacer x:=izq[x] devuelve x ABB_MÁXIMO (x) {Devuelve un puntero al nodo con la clave más grande del árbol x, x <> nil} mientras der[x]≠nil hacer x:=der[x] devuelve x 22 SUCESOR EN UN ABB 15 6 3 2 18 7 4 17 20 13 9 Sucesor del 15? Sucesor del 13? 23 SUCESOR EN UN ABB ABB_SUCESOR (x) {Devuelve un puntero al sucesor del nodo x si existe o Nil si la clave de x es la mayor del ABB} si der[x]≠nil entonces devuelve ABB_MÍNIMO(der[x]) {buscar el antecesor más pequeño de x cuyo hijo izquierdo también sea antecesor de x} y:=p[x]; mientras y≠nil ∧ x=der[y] hacer x:=y; y:=p[y]; Coste O(h) devuelve y 24 INSERTAR EN UN ABB ABB_INSERTA (T,z) {Inserta un valor v en una posición adecuada en un ABB T, clave[z]=v,izq[z]=nil, der[z]=nil} y:=nil;x:=T; mientras x≠nil hacer y:=x; si clave[z]<clave[x] entonces x:=izq[x] sino x:=der[x] p[z]:=y; si y=nil entonces T:=z sino si clave[z]<clave[y]entonces izq[y]:=z sino der[y]:=z 25 Insertar en un ABB. Ejemplo Insertar un nodo con clave 13 12 6 3 18 7 20 15 13 17 26 BORRAR EN UN ABB. Ejemplo Borrar z 15 Caso 3: Tiene 2 hijos 5 z 3 Caso 2: Solo tiene 1 hijo 16 12 20 Caso 1: No tiene hijos 10 z 13 z 18 23 6 7 27 BORRAR EN UN ABB. Ejemplo (cont.) 15 Caso 1: z no tiene hijos 5 16 3 12 10 20 18 23 6 7 28 BORRAR EN UN ABB. Ejemplo (cont.) 15 Caso 2: z tiene 1 hijo 5 16 3 z 12 10 20 13 18 23 6 7 29 BORRAR EN UN ABB. Ejemplo (cont.) 15 Caso 3: z tiene 2 hijos 5 z 16 intercambio 3 12 10 20 18 23 Sucesor con 1 hijo 6 7 30 BORRAR EN UN ABB ABB_BORRA (T,z) si izq[z]=nil ∨ der[z]=nil entonces y:=z sino y:=ABB_SUCESOR(z); si izq[y]≠nil entonces x:=izq[y] sino x:=der[y] si x ≠nil entonces p[x]:=p[y]; si p[y]=nil entonces T:=x sino si y=izq[p[y]] entonces izq[p[y]]:=x sino der[p[y]]:=x si y≠z entonces clave[z]:=clave[y] Si y tiene otros campos copiar devuelve y 31 4. TABLAS DE DISPERSIÓN • Estructura de datos especialmente diseñada para la implementación de DICCIONARIOS. • Puntos a tratar: – – – – Definición Resolución de colisiones Diccionarios Funciones de dispersión 32 Tablas de direccionamiento directo • Si |U|<<< y asumimos que no hay dos elementos con la misma clave: T 0 U información 1 0 7 9 4 1 S clave 2 6 5 3 2 2 3 3 4 5 5 6 8 7 8 U={0,1,..,9}; S={2,3,5,8} 8 9 33 Tablas de Dispersión (cont.) • Complejidad espacial: – Sea |U|el tamaño del conjunto universal y |S| el tamaño del conjunto a representar. El espacio en memoria para representar S es Θ (|U|). • Si |U|>>>> ?? • Si |S|<<<<|U| ?? • Usar un vector T[0..B-1], con B<<|U|. Un elemento de clave k se almacena en la posición h(k). T es una tabla de dispersión (tabla hash) y h es la función de dispersión. A cada una de las T[j] se les llama cubeta. 34 Tablas de dispersión (cont.) l Función de dispersión h: U -> {0,1,2,..,B-1}, Coste Θ(1) T 0 U h(k1) h(k4) S k1 h(k2)=h(k5) COLISIONES k2 k4 k5 k3 h(k3) B-1 35 Tratamiento de las colisiones • Definir una función de dispersión que minimice el número de colisiones (Dispersión efectiva). • Dos métodos para tratar las colisiones: – Encadenamiento – Direccionamiento abierto 36 Resolución de colisiones por encadenamiento • Lista de claves que tienen el mismo valor de la función de dispersión T[j]: puntero a la cabeza de lista de aquellos elementos cuya función hash es j (h(k)=j) 37 Resolución de colisiones por encadenamiento T 0 U k1 k4 k6 S k1 k2 k4 k6 k7 k2 k5 k7 k5 k3 k3 B-1 38 Implementación de un diccionario • Buscar(T,k) Busca elemento con clave k en la lista T[h(k)] • Insertar(T,x) Inserta x en cabeza de la lista T[h(clave[x])] • Borrar(T,x) Borra el elemento x de la lista T[h(clave[x])] 39 Análisis de costes • Insertar: O(1) – Si tenemos que comprobar previamente que no está: el coste de Buscar. • Buscar: O(|S|)en el peor de los casos – Todos los elementos de S están en la misma cubeta • Borrar: O(1) – Si no tenemos la dirección hay que buscar previamente el elemento: el coste de Buscar. 40 Análisis del CM de Buscar • Asumimos hashing uniforme simple: – La probabilidad de que un elemento de U se almacene en cualquier posición de la tabla es la misma. • Asumimos que el coste de calcular h es O(1) • Suponemos que las colisiones se han resuelto por encadenamiento. • Definimos el factor de carga de la tabla como α≡n/B, donde n=|S|. 41 CM de Buscar (cont.) • El coste de Buscar es O(1+α) – Si n es proporcional a B, n∈Θ(B), α=n/B∈Θ(1) – Y por lo tanto el coste de Buscar es O(1) – Así, todas las operaciones del tipo diccionario se pueden efectuar con coste constante 42 LA FUNCIÓN DE DISPERSIÓN • Hashing Uniforme Simple: • Definición: ∑ 1 p(k) = B k / h(k)= j – Método de la División: h(k)= k mod B Restricción: B nº primo no cercano a una potencia de 2. – Método de la Multiplicación: h(k)= B *(k*A-[k*A]), o<A<1 B se suele tomar una potencia de 2 A≅(51/2-1)/2=0.6180339887.. – Hashing Universal 43 Funciones hash sobre cadenas • f1(s) x:=0; for i:=1 to length(s) do x:=x+ord(s[i]) dev x mod B Problemas: – f1(abc)=f1(bca) • f2(s) dev (ord(s[1])+255ord(s[2])+2552ord(s[3]))modB 44 Funciones hash sobre cadenas (cont.) • f3(s) x:=ord(s[1]); for i:=2 to length(s) do x:=(x*256)+ord(s[i]))mod B dev x Problemas: – Cálculo más costoso (bucle con mod) 45 5. ÁRBOLES PARCIALMENTE ORDENADOS • Arbol Binario Completo: Un AB es completo si tiene todos sus niveles completos, a excepción quizás del último en el cuál todas las hojas estan tan a la izquierda como sea posible. • Árbol parcialmente ordenado (Montículo o Heap): Es un árbol binario completo,con la propiedad de orden: el valor de cualquier nodo es mayor o igual (o menor o igual) que el de sus nodos hijos. Heaps Ejemplo: 150 125 80 15 20 30 75 25 72 15 • Propiedades: – todas las ramas del árbol son secuencias ordenadas, – la raíz del árbol es el nodo de máximo (mínimo) valor, y – todo subárbol de un heap es, a su vez, un heap. Implementación de un heap • Un AB completo, y por lo tanto un heap admite una representación en forma de vector, numerando sus nodos de arriba abajo y de izquierda a derecha, fijando este orden la posición en el vector: v[1] 150 75 125 80 15 30 20 v 25 v[4] 72 15 v[5] v[6] v[8] v[9] v[10] 150 125 75 1 v[3] v[2] 2 3 80 30 25 4 5 6 72 15 20 7 8 9 15 10 v[7] Implementación de un heap (cont.) • v[1]es la raíz, • Dado un nodo v[i], – si 2i≤n entonces v[2i]es el nodo hijo izquierdo, – si 2i+1≤ n entonces v[2i+1] es el nodo hijo derecho, – si i≠1, v[idiv2] es el nodo padre. • Si es heap: ∀i:2≤i≤n:v[idiv2]≥v[i] • Un montículo de n elementos tiene una altura Θ(log n). Operaciones básicas sobre Heaps • Demostrarán la utilidad de esta estructura para: – el diseño de un algoritmo de ordenación rápido (HeapSort) – la representación de colas de prioridad Operaciones básicas sobre Heaps (cont.) – Ajustar, es la operación clave para mantener la propiedad de heap. Coste O(log n) (Heapify) – Construir_heap, para convertir un vector, en principio desordenado, en un heap. Coste O(n). (Build_Heap) – HeapSort, para ordenar un vector. Coste O(nlogn) – EliminaMax e Inserta, para extraer el máximo de un conjunto y eliminarlo y para insertar, características de las colas de prioridad. Costes O(log n) (Extraxt_Max e Insert) Ajustar. Algoritmo. {Izq(i) y Der(i) son heaps y 1<=i<=n} Ajustar (A,i) O(log n), n=Talla[A] l:=Izq(i); r:=Der(i); Si l<=Talla[A] y A[l]>A[i] entonces mayor:=l sino mayor:=i; Si r<=Talla[A] y A[r]>A[mayor] entonces mayor:=r Si mayor<>i entonces intercambiar(A[i],A[mayor]) Ajustar(A,mayor) {A[i..n]es un heap} Construir un heap. Algoritmo. Construir_Heap (A) { Convierte un vector A[1..n], donde n=Longitud[A], en un heap } Talla[A]:=Longitud[A] For i:=[Longitud[A]/2] downto 1 do Ajustar(A,i) Complejidad Temporal: •El coste de ajustar un nodo es proporcional a su altura •En un heap de n elementos hay como mucho (n/2h+1)+1 nodos de altura h. T(n) = log 2 n ∑ h=0 n h + 1 + 1 ∗ h ∈ O(n) + Θ(log 2 n) ∈ O(n) 2 HeapSort HeapSort (A) /*Ordena el vector A[1..n], donde n=Longitud[A]*/ Construir_Heap(A); For i:=Longitud[A] downto 2 do intercambiar(A[1],A[i]); Talla[A]:=Talla[A]-1; Ajustar(A,1) Complejidad Temporal: Coste de Construir_heap + Coste del bucle T(n) ∈O(n)+O(nlogn) ∈O(nlogn) Colas de Prioridad • Conjunto con las operaciones: – Insertar(S,x): inserta el elemento x e el conjunto S. – Máximo(S): devuelve el elemento de S cuya clave sea máxima. – EliminaMax(S) elimina y devuelve el elemento de S cuya clave sea máxima. EliminaMax. EliminaMax (A) /* Devuelve el máximo de A y lo borra */ Si Talla[A]<1 entonces Error Coste temporal O(logn) sino Max:=A[1]; A[1]:=A[Talla[A]]; Talla[A]:=Talla[A]-1; Ajustar(A,1); devuelve Max Insertar. Algoritmo. Insertar(A,k) /* Añade k al Heap A */ Talla[A]:=Talla[A]+1; i:=Talla[A]; while i>1 and A[Padre[i]]<k do A[i]:= A[Padre[i]]; i:=Padre[i]; Coste temporal O(logn) A[i]:=k; IMPLEMENTACIÓN DE CONJUNTOS. RESUMEN Cola Prioridad Diccionario COSTE PROMEDIO h∈O(log n) Busca(S,k) Lista ordenada O(n) Inserta(S,x) Tabla Hash He a p O(logn) O(1) O(n) O(n) O(logn) O(1) O(logn) Borra(S,x) O(n) O(logn) O(1) O(logn) Mínimo(S) O(1) O(logn) O(n) O(1) Eli_Min(S) O(1) O(logn) O(n) O(logn) Operación AB B S: conjunto; n=|S|;x: puntero a objeto; k:clave del objeto 58 E. de Datos para Conjuntos Disjuntos • Un MFSet (Merge-Find Set) es una estructura tipo conjunto en la que los elementos están organizados en subconjuntos disjuntos y el nº de elementos es fijo (no se añaden ni se borran). Las operaciones características son: – Combina: hace la unión de dos conjuntos disjuntos (Merge) – Encuentra: dado un elemento debe determinar a qué conjunto pertenece (Find) 59 MFSets. Ejemplo A 1 C B 3 7 12 5 4 6 13 2 10 8 11 9 Aplicaciones: •Equivalencia entre autómatas finitos •Determinación de componentes conexas de un gnd •Obtención del AEM en un gnd 60 Operaciones sobre MFSets • Si x e y son elementos (objetos) del conjunto: – Construir_Cjto(x): crea un nuevo conjunto cuyo único miembro es x. – Combina(x,y): une los conjuntos a los que pertenecen x e y – Encuentra(x): devuelve un puntero al representante del conjunto al que pertenece x. 61 Componentes conexas de un grafo • Sea G=(V,E) un grafo no dirigido – V[G] es el conjunto de vértices – E[G] es el conjunto de arcos ComponentesConexas(G) ∀v∈V[G] hacer Construir_Cjto(v); ∀(u,v)∈E[G] hacer Si Encuentra(u)≠Encuentra(v) entonces Combina(u,v) 62 Ejemplo a b e c d g f h j i 63 Ejemplo. Iteración 7 a b e c d g Arco f h j i Colección de conjuntos disjuntos {a} {b} {c} {d} {e} {f} {g} {h} {i} {j} (b,d) {a} {b,d} {c} {e} {f} {g} {h} {i} {j} (e,g) {a} {b,d} {c} {e,g} {f} {h} {i} {j} (a,c) {a,c} {b,d} {e,g} {f} {h} {i} {j} (h,i) {a,c} {b,d} {e,g} {f} {h,i} {j} (a,b) {a,c,b,d} {e,g} {f} {h,i} {j} (e,f) {a,c,b,d} {e,g,f} {h,i} {j} (b,c) {a,c,b,d} {e,g,f} {h,i} {j} 64 Representación de un MFSet • La más sencilla... • MFSet=vector[1..N] de TipoNombreCjto; – N es el número de elementos – M[x] es el conjunto al que pertenece x • Operaciones – Encuentra(x): es un acceso a M[x], O(1) – Combina(x,y): recorrido sobre el vector, O(N) • Coste amortizado: – Una secuencia de N-1 operaciones combina tiene un coste O(N2) 65 Ejemplo {{1},{2},{3},{4},{5}} Combina(1,2) {{1,2},{3},{4},{5}} Combina(2,3) {{1,2,3},{4}{5}} Combina(3,4) {{1,2,3,4},{5}} Combina(4,5) {{1,2,3,4,5}} 1 2 3 4 5 1 2 3 4 5 1 1 3 4 5 1 2 3 4 5 1 1 1 4 5 1 2 3 4 5 1 1 1 1 5 1 2 3 4 5 1 1 1 1 1 1 3 4 5 2 66 MFSet. Representación en árbol • Cada subconjunto es un árbol en el que cada nodo apunta al padre. • La raíz del árbol puede usarse para nombrar el conjunto. • El MFSet estará representado por una colección de árboles (un bosque). 3 3 1 7 5 4 9 2 8 10 6 1 8 5 6 9 7 4 10 2 67 MFSet. Rep. en árbol (cont.) • Los árboles no son necesariamente binarios, pero su representación es muy fácil ya que sólo necesitaremos un apuntador al padre: – MFSet= vector[1..N] de enteros; – M[i] es el padre del elemento i; – Podemos hacer que la raíz se apunte a sí mismo: i es raíz si M[i]=i. 68 Ejemplo 3 1 8 5 6 9 7 4 10 2 5 9 3 5 3 8 5 8 8 6 1 2 3 4 5 6 7 8 9 10 69 Operaciones • Combina: hacer que la raíz de un árbol sea hijo del otro. Coste constante. • Encuentra: devolver la raíz del árbol que contiene a x. Coste proporcional a la profundidad del nodo, que en el peor de los casos es N-1. • m operaciones de búsqueda tendrían un coste O(mn) en el peor caso. 70 Mejoras del Coste. Heurísticos • m operaciones Encuentra tienen un coste O(m) – Combinar por Rango – Comprimir Caminos 71 Combinar por Rango • La idea es hacer la operación combina de forma que la raíz del árbol con menos nodos apunte a la raíz del árbol con más nodos. Para ello en cada nodo se mantiene un rango que aproxima el logaritmo de la talla del subárbol, es una cota de la altura del nodo. 72 Implementación de Combina • Construir_Cjto(x) M[x]:=x; rango[x]:=0; • Combina(x,y) Une(Encuentra(x),Encuentra(y)) • Une(x,y) Si rango[x]>rango[y] entonces p[y]:=x sino p[x]:=y; Si rango[x]=rango[y] entonces rango[y]:=rango[y]+1; 73 Compresión de Caminos • El efecto de la Compresión de Caminos sobre la operación Encuentra es que todo nodo en el camino de x a la raíz cambia su padre por la raíz. • Permite realizar las m operaciones de búsqueda con coste O(m α(m,n)), donde α(m,n) es una inversa de la función de Ackerman que crece muy lentamente. 74 Operación Encuentra 1 2 3 4 Encuentra(8)=1 1 2 3 5 6 7 4 5 7 8 6 8 l Encuentra(x) Si x≠M[x] entonces M[x]:=Encuentra(M[x]); devuelve M[x] 75