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

 


Fe de erratas


VOLUMEN I
ESTRUCTURAS DE DATOS

Ginés García Mateos
Joaquín Cervera López
Norberto Marín Pérez
Domingo Giménez Cánovas

ISBN: 84-8425-311-2

Comprar en Diego Marín

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
Joaquín Cervera López
Ginés García Mateos
Norberto Marín Pérez

ISBN: 84-8425-312-0

Comprar en Diego Marín

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