PDF de programación - Conjuntos y diccionarios - Estructura de datos

Programa de teoría
AED I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

AED II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

AED I: ESTRUCTURAS DE DATOS
Tema 2. Conjuntos y

Diccionarios.

2.1. Repaso del TAD Conjunto.
2.2. Implementaciones básicas.
2.3. El TAD Diccionario.
2.4. Las tablas de dispersión.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

1

2

1

2.1. Repaso del TAD Conjunto.

Definición y propiedades.

• Conjunto: Colección no ordenada de

elementos (o miembros) distintos.

• Elemento: Cualquier cosa, puede ser un

elemento primitivo o, a su vez, un conjunto.

C: Conjunto
de enteros

8

3

1

5

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

Diagrama
de patata

3

2.1. Repaso del TAD Conjunto.

• En programación, se impone que todos

los elementos sean del mismo tipo:
Conjunto[ T ] (conjuntos de enteros, de
caracteres, de cadenas ...)

• ¿En qué se diferencia el TAD

Conjunto del TAD Lista?

• ¿En qué se diferencia el TAD

Conjunto del TAD Bolsa?

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

4

2

2.1. Repaso del TAD Conjunto.

• Puede existir una relación de orden en el

conjunto.

• Relación “<” de orden en un conjunto C:

– Propiedad transitiva: para todo a, b, c, si

(a<b) y (b<c) entonces (a<c).

– Orden total: para todo a, b, sólo una de las
afirmaciones (a<b), (b<a) o (a=b) es cierta.

• … colección no ordenada…  Se refiere

al orden de inserción de los elementos.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

5

2.1. Repaso del TAD Conjunto.

Repaso de Notación de Conjuntos.

• Definición:

Por extensión
A= {a, b, c, ..., z}
B= {1, 4, 7} = {4, 7, 1}

• Pertenencia:

x  A

• Conjunto vacío:

Ø

Inclusión:

•
• Unión:

A  B

A  B

Mediante proposiciones

C= {x | proposición de x}
D= {x | x es primo y menor que 90}
• No pertenencia: x  A

• Conjunto universal: U
•
A  B
• Diferencia:

Intersección:

A – B

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

6

3

2.1. Repaso del TAD Conjunto.
Operaciones más comunes.

C: Conjunto de todos los Conjunto[T]
a, b, c  C;

x  T

• Vacío :  C
• Unión : C x C  C
• Intersección : C x C  C
• Diferencia : C x C  C
• Combina : C x C  C

• Miembro : T x C  B

a:= Ø
c:= a  b
c:= a  b
c:= a – b
c:= a  b,
con a  b = Ø
x  a

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

7

2.1. Repaso del TAD Conjunto.
Operaciones más comunes.

• Inserta : T x C  C
• Suprime : T x C  C
• Min : C  T
• Max : C  T
• Igual : C x C  B

a:= a  {x}
a:= a – {x}
minxa(x)
maxxa(x)
a == b

• … elementos distintos…  Si insertamos un

elemento que ya pertenece, obtenemos el mismo
conjunto.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

8

4

2.2. Implementaciones básicas.

• Problema: ¿Cómo representar el tipo conjunto,

de forma que las operaciones se ejecuten
rápidamente, con un uso razonable de memoria?

• Respuesta:
• Dos tipos de implementaciones básicas:

en este tema y el siguiente.

– Mediante arrays de booleanos.
– Mediante listas de elementos.

• La mejor implementación depende de cada

aplicación concreta:
– Operaciones más frecuentes en esa aplicación.
– Tamaño y variabilidad de los conjuntos usados.
– Etc.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

9

2.2. Implementaciones básicas.

C: Conjunto

8

3

1

5

3

2

1
10
1 0 1 0 1 0 0 1 0 0

7

8

9

4

5

6

8

1

3

5

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

Array de
booleanos

Lista de
elementos
+ d

10

5

2.2. Implementaciones básicas.
2.2.1. Mediante arrays de booleanos.

• Idea: Cada elemento del conjunto universal se representa
con 1 bit. Para cada conjunto concreto A, el bit asociado a
un elemento vale:

1 - Si el elemento pertenece al conjunto A
0 - Si el elemento no pertenece a A

• Definición:

tipo

Conjunto[T] = array [1..Rango(T)] de booleano

Donde Rango(T) es el tamaño del conj. universal.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

11

2.2.1. Mediante arrays de booleanos.

• Ejemplo: T = {a, b, …, g}

C= Conjunto[T]
A = {a, c, d, e, g}
B = {c, e, f, g}
a
1

d
1

b
0

c
1

a
0

b
0

c
1

d
0

e
1

e
1

f
0

f
1

g
1

g
1

A: Conjunto[a..g]

B: Conjunto[a..g]

• Unión, intersección, diferencia: se transforman en las

operaciones booleanas adecuadas.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

12

6

2.2.1. Mediante arrays de booleanos.

operación Unión (A, B: Conjunto[T]; var C: Conjunto[T])

para cada i en Rango(T) hacer

C[i]:= A[i] OR B[i]

operación Intersección (A, B: Conjunto[T]; var C: Conjunto[T])

para cada i en Rango(T) hacer

C[i]:= A[i] AND B[i]

operación Diferencia (A, B: Conjunto[T]; var C: Conjunto[T])

para cada i en Rango(T) hacer

C[i]:= A[i] AND NOT B[i]

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

13

2.2.1. Mediante arrays de booleanos.

operación Inserta (x: T; var C: Conjunto[T])

C[x]:= 1

operación Suprime (x: T; var C: Conjunto[T])

C[x]:= 0

operación Miembro (x: T; C: Conjunto[T]): booleano

