Diseño De Algoritmos

UNIDAD II‎ > ‎

2.3. DISEÑO DE ALGORITMOS APLICADOS A PROBLEMAS.

1.2 Algoritmos diseño.

Para llegar a la realización de un programa es necesario el diseño previo de algoritmo, de modo que sin algoritmo no puede existir un programa.

Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que lo ejecuta. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será siempre el mismo.

Dada la importancia del algoritmo en la ciencia de la computación, un aspecto muy importante será el diseño de algoritmos. El diseño de la mayoría de los algoritmos requiere creatividady conocimientos profundos de la técnica de la programación.

Técnicas de diseño de algoritmos

Algoritmos voraces (greedy): seleccionan los elementos más prometedores del conjunto de candidatos hasta encontrar una solución. En la mayoría de los casos la solución no es óptima.

Algoritmos paralelos: permiten la división de un problema en subproblemas de forma que se puedan ejecutar de forma simultánea en varios procesadores.

Algoritmos probabilísticos: algunos de los pasos de este tipo de algoritmos están en función de valores pseudoaleatorios.

Algoritmos determinísticos: el comportamiento del algoritmo es lineal: cada paso del algoritmo tiene únicamente un paso sucesor y otro antecesor.

Algoritmos no determinísticos: el comportamiento del algoritmo tiene forma de árbol y a cada paso del algoritmo puede bifurcarse a cualquier número de pasos inmediatamente posteriores, además todas las ramas se ejecutan simultáneamente.

Divide y vencerás: dividen el problema en subconjuntos disjuntos obteniendo una solución de cada uno de ellos para después unirlas, logrando así la solución al problema completo.

Metaheurísticas: encuentran soluciones aproximadas (no óptimas) a problemas basándose en un conocimiento anterior (a veces llamado experiencia) de los mismos.

Programación dinámica: intenta resolver problemas disminuyendo su coste computacional aumentando el coste espacial.

Ramificación y acotación: se basa en la construcción de las soluciones al problema mediante un árbol implícito que se recorre de forma controlada encontrando las mejores soluciones.

Vuelta atrás (backtracking): se construye el espacio de soluciones del problema en un árbol que se examina completamente, almacenando las soluciones menos costosas.

Características de algoritmo

La resolución de un problema exige el diseño de un algoritmo que resuelva el problema, como lo muestra la siguiente figura:

Pasos para la resolución de un problema

1.- Diseño del algoritmo que describe la secuencia ordenada de pasos �sin ambigüedades- que conducen a la solución de un problema dado.(Análisis del problema y desarrollo del algoritmo).

2.- Expresar el algoritmo como un programa en un lenguaje adecuado. (Fase de codificación).

3.- Ejecución y validación del programa por la computadora.

Características de los algoritmos

Un algoritmo debe:

ser preciso e indicar el orden de realización de cada paso.

estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez.

ser finito. Si se sigue un algoritmo, se debe terminar en algún momento; o sea, debe tener un número finito de pasos.

Existen dos herramientas utilizadas conceptualmente para diseñar algoritmos: los diagramas de flujo y el pseudocódigo

2.4 DISEÑO ALGORITMICO DE FUNCIONES

El algoritmo principal cuando sea necesario. Los módulos son independientes en el sentido de que ningún módulo puede tener acceso directo a cualquier otro módulo, con excepción del módulo al que llama y sus propios submódulos. Sin embargo, los resultados producidos por un módulo pueden ser utilizados por cualquier otro módulo cuando se transfiera a ellos el control. Los módulos tienen una entrada y una salida. Se pueden tomar decisiones dentro de un módulo que tenga repercusión en todo el flujo, pero el salto debe ser únicamente hacia el programa principal. Al descomponer un programa en módulos independientes más simples se conoce también como el método de "Divide y vencerás".

El problema principal es denominado controlador o conductor (drive) y la solución de los subproblemas son conocidos como procedimientos (subrutinas) o funciones.

Se dice que el programa Introducción

La programación

...