Translate

sábado, 26 de enero de 2013

Técnicas de Diseño de Algoritmos.


Diseño e Implementación.

Un algoritmo y los programas que lo implementan en una máquina específica puede analizarse a diferentes niveles de abstracción.

·         Nivel alto de abstracción, está la representación por medio de las especificaciones (requerimientos) que constituyen una descripción general de lo que hace el algoritmo, y el software asociado a él, es decir cuál es el problema que resuelve y de qué modo lo resuelve.

·         Nivel bajo de abstracción, el algoritmo, y sus programas que lo representan, se expresa por medio de una lista de instrucciones en lenguaje de máquina (código ejecutable), que finalmente realizan todo el proceso lógico expresado en la programación a partir del algoritmo diseñado. Ambos niveles de abstracción son descripciones exactas del algoritmo, pero son tan diferentes que con frecuencia se pierde la perspectiva de cómo una abstracción se convierte en la otra.

El esfuerzo y las técnicas implicadas en ir desde las especificaciones, hasta el lenguaje de máquina, está constituido alrededor de niveles intermedios de abstracción.

Diseño descendente (Top-Down).

El proceso del Diseño descendente se caracteriza por ser una estrategia del tipo dividir-para-conquistar, que implica la descomposición del problema original en varios sub-problemas cada uno de los cuales es de más fácil manejo y solución. Puesto que las relaciones entre los sub-problemas se establecen igualmente desde las primeras etapas, cada sub-problema se puede considerar y resolver independientemente. A medida que el proceso de descomposición funcional avanza, los algoritmos resultantes contienen más y más detalles descriptivos de la solución del problema inicialmente planteado.

La descomposición funcional es un factor crucial en el proceso del Diseño descendente por cuanto los algoritmos finales dependen de las decisiones hechas en el proceso de descomposición. Son fundamentales aquí: la experiencia y el conocimiento del analista y del diseñador, tanto a nivel del dominio del problema planteado como a nivel de las técnicas involucradas en el proceso de análisis y diseño.

Descomposición funcional.

Como su nombre lo implica, la Descomposición Funcional permite identificar y expresar en cada nivel del análisis y diseño las funciones u operaciones o sub-problemas en los cuales se puede descomponer (dividir) un problema, para facilitar su solución.

Refino Progresivo.

La Técnica de Refino Progresivo es una forma del diseño descendente. Su filosofía básica plantea desglosar un problema en una secuencia lógica de procesos (o bloques) de alto nivel. Generalmente, una representación en P-código o diagramática se utiliza para dichos procesos generales. Luego, cada uno de estos procesos es desglosado, o detallado, en subprocesos, que – a su vez- son susceptibles de refino posterior. El refino se prosigue hasta el nivel en cual cada proceso refinado puede expresarse vía procedimientos (sub-programas, sub-rutinas, funciones) conocidos o es tan simple que ya no admite refino posterior.

El trabajo del Refino Progresivo exige pensamiento estructurado para organizar eficientemente los bloques genéricos y su detalle subsiguiente, de tal forma que la modularización lograda implemente correctamente las ideas originales del diseño de los algoritmos. Sin embargo, en la construcción de grandes o gigantescos sistemas basados en software pueden surgir problemas de coherencia, consistencia y paralelismo (convergencia) entre módulos.

El Refino Progresivo también se llama Refino paso a paso está estructurado entorno a una idea básica: empezar un algoritmo con una descripción simple y genérica, que se conoce como correcta, y expandirla a través de diferentes etapas hasta obtener una versión detallada, correcta y robusta del algoritmo planteado. En cada etapa, una operación o una acción se seleccionan para la siguiente expansión, consistente en otras sub-etapas con mayor rigor en el detalle. Cualquier paso u operación que sea vaga o confusa es candidata para ser expandida. El proceso de expansión termina cuando todas las etapas y sub-etapas están suficientemente detalladas.

Técnicas de Refino Progresivo.

            El Refino Progresivo se encuadra dentro de las primeras propuestas serias, de la comunidad científica internacional, para lograr un diseño de software (programas) más confiable, seguro y eficiente, mediante el uso sistemático de métodos de análisis y síntesis de programas.
Actividades íntimamente ligadas con los procesos lógicos de pensamiento y la modelación matemática, pues al fin y al cabo, el software tiene una naturaleza inherente con las matemáticas; en otras palabras: el software es una forma de las matemáticas.

Aunque el proceso de aplicar el Refino Progresivo, como todos los enfoques modernos para la construcción de software eficiente y de calidad, tiene una sólida base lógico-matemática, también posee un alto contenido de labor artística y artesanal, dependiente del conocimiento, destrezas y experiencia del analista, del diseñador o del programador. Hay sin embargo ciertos lineamientos generales que ayudan en el proceso de refino. Algunos de ellos son los siguientes:

1. Fijar la atención. La principal ventaja del proceso de Refino Progresivo es que facilita el centrar la atención en un problema a la vez, con el manejo de pocos detalles. Además, en cada paso del refino se obtiene uno de los siguientes resultados:

El problema sobre el cual se tiene centrada la atención se descompone en otros Sub-problemas;
El problema se puede representar directamente, ya sea en código o en diagrama, pues no requiere más refino;
O, una parte del problema se puede descomponer en otros sub-problemas, y otra parte del problema se puede representar directamente en código fuente o en diagrama (u otra representación).

2. Aislar problema o sub-problema. Durante el proceso de refino, normalmente se aísla uno de los sub-problemas y se concentra en él, obteniéndose una solución para ese problema. Al final de todo el proceso de refino, la integración de las soluciones a todos los sub-problemas constituye la solución del problema original. Sin embargo, este proceso no está exento de riesgos, especialmente en grandes proyectos: la coherencia y consistencia, es decir el acoplamiento de los módulos vía de las interfaces, y entre las diferentes soluciones, puede convertirse en un cuello de botella y afectar el desempeño de todo el proceso.

3. Etiquetas. Para guiar y facilitar el refino se emplean etiquetas para nombrar a cada
Sub-problema. Como actualmente se dispone de entornos visuales automatizados en gran parte, es muy conveniente nombrar los procedimientos (o subprogramas) resultantes conforme a los eventos propios de cada proceso. Así se facilitará, además, la escritura del código fuente (los programas).

4. Procedimientos y Funciones. Cuando un problema es sometido al proceso de
Descomposición funcional es posible emplear en uno de los módulos ciertas operaciones definidas previamente en otros módulos. Esto evitará redundancia en el código fuente. Normalmente, se hace a nivel de módulos de clase, módulos de programa, o módulos de diseño (como los formularios en VisualBasic), por medio de funciones y procedimientos de uso general. Dividir un problema en subprogramas (procedimientos y funciones) simplifica la solución del problema y facilita la reusabilidad del código fuente (programas) al crear rutinas que se pueden emplear en otros proyectos.

5. Descomposición lineal. Cuando un problema (o sub-problema) tiene relativamente pocos parámetros de entrada, y relativamente pocas complejas operaciones de cálculo, un algoritmo resultante de primer nivel es exactamente una secuencia lineal de operaciones simples, ya sean aritméticas, lógicas, de tipo string o de matemáticas complejas.

Para situaciones como estas, los pasos esquematizados en esta figura serían suficientes como una descomposición inicial, base del refino posterior. Y corresponde al esquema general de un módulo (función o sub-programa).
Este esquema corresponde a todo algoritmo secuencial que tiene una entrada, unas operaciones da cálculo, y una salida (E - P- S).

6. Descomposición iterativa. Algunos problemas (o sub-problemas) procesan más de un conjunto de datos por lo cual es preciso alguna forma de iteración en el algoritmo, generándose así la Descomposición iterativa mostrada en la siguiente figura, en la cual los parámetros de entrada generan condiciones que hacen posible la iteración.

En este esquema de algoritmo se emplea una estructura iterativa automática.
La condición que se evalúa para el proceso iterativo (CondLog) se genera con los valores de entrada que intervienen en expresiones lógicas.