PDF de programación - 7. Diseño de Algoritmos

7. Diseño de Algoritmos

Como ya hemos mencionado, el principio básico del diseño descendente es “tratar de
resolver un problema mediante la resolución de problemas más simples”. En este capítulo
ahondaremos en el diseño de algoritmos iterativos.

En la sección 7.1 presentamos estrategias de solución de problemas basadas en el diseño
descendente. Presentaremos en la sección 7.2 esquemas de algoritmos básicos de
tratamiento secuencial.

Como vimos en la sección 3.2, el diseño descendente también se denomina técnica de
refinamiento sucesivo. Hasta el momento hemos aplicado el diseño descendente sólo para
refinar acciones abstractas en términos de acciones cada vez menos abstractas, es decir, que
se acercan cada vez más a las instrucciones propias de nuestro lenguaje de programación.
Sin embargo, cuando hacemos un primer algoritmo para resolver un problema, las acciones
describen realmente la interacción de los objetos involucrados en el enunciado del
problema. Por lo tanto no basta con refinar las acciones entre objetos sino que es preciso
refinar (o representar) los objetos abstractos en términos de objetos más concretos. Con
frecuencia, los objetos involucrados en el enunciado del problema no son directamente
representables en lenguajes de programación convencionales (por ejemplo, los conjuntos);
de allí la necesidad de refinar datos. La representación de objetos abstractos en términos de
objetos concretos lo llamamos refinamiento de datos, y presentaremos una metodología a
seguir para llevar a cabo tal representación.

7.1. Diseño Descendente

La metodología de diseño descendente de programas consiste en:

1) Definir una solución de un problema en términos de la composición de soluciones
de problemas que a priori son más sencillos de resolver, o de esquemas de solución
ya conocidos.

2) La primera solución del problema corresponderá a una composición de acciones
sobre los objetos al más alto nivel de abstracción, es decir, a los involucrados en la
especificación del problema.

3) Aplicar refinamiento sucesivo, el cual consiste en refinar tanto las acciones como

los datos hasta conseguir que el algoritmo inicial se convierta en un programa.

En esta sección ahondaremos en la práctica del diseño descendente, tanto en refinamiento
de acciones como de datos. Hasta el momento hemos aplicado el diseño descendente sólo
para refinar acciones abstractas en términos de acciones cada vez menos abstractas, es
decir, que se acercan cada vez más a las instrucciones propias de nuestro lenguaje de
programación. Sin embargo, cuando hacemos un primer algoritmo para resolver un
problema, las acciones describen realmente la interacción de los objetos involucrados en el
enunciado del problema. Por lo tanto no basta con refinar las acciones entre objetos sino
que es preciso refinar (o representar) los objetos abstractos en términos de objetos más
concretos, a esto último es a lo que llamamos refinamiento de datos. En los ejemplos de

131

diseño descendente vistos hasta ahora, no fue necesario refinar los datos pues estos
correspondían a tipos no estructurados, como los números enteros, los booleanos, etc.,
considerados tipos básicos de nuestro pseudolenguaje que no hace falta refinar.

El principio básico del diseño descendente es “se debe programar hacia un lenguaje de
programación y no en el lenguaje de programación”, lo que significa partir de algoritmos en
términos de los objetos involucrados en la especificación original del problema e ir
refinándolos hasta obtener un programa en el lenguaje de programación que hayamos
escogido. Una vez que un primer algoritmo correcto es encontrado, podemos cambiar la
representación de los objetos por otros para mejorar, por ejemplo, la eficiencia (en el
Capítulo 9 hablaremos de eficiencia) y/o implementarlos en el lenguaje de programación.

Cada objeto involucrado en la especificación de un problema posee una estructura y
propiedades que lo caracteriza. Esta estructura y propiedades definen la clase o el tipo del
objeto. Mas concretamente, una clase de objetos se define por un conjunto de valores y un
comportamiento que viene expresado por operaciones sobre ese conjunto de valores; por
ejemplo, el tipo número entero tiene como conjunto de valores {..., -1, 0, 1, 2, 3, ...} y
como operaciones la suma, la resta, la multiplicación, etc. El tipo secuencia de caracteres
tiene como conjunto de valores a las funciones de [0..n) en los caracteres, cualquiera sea el
número natural n, y algunas operaciones son obtener el primero de la secuencia, insertar un
elemento en una posición dada de una secuencia, etc.

En un lenguaje de programación moderno, como JAVA, que permite definir clases de
objetos, el refinamiento de datos se efectúa construyendo una unidad de programa aparte,
llamada igualmente clase, que contiene segmentos de programa que implementan por una
parte la representación de los objetos en términos de las estructuras de datos que ofrece el
lenguaje y por otra parte, las operaciones de la clase. Decimos que JAVA permite
encapsular la implementación de tipos abstractos de datos. El encapsulamiento de datos
conlleva al ocultamiento de datos, es decir, el programador que sólo desea manipular
objetos de un determinado tipo de datos no tiene por qué preocuparse por cómo se
representa ese tipo en función de tipos concretos; lo que realmente le interesa es poder
operar con objetos de ese tipo, y por lo tanto la implementación puede permanecer oculta al
programador, permitiéndole así no involucrarse con los detalles de implementación del
tipo.

7.1.1. Tratar de resolver un problema en términos de problemas más
simples

El término “más simple” puede significar diferentes cosas según el contexto. Un problema
puede ser más simple debido a que algunas de sus restricciones han sido omitidas
(resultando en una generalización del problema). El problema puede ser más simple porque,
al contrario, le hemos agregado restricciones. Cualquiera sea el caso, la estrategia de
resolver un problema en términos de problemas más simples consiste entonces primero que
nada en tratar de identificar y resolver casos mas simples del mismo problema y tratar de
resolver el problema original utilizando la solución de los casos más simples

132

Ejemplo:

Problema: Se quiere encontrar un programa que intercambie dos segmentos de un arreglo b
con dominio [m..p), es decir, dados m< n < p y el arreglo b de la figura siguiente:

m
B[m..n)

n

p-1

B[n..p)

b:

Donde B es el valor original del arreglo b. El arreglo b quedará modificado como en la
figura siguiente:

m
B[n..p)

m+p-n

p-1

B[m..n)

b:

El programa sólo podrá declarar un número constante de variables adicionales de tipos
básicos y utilizar sólo operaciones de intercambio de dos elementos de un arreglo más las
propias a de los tipos básicos.

Solución:

¿Cómo comenzaríamos?. Si los dos segmentos del arreglo son del mismo largo tendríamos
un problema más simple que resolver (ejercicio: Hacer un procedimiento llamado
IntercambiarIguales que intercambie dos segmentos disjuntos de igual largo de un arreglo,
se pasará como parámetros el arreglo, el índice inicial de cada segmento y el largo de los
segmentos a intercambiar). Supongamos que el procedimiento IntercambiarIguales
consiste en intercambiar dos segmentos disjuntos de igual largo. Veamos si podemos
resolver nuestro problema en términos de este problema más simple.

Suponga por el momento que el segmento b[m..n) es mas largo que b[n..p). Consideremos
que el segmento b[m..n) consiste de dos segmentos, el primero de los cuales es del mismo
largo que b[n..p) (ver diagrama (a) dado más abajo). Entonces los segmentos de igual largo
x1 y y pueden ser intercambiados obteniéndose el diagrama (b); además, el problema
original puede ser resuelto intercambiando los segmentos x2 y x1. Estas dos secciones
pueden ser de distintos largos, pero el largo del mayor segmento es menor que el largo del
mayor segmento del problema original, por lo que hemos hecho algún progreso.

m

m

x1

y

b:

b:

m+p-n

x2

m+p-n

x2

p-1

p-1

n

n

y

x1

(a)

(b)

Ahora supongamos que en lugar del primer segmento del problema original, es el segundo
segmento el que tiene largo mayor, es decir, b[n..p) es más grande. Este caso es ilustrado en

133

el diagrama (c), y el procedimiento IntercambiarIguales puede ser utilizado para
transformar el arreglo como en el diagrama (d).

(c)

(d)

m

m

y

x2

b:

b:

n

n

x1

x1

m+p-n p-1

x2

m+p-n p-1

y

Ahora tratemos de llevar esta idea a un programa. Los diagramas (b) y (d) indican que
después de ejecutar IntercambiarIguales, n siempre es el índice inferior de la sección más a
la derecha a ser intercambiada. Lo cual es cierto también al comienzo.

Supongamos que en (b) x1 es mas largo que x2, tendremos la situación siguiente:

(b’)

b:

m

y

m+p-n
x2

n

x1

1

p-1

x2

1

Donde x1 = x1
mediante IntercambiarIguales obtenemos:

1 , x2 y x2

1x2

1 tienen el mismo largo. Después de intercambiar x2 y x2

1

(b’’)

b:

m

y

h

x2

1

n

x1

1

k

p-1

x2

Note que los segmentos [m..h) y [k..p) ya están en el sitio que les corresponde, y hay que
intercambiar los subsegmentos [h..n) y [n..k) del segmento [h..k). Por lo tanto, podemos
obtener el invariante:

b:

m

Ya intercam-
biado

h
Intercambiar
con b[n..k)

n
Intercambiar
con b[h..n)

p-1
k
Ya intercam-
biado

Sin embargo, note que el algoritmo requiere la comparación de los largos de b[n..k) y
b[h..n). También, el procedimiento IntercambiarIguales requiere los largos de los
segm