devolver C[x]==1

• ¿Cuánto tardan las operaciones anteriores?
• ¿Cómo serían: Igual, Min, Max, ...?

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

14

7

2.2.1. Mediante arrays de booleanos.

Ventajas
• Operaciones muy sencillas de

implementar.

• No hace falta usar memoria dinámica.
• El tamaño usado es proporcional al

tamaño del conjunto universal,
independientemente de los elementos que
contenga el conjunto.

• ¿Ventaja o inconveniente?

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

15

2.2.1. Mediante arrays de booleanos.

• Ejemplo. Implementación en C, con

T = {1, 2, …, 64}
tipo

Conjunto[T] = long long

• Unión (A, B, C)  C = A | B;
• Intersección (A, B, C)  C = A & B;
• Inserta (x, C)  C = C | (1<<(x-1));
• ¡Cada conjunto ocupa 8 bytes, y las opera-
ciones se hacen en 1 o 3 ciclos de la CPU!

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

16

8

2.2.1. Mediante arrays de booleanos.

• Ejemplo. Implementación con

T = enteros de 32 bits = {0, 1, …, 232-1}
tipo

Conjunto[T] = array [4.294.967.296] de
bits = array [536.870.912] de bytes

• ¡Cada conjunto ocupa 0.5 Gigabytes,

independientemente de que contenga sólo
uno o dos elementos…!

• ¡El tiempo es proporcional a ese tamaño!

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

17

2.2.2. Mediante listas de elementos.
• Idea: Guardar en una lista los elementos que

pertenecen al conjunto.

• Definición:

tipo

Conjunto[T] = Lista[T]

• C = {1, 5, 8, 3}

8

1

3

5

C: Conjunto[T]

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

18

9

2.2.2. Mediante listas de elementos.

Ventajas:
• Utiliza espacio proporcional al tamaño del

conjunto representado (no al conjunto universal).

• El conjunto universal puede ser muy grande, o

incluso infinito.

Inconvenientes:
• Las operaciones son menos eficientes si el

conjunto universal es reducido.

• Gasta más memoria y tiempo si los conjuntos

están muy llenos.

• Más complejo de implementar.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

19

2.2.2. Mediante listas de elementos.

operación Miembro (x: T; C: Conjunto[T]): booleano

Primero(C)
mientras NOT EsUltimo(C) AND Actual(C) ≠ x hacer

Avanzar(C)

devolver NOT EsUltimo(C)

Evaluación en
cortocircuito

operación Intersección (A, B; Conjunto[T]; var C: Conjunto[T])

C:= ListaVacía
Primero(A)
mientras NOT EsUltimo(A) hacer

si Miembro(Actual(A), B) entonces

InsLista(C, Actual(A))

Avanzar(A)

finmientras

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

20

10

2.2.2. Mediante listas de elementos.

• ¿Cuánto tiempo tardan las operaciones anteriores?

Suponemos una lista de tamaño n y otra m (o
ambas de tamaño n).

• ¿Cómo sería Unión, Diferencia, Inserta, Suprime,

etc.?

• Inconveniente: Unión, Intersección y Diferencia
recorren la lista B muchas veces (una por cada
elemento de A).

• Se puede mejorar usando listas ordenadas.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

21

2.2.2. Mediante listas de elementos.

• Listas no ordenadas.

8

1

• Listas ordenadas.

1

3

3

5

5

8

C: Conjunto[T]

C: Conjunto[T]

• Miembro, Inserta, Suprime: Parar si encontramos

un elemento mayor que el buscado.

• Unión, Intersección, Diferencia: Recorrido

simultáneo (y único) de ambas listas.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

22

11

2.2.2. Mediante listas de elementos.

operación Miembro (x: T; C: Conjunto[T]): booleano

Primero(C)
mientras NOT EsUltimo(C) AND Actual(C) < x hacer

Avanzar(C)

devolver NOT EsUltimo(C) AND Actual(C) == x

1

3

5

8

C: Conjunto[T]

• ¿Cuánto es el tiempo de ejecución ahora?

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

23

2.2.2. Mediante listas de elementos.

• Unión: Idea parecida al procedimiento de mezcla,

en la ordenación por mezcla.

1

actual
3

actual
1

3

4

5

5

3

4

8

9

5

8

A: Conjunto[T]

B: Conjunto[T]

C: Conjunto[T]

9

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

24

12

2.2.2. Mediante listas de elementos.

operación Unión (A, B: Conjunto[T]; var C: Conjunto[T])

C:= ListaVacía
Primero(A)
Primero(B)
mientras NOT (EsUltimo(A) AND EsUltimo(B)) hacer
si EsUltimo(B) OR Actual(A)<Actual(B) entonces

sino si EsUltimo(A) OR Actual(B)<Actual(A) entonces

InsLista(C, Actual(A))
Avanza(A)

InsLista(C, Actual(B))
Avanza(B)

sino

finsi

finmientras

InsLista(C, Actual(A))
Avanza(A)
Avanza(B)

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

25

2.2.2. Mediante listas de elementos.
• ¿Cuánto es el tiempo de ejecución? ¿Es

sustancial la mejora?

• ¿Cómo serían la Intersección y la

Diferencia?

• ¿Cómo serían las operaciones Min, Max?
• ¿Cuánto es el uso de memoria para

tamaño n? Supongamos que 1 puntero =
k1 bytes, 1 elemento = k2 bytes.

A.E.D. I

Tema 2. Conjuntos y Diccionarios.

26

13

2.2. Implementaciones básicas.
Conclusiones

• Arrays de booleanos: muy rápida para las

operaciones de inserción y consulta.

• Inviable si el tamaño del conjunto universal