Diseño de programas

Este debería ser el primer libro de programación que todo estudiante de informática y programador debería leer. Aquí se trata la problemática fundamental de la algoritmia: resolver un problema encontrando la solución (o soluciones) que mejor aprovechan los recursos del computador (el tiempo de CPU y el espacio en memoria). Muchos creen que saber programar es conocer el último lenguaje de programación o los secretos de los más potentes. Este libro persigue romper con esa idea errónea.

Saber programar es (además de buscar la implementación más eficaz) conocer las técnicas de diseño más usuales, le e enseñará, con múltiples ejemplos desarrollados y una detallada descripción de los razonamientos seguidos en cada paso, a fin de mejorar su capacidad para resolver y enfrentarse a un problema algorítmico.

Ventajas Competitivas:

Formalismo matemático presente siempre que el problema lo permita.

Enfoque en la resolución de problemas clásicos como el cambio de monedas o el problema de la mochila, tratados utilizando Control Óptimo.

Práctico ya que el estudiante encontrará gran número de cuestiones o ejercicios muy variados al final de cada capítulo.

Contiene cuestiones están totalmente resueltas o se dan los detalles relevantes para terminar de resolverlas.

Conozca

Los principales enfoques, conceptos, métodos y herramientas para el desarrollo de Algoritmos.

Fundamentos teóricos de los esquemas algorítmicos.

La técnica de diseño recursiva por inmersión y su relación con la iteración.

Algunos algoritmos clásicos para problemas fundamentales.

Aprenda

Técnicas fundamentales de diseño y análisis de algoritmos como la técnica de descomposición modular de programas.

Cómo analizar la eficiencia de los programas como un criterio de calidad.

Cómo utilizar técnicas avanzadas de diseño y análisis de algoritmos.

A identificar las componentes más relevantes de un problema y seleccionar la técnica algorítmica más adecuada.

Cómo seleccionar los tipos de datos más adecuados para mejorar la eficiencia de una solución algorítmica.

Como enfrentar problemas de difícil de manejo de información y conocimiento.

Cuáles herramientas metodológicas son más adecuadas para cada caso.

Realice

Diseñe e implemente basándose en el método de optimización que proporcionan los algoritmos.

La implementación de los principales paradigmas de computación.

Aumente

Su capacidad de resolución de problemas de formas no convencionales.

Desarrollo su pensamiento crítico.

INTRODUCCIÓN ………………………………………………………………………………………………..13
CAPÍTULO 1. LENGUAJE ALGORÍTMICO ………………………………………………………15
1.1 DEFINICIÓN DE ALGORITMO ……………………………………………………………………16
1.2 LA ROTACIÓN DE UNA LISTA DE NÚMEROS NATURALES …………………….20
1.3 CUESTIONES………………………………………………………………………………………………23
1.3.1 Dos comerciales en el restaurante ……………………………………………………………..23
1.3.2 Invertir una lista ……………………………………………………………………………………..23
1.3.3 El palíndromo…………………………………………………………………………………………24
1.4 RESPUESTAS A LAS CUESTIONES PLANTEADAS ……………………………………24
1.4.1 Dos comerciales en el restaurante ……………………………………………………………..24
1.4.2 Invertir una lista ……………………………………………………………………………………..25
1.4.3 El palíndromo…………………………………………………………………………………………25
CAPÍTULO 2. COMPLEJIDAD ALGORÍTMICA………………………………………………..27
2.1 ESTIMACIÓN DE LOS TIEMPOS DE EJECUCIÓN DEL ALGORITMO…………28
2.2 ALGORITMOS ITERATIVOS ………………………………………………………………………30
2.3 ESTRUCTURAS DE DATOS ………………………………………………………………………..31
2.4 NOTACIÓN ASINTÓTICA …………………………………………………………………………..33
2.4.1 Recurrencias homogéneas ………………………………………………………………………..34
2.4.2 Recurrencias no homogéneas……………………………………………………………………35
2.4.3 Ejemplo de aplicación ……………………………………………………………………………..36
2.4.4 Divide y Vencerás …………………………………………………………………………………..37
2.5 CUESTIONES………………………………………………………………………………………………38
2.6 RESPUESTAS A LAS CUESTIONES PLANTEADAS ……………………………………40
CAPÍTULO 3. DIVIDE Y VENCERÁS …………………………………………………………………43
3.1 CONSIDERACIONES GENERALES……………………………………………………………..44

