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

Imágen de pdf Conjuntos y diccionarios - Estructura de datos

Conjuntos y diccionarios - Estructura de datosgráfica de visualizaciones

Publicado el 6 de Junio del 2018
476 visualizaciones desde el 6 de Junio del 2018
336,7 KB
31 paginas
Creado hace 3a (18/09/2016)
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
  • Links de descarga
http://lwp-l.com/pdf11619

Comentarios de: Conjuntos y diccionarios - Estructura de datos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad