Técnicas de Diseño de Algoritmos

 

 Técnicas de Diseño de Algoritmos

UNIVERSIDAD DE MALAGA

326 Pag. 

Descargar

INTRODUCCIÓN

En un sentido amplio, dado un problema y un dispositivo donde resolverlo, es
necesario proporcionar un método preciso que lo resuelva, adecuado al dispositivo.
A tal método lo denominamos algoritmo.
En el presente texto nos vamos a centrar en dos aspectos muy importantes de los
algoritmos, como son su diseño y el estudio de su eficiencia.
El primero se refiere a la búsqueda de métodos o procedimientos, secuencias
finitas de instrucciones adecuadas al dispositivo que disponemos, que permitan
resolver el problema. Por otra parte, el segundo nos permite medir de alguna forma
el coste (en tiempo y recursos) que consume un algoritmo para encontrar la
solución y nos ofrece la posibilidad de comparar distintos algoritmos que resuelven
un mismo problema.
Este capítulo está dedicado al segundo de estos aspectos: la eficiencia. En
cuanto a las técnicas de diseño, que corresponden a los patrones fundamentales
sobre los que se construyen los algoritmos que resuelven un gran número de
problemas, se estudiarán en los siguientes capítulos.

EFICIENCIA Y COMPLEJIDAD

Una vez dispongamos de un algoritmo que funciona correctamente, es necesario
definir criterios para medir su rendimiento o comportamiento. Estos criterios se
centran principalmente en su simplicidad y en el uso eficiente de los recursos.
A menudo se piensa que un algoritmo sencillo no es muy eficiente. Sin
embargo, la sencillez es una característica muy interesante a la hora de diseñar un
algoritmo, pues facilita su verificación, el estudio de su eficiencia y su
mantenimiento. De ahí que muchas veces prime la simplicidad y legibilidad del
código frente a alternativas más crípticas y eficientes del algoritmo. Este hecho se
pondrá de manifiesto en varios de los ejemplos mostrados a lo largo de este libro,
en donde profundizaremos más en este compromiso.

CAPÍTULO 1: LA COMPLEJIDAD DE LOS ALGORITMOS........................ 1

1.1 Introducción ................................................................................................ 1
1.2 Eficiencia y complejidad............................................................................. 1
1.3 Cotas de complejidad. Medidas asintóticas................................................. 6
1.4 Resolución de ecuaciones en recurrencia.................................................. 10
1.5 Problemas propuestos................................................................................ 16
1.6 Solución a los problemas propuestos ........................................................ 22
CAPÍTULO 2: ORDENACIÓN........................................................................... 57
2.1 Introducción .............................................................................................. 57
2.2 Ordenación por Inserción .......................................................................... 60
2.3 Ordenación por Selección ......................................................................... 61
2.4 Ordenación Burbuja .................................................................................. 62
2.5 Ordenación por Mezcla (Mergesort) ......................................................... 63
2.6 Ordenación mediante Montículos (Heapsort) ........................................... 65
2.7 Ordenación Rápida de Hoare (Quicksort) ................................................. 67
2.8 Ordenación por Incrementos (Shellsort) ................................................... 70
2.9 Otros algoritmos de ordenación ................................................................ 71
2.10 Problemas propuestos.............................................................................. 74
2.11 Solución a los problemas propuestos ...................................................... 77
CAPÍTULO 3: DIVIDE Y VENCERÁS........................................................... 105
3.1 Introducción ............................................................................................ 105
3.2 Búsqueda binaria..................................................................................... 108
3.3 Búsqueda binaria no centrada ................................................................. 109
3.4 Búsqueda ternaria.................................................................................... 110
3.5 Multiplicación de enteros ........................................................................ 112
3.6 Producto de matrices cuadradas (1)......................................................... 114
3.7 Producto de matrices cuadradas (2)......................................................... 116
3.8 Mediana de dos vectores ......................................................................... 117
3.9 El elemento en su posición...................................................................... 119
3.10 Repetición de cálculos en Fibonacci ..................................................... 120
3.11 El elemento mayoritario ........................................................................ 121
3.12 La moda de un vector ............................................................................ 124
3.13 El torneo de tenis................................................................................... 127
3.14 Divide y Vencerás multidimensional .................................................... 132
3.15 La subsecuencia de suma máxima......................................................... 137

CAPÍTULO 4: ALGORITMOS ÁVIDOS........................................................ 141

4.1 Introducción ............................................................................................ 141
4.2 El problema del cambio........................................................................... 143
4.3 Recorridos del caballo de ajedrez............................................................ 147
4.4 La división en párrafos............................................................................ 150
4.5 Los algoritmos de Prim y Kruskal........................................................... 155
4.6 El viajante de comercio ........................................................................... 160
4.7 La mochila............................................................................................... 164
4.8 La mochila (0,1) ...................................................................................... 165
4.9 El fontanero diligente.............................................................................. 166
4.10 Más fontaneros ...................................................................................... 167
4.11 La asignación de tareas ......................................................................... 168
4.12 Los ficheros y el disquete...................................................................... 171
4.13 El camionero con prisa.......................................................................... 173
4.14 La multiplicación óptima de matrices ................................................... 175
CAPÍTULO 5: PROGRAMACIÓN DINÁMICA............................................ 177
5.1 Introducción ............................................................................................ 177
5.2 Cálculo de los números de Fibonacci...................................................... 178
5.3 Cálculo de los coeficientes binomiales ................................................... 180
5.4 La subsecuencia común máxima............................................................. 181
5.5 Intereses bancarios .................................................................................. 184
5.6 El viaje más barato por río ...................................................................... 186
5.7 Transformación de cadenas..................................................................... 187
5.8 La función de Ackermann ....................................................................... 189
5.9 El problema del cambio........................................................................... 191
5.10 El algoritmo de Dijkstra ........................................................................ 194
5.11 El algoritmo de Floyd............................................................................ 196
5.12 El algoritmo de Warshall....................................................................... 197
5.13 Ordenaciones de objetos entre dos relaciones....................................... 198
5.14 El viajante de comercio ......................................................................... 200
5.15 Horarios de trenes.................................................................................. 201
5.16 La mochila (0,1) .................................................................................... 202
5.17 La mochila (0,1) con múltiples elementos ............................................ 205
5.18 La multiplicación óptima de matrices ................................................... 206

CAPÍTULO 6: VUELTA ATRÁS..................................................................... 211

6.1 Introducción ............................................................................................ 211
6.2 Las n reinas ............................................................................................. 212
6.3 Recorridos del rey de ajedrez .................................................................. 219
6.4 Recorridos del rey de ajedrez (2) ............................................................ 222
6.5 Las parejas estables ................................................................................. 224
6.6 El laberinto .............................................................................................. 226
6.7 La asignación de tareas ........................................................................... 229
6.8 La mochila (0,1) ...................................................................................... 231
6.9 Los subconjuntos de suma dada .............................................................. 234
6.10 Ciclos Hamiltonianos. El viajante de comercio .................................... 236
6.11 El continental ........................................................................................ 239

6.13 La asignación de tareas en paralelo....................................................... 244

6.14 El coloreado de mapas........................................................................... 246
6.15 Reconocimiento de grafos..................................................................... 249
6.16 Subconjuntos de igual suma.................................................................. 251
6.17 La múltiples mochilas (0,1)................................................................... 253
CAPÍTULO 7: RAMIFICACIÓN Y PODA..................................................... 255
7.1 Introducción ............................................................................................ 255
7.2 Consideraciones de implementación ....................................................... 257
7.3 El puzzle (n2–1)....................................................................................... 262
7.4 El viajante de comercio ........................................................................... 270
7.5 El laberinto .............................................................................................. 278
7.6 La colocación óptima de rectángulos ...................................................... 285
7.7 La mochila (0,1) ...................................................................................... 291
7.8 La mochila (0,1) con múltiples elementos .............................................. 296
7.9 La asignación de tareas ........................................................................... 298
7.10 Las n reinas ........................................................................................... 303
7.11 El fontanero con penalizaciones............................................................ 307
BIBLIOGRAFÍA Y REFERENCIAS ............................................................... 315