ALGORITMOS

Un algoritmo es un método paso a paso para resolver algunos problemas. Los enfoques de este tipo para resolver problemas no son novedad; de hecho, la palabra “algoritmo” se deriva del nombre del matemático persa del siglo _IX, al-Khowa¯rizmi. En la actualidad, “algoritmo” suele referirse a una solución ejecutable por una computadora. En este libro, la preocupación principal será que se pueda ejecutar en una computadora “tradicional”, es decir, una compu- tadora personal, con un solo procesador que ejecute instrucciones paso a paso.

Después de introducir los algoritmos y proporcionar varios ejemplos, nos dedicare- mos al análisis de los algoritmos, es decir, al tiempo y espacio requeridos para ejecutarlos. Concluiremos con un examen de los algoritmos recursivos, los que se refieren o recurren a sí mismos.

Por lo general, los algoritmos tienen las siguientes características:

■                    Entrada El algoritmo recibe datos de entrada.

■                    Salida El algoritmo produce una salida.

■                    Precisión Los pasos se establecen con precisión.

Determinismo   Los resultados intermedios de cada paso de ejecución son únicos y están determinados sólo por las entradas y los resultados de los pasos anteriores

■ Carácter finito El algoritmo termina; es decir, se detiene después de ejecutar un número finito de instrucciones.

■  Corrección La salida producida por el algoritmo es correcta; es decir, el algorit- mo resuelve el problema sin errores.

■  Generalidad   El algoritmo se aplica a un conjunto de entradas.

Como ejemplo, considere el siguiente algoritmo que encuentra el máximo de tres números

a, b y c:

1.  grande = a,

2.  Si b > grande, entonces grande = b,

3.  Si c > grande, entonces grande = c.

=

(Como se explica en el apéndice C, es el operador asignación.)

La idea del algoritmo es inspeccionar los números uno por uno y copiar el valor más grande encontrado a la variable grande. En la conclusión del algoritmo, grande será igual al valor mayor de los tres números.

Ahora se muestra la manera en que el algoritmo anterior se ejecuta para algunos va- lores específicos de a, b y c. Esta simulación se llama seguimiento o rastreo. Primero su- ponga que

a = 1,                                                                                                     b = 5,  c = 3

En la línea 1, grande tiene el valor de a (1). En la línea 2, b > grande (5 > 1) es verdade- ra, de manera que grande es igual a b (5). En la línea 3, c > grande (3 > 5) es falsa, y no hay cambio. En este punto grande es 5, el valor mayor entre a, b y c.

Suponga que

a = 6,                                                                                                     b = 1,  c = 9

En la línea 1, grande tiene el valor de a (6). En la línea 2, b > grande (1 > 6) es falsa, y no hay cambio. En la línea 3, c > grande (9 > 6) es verdadera, de manera que grande es igual a 9. En este punto grande es 9, el valor mayor entre a, b y c.

Se verifica que el ejemplo de algoritmo tiene las propiedades establecidas al inicio de esta sección.

El algoritmo recibe los tres valores a, b y c como entrada y produce el valor grande

como salida.

Los pasos del algoritmo se establecen con suficiente precisión de manera que éste puede escribirse en un lenguaje de programación y ser ejecutado por una computadora.

A partir de los valores de entrada, cada paso intermedio de un algoritmo produce un resultado único. Por ejemplo, dados los valores

a = 1,                                                                                                     b = 5,  c = 3,

en la línea 2, grande tiene el valor 5 sin importar quién ejecuta el algoritmo.

El algoritmo termina después de un número finito de pasos (tres pasos) y contesta co- rrectamente la pregunta planteada (encontrar el mayor de tres valores de entrada).

El algoritmo es general; permite encontrar el valor más grande de cualesquiera tres números.

La descripción de qué es un algoritmo será suficiente para las necesidades de este li- bro. Sin embargo, debe observarse que es posible dar una definición matemática precisa de “algoritmo” (vea las notas del capítulo 12).

++

Aunque el lenguaje común en ocasiones es adecuado para especificar un algoritmo, la mayoría de los matemáticos y los especialistas en ciencias de la computación prefieren el seu- docódigo por su precisión, estructura y universalidad. El seudocódigo recibe este nombre porque se parece a un código real en lenguaje de computadora, como C y Java. Existen muchas versiones de seudocódigo. A diferencia de los lenguajes para computadora que deben preocuparse por puntos y comas, mayúsculas y minúsculas, palabras reservadas y otros ele- mentos, cualquier versión de seudocódigo es aceptable siempre y cuando sus instrucciones no sean ambiguas. Nuestro seudocódigo se describe con detalle en el apéndice C.

En cuanto al ejemplo de un algoritmo escrito en seudocódigo, se escribe el primer al- goritmo de esta sección que encuentra el máximo de tres números.

Nuestros algoritmos consisten en un título, una breve descripción del algoritmo, la entrada y la salida del algoritmo, y las funciones que contienen las instrucciones del algo- ritmo. El algoritmo 4.1.1 consta de una sola función. Para hacer más conveniente la refe- rencia a las líneas individuales dentro de una función, en ocasiones se numeran algunas de ellas. La función del algoritmo 4.1.1 tiene ocho líneas numeradas.

Cuando se ejecuta la función del algoritmo 4.1.1, en la línea 2 se hace grande igual a a. En la línea 3 se comparan b y grande. Si b es mayor que grande, se ejecuta la línea 4

grande = b

pero si b no es mayor que grande, se salta a la línea 5. En la línea 5 se comparan c y gran- de. Si c es mayor que grande, se ejecuta la línea 6

grande = c

pero si c no es mayor que grande, se salta a la línea 7. Así, al llegar a la línea 7, el valor de

grande será correctamente el mayor entre a, b y c.

En la línea 7 se regresa el valor de grande, que es igual al mayor de los números a, b y c, al que invoca la función y la termina. El algoritmo 4.1.1 ha encontrado correctamente el mayor de los tres números.

El método del algoritmo 4.1.1 resulta útil para encontrar el valor más grande en una sucesión.

Para el paso base (i = 1), se observa que antes de que inicie la ejecución del ciclo “for”,

se asigna a grande el valor s1; entonces grande es sin duda el valor mayor de la subsucesión s1. Suponga que grande es el valor mayor en la subsucesión s1, . . . , si. Si i < n es ver- dadera (de manera que el cuerpo del

ciclo “for” se ejecuta de nuevo), i se convierte en i +

1.                                                                                                                     

+

Suponga primero que si+1 > grande. Entonces si+1 es el valor mayor en la subsucesión s1, . . . , si, si+1. En este caso, el algoritmo asigna a grande el valor si+1. Ahora grande es igual al mayor valor en la subsucesión s1, . . . , si, si+1. Suponga ahora que si+1 ≤ grande. Entonces se concluye que grande es el valor mayor en la subsucesión s1, . . . , si, si 1. En este caso, el algoritmo no cambia el valor de grande; así, grande es el mayor valor en la subsucesión s1, . . . , si, si+1. Se ha probado el paso inductivo; por lo tanto, grande es el mayor valor en la subsucesión s1, . . . , si es un ciclo invariante. El ciclo “for” termina cuando i = n. Como

grande es el mayor valor en la subsucesión s1, . . . , si es un ciclo invariante, en este punto grande es el valor más grande en la subsucesión s1, . . . , sn. Por lo tanto, el algoritmo 4.1.2 es correcto.