PDF de programación - Introducción a la metodología de diseño descendente

Introducción
a la metodología
de diseño
descendente

Josep Vilaplana Pastó
M. Jesús Marco Galindo

PID_00149892

© FUOC • PID_00149892

Índice

Introducción a la metodología de diseño descendente

Introducción...........................................................................................

Objetivos ..................................................................................................

1. Diseño descendente..........................................................................
1.1. Análisis de problemas complejos ..................................................
1.2. ¿Análisis ascendente o descendente? ............................................
1.3. Orientaciones de las abstracciones................................................
1.4. Formas de trabajar y presentar el diseño descendente..................
1.5. Herramientas de la notación para abstraer datos..........................
1.6. Herramientas de la notación para abstraer código........................
1.7. Trabajando con profundidad el ejemplo.......................................
1.8. Valoración final de la metodología ...............................................
1.9. Últimas observaciones ...................................................................

5

8

9
9
10
12
13
16
19
21
26
28

Resumen...................................................................................................

29

Ejercicios de autoevaluación ..............................................................

37

Solucionario............................................................................................

41

Glosario....................................................................................................

56

Bibliografía.............................................................................................

57

© FUOC • PID_00149892

Introducción

5

Introducción a la metodología de diseño descendente

En este módulo aprenderemos a desarrollar algoritmos para problemas más
complicados que los que hemos visto hasta ahora. No introduciremos ningún
elemento más del lenguaje algorítmico. Lo que haremos, en todo caso, es ma-
durar el uso que daremos a algunos de los elementos, como por ejemplo la de-
claración de acciones, las funciones y la definición de nuevos tipos. Dicho de
otro modo, aquí propondremos una metodología por la cual llegaremos, si la
seguimos, al diseño de algoritmos correctos e inteligibles que solucionan enun-
ciados más complejos.

Pensad que...

... el seguimiento de la metodo-
logía que propondremos servi-
rá para que nuestros diseños se
hagan en un tiempo de desa-
rrollo mínimamente razonable,
de modo que aumente nuestro
grado de eficacia al producir al-
goritmos correctos. Recordad
los objetivos que nos habíamos
propuesto en el módulo “Intro-
ducción a la programación”.

Hasta ahora nos hemos dedicado, por un lado, a aprender la sintaxis y la semán-
tica de los elementos del lenguaje algorítmico. Con la resolución de problemas
sencillos hemos desarrollado la destreza al expresar nuestros algoritmos de for-
ma clara y no ambigua. A pesar de ello, para diseñar nuestros primeros algorit-
mos hemos estudiado unas pautas metodológicas basadas en la aplicación de los
esquemas de tratamiento secuencial. El uso de estos esquemas nos ayuda a evi-
tar errores típicos en los que podemos caer, así como a formular algoritmos in-
teligibles.

Así pues, la metodología que se imparte en este curso no es exclusiva de este
módulo, sino que en los módulos anteriores ya se ha propuesto de forma pro-
gresiva una metodología que hay que seguir para problemas más sencillos que
los que encontraremos a partir de este momento. Sin embargo, todo lo que he-
mos aprendido gracias a estos problemas más sencillos nos servirá también
para los problemas complejos que propondremos más adelante.

Los problemas sencillos que hemos estado resolviendo se caracterizan por te-
ner una solución que utiliza un número razonable de elementos básicos del
lenguaje algorítmico.

Los enunciados de los problemas sencillos hacen referencia a objetos
que están muy cercanos a los tipos elementales de lenguaje o que son
directamente representables por éstos.

El tratamiento que hay que aplicar a estos objetos se puede alcanzar con unas
pocas asignaciones y con algunas construcciones algorítmicas. El resultado fi-
nal es un algoritmo comprensible y legible en términos de los elementos bási-
cos del lenguaje algorítmico.

© FUOC • PID_00149892

6

Introducción a la metodología de diseño descendente

Al desarrollar aplicaciones más reales, nos encontramos con problemas gran-
des y complejos.

¿Os imagináis...

... lo que conseguiríamos si ex-
pusiésemos el funcionamiento
de un programa en términos
del movimiento de electrones
que hay por las pistas de cobre
de la placa de circuito impreso
y en el silicio de vuestro orde-
nador? Acabaríamos confundi-
dos y distraídos por el exceso
de información en la exposi-
ción, y perderíamos toda refe-
rencia a aquello de lo que
estamos hablando.

Los enunciados de problemas complejos hacen referencia a objetos que
no tienen una correspondencia directa con los tipos elementales de la
notación algorítmica.

