PDF de programación - Programa de teoría Parte I. Estructuras de Datos

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

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

Parte 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.

Tema 2. Conjuntos y Diccionarios.

PARTE 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.
2.5. Relaciones muchos a muchos.

A.E.D.

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

Diagrama

de patata

A.E.D.

Tema 2. Conjuntos y Diccionarios.

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.

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.

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}

Mediante proposiciones

C= {x | proposición de x}
D= {x | x es primo y menor que 90}

• Pertenencia:

x ∈ A

• No pertenencia: x ∉ A

• Conjunto vacío:

Ø

•

Inclusión:

• Unión:

A ⊆ B

A ∪ B

• Conjunto universal: U
•

Intersección:

A ∩ B

• Diferencia:

A.E.D.

Tema 2. Conjuntos y Diccionarios.

A – B

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.

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.

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:

– 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.

Tema 2. Conjuntos y Diccionarios.

9

2.2. Implementaciones básicas.

C: Conjunto

8

3

1

5

2

3

4

1
10
0010010101

8

9

5

6

7

8

1

3

5

Array de
booleanos

Lista de
elementos

A.E.D.

Tema 2. Conjuntos y Diccionarios.

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.

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.

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])

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

A.E.D.

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.

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.

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
operaciones se hacen en 1 o 3 ciclos!

A.E.D.

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 Gygabytes,

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

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

A.E.D.

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.

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.

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 Actual(C) ≠ x AND NOT EsUltimo(C) hacer

Avanzar(C)

devolver Actual(C) == x

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.

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 Intersecció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.

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.

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 Actual(C) < x AND NOT EsUltimo(C) hacer

Avanzar(C)

devolver Actual(C) == x

1

3

5

8

C: Conjunto[T]

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

A.E.D.

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

8

9

A: Conjunto[T]

B: Conjunto[T]

3

4

5

8

C: Conjunto[T]

9

A.E.D.

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

finsi

finmientras

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

A.E.D.

Tema 2. Conjuntos y Diccionarios.

25

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

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

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

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.

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 es

muy grande.

• Listas de elementos: uso razonable de
memoria, proporcional al tamaño usado.

• Muy ineficiente para la inserción y consulta de

un elemento.

• Solución: T