Programas directos

Mis primeros ejemplos

Ejemplo 1: Preparación de una marinada

En un viejo libro de cocina, leo la siguiente receta, en la página 41:

«MARINADA

Tomillo - laurel - perejil - ajo - aceite - vinagre - sal - pimienta.

Ponga en un plato 2 partes de aceite por una de vinagre, el tomillo, el laurel, el perejil, el ajo picado fino, salpimiente e introduzca en la mezcla la carne que desea marinar. Puede dejarla marinar de 2 a 6 días, pero añada aceite y vinagre todos los días. Para el pescado, puede sustituir el vinagre por zumo de limón.»

Esta receta describe un algoritmo: ¿cómo hacer una marinada? A partir de los ingredientes enumerados, describe una sucesión de operaciones que los usan para obtener un resultado. La receta podría enumerar las distintas operaciones ordenándolas:

1. Mezclar en un plato 2 partes de aceite por una de vinagre. Para el pescado, sustituir el vinagre por zumo de limón.

2. Picar el ajo fino.

3. Añadir a la vinagreta el tomillo, el laurel, el perejil y el ajo picado.

4. Salpimentar.

5. Colocar la carne que desea marinar en la mezcla.

6. Durante un período de 2 a 6 días, añadir aceite y vinagre todos los días.

Ejemplo 2: Suma de dos números enteros

Todos los alumnos aprenden a sumar dos números enteros positivos en primaria. Para calcular la suma de 127 y 35, aprenden a «colocar» la suma, poniendo en columnas las cifras...

Definición informal de un algoritmo

Un algoritmo es la descripción de un procedimiento. Describe una sucesión de operaciones elementales, expresadas en un leguaje dado, para ejecutar en un orden determinado. La ejecución solo es posible cuando se cumplen determinadas condiciones. El ajo solo se añade después de picarlo o solo se puede calcular el umbral de activación c_a después de obtener la media de las ventas diarias m_v. La ejecución de las operaciones elementales de las que trata permite que el sistema considerado pase de un estado inicial I, representado por los valores de los atributos dados, a un estado final F, representado por los valores nuevos de los atributos y los resultados que se han de obtener. Para la suma, los atributos dados son los dos enteros a y b con sus respectivos valores, 127 y 35. El estado inicial se representa mediante estos dos valores. El resultado es 162 y el estado final está representado por los tres valores, 127, 35 y 162. La figura que aparece debajo representa los dos estados y la transición que hace pasar de uno a otro.

El estado inicial I o e₁ se caracteriza por los valores 127 y 35 de a y b, respectivamente. El estado final F o e₂ se caracteriza por los mismos valores, 127 y 35, y por el valor 162, que resulta de la suma de a y b.

Del mismo modo, el estado inicial I del ejemplo de gestión de stock está formado por los valores de los atributos c_s, t_r y v₁, v₂, ..., v₁₂. El estado final F se representa por los valores de c_s, v₁, v₂, ..., v₁₂ y el valor de un atributo resultado, llamémoslo...

Especificaciones

Cuando se busca escribir un algoritmo, una tarea importante consiste en especificarlo. Se trata de decir, de la manera más precisa posible, qué hace el algoritmo sin explicar cómo lo hace. En este sentido, especificar un algoritmo es plantear formalmente el problema que resuelve, como se puede ver en los apartados anteriores de este capítulo. Es una etapa difícil, pero indispensable para definir claramente el algoritmo y sus efectos. Esta sección introduce esta etapa de especificación mediante algunos ejemplos y ejercicios resueltos. Se completa a lo largo del libro, conforme vayamos construyendo las herramientas necesarias.

De hecho, esta etapa de especificación es el único objeto de estudio de este libro. Adicionalmente, este libro también muestra cómo realizar algoritmos sencillos, pero solo cuando las etapas de su construcción ponen de relieve su conformidad con las especificaciones. De esta manera se prepara la etapa de la prueba del algoritmo, pero esta etapa supera los objetivos de este libro. Vamos a estudiar un ejemplo.

Consideramos un semáforo que regula la circulación en un cruce.

Escribir el algoritmo que determina el color del semáforo durante el próximo cambio.

Solución

Un semáforo como este controla la circulación mediante tres colores: verde, naranja y rojo. Los colores se encadenan en este orden con una cadencia fijada. Cuando el color es rojo, el cambio hace pasar el semáforo a verde. Solo nos interesa el cambio de color, en otras palabras, la operación que hace cambiar de un color a otro en el orden determinado.

Supongamos que disponemos de una operación, creada por sucesor, que toma como entrada un color del conjunto C = {rojo; verde; naranja} y que devuelve su sucesor en la serie ordenada (verde; naranja; rojo). Con estas hipótesis, el algoritmo se escribe de la siguiente manera:

algoritmo: cambiar el color 
Entrada 
   c: un COLOR del conjunto {verde; naranja; rojo}  
Efecto 
    c = sucesor del valor antiguo de c 

Esta notación indica el nombre del algoritmo: cambiar el color. También indica que este algoritmo utiliza un dato...

Mis primeros algoritmos

Esta sección se complementa con la anterior mostrando, en algunos ejemplos básicos, las notaciones usadas para decir cómo realiza su cálculo un algoritmo, dicho de otro modo, cómo garantizar la transición desde el estado inicial I hasta el estado final F del sistema de software. Seguimos quedándonos, como en todo el capítulo, con ideas intuitivas no formalizadas, pero sin embargo rigurosas. Aquí también, el método se expone a partir de ejercicios resueltos.

Este ejercicio retoma el estudio del ejemplo 4 que empezó al inicio de la sección «Definición informal de un algoritmo».

Escribir las instrucciones que resuelven el problema propuesto.

Solución

Se trata de estudiar cuáles son las transiciones que harán pasar el sistema de software de su estado inicial I, donde conocemos los valores de los datos de entrada del problema, al estado final F donde se sabe si hay que realizar un reabastecimiento o no. Durante el estudio preliminar de este ejemplo, hemos visto que las etapas del cálculo se organizan según el siguiente plan:

Este algoritmo resuelve el problema y está completo si se sabe calcular una media. Para tener éxito presentando la solución de problemas más complejos, para los que esta forma sencilla de escritura en lenguaje natural no se ha adaptado, vamos a escribir la solución encontrada usando un formalismo un poco más restrictivo que el lenguaje natural.

Ahora se trata de decir cómo se han efectuado los cálculos de cada etapa para tomar la decisión.

Se obtiene la media de las ventas diarias m_v dividiendo el total de las ventas durante el año entre la cantidad de días laborables. Si consideramos 25 días laborables por mes, tenemos:

El umbral de activación c_a es el producto de esta media por el tiempo t_r de reabastecimiento: c_a = m_v x t_r

Como v_i, t_r y c_s son datos del problema, disponemos de todo lo necesario para organizar el cálculo completo. A continuación...

Ejercicios resueltos

Esta sección propone algunos ejercicios que requieren reflexionar un poco más. Se trata de preparar soluciones completas y listas para la etapa de implementación, incluso si un mismo problema puede dar lugar a distintas soluciones, todas correctas. Estas proposiciones de soluciones se desarrollan después de cada enunciado. En todas ellas, las notaciones se completan mediante las notaciones necesarias para su expresión. Sin embargo, invitamos al lector a reflexionar sobre estos problemas, a especificarlos y, si es posible, resolverlos de manera informal, por ejemplo, redactando las soluciones «en español» antes de estudiar las soluciones propuestas.

Dadas dos variables cualesquiera de un tipo T que no se ha determinado.

1. Escribir el algoritmo que intercambia los valores de estas dos variables.

Sean V₁ el valor del dato contenido en la variable v₁ y V₂ el valor contenido en v₂. Cuando el algoritmo termina, el dato contenido en la variable v₁ debe tener el valor V₂ y el contenido en v₂ debe tener el valor V₁.

Indicación: dadas una botella llena de agua y una botella llena de vino. ¿Cómo intercambiar los contenidos de las dos botellas sin mezclarlos?

La indicación anterior sugiere usar una variable intermedia para resolver el problema. ¿Se puede hacer de otra manera? Ese es el tema de la siguiente pregunta.

Suponemos que los objetos de tipo T a los que pertenecen los valores de las variables v₁ y v₂ se pueden sumar o restar. Es el caso de los números enteros o reales, por ejemplo. 

2. La misma pregunta que antes, pero el algoritmo propuesto solo hace sumas y restas, usando solo las variables v₁ y v₂.

Solución

Podemos empezar especificando el algoritmo. Es lo que hacemos aquí debajo. Observe que se trata de modificar los datos recibidos como entrada. Los valores que hay que intercambiar están contenidos en variables que debe modificar el algoritmo: se trata de un procedimiento.

Algoritmo intercambiar  
    # Intercambiar los valores de a y b. ...

Ejercicios

Las soluciones de los ejercicios propuestos no requieren el uso de ningún concepto nuevo. Para dar una solución completa a estos ejercicios solo se necesitan los conceptos estudiados en este capítulo, incluso si, a veces, hay una solución mejor que la que está a nuestro alcance en este momento. Cada ejercicio debe estar completamente especificado, la realización del algoritmo propuesto debe estar completa y, si procede, demostrada. Algunos enunciados son imprecisos de manera deliberada y, a veces, permiten distintas interpretaciones. Los algoritmos, para resolverlos, deben estar perfectamente definidos y no dejar ninguna ambigüedad. Por lo tanto, habrá que hacer elecciones que se dejan a la discreción del lector, pero que deben estar claramente enunciadas si no están justificadas.

1. Escribir un algoritmo que calcula el precio con todos los impuestos incluidos (TII) para un precio sin impuestos y un porcentaje de IVA dado.

2. Escribir un algoritmo que calcula el importe de los intereses generados por un capital invertido a un interés dado durante un tiempo dado, expresado en meses.

1. Escribir un algoritmo que calcula la media aritmética de tres números dados.

2. La misma pregunta para una media ponderada cuando se dan los números y los coeficientes de ponderación....

Resumen

Este capítulo ha abordado la escritura de algoritmos. Un algoritmo es la descripción de un procedimiento de cálculo compuesto de una sucesión de operaciones. Una función calcula un resultado a partir de datos que no modifica. Un procedimiento modifica un estado calculando los nuevos valores de los datos.

La elaboración de un algoritmo se descompone en dos fases que no se deben confundir. La especificación precisa lo que hace el algoritmo sin decir cómo lo hace. La especificación de un algoritmo forma parte de su documentación. Está compuesta de la firma del módulo de software, de la precondición y de la poscondición. La definición del algoritmo expresa mediante instrucciones cómo realiza el cálculo.

La precondición agrupa las condiciones que deben satisfacer los datos en la entrada para que el algoritmo calcule sus resultados. Deben ser simultáneamente VERDADERAS para que el algoritmo realice un cálculo «justo» que genere los resultados esperados. Garantizar estas condiciones es responsabilidad del cliente de software de los servicios. La poscondición expresa las garantías que aporta el algoritmo sobre el trabajo que realiza y los resultados que produce, en cuando se cumple la precondición.

La sintaxis para escribir un algoritmo no está sujeta a normas. No existe un «lenguaje...