Sinopsis

Este libro sobre algoritmia está destinado a todas las personas interesadas en el desarrollo de aplicaciones informáticas y que desean iniciarse o recordar las bases fundamentales de la programación. Aquí no se trata de programar con uno u otro lenguaje, sino de pensar en un problema para diseñar una solución abstracta. Este trabajo de reflexión y creación prepara la última fase de implementación y del ciclo vital del programa concreto.

En este libro el lector no encontrará una recopilación de algoritmos que luego tendría que adaptar para resolver problemas. Al contrario, es una introducción original y eficaz a la algoritmia para aprender a analizar un problema.

El libro está dividido en dos partes. En la primera parte se explican en detalle las ideas de algoritmia básica y el método de construcción razonada de un algoritmo imperativo. En ella, el autor explica con precisión la distinción entre la especificación y la realización de un algoritmo, y muestra que el algoritmo propiamente dicho termina donde empieza la programación. En la segunda parte, el autor propone soluciones a problemas más elaborados en diversos campos del cálculo automático, como la simulación de fenómenos aleatorios o el encriptado de datos.

Todas las actividades propuestas son básicas, con una preocupación constante por dar preferencia al razonamiento que conduce a la elaboración de los algoritmos.

Índice

¿Qué es la algoritmia?

1. ¿ Qué es la algoritmia ?
2. Estructura del libro
3. Público objetivo
4. Convenciones adoptadas

Programas directos

1. Introducción
2. Mis primeros ejemplos
3. Definición informal de un algoritmo
4. Especificaciones
5. Mis primeros algoritmos
6. Ejercicios resueltos
7. Ejercicios
8. Resumen

La alternativa

1. Introducción
2. Definición de la alternativa
3. Ejercicios resueltos
4. Ejercicios
5. Resumen

Estructuras elementales

1. Introducción
2. Las cadenas de caracteres
2.1 Los caracteres
2.2 Las cadenas de caracteres
2.3 Ejercicios de aplicación en las cadenas de caracteres
3. La tabla
3.1 Las tablas simples
3.2 Tablas compuestas
3.3 Dos funciones útiles en las tablas
3.3.1 La función pertenece
3.3.2 La función sub_tabla
3.4 Ejercicios de aplicación en las tablas
4. Definir un tipo de datos nuevo
4.1 Definir un tipo de datos
4.2 Explicación de los invariantes
4.3 Ejercicios de aplicación en los tipos de datos
5. Resumen

Iteración

1. Introducción
2. Mis primeros ejemplos de construcción de iteraciones
2.1 La tabla de multiplicar
2.1.1 El problema
2.1.2 Construcción de la iteración
2.1.3 Otra versión
2.2 Iterar en una tabla
2.2.1 Posición del componente mínimo de una tabla
2.2.2 Buscar en una tabla ordenada
2.2.3 Búsqueda por dicotomía
2.2.4 Extensiones
3. Explorar una tabla
3.1 Buscar una identidad: el problema
3.2 Escribir el algoritmo buscar_identidad
3.3 Uso: borrar todos los clientes de identidad dada
3.4 Definición de buscar_identidad
3.5 Envejecer a los clientes
3.6 Ejercicios
4. ¿ Algoritmo o programa ?
4.1 Un ejemplo edificante
4.1.1 Algunas torpezas: las notaciones
4.1.2 Cuando los errores hacen olvidar las torpezas
4.2 Una solución al problema de la media
4.3 Completar el ejercicio: las especificaciones que faltan
4.4 Completar el ejercicio: llenar la tabla
5. Ejercicios de aplicación
6. Resumen

Recursividad

1. Introducción
2. Introducción a la recursividad: las cadenas de caracteres
2.1 Presentación de la recursividad
2.2 Algunos ejemplos de especificaciones recursivas
2.3 Ejercicios resueltos
2.4 Ejercicios
3. Los números y la recursividad
3.1 Aritmética
3.2 Factorial y otros ejercicios usados
3.3 Fracciones
3.4 Función real
4. Números y cadenas de caracteres: edición de un número entero
5. Problemas
5.1 Búsqueda por dicotomía en una tabla ordenada
5.2 Palíndromos
5.3 La bandera de Dijkstra
6. Resumen

¿Recursividad o iteración?

1. Introducción
2. Recordamos la recursividad
2.1 Primer ejemplo
2.2 Segundo ejemplo
2.3 Tercer ejemplo
3. ¿ Recursividad o iteración ?
4. Ejercicios
5. Resumen

Ordenar

1. Introducción
2. Especificar un algoritmo de orden
2.1 Presentación del problema del orden
2.2 Estudio de la poscondición del orden
3. Algunos algoritmos simples
3.1 Orden por permutaciones: introducción
3.2 Orden por permutaciones
3.3 Ordenación «de burbuja» (bubble sort)
3.4 Otras maneras de ordenar por permutaciones
4. Fusionar dos tablas ordenadas
4.1 Definición de un vector
4.1.1 Definición de los predicados
4.1.2 Primitivas de colocación dentro del vector
4.1.3 Acceso a los componentes del vector
4.1.4 Ejemplos
4.2 Fusión de dos vectores ordenados
4.2.1 Especificación del algoritmo de fusión
4.2.2 Análisis de la fusión
5. Ejercicios
5.1 Ordenación por inserción dicotómica
5.2 Una ordenación topológica
5.3 Completar las especificaciones
6. Resumen

Edición de un número

1. Introducción
2. Edición de un número entero en una base cualquiera
2.1 Número de cifras de un número entero
2.2 Resolución del problema de edición
2.3 Resolución del problema recíproco
3. Conversión de las direcciones de Internet
3.1 Conversión de un número entero en dirección «Internet Protocol»
3.1.1 Introducción
3.1.2 Conversión de una dirección IPv4 en un número entero
3.1.3 Conversión de una dirección entera en una dirección IPv4
3.2 Ejercicio
4. Conversión de un número entero en números romanos
5. Verificación de identificadores de empresas
6. Verificación de los identificadores de libros
7. Resumen

Introducción a los archivos

1. Introducción
2. Conceptos básicos
2.1 Archivos y artículos
2.2 Organización y acceso a los archivos
2.3 Asociación de un archivo físico a un programa
3. Organización secuencial
3.1 Introducción
3.2 Tratamiento de un archivo secuencial en modo lectura
3.3 Recorrido de un archivo secuencial
3.4 Tratamiento de escritura de un archivo secuencial
3.5 Actualización de un archivo a organización secuencial
4. La organización directa y el acceso selectivo
4.1 Correspondencia con la ayuda de una tabla de acceso
4.2 Correspondencia mediante una función de reparto
5. Problemas
5.1 Estadísticas de importación/exportación
5.2 Utilizar un cuestionario de actitud
5.3 Utilizar las respuestas a una encuesta de utilidad pública
5.4 Buscar los anagramas en un diccionario
6. Resumen

Simular

1. Introducción
2. Generar números pseudoaleatorios
2.1 Algunos generadores
2.1.1 El generador 147
2.1.2 Generadores de Hamming
2.2 Probar una serie de números pseudoaleatorios
2.2.1 Prueba del histograma
3. Juegos de azar
3.1 Simular una ruleta
3.2 Simular un dado
4. Simulación del proceso dinámico
4.1 Propagación de un rumor
4.2 Carrera de persecución
5. Simulación estadística de fenómenos deterministas
5.1 Calcular p
5.2 Evaluar una integral definida
6. Simulación de fenómenos aleatorios
6.1 Cazar moscas
6.2 Propagación de un rumor
6.3 Fiabilidad de los sistemas
6.4 Dispersión de los valores de los componentes de un circuito electrónico
7. Resumen

Encriptar