3.2 ROTAR UNA IMAGEN ………………………………………………………………………………..45
3.3 BÚSQUEDA BINARIA…………………………………………………………………………………48
3.4 EL PROBLEMA DE LA ORDENACIÓN ……………………………………………………….49
3.4.1 La ordenación por mezcla ………………………………………………………………………..51
3.4.2 Ordenación rápida …………………………………………………………………………………..52
3.4.2.1 LA BANDERA HOLANDESA …………………………………………………………53
3.5 CUESTIONES………………………………………………………………………………………………56
3.5.1 K-ésimo menor elemento de un vector ………………………………………………………56
3.5.2 Pseudomediana……………………………………………………………………………………….56
3.5.3 Rotación de una imagen …………………………………………………………………………..56
3.5.4 Rotación de un vector………………………………………………………………………………56
3.5.5 Intercalación de dos vectores ordenados…………………………………………………….57
3.5.6 Multiplicación de naturales grandes…………………………………………………………..57
3.5.7 Suma de la subsecuencia máxima de un vector de naturales …………………………58
3.5.8 Moda de un vector…………………………………………………………………………………..58
3.5.9 Búsqueda de un elemento en un vector ordenado………………………………………..58
3.5.10 Elemento mayoritario de un vector ………………………………………………………….58
3.5.11 Algoritmo Shannon-Fano……………………………………………………………………….58
3.5.12 Mínimo y máximo de un vector no ordenado ……………………………………………59
3.6 RESPUESTAS A LAS CUESTIONES PLANTEADAS ……………………………………59
3.6.1 K-ésimo menor elemento de un vector ………………………………………………………59
3.6.2 Pseudomediana……………………………………………………………………………………….60
3.6.3 Rotación de una imagen …………………………………………………………………………..62
3.6.4 Rotación de un vector………………………………………………………………………………63
3.6.5 Intercalación de dos vectores ordenados…………………………………………………….64
3.6.6 Multiplicación de naturales grandes…………………………………………………………..65
3.6.7 Suma de la subsecuencia máxima de un vector de naturales …………………………67
3.6.8 Moda de un vector…………………………………………………………………………………..69
3.6.9 Búsqueda de un elemento en un vector ordenado………………………………………..72
3.6.10 Elemento mayoritario de un vector ………………………………………………………….73
3.6.11 Algoritmo de Shannon-Fano …………………………………………………………………..75
3.6.12 Mínimo y máximo de un vector no ordenado ……………………………………………76
CAPÍTULO 4. PROGRAMACIÓN DINÁMICA……………………………………………………77
4.1 PLANTEAMIENTO DEL PROBLEMA DE CONTROL ÓPTIMO ……………………77
4.2 PROPIEDAD DE CAUSALIDAD ………………………………………………………………….78
4.3 CONTROL ÓPTIMO CON PROGRAMACIÓN DINÁMICA……………………………79
4.3.1 El problema de la producción con beneficio máximo…………………………………..80
4.3.2 Solucionando problemas con Programación Dinámica ………………………………..83
4.3.3 El cambio de monedas……………………………………………………………………………..86
4.4 CUESTIONES………………………………………………………………………………………………87
4.4.1 El problema del cambio de monedas………………………………………………………….87
4.4.2 Los litros de leche …………………………………………………………………………………..88
4.4.3 Juego con fichas ……………………………………………………………………………………..88
4.4.4 Inversión en negocios………………………………………………………………………………88

4.4.5 División de una cantidad ………………………………………………………………………….88
4.4.6 Carga de un avión……………………………………………………………………………………89
4.4.7 Fabricación de automóviles………………………………………………………………………89
4.4.8 Fabricación de papel………………………………………………………………………………..90
4.4.9 El problema de la subsecuencia común más larga ……………………………………….90
4.4.10 Conversión a palíndromo ……………………………………………………………………….90
4.4.11 Caminos mínimos en grafos dirigidos y ponderados ………………………………….91
4.4.12 El problema de la multiplicación de n matrices…………………………………………91
4.4.13 Multiplicar de forma óptima n matrices …………………………………………………..91
4.4.14 Operaciones con cadenas de caracteres…………………………………………………….91
4.4.15 Número de árboles binarios…………………………………………………………………….92
4.4.16 El problema de los dos puntos más cercanos …………………………………………….92
4.4.17 Número de caminos distintos ………………………………………………………………….92
4.4.18 La función de Fibonacci…………………………………………………………………………93
4.4.19 Número de ordenaciones con los operadores = y <……………………………………93
4.5 SOLUCIONES ……………………………………………………………………………………………..94
4.5.1 El problema del cambio de monedas………………………………………………………….94
4.5.2 Los litros de leche …………………………………………………………………………………..95
4.5.3 Juego con fichas ……………………………………………………………………………………..96
4.5.4 Inversión en negocios………………………………………………………………………………96
4.5.5 División de una cantidad ………………………………………………………………………….97
4.5.6 Carga de un avión……………………………………………………………………………………99
4.5.7 Fabricación de automóviles………………………………………………………………………99
4.5.8 Fabricación de papel………………………………………………………………………………100
4.5.9 El problema de la subsecuencia común más larga ……………………………………..101
4.5.10 Conversión a palíndromo ……………………………………………………………………..103
4.5.11 Caminos mínimos en grafos dirigidos y ponderados. ……………………………….105
4.5.12 El problema de la multiplicación de n matrices……………………………………….108
4.5.13 Multiplicar de forma óptima n matrices ………………………………………………..112
4.5.14 Operaciones con cadenas de caracteres…………………………………………………..113
4.5.15 Número de árboles binarios…………………………………………………………………..117
4.5.16 El problema de los dos puntos más cercanos …………………………………………..118
4.5.17 Número de caminos distintos ………………………………………………………………..119
4.5.18 La función de Fibonacci……………………………………………………………………….120
4.5.19 Número de ordenaciones con los operadores = y <………………………………….121
CAPÍTULO 5. TÉCNICAS DE BACKTRACKING Y VORAZ ……………………………123
5.1 CONTROL ÓPTIMO CON BACKTRACKING……………………………………………..125
5.2 ALGORITMOS DE BACKTRACKING………………………………………………………..126
5.3 DISEÑO VORAZ………………………………………………………………………………………..127
5.4 OPTIMIZAR UNA DIETA…………………………………………………………………………..128
5.5 CUESTIONES…………………………………………………………………………………………….130
5.5.1 El laberinto …………………………………………………………………………………………..130
5.5.2 Todas las sumas de n cifras…………………………………………………………………….131
5.5.3 El cruce de calles con semáforos……………………………………………………………..131

5.5.4 El cruce de calles con semáforos (Voraz) …………………………………………………133
5.5.5 Oficinas de correos………………………………………………………………………………..133
5.5.6 El problema del cambio de monedas (Voraz) ……………………………………………134
5.5.7 Árbol de recubrimiento mínimo. Algoritmo de Kruskal……………………………..134
5.5.8 Expresión lógica inconsistente………………………………………………………………..135
5.5.9 Asignación de n tareas a n agentes………………………………………………………….135
5.5.10 El problema del viajante con prisa …………………………………………………………136
5.5.11 Horario de clase…………………………………………………………………………………..136
5.5.12 Paradas de autobús ………………………………………………………………………………136
5.5.13 Paradas de autobús Voraz …………………………………………………………………….137
5.5.14 Sudoku……………………………………………………………………………………………….137
5.6 SOLUCIONES A LAS CUESTIONES PLANTEADAS ………………………………….139
5.6.1 El laberinto …………………………………………………………………………………………..139
5.6.2 Todas las sumas de n cifras…………………………………………………………………….140
5.6.3 El cruce de calles con semáforos……………………………………………………………..141
5.6.4 El cruce de calles con semáforos (Voraz) …………………………………………………142
5.6.5 Oficinas de correos………………………………………………………………………………..142
5.6.6 El problema del cambio de monedas (Voraz) ……………………………………………145
5.6.7 Árbol de recubrimiento mínimo. Algoritmo de Kruskal……………………………..145
5.6.8 Expresión lógica inconsistente………………………………………………………………..147
5.6.9 Asignación de n tareas a n agentes………………………………………………………….149
5.6.10 Subredes interesantes …………………………………………………………………………..150
5.6.11 El problema del viajante con prisa …………………………………………………………153
5.6.12 Horario de clases …………………………………………………………………………………154
5.6.13 Paradas de autobús Backtracking…………………………………………………………..156
5.6.14 Paradas de autobús Voraz …………………………………………………………………….156
5.6.15 Sudoku……………………………………………………………………………………………….157
CAPÍTULO 6. RAMIFICACIÓN Y ACOTACIÓN ……………………………………………..161
6.1 EL PROBLEMA DE LA ASIGNACIÓN ……………………………………………………….162
6.2 OTRAS MEJORAS……………………………………………………………………………………..165
6.3 CUESTIONES…………………………………………………………………………………………….165
6.3.1 La asignación de n tareas a n agentes………………………………………………………165
6.3.2 Murallas……………………………………………………………………………………………….165
6.4 SOLUCIONES ……………………………………………………………………………………………166
6.4.1 La asignación de n tareas a n agentes………………………………………………………166
6.4.2 Murallas……………………………………………………………………………………………….167
CAPÍTULO 7. ALGORITMOS PROBABILISTAS ……………………………………………..171
7.1 CLASIFICACIÓN DE LOS ALGORITMOS PROBABILISTAS……………………..172
7.2 FUNCIONES PREVIAS ………………………………………………………………………………172
7.3 LISTAS CON SALTOS ORDENADA…………………………………………………………..173
7.4 ALGORITMOS DE MONTE CARLO…………………………………………………………..175
7.5 COMPROBACIÓN DE LA PRIMALIDAD …………………………………………………..176
7.6 ALGORITMOS DE LAS VEGAS…………………………………………………………………179

7.7 CUESTIONES…………………………………………………………………………………………….181
7.7.1 Verificación de un producto matricial………………………………………………………181
7.7.2 El problema de las 8 reinas …………………………………………………………………….183
7.7.3 Seleccionar el k-ésimo elemento menor de un vector…………………………………183
7.7.4 Factorización de un número natural n………………………………………………………184
BIBLIOGRAFÍA BÁSICA…………………………………………………………………………………..187
ÍNDICE ALFABÉTICO………………………………………………………………………………………189