| |
|
INDICE
|
VOLUMEN 1
Capítulo 1.— Tratamiento de la informar7ón mediante secuencias ................................................ 1
1.1 Elementos básicos de la notación algorítmica ..... . ..... , • . . . • •1
1.11 Algunas definiciones ............... . ..... • . . . 1
. . • • • .... • . •
1.12 Composición de acciones . ...... . . . . . ........ . . . , . • . 5
. . .
1.13 Ejercicios ........................... . . .. .. . • 10
1.2 Un método de construcción de algoritmos ......................................... 15
1.21.Introducción ........................................................................ 15
1.22 Composición secuencia! ......... . . . . . . . . . . , . ..... . . . • • . . . • . 15
1.23 Composiciones condicional, alternativa o selectiva . . . . . . . .. .........15
. . • . • .
1.24 Composición iterativa .. . ............... . . . ........ . .. . .. . .. . .. 16
1.25 Utilización del análisis descendente en el tratamiento secuencial . 21
1.3 Aprendizaje de la concepción de algoritmos ....... . ......... , . , . ... ............................. • . 26
1.31 Descripción de informaciones ........ . . . . .... . . . . . . . . . . . . • . 26
1.32 La máquina de <caracteres) . . . . ............. . . . . . . . . ....... . 28
1.33 Ejercicio modelo núm. 1: contar los caracteres 'A' . . . • . . . . . . • .29
1,34 Ejercicio modelo núm. 2: contar los grupos 'LA' ...... . . . . . . . . . .. 34
1.35 Ejercicio modelo núm. 3: contar el número de palabras de una frase . ... 51
1.36 Ejercicio modelo núm. 4: contar el número de veces que aparece la primera palabra de una frase ........................................................................ 56
1.37 Ejercicio modelo núm. 5: tratar una sucesión de telegramas . . . . .70
Capítulo 2.— Tratamientos elementales sobre secuencias .................. 77
2.1 Esquemas fundamentales ....................................... .78
2.11 Enumeración 78
2.12 Enumeración parcial .........................................78
2.2 Algoritmos básicos para el tratamiento de secuencias ....................81
2.21 Concatenación de dos secuencias . 81
2.22 Reunión de dos secuencias no ordenadas ...................................82
2,23 Intersección de dos secuencias no ordenadas .............................83
2.24 Fusión de dos secuencias ordenadas 84
2.3 Ejercicios ...................................................................................................85
Capítulo 3.— Organización y representación de la información con ayuda de secuencias 86
3.1 Generalidades.......................................................................... 86
3.2 Secuencias con enlaces implícito .............................................. .90
3.3 Secuencias con enlaces explícitos ......................................................................... 94
3.4 Algunas secuencias particulares 98
3.5 Aprendizaje de las técnicas de representación de secuencias........................ 99
3.51 Ejercicio modelo núm. 6: codificación de una frase ...................................... 99
3.52 Ejercicio modelo núm. 7: contar las ocurrencias de cada letra del alfabeto ..... 102
3.53 Ejercicio modelo núm. 8: contar las ocurrencias de cada cáracter de un texto .... 103
3.54 Ejercicio modelo núm. 9: operaciones sobre polinomios 105
3.55 Ejercicio modelo núm. 10: generación de números primos 117
3.6 Representación de la información por medio de tablas 121
3.61 Generalidades 121
3.62 Ejercicio modelo núm. 11: gestión de un diccionario 123
3.7 Gestión del espacio libre 134
3.71 Gestión inmediata del espacio libre 134
3.72 Gestión diferida del espacio libre 136
3.73 Reparto del espacio libre entre varias secuencias 138
Capítulo 4.— Utilización de un autómata de estados finitos 141
4.1 Generalidades sobre los autómatas de estados finitos 141
4.2 Aprendizaje del uso de autómatas de estados finitos 144
4.21 Ejercicio modelo núm. 12: contar las palabras terminadas por <ción> .. 144
4.22 Algunos ejemplos de autómatas de estados finitos 147
Anexo 150
Bibliografía 155
Índice alfabético 157
VOLUMEN 2Introducción IX
Capítulo 1. Recurrencia 1
1.1 Demostración por recurrencia del conjunto de entenos naturales 1
1.11 Primera forma de demostración por recurrencia 1
1.12 Segunda forma de demostración por recurrencia 3
1.13 Aplicación de la recurrencia sobre los enteros 5
1.14 Ejercicios 7
1.2 Definición recurrente de un conjunto 7
1.21 Principio 8
1.22 Ejemplos 9
1.23 Demostración por recurrencia 11
1.24 Ejercicios 13
1.3 Conclusión 13
Capítulo 2. Escritura de funciones. Procedimientos recursivos 14
2.1 Introducción al análisis recurrente 14
2.11 Definición recurrente de una función 14
2.12 Introducción a la notación recursiva 16
2.13 Ejercicios 22
2.2 Etapas de la construcción de un algoritmo 23
2.21 Ejemplo 4: rayuela 24
2.22 Ejemplo 5: plano de la ciudad 27
2.23 Ejemplo 6: inversión de una cadena 30
2.24 Terminación y corrección de un algoritmo recursivo 35
2.25 Ejercicios 38
Capítulo 3. Acciones recursivas 41
3.1 Composición recursiva 41
3.2 Ejemplos 7 y 8: impresiones en una pantalla 41
3.21 Máquina de imprimir 42
3.22 Ejemplo 7: impresión de una cadena 42
3.23 Ejemplo 8: impresión de un número entero 45
3.24 Ejercicios 48
3.3 Trazado de figuras imbricadas: ejemplos 9 y 10 49
3.31 Primitivas de dibujo 49
3.32. Ejemplo 9: cuadrados encajados 52
3.33 Ejemplo 10: trazado de cuadrados imbricados con restricciones 53
3.34 Ejercicios 57
3.4 Conclusión: una primera síntesis 60
3.41 Principios generales del análisis recurrente 60
3.42 Ejemplo 11: búsqueda asociativa en una sucesión 61
3.43 Ejemplo 12: suma, multiplicación 66
3.44 Ejemplo 13: división euclidiana (reducción logarítmica) 70
3.45 Ejemplo 14: torre de Hanoi 74
3.46 Ejercicios 80
Capítulo 4. Análisis recurrente y tratamiento secuencial 83
4.1 Generalidades sobre las secuencias 83
4.11 Definición recurrente de una secuencia 83
4.12 Notaciones 84
4.13 Ejemplos 88
4.14 Análisis recurrente y tratamiento de secuencias 90
4.2 Algoritmos de tratamiento de secuencias 93
4.21 Recorrido de una secuencia 93
4.22 Recorrido de una subsecuencia 94
4.23 Búsqueda de un elemento en una secuencia 96
4.3 Transformación recursiva-itinerativa (primera parte) 99
4.31 Algunos ejemplos simples 99
4.32 Transformación de acciones recursivas 102
4.33 Transformación de funciones recursivas 106
4.34 Ejercicios 107
4.4 Problema dirigido – evaluación de una expresión aritmética 107
4.41 Problema simplificado 107
4.42 Introducción de paréntesis 108
4.43 Generalización 108
4.44 Introducción de prioridades 109
4.45 Conclusión: "programa dirigido por los datos" 109
Capitulo 5. Tratamiento arborescente de la información 110
5.1 Definiciones 110
5.11 Árboles n-arios 110
5.12 Arboles binarios 114
5.13 Ejercicios 115
5.2 Análisis recurrente y tratamiento de árboles 117
5.21 Descripción de un árbol binario 117
5.22 Tratamiento de árboles binarios 120
5.23 Descripción de un árbol n-ario 123
5.24 Tratamiento de árboles n-arios 124
5.25 Ejercicios 128
5.3 Serie de ejercicios llevados a expresiones aritméticas 129
5.31 Convenciones 129
5.32 Formas lineales de una expresión aritmética (ejercicios) 131
5.33 Evaluaciones "posfijas" de una expresión aritmética (ejercicios) 132
Capítulo 6. Árboles: algoritmos – representaciones 134
6.1 Esquemas: definiciones recursivas 134
6.11 Recorrido de árboles 134
6.12 Ejemplo 17: las ocho reinas 141
6.13 Búsqueda de un elemento en un árbol 144
6.14 Ejercicios . ......................,147
6.15 Conclusión 148
6.2 Algoritmos itinerativos de tratamiento de árboles 148
6.21 "Máquina árbol" ................................ ..... . . . 148
6.22 Realización de las primitivas PADRE y ESDERECHO .. 150
6.23 Formas iterativas de recorrido de árboles ...... 152
6.24 Estudio de algunos algoritmos iterativos ....... 160
6.25 Ejercicios ..................................... 164
6.3 Algunas representaciones ....... 165
6.31 Representaciones de enlaces explícitos 165
6.32 Representación de enlaces implícitos ............................ 166
6.33 Ejercicios ......................... 167
Capitulo 7. Aplicación del tratamiento arborescente al estudio de algoritmos recursivos ...................................................................... 169
7.1 Estudio de un modelo de reducción logaritmica ..................... 169
7.11 Presentación del problema - solución 169
7.12 Aplicación del tratamiento arborescente ................... 170
7.13 Otra forma de aceleración logarítmica ....................... 174
7.14 Ejercicios .................................................. 176
7.2 Transformación recursivo – iterativo (segunda parte) 176
7.21 Un ejemplo de transformación ................................ 176
7.22 Transformación de acciones recursivas que generan dos llamadas recursivas 180
7.23 Caso de los algoritmos recursivos que generan más de dos llamadas recursivas 181
7.24 Ejercicios 183
7.3 Ejemplo 18: un algoritmo de ordenación 184
7.31 Algoritmo de salida 184
7.32 Aplicación del tratamiento arborescente ........ 185
7.33 Simplificación: otra estructuración en árbol 186
7.34 Otra forma de algoritmo ...................... ............... 188
Bibliografía ........ 191
Índice alfabético ........... 193
|
|
