Tarea

Estrategias de Diseño de Algoritmos
Introducción A través de los años, los científicos de la computación han identificado diversas técnicas generales que a menudo producen algorit mos eficientes para la resolución de muchas clases de problemas. Este capítulo presenta algunas de las técnicas más importantes como son: recursión, dividir para conquistar, técnicas ávidas, el método de retroceso yprogramación dinámica. Se debe, sin embargo, destacar que hay algunos problemas, como los NP completos, para los cuales ni éstas ni otras técnicas conocidas producirán soluciones eficientes. Cuando se encuentra algún problema de este tipo, suele ser útil determinar si las entradas al problema tienen características especiales que se puedan explotar en la búsqueda de una solución, o si puede usarsealguna solución aproximada sencilla, en vez de la solución exacta, difícil de calcular. Recursión La recursividad es una técnica fundamental en el diseño de algoritmos eficientes, que está basada en la solución de versiones más pequeñas del problema, para obtener la solución general del mismo. Una instancia del problema se soluciona según la solución de una o más instancias diferentes y más pequeñas que ella. Es una herramienta poderosa que sirve para resolver cierto tipo de problemas reduciendo la complejidad y ocultando los detalles del problema. Esta herramienta consiste en que una función o procedimiento se llama a sí mismo. Una gran cantidad de algoritmos pueden ser descritos con mayor claridad en términos de recursividad, típicamente el resultado será que sus programas serán máspequeños. La recursividad es una alternativa a la iteración o repetición, y aunque en tiempo de computadora y en ocupación en memoria es la solución recursiva menos eficiente que la solución iterativa, existen numerosas situaciones en las que la recursividad es una solución simple y natural a un problema que en caso contrario ser difícil de resolver. Por esta razón se puede decir que larecursividad es una herramienta potente y útil en la resolución de problemas que tengan naturaleza recursiva y, por ende, en la programación. Existen numerosas definiciones de recursividad , algunas de las más importantes o sencillas son éstas: • • Un objeto es recursivo si figura en su propia definición. Una definición recursiva es aquella en la que el objeto que se define forma parte de la definición(recuerde la regla gramatical: lo definido nunca debe formar parte de la definición)

La característica importante de la recursividad es que siempre existe un medio de salir de la definición, mediante la cual se termina el proceso recursivo. Ventajas: • • Puede resolver problemas complejos. Solución más natural.

Desventajas: • • • Se puede llegar a un ciclo infinito. Versión no recursiva másdifícil de desarrollar. Para la gente sin experiencia es difícil de programar.

Tipos de Recursividad • Directa o simple: un subprograma se llama a si mismo una o más veces directamente.

•

Indirecta o mutua: un subprograma A llama a otro subprograma B y éste a su vez llama al subprograma A.

a) Propiedades para un Procedimiento Recursivo • Debe de existir cierto criterio (criterio base) endonde el procedimiento no se llama a sí mismo. Debe existir al menos una solución no recursiva. • En cada llamada se debe de acercar al criterio base (reducir rango). El problema debe reducirse en tamaño, expresando el nuevo problema en términos del propio problema, pero más pequeño. Los algoritmos de divide y vencerás pueden ser procedimientos recursivos. b) Propiedades para una Función Recursiva• Debe de haber ciertos argumentos, llamados valores base para los que la función no se refiera a sí misma. • Cada vez que la función se refiera así misma el argumento de la función debe de acercarse más al valor base. Ejemplos: Factorial n! = 1 * 2 * 3 ... * (n- 2) * (n-1) * n 0! = 1 1! = 1 2! = 1 * 2 3! = 1 * 2 * 3 ... n! = 1 * 2 * 3 ... * (n- 2) * (n-1) * n ⇒ n! = n* (n-1)!

si n = 0...