TEXTO
GUÍA:
ALGORITMOS Y ESTRUCTURAS DE DATOS
Primera edición, Junio 2003
(c)
Ginés García Mateos
Joaquín Cervera López
Norberto Marín Pérez
Domingo Giménez Cánovas
(c)
Editorial Diego Marín
Colección Textos-Guía
ICE - Universidad
de Murcia
 |
VOLUMEN I ESTRUCTURAS DE DATOS Ginés
García Mateos ISBN: 84-8425-311-2 |
Número de páginas: 353
Descripción: Este libro está pensado para ser usado en una asignatura anual de segundo curso de una ingeniería en informática. En consecuencia, se da por hecho que el lector conoce algún lenguaje de alto nivel -imperativo u orientado a objetos- y ha tenido sus primeras experiencias de programación en algún proyecto de tamaño pequeño o mediano. El primer volumen está centrado en los tipos de datos y su implementación eficiente. Empieza con un repaso, en el capítulo 1, de los principales conceptos de programación que el lector debería conocer y una visión general del proceso de resolución de problemas. El capítulo 2 está centrado en las especificaciones, y particularmente en las formales: algebraicas y constructivas. Los capítulos 3 y 4 tratan de la implementación de conjuntos y diccionarios. En el capítulo 3 se desarrollan las tablas de dispersión y otras estructuras lineales, y en el 4 se estudian las implementaciones arbóreas, mediante tries, árboles de punteros al padre, árboles AVL y B. El capítulo 5 está dedicado a los grafos, estructuras de representación, problemas y algoritmos sobre los mismos.
Extracto de muestra: Apartado 4.2. Relaciones de equivalencia
Tabla de
contenidos: Completa
1. Problemas, programas,
estructuras y algoritmos
2. Abstracciones y especificaciones
3. Conjuntos y diccionarios
4. Representación de conjuntos mediante árboles
5. Grafos
A. Tutorial de ANSI C
B. Introducción básica a C++
C. Práctica 1: Análisis y diseño de estructuras de
datos
 |
VOLUMEN II ALGORITMOS Domingo
Giménez Cánovas ISBN: 84-8425-312-0 |
Número de páginas: 289
Descripción: Este volumen está orientado al análisis y diseño de algoritmos. Los capítulos 6, 7 y 8 constituyen un bloque de análisis de algoritmos. El capítulo 6 introduce algunos conceptos básicos del análisis. Las notaciones asintóticas son tratadas en el capítulo 7, donde se estudian sus propiedades y extensiones. En el capítulo 8 se desarrolla una serie de herramientas matemáticas para resolver ecuaciones de recurrencia, como las que aparecen en el análisis de algoritmos recursivos. Por otro lado, los capítulos del 9 al 13 constituyen otro gran bloque de técnicas generales de diseño de algoritmos. En el capítulo 9 se analiza la técnica de divide y vencerás. En el capítulo 10 se tratan los algoritmos voraces y su uso para construir heurísticas. El capítulo 11 presenta la programación dinámica. En los capítulos 12 y 13 se desarrollan las técnicas de backtracking y ramificación y poda, respectivamente, de recorrido implícito en árbol de soluciones. El capítulo 14, trata de las técnicas de resolución de juegos, la estrategia minimax y la poda alfa/beta. Finalmente el capítulo 15 trata brevemente la complejidad de problemas, las clases de problemas y equivalencia entre problemas.
Tabla de
contenidos: Completa
6. Análisis de algoritmos
7. Notaciones asintóticas
8. Ecuaciones de recurrencia
9. Divide y vencerás
10. Algoritmos voraces
11. Programación dinámica
12. Backtracking
13. Ramificación y poda
14. Árboles de juegos
15. Complejidad algorítmica
D. Práctica 2: Análisis de algoritmos
E. Práctica 3: Esquemas algorítmicos
ALGORITMOS Y
ESTRUCTURAS DE DATOS
ISBN: Obra completa: 84-8425-310-4
TABLA DE CONTENIDOS DETALLADA
VOLUMEN I: ESTRUCTURAS DE DATOS
1 Problemas, programas, estructuras y
algoritmos......................................1
1.1 Resolución de
problemas......................................3
1.1.1 Análisis de
requisitos del
problema......................................3
1.1.2 Modelado del
problema y algoritmos
abstractos......................................4
1.1.3 Diseño de la
solución......................................5
1.1.4 Implementación del
diseño......................................6
1.1.5 Verificación y
evaluación de la
solución......................................7
1.2 Tipos de
datos......................................7
1.2.1 Definición de tipo
de datos, tipo abstracto y
estructura......................................8
1.2.2 Tipos de
tipos......................................10
1.2.3 Repaso de tipos y
pseudolenguaje de
definición......................................12
1.3 Algoritmos y
algorítmica......................................14
1.3.1 Definición y
propiedades de
algoritmo......................................15
1.3.2 Análisis de
algoritmos......................................17
1.3.3 Diseño de
algoritmos......................................21
1.3.4 Descripción del
pseudocódigo
utilizado......................................25
1.4 Consejos para una buena
programación......................................26
1.4.1 Importancia del
análisis y diseño
previos......................................26
1.4.2 Modularidad:
encapsulación y
ocultamiento......................................28
1.4.3 Otros
consejos......................................29
Ejercicios
propuestos......................................31
Cuestiones de
autoevaluación......................................31
Referencias
bibliográficas......................................32
2 Abstracciones y
especificaciones......................................35
2.1 Las abstracciones en
programación......................................37
2.1.1 Diseño mediante
abstracciones......................................38
2.1.2 Mecanismos de
abstracción: especificación y
parametrización......................................39
2.1.3 Tipos de
abstracciones: funcional, de datos e
iteradores......................................40
2.1.4 Mecanismos de
abstracción en los lenguajes de
programación......................................42
2.2 Especificaciones
informales......................................47
2.2.1 Especificación
informal de abstracciones
funcionales......................................47
2.2.2 Especificación
informal de abstracciones de
datos......................................48
2.2.3 Especificación
informal de abstracciones de
iteradores......................................51
2.3 Especificaciones formales
algebraicas......................................52
2.3.1 Propiedades,
notación y ventajas de las especificaciones
formales......................................53
2.3.2 Especificaciones
algebraicas o
axiomáticas......................................54
2.3.3 Taxonomía de las
operaciones de un
TAD......................................56
2.3.4 Completitud y
corrección de la
especificación......................................57
2.3.5 Reducción de
expresiones
algebraicas......................................59
2.4 Especificaciones formales
constructivas......................................61
2.4.1 Precondiciones y
postcondiciones......................................61
2.4.2 Especificación
como contrato de una
operación......................................62
2.4.3 Necesidad de un
modelo subyacente......................................64
2.4.4 Ejecución de
especificaciones
constructivas......................................67
Ejercicios
resueltos......................................68
Ejercicios
propuestos......................................75
Cuestiones de
autoevaluación......................................77
Referencias
bibliográficas......................................78
3 Conjuntos y
diccionarios......................................79
3.1 Los tipos abstractos
conjunto y
diccionario......................................81
3.1.1 El concepto
matemático de
conjunto......................................82
3.1.2 El tipo abstracto
diccionario......................................83
3.1.3 Representación
mediante arrays de
booleanos......................................85
3.1.4 Representación
mediante listas de
elementos......................................87
3.2 Tablas de
dispersión......................................90
3.2.1 La dispersión y
los sinónimos......................................91
3.2.2 Dispersión
abierta......................................92
3.2.3 Dispersión
cerrada......................................94
3.2.4 Funciones de
dispersión......................................100
3.2.5 Estrategias de
redispersión......................................102
3.3 Combinando estructuras de
datos......................................104
3.3.1 Estructuras de
datos múltiples......................................105
3.3.2 La relación muchos
a muchos......................................109
3.3.3 Estructuras de
listas
múltiples......................................113
Ejercicios
resueltos......................................116
Ejercicios
propuestos......................................122
Cuestiones de
autoevaluación......................................125
Referencias
bibliográficas......................................126
4 Representación de conjuntos mediante
árboles......................................127
4.1 Árboles
trie......................................129
4.1.1 Árboles de
prefijos......................................130
4.1.2 Representación de
nodos trie......................................132
4.1.3 Búsqueda e
inserción de palabras en un
trie......................................136
4.1.4 Eficiencia y
comparación entre
estructuras......................................138
4.2 Relaciones
de equivalencia......................................142
4.2.1 Representaciones
sencillas de relaciones de
equivalencia......................................145
4.2.2 Representación
mediante punteros al
padre......................................147
4.2.3 Equilibrado y
compresión de
caminos......................................149
4.3 Árboles de búsqueda
balanceados......................................154
4.3.1 Árboles binarios
de búsqueda......................................154
4.3.2 El peor caso de
árbol AVL......................................157
4.3.3 Rotaciones simples
y dobles sobre
AVL......................................160
4.3.4 Inserción en un
árbol AVL......................................162
4.3.5 Eliminación en un
árbol AVL......................................165
4.4 Árboles
B......................................168
4.4.1 Árboles de
búsqueda no
binarios......................................168
4.4.2 Inserción en un
árbol B......................................172
4.4.3 Eliminación en un
árbol B......................................172
4.4.4 Análisis de
eficiencia de los árboles
B......................................174
Ejercicios
resueltos......................................177
Ejercicios
propuestos......................................184
Cuestiones de
autoevaluación......................................187
Referencias
bibliográficas......................................189
5 Grafos......................................191
5.1 Definiciones y terminología
de grafos......................................193
5.1.1 Definición y tipos
de grafos......................................194
5.1.2 Terminología de la
teoría de
grafos......................................196
5.1.3 Árboles, grafos y
multigrafos......................................198
5.1.4 Especificación del
tipo grafo......................................201
5.2 Estructuras de representación de
grafos......................................203
5.2.1 Representación con
matrices de
adyacencia......................................204
5.2.2 Representación con
listas de
adyacencia......................................206
5.2.3 Comparación entre
estructuras de
representación......................................208
5.3 Recorridos sobre
grafos......................................211
5.3.1 Búsqueda primero
en profundidad......................................211
5.3.2 Búsqueda primero
en anchura......................................215
5.4 Árboles de expansión de coste
mínimo......................................217
5.4.1 Algoritmo de
Prim......................................218
5.4.2 Algoritmo de
Kruskal......................................221
5.5 Problemas de caminos
mínimos......................................223
5.5.1 Caminos mínimos
empezando por un
origen......................................224
5.5.2 Caminos más cortos
entre todos los
vértices......................................229
5.6 Algoritmos sobre grafos
dirigidos......................................234
5.6.1 Componentes
fuertemente
conexos......................................235
5.6.2 Grafos dirigidos
acíclicos......................................239
5.6.3 Flujo máximo en
redes......................................243
5.7 Algoritmos sobre grafos no
dirigidos......................................247
5.7.1 Puntos de
articulación y componentes
biconexos......................................248
5.7.2 Circuitos de
Euler......................................251
5.8 Otros problemas con
grafos......................................253
5.8.1 Ciclos
hamiltonianos......................................254
5.8.2 Problema del
viajante......................................255
5.8.3 Coloración de
grafos......................................256
5.8.4 Isomorfismo de
grafos......................................257
Ejercicios
resueltos......................................259
Ejercicios
propuestos......................................266
Cuestiones de
autoevaluación......................................270
Referencias
bibliográficas......................................271
A Tutorial de ANSI
C......................................275
A.1 Introducción......................................277
A.2 Primeros
pasos......................................279
A.3 Tipos de datos elementales y
variables......................................280
A.3.1 Tipo
char......................................281
A.3.2 Tipo
int......................................281
A.3.3 Tipos
enumerados......................................282
A.3.4 Tipos float y
double......................................282
A.3.5 Las conversiones de
tipo......................................282
A.3.6 Modos de
almacenamiento de las
variables......................................283
A.4 Operadores......................................285
A.4.1 Aritméticos......................................285
A.4.2 Incrementales......................................285
A.4.3 Relacionales......................................286
A.4.4 Lógicos......................................286
A.4.5 De manejo de
bits......................................287
A.4.6 De
asignación......................................287
A.4.7 De dirección e
indirección......................................287
A.4.8 Otros
operadores......................................288
A.4.9 Expresiones:
precedencia y
asociatividad......................................288
A.5 Sentencias de control de
flujo......................................290
A.5.1 Sentencias de
selección......................................290
A.5.2 Sentencias de
iteración......................................293
A.6 Tipos de datos agregados y
punteros......................................295
A.6.1 Punteros......................................296
A.6.2 Arrays......................................297
A.6.3 Relación entre
arrays y
punteros......................................299
A.6.4 Estructuras y
uniones......................................301
A.6.5 Definición de
tipos......................................303
A.7 Funciones......................................303
A.7.1 Función main con
argumentos......................................305
A.7.2 Funciones como
parámetros......................................305
A.8 Funciones de
E/S......................................306
A.8.1 printf......................................306
A.8.2 scanf......................................307
A.8.3 putchar y
getchar......................................308
A.8.4 Manejo de
ficheros......................................308
A.9 Gestión dinámica de la
memoria......................................310
A.10 El preprocesador de
C......................................312
A.11 Programas con varios
ficheros......................................313
Ejercicios
Propuestos......................................315
Referencias
bibliográficas......................................317
B Introducción básica a
C++......................................319
B.1 Pequeños cambios respecto a
C......................................320
B.1.1 Variables y
tipos......................................320
B.1.2 Funciones......................................321
B.1.3 Operadores new y
delete......................................323
B.1.4 Gestión de
E/S......................................324
B.2 Introducción a la
POO......................................324
B.3 Clases y objetos en C++, primeros
pasos......................................325
B.4 Programa ejemplo: TAD cadena de
caracteres......................................327
B.5 Plantillas......................................333
B.6 Excepciones......................................335
Ejercicios
Propuestos......................................337
Referencias
bibliográficas......................................338
C Práctica 1: Análisis y diseño de
estructuras de
datos......................................339
C.1 Enunciado......................................339
C.2 Análisis de los requisitos de la
aplicación......................................341
C.3 Diseño del
programa......................................343
C.4 Implementación del
diseño......................................348
C.5 Validación y
verificación......................................349
C.6 Informe del
desarrollo......................................350
VOLUMEN II: ALGORITMOS
6 Análisis de
algoritmos......................................1
6.1 Consumo de
recursos......................................3
6.1.1 Factores que
influyen en el consumo de
recursos......................................3
6.1.2 Tiempos de
ejecución......................................5
6.1.3 Ocupación de
memoria......................................6
6.1.4 Estudio de tiempo
de ejecución y ocupación de
memoria......................................6
6.2 Análisis de
algoritmos......................................8
6.2.1 Análisis a priori
y a posteriori......................................8
6.2.2 El proceso de
conteo de
instrucciones......................................8
6.2.3 Estudio
experimental......................................13
Ejercicios
resueltos......................................14
Ejercicios
propuestos......................................18
Cuestiones de
autoevaluación......................................19
Referencias
bibliográficas......................................19
7 Notaciones
asintóticas......................................21
7.1 Notaciones
asintóticas......................................23
7.1.1 La notación
O......................................24
7.1.2 La notación
Omega......................................25
7.1.3 La notación
Theta......................................25
7.1.4 La notación
o-pequeña......................................26
7.2 Propiedades de las notaciones
asintóticas......................................27
7.3 Complejidades más
frecuentes......................................29
7.4 Extensiones de las notaciones
asintóticas......................................30
7.4.1 Notaciones con
varios
parámetros......................................30
7.4.2 Notaciones
condicionales......................................31
Ejercicios
resueltos......................................32
Ejercicios
propuestos......................................41
Cuestiones de
autoevaluación......................................43
Referencias
bibliográficas......................................44
8 Ecuaciones de
recurrencia......................................45
8.1 Ecuaciones de
recurrencia......................................47
8.2 Expansión de la
recurrencia......................................48
8.3 Método de la ecuación
característica......................................49
8.3.1 Ecuaciones
lineales
homogéneas......................................49
8.3.2 Ecuaciones
lineales no
homogéneas......................................51
8.3.3 Cambio de
variable......................................52
8.3.4 Transformación de
la imagen......................................52
8.4 Técnica de la inducción
constructiva......................................53
8.5 Fórmulas
maestras......................................54
Ejercicios
resueltos......................................56
Ejercicios
propuestos......................................57
Cuestiones de
autoevaluación......................................58
Referencias
bibliográficas......................................58
9 Divide y
vencerás......................................59
9.1 Método
general......................................61
9.1.1 Esquema
general......................................61
9.1.2 Esquema
recursivo......................................61
9.2 Análisis de
tiempos......................................62
9.2.1 Caso de dos
subproblemas......................................62
9.2.2 Caso de a
subproblemas......................................63
9.3 Búsqueda del máximo y
mínimo......................................64
9.3.1 Método
directo......................................64
9.3.2 Con divide y
vencerás......................................65
9.3.3 Comparación......................................67
9.4 Ordenación por
mezcla......................................67
9.4.1 Algoritmo divide y
vencerás......................................67
9.4.2 Estudio......................................69
9.5 Ordenación
rápida......................................70
9.5.1 Algoritmo divide y
vencerás......................................70
9.5.2 Estudio......................................71
9.5.3 El problema de
selección......................................72
9.6 Multiplicación de enteros
largos......................................73
9.6.1 Multiplicación de
Karatsuba y Ofman......................................74
9.7 Multiplicación de
matrices......................................76
9.7.1 Multiplicación de
Strassen......................................77
Ejercicios
resueltos......................................78
Ejercicios
propuestos......................................93
Cuestiones de
autoevaluación......................................94
Referencias
bibliográficas......................................95
10 Algoritmos
voraces......................................97
10.1 Método
general......................................99
10.1.1 Esquema
general......................................99
10.1.2 Distintas
posibilidades en la solución de
problemas......................................100
10.1.3 Análisis del
tiempo de
ejecución......................................100
10.2 Ejemplos de avance rápido con técnicas
heurísticas......................................101
10.2.1 Problema del
cambio de
monedas......................................101
10.2.2 Paseo del
caballo......................................103
10.2.3 Camino mínimo en
grafos
multietapa......................................103
10.3 Problema de la mochila no
0/1......................................105
10.3.1 Planteamiento......................................105
10.3.2 Esquema de
solución......................................106
10.3.3 Solución
óptima......................................107
10.4 Secuenciamiento de trabajos a
plazos......................................108
10.4.1 Planteamiento......................................108
10.4.2 Solución
óptima......................................109
10.4.3 Algoritmo......................................110
10.5 Heurísticas
voraces......................................112
10.5.1 Problema del
viajante......................................112
10.5.2 Coloración de
grafos......................................114
Ejercicios
resueltos......................................115
Ejercicios
propuestos......................................117
Cuestiones de
autoevaluación......................................118
Referencias
bibliográficas......................................119
11 Programación
dinámica......................................121
11.1 Método
general......................................123
11.1.1 Ideas
generales......................................123
11.1.2 Programación
dinámica en problemas que no son de
optimización......................................125
11.1.3 Análisis de
tiempo de ejecución y ocupación de
memoria......................................126
11.2 Problema del grafo
multietapa......................................127
11.3 Problema del cambio de
monedas......................................128
11.3.1 Planteamiento de
la solución por programación
dinámica......................................128
11.3.2 Algoritmo......................................129
11.4 Problema de la mochila
0/1......................................130
11.4.1 Planteamiento de
solución por programación
dinámica......................................130
11.4.2 Algoritmo......................................131
11.5 Multiplicación encadenada de
matrices......................................132
11.5.1 Planteamiento......................................132
11.5.2 Solución por
programación
dinámica......................................133
Ejercicios
resueltos......................................134
Ejercicios
propuestos......................................142
Cuestiones de
autoevaluación......................................144
Referencias
bibliográficas......................................145
12 Backtracking......................................147
12.1 Método
general......................................149
12.1.1 Ideas
generales......................................149
12.1.2 Distintos tipos
de árboles de
soluciones......................................150
12.1.3 Esquemas de
backtracking......................................152
12.1.4 Análisis de
algoritmos de
backtracing......................................157
12.2 Problema de las
reinas......................................157
12.2.1 Planteamiento......................................157
12.2.2 Soluciones por
backtracking......................................158
12.2.3 Estudio......................................162
12.3 Problema de la
mochila......................................163
12.3.1 Planteamiento......................................163
12.3.2 Solución con
árbol binario......................................164
12.3.3 Mejora de la
función
criterio......................................165
12.3.4 Modificación del
orden de
recorrido......................................166
12.3.5 Solución con
árbol
combinatorio......................................167
Ejercicios
resueltos......................................168
Ejercicios
propuestos......................................182
Cuestiones de
autoevaluación......................................183
Referencias
bibliográficas......................................183
13 Ramificación y
poda......................................185
13.1 Método
general......................................187
13.1.1 Ideas
generales......................................187
13.1.2 Estrategias de
poda......................................188
13.1.3 Estrategias de
ramificación......................................188
13.1.4 Esquema
general......................................191
13.1.5 Análisis de
algoritmos de ramificación y
poda......................................191
13.2 Problema de la mochila
0/1......................................192
13.2.1 Árboles de
solución......................................192
13.2.2 Estimación del
beneficio y las
cotas......................................192
13.2.3 Estrategias de
ramificación y
poda......................................193
13.2.4 Algoritmo......................................194
13.3 Secuenciamiento de trabajos con
plazos......................................196
13.3.1 Definición del
problema......................................196
13.3.2 Diseño de una
solución......................................197
13.4 Problema de las
reinas......................................198
Ejercicios
resueltos......................................204
Ejercicios
propuestos......................................219
Cuestiones de
autoevaluación......................................220
Referencias
bibliográficas......................................222
14 Árboles de
juegos......................................223
14.1 Árboles de
juegos......................................225
14.2 Estrategia
minimax......................................227
14.2.1 Algoritmo......................................228
14.3 Poda
alfa-beta......................................229
14.3.1 Algoritmo......................................230
Ejercicios
resueltos......................................231
Ejercicios
propuestos......................................235
Cuestiones de
autoevaluación......................................237
Referencias
bibliográficas......................................238
15 Complejidad
algorítmica......................................239
15.1 Complejidad de
problemas......................................241
15.1.1 Concepto de cota
inferior de un
problema......................................241
15.1.2 Métodos para la
obtención de la cota inferior de un
problema......................................242
15.2 Equivalencia de
problemas......................................245
15.2.1 Reducción entre
problemas
matriciales......................................246
15.3 Clasificación de
problemas......................................247
15.3.1 Problemas P y
NP......................................248
15.3.2 Soluciones
heurísticas y
aproximadas......................................248
Ejercicios
resueltos......................................249
Ejercicios
propuestos......................................250
Cuestiones de
autoevaluación......................................251
Referencias
bibliográficas......................................251
D Práctica 2: Análisis de
algoritmos......................................255
D.1 Enunciado......................................255
D.2 Cómo resolver la
práctica......................................257
E Práctica 3: Esquemas
algorítmicos......................................277
E.1 Enunciado......................................277
E.2 Programación
dinámica......................................278
E.2.1 Resolución......................................278
E.2.2 Estudio teórico y
experimental......................................278
E.3 Avance
rápido......................................280
E.3.1 Resolución......................................280
E.3.2 Estudio teórico y
experimental......................................281
E.4 Backtracking......................................282
E.4.1 Resolución......................................282
E.4.2 Estudio teórico y
experimental......................................283
E.5 Ramificación y
poda......................................284
E.5.1 Resolución......................................284
E.5.2 Estudio teórico y
experimental......................................286
Ginés
García Mateos
Facultad de Informática. Despacho E-20.
Campus de
Espinardo. Universidad de Murcia.
30071 Murcia (SPAIN)
Teléfono: +34 968
36 46 08
Fax: +34 968 36 41
51
E-mail: ginesgm@um.es