El tratamiento de estos objetos puede no ser elemental y, asimismo, también
puede llevar a un número de sentencias y declaraciones excesivamente eleva-
do, si expresamos todo lo que hay que hacer como una composición secuen-
cial de asignaciones, iteraciones y/o alternativas.

El resultado es un algoritmo de muchas páginas, difícil de seguir y, por lo tan-
to, también de saber si funciona, y lleno de detalles (algunas veces repetidos)
que lo hacen prácticamente ilegible. El número de detalles que hay que tener
en cuenta es excesivo, y nuestra capacidad de ser conscientes de todos los de-
talles es limitada. Pensar estos enunciados en términos de los elementos bá-
sicos del lenguaje, sin unas pautas que seguir, nos puede comportar muchos
quebraderos de cabeza y bastante dispersión mental, de forma que disminu-
ye nuestra capacidad de comprensión sobre lo que hacemos y, por lo tanto,
nuestra seguridad sobre si estamos realizando un algoritmo correcto y legible
(mantenible). Con estas circunstancias, llegamos a la conclusión de que la no-
tación algorítmica es tan elemental que hace incómodo y poco práctico el de-
sarrollo de aplicaciones reales, y de que haría falta un lenguaje más cómodo
que comprendiese objetos más reales.

Si este apreciado lenguaje existiese, con la cantidad y la variedad de problemas
que hay por resolver, tendría un número tan grande de acciones y tipos que
nunca acabaríamos de conocerlo a fondo. Se pueden encontrar algunos len-
guajes específicos para algunas aplicaciones concretas, pero cuando no los en-
contramos, ¿qué hacemos?

La notación algorítmica tiene los suficientes elementos para construir
cualquier algoritmo que deseemos a partir de los tipos elementales, la
asignación y las composiciones algorítmicas. El lenguaje algorítmico
también permite ampliar el propio lenguaje definiendo y construyendo
tipos más complejos y definiendo las acciones y/o funciones que más
nos convengan.

Con las características del lenguaje algorítmico, todo lo que nos hace falta es
saber qué metodología debemos seguir para llevar a buen fin el diseño de un
problema complejo. Esta metodología consistirá en descomponer un proble-

© FUOC • PID_00149892

7

Introducción a la metodología de diseño descendente

ma complejo en subproblemas más sencillos e independientes entre sí. La so-
lución de estos subproblemas implicará la solución del problema. Por otro
lado, la descomposición del problema se hace mediante la abstracción.

La abstracción es el resultado de aislar ciertos aspectos (cualidad, atribu-
tos, etc.) de un todo para poder razonar o pensar de forma más cómoda
y menos dispersa (en nuestro caso, para la solución de problemas).

En el fondo, se trata de simplificar alguna realidad y reducirla sólo a los aspec-
tos que tengan una especial relevancia o un interés determinado para lo que
estamos pensando o haciendo.

Hemos estado utilizando la abstracción prácticamente desde el inicio del cur-
so: el modelo de secuencia, los esquemas (que podríamos considerar como al-
goritmos abstractos), etc. A partir de este módulo, sin embargo, tendremos que
aprender a abstraer de forma más adecuada problemas más complejos que los
que hemos trabajado hasta ahora. Deberemos descomponer el problema en
subproblemas más sencillos. Este módulo os proporcionará las técnicas nece-
sarias para hacerlo (herramientas de la notación para abstraer datos y abstraer
código) y una metodología a seguir (diseño descendente).

© FUOC • PID_00149892

Objetivos

8

Introducción a la metodología de diseño descendente

Cuando hayáis estudiado este módulo, seréis capaces de:

• Analizar problemas de cierta complejidad y descomponerlos en subproble-
mas más sencillos, aplicando la técnica de diseño descendente por refina-
mientos sucesivos.

• Saber que hay descomposiciones de problemas más convenientes y efectivas
que otras para el diseño. La elección de abstracciones convenientes al pro-
blema y el seguimiento de las pautas indicadas en este módulo os llevarán a
descomposiciones efectivas.

• Aplicar los conceptos estudiados en los módulos anteriores para resolver
cada uno de los subproblemas sencillos, utilizando la abstracción de código
y datos.

• Desarrollar algoritmos de forma efectiva y en un tiempo razonable para re-

solver problemas más reales.

© FUOC • PID_00149892

9

Introducción a la metodología de diseño descendente

1. Diseño descendente

1.1. Análisis problemas complejos

Como ya hemos adelantado en la introducción, la forma de enfrentarse a un
problema complejo consiste en descomponerlo en una colección de subproble-
mas más sencillos e independientes, de forma que la solución de estos subpro-
blemas implique la solución del problema en cuestión. Al mismo tiempo,