recursividad un análisis posterior -...
TRANSCRIPT
Recursividad... un análisis posterior
Jaime Gutiérrez AlfaroIntroducción a la programación
I semestre, 2015
Agenda
● Introducción
● Tipos de recursión
● Evaluaciones pendientes: pila, cola
● Número de llamadas: simple, doble
● Estructura de las llamadas: directa, indirecta, anidada
● Análisis de algoritmos
● Cálculos por aproximación
● Concepto de error
● Depuración
● Temas de discusión
● Ejercicios
Construyendo Programas
Buscar soluciones a problemas (pensar en un algoritmo) requiere de una etapa previa de razonamiento lógico (proceso que no es trivial)
Algunos elementos que nos pueden ayudar a desarrollar esta capacidad:
● Análisis de algoritmos ya realizados: comprenderlos, apropiarse...
● Construir soluciones propias: práctica, ejercicios.
● Buena disposición para enfrentar los problemas con ingenio.
Y más frustración CC-NC-ND Pablo Municio @ Flickr
Análisis de Algoritmos
Establecer comparaciones entre distintos algoritmos → Optimizar recursos
¿Cómo se puede evaluar la eficiencia de un algoritmo?
● Comparaciones de razonabilidad: se aplica principalmente al tiempo de ejecución y apela al sentido común (subjetividad asociada al contexto de ejecución).
→ e.g. buscar un libro en una base de datos, ¿cuanto tiempo es razonable esperar?
● Análisis de Algoritmos: cantidad de recursos necesarios (principalmente el tiempo)
● Comparaciones empíricas: estimaciones teóricas.
● Análisis matemáticos: comportamiento matemático del algoritmo al “enfrentar” un conjunto grande de datos. [curso: Análisis de algoritmos]
Análisis Empírico de Algoritmos
Usando Fibonacci: implementado con recursividad de pila vs. recursividad de cola.
fibonacci(0), si n = 0 → 0
fibonacci(1), si n = 1 → 1
fibonacci(n), si n >= 2 → fibonacci( n - 1) + fibonacci( n – 2)
Análisis Empírico de Algoritmos
Fibonacci versión recursividad de Pila
def fib_pila(n):
if isinstance(n, int) and n >= 0:
return fib_pila_aux(n)
else: return 'Error'
def fib_pila_aux(n):
if n == 0 or n == 1:
return n
else: return fib_pila_aux(n - 1) + fib_pila_aux(n - 2)
Análisis Empírico de Algoritmos
Fibonacci versión recursividad de Cola
def fib_cola(n):
if isinstance(n, int) and n >= 0:
#f1 = fib(1)?, f2 = fib(0)?, cont=0, n =n
return fib_cola_aux(n, 0, 1, 0)
else: return 'Error'
def fib_cola_aux(n, cont, f1, f2):
if cont == n: return f2
#f1 = fib(cont-1), f2 = fib(cont) ??
else: return fib_cola_aux(n, cont+1, f2, f1 + f2 )
Análisis Empírico de Algoritmos
Ejecución de fibonacci implementado con recursividad de cola
>>> fib_cola(6)
fib_colaaux(6,0,1,0) #f1 = fib(1), f2 = fib(0)
fib_colaaux(6,1,0,1) #f1 = fib(0), f2 = fib(1)
fib_colaaux(6,2,1,1) #f1 = fib(1), f2 = fib(2)
fib_colaaux(6,3,1,2) #f1 = fib(2), f2 = fib(3)
fib_colaaux(6,4,2,3) #f1 = fib(3), f2 = fib(4)
fib_colaaux(6,5,3,5) #f1 = fib(4), f2 = fib(5)
fib_colaaux(6,6,5,8) #f1 = fib(5), f2 = fib(6)
>>> 8
Análisis Empírico de Algoritmos
La fórmula para calcular las llamadas recursivas (T) en estas implementaciones sería:
R. Pila: T(n) = T(n-1) + T(n-2) + 1
Si hacemos fib(2):
T(2) = T(1) + T(0) + 1
T(2) = 1 + 1 + 1
T(2) = 3
R. Cola: T(n) = n – 1
Si hacemos fib(2):
T(2) = 1
Análisis Empírico de Algoritmos
Una comparación de las llamadas recursivas realizadas...
n fib(n) Llamadas recursivas en Pila
Llamadas recursivas en Cola
2 1 3 1
3 2 5 2
4 3 9 3
5 5 15 4
6 8 25 5
7 13 41 6
8 21 67 7
9 34 109 8
10 55 177 9
...
35 9 227 465 29 860 703 34
Cálculos por aproximación
Forman parte del análisis numérico
● Disciplina ocupada de describir, analizar y crear algoritmos numéricos que permiten resolver problemas matemáticos, con una precisión determinada.
● Consiste en realizar una serie de cálculos sucesivos hasta obtener un resultado que se aproxime de forma “aceptable” (entre más grande la cantidad de cálculos mayor la aproximación).
● Ejemplo: calcular Pi:
3,14159265358979323846...
Sumatoria Leibniz
Portland Pi CC BY-NC-SA skylkarprimm @ Flickr
http://www.eveandersson.com/pi/gregory-leibniz?
Concepto de Error
Es una medida de ajuste del cálculo de una magnitud con respecto al valor real o teórico que dicha magnitud tiene.
Sirve para estimar el grado de precisión que tiene una solución obtenida. (qué tanto nos aproximamos)
Un resultado es aceptable, si definimos un grado de error y se cumple que:
| Respuesta real – Aproximación (respuesta obtenida) | <= Error
Ejemplos de grados de precisión:
| 3.14159 – 3.1426 | = 0,00101
| 3.14159 – 3.14158 | = 0,00001
Depuración: Debug / Trace
La función trace es una alternativa al “debugger” utilizado hasta ahora.
● ¿Para que sirven las herramientas de depuración?
● ¿Qué sentido tiene utilizarlas?
● ¿Cuándo deben utilizarse?
def digitos(num):
if num == 0:
return 0
else:
return 1 + digitos(num//10)
Depuración: Debug / Trace
Con debugger:
Depuración: Debug / Trace
Con Trace:
● Se utiliza una biblioteca que le de “seguimiento” al “rastro” del código que se quiere revisar.
● >>> help(trace)
Ejemplo de Código:
import trace
#requiere la función dígitos implementada anteriormente
tracer = trace.Trace(count=0, trace=1, countfuncs=0, countcallers=0)
tracer.runfunc(digitos,7654)
Depuración: Debug / Trace
Al ejecutar el programa:
Temas de Discusión en Grupos
● Las herramientas de depuración como el Debugger o la función trace deberían ser utilizados siempre, incluso cuando se piense que la solución está correcta.
● Realizar las ejecuciones manuales de las funciones es un proceso que debe realizarse solamente cuando se detecte un error en los resultados obtenidos.
● Los comentarios en el código fuente de un programa son un aspecto secundario cuando se analiza la calidad de la solución obtenida.
Ejercicios
Implemente la función de Ackerman
● Haga un cuadro con sus primeros resultados.
● Utilice el debugger y la función trace para revisar su comportamiento.
● Esboce un análisis del comportamiento de esa función.
Implemente la sumatoria Leibniz y calcule por aproximación el valor de Pi con una precisión de al menos 10 números fraccionarios correctos.
● Haga un cuadro con los resultados obtenidos
● Utilice el debugger y la función trace para revisar su comportamiento.
● Esboce un análisis del comportamiento de esa función.
Referencias y Lecturas Complementarias
● Material suministrado por el profesor Jeff Schmidt, Instituto Tecnológico de Costa Rica. I semestre 2011.
● Cálculo de Pi utilizando la aproximación de Gregory-Leibniz: http://www.eveandersson.com/pi/gregory-leibniz?
● Trace (depurador): http://docs.python.org/3/library/trace.html
● En general: http://docs.python.org/3/
32
Las presentaciones para el curso IC-1800: "Introducción a la Programación" por Ing. En Computación Alajuela se distribuyen bajo una
Licencia Creative Commons Atribución-Compartir Igual 3.0 Costa Rica.
http://creativecommons.org/licenses/by-sa/3.0/cr/http://creativecommons.org/licenses/by-sa/3.0/cr/ *La licencia de la presentación no cubre las imágenes utilizadas*
Recursividad... un análisis posterior
Jaime Gutiérrez AlfaroIntroducción a la programación
I semestre, 2015
Agenda
● Introducción
● Tipos de recursión
● Evaluaciones pendientes: pila, cola
● Número de llamadas: simple, doble
● Estructura de las llamadas: directa, indirecta, anidada
● Análisis de algoritmos
● Cálculos por aproximación
● Concepto de error
● Depuración
● Temas de discusión
● Ejercicios
Construyendo Programas
Buscar soluciones a problemas (pensar en un algoritmo) requiere de una etapa previa de razonamiento lógico (proceso que no es trivial)
Algunos elementos que nos pueden ayudar a desarrollar esta capacidad:
● Análisis de algoritmos ya realizados: comprenderlos, apropiarse...
● Construir soluciones propias: práctica, ejercicios.
● Buena disposición para enfrentar los problemas con ingenio.
Y más frustración CC-NC-ND Pablo Municio @ Flickr
Análisis de Algoritmos
Establecer comparaciones entre distintos algoritmos → Optimizar recursos
¿Cómo se puede evaluar la eficiencia de un algoritmo?
● Comparaciones de razonabilidad: se aplica principalmente al tiempo de ejecución y apela al sentido común (subjetividad asociada al contexto de ejecución).
→ e.g. buscar un libro en una base de datos, ¿cuanto tiempo es razonable esperar?
● Análisis de Algoritmos: cantidad de recursos necesarios (principalmente el tiempo)
● Comparaciones empíricas: estimaciones teóricas.
● Análisis matemáticos: comportamiento matemático del algoritmo al “enfrentar” un conjunto grande de datos. [curso: Análisis de algoritmos]
Análisis Empírico de Algoritmos
Usando Fibonacci: implementado con recursividad de pila vs. recursividad de cola.
fibonacci(0), si n = 0 → 0
fibonacci(1), si n = 1 → 1
fibonacci(n), si n >= 2 → fibonacci( n - 1) + fibonacci( n – 2)
Análisis Empírico de Algoritmos
Fibonacci versión recursividad de Pila
def fib_pila(n):
if isinstance(n, int) and n >= 0:
return fib_pila_aux(n)
else: return 'Error'
def fib_pila_aux(n):
if n == 0 or n == 1:
return n
else: return fib_pila_aux(n - 1) + fib_pila_aux(n - 2)
Esta implementación es una “traducción literal” de la fórmula matemática.
Análisis Empírico de Algoritmos
Fibonacci versión recursividad de Cola
def fib_cola(n):
if isinstance(n, int) and n >= 0:
#f1 = fib(1)?, f2 = fib(0)?, cont=0, n =n
return fib_cola_aux(n, 0, 1, 0)
else: return 'Error'
def fib_cola_aux(n, cont, f1, f2):
if cont == n: return f2
#f1 = fib(cont-1), f2 = fib(cont) ??
else: return fib_cola_aux(n, cont+1, f2, f1 + f2 )
Esta implementación es bien interesante porque no es solo una traducción, sino que implica un análisis adicional.
Dado que el fibonacci de n es el resultado de sumar los dos anteriores (n-1 y n-2) entonces la propuesta de esta solución es comenzar con los primeros dos valores de fibonacci (1 y 0) y ir calculando los fibonaccis siguientes (2, 3, 4, 5... etc) hasta llegar a n.
Por esa razón es que en el “return” recursivo de la función auxiliar pasa el parametro f1 es pasado con el valor con de la variable de f2 que contenía la suma de fibonacci de (n-2).
Análisis Empírico de Algoritmos
Ejecución de fibonacci implementado con recursividad de cola
>>> fib_cola(6)
fib_colaaux(6,0,1,0) #f1 = fib(1), f2 = fib(0)
fib_colaaux(6,1,0,1) #f1 = fib(0), f2 = fib(1)
fib_colaaux(6,2,1,1) #f1 = fib(1), f2 = fib(2)
fib_colaaux(6,3,1,2) #f1 = fib(2), f2 = fib(3)
fib_colaaux(6,4,2,3) #f1 = fib(3), f2 = fib(4)
fib_colaaux(6,5,3,5) #f1 = fib(4), f2 = fib(5)
fib_colaaux(6,6,5,8) #f1 = fib(5), f2 = fib(6)
>>> 8
Note como el fib de n-2 siempre pasa a ser fib de n-1 en la siguiente invocación, o en otras palabras f2 pasa a ser f1 en la siguiente llamada.
(Mostrar esto con flechas en la pizarra)
Análisis Empírico de Algoritmos
La fórmula para calcular las llamadas recursivas (T) en estas implementaciones sería:
R. Pila: T(n) = T(n-1) + T(n-2) + 1
Si hacemos fib(2):
T(2) = T(1) + T(0) + 1
T(2) = 1 + 1 + 1
T(2) = 3
R. Cola: T(n) = n – 1
Si hacemos fib(2):
T(2) = 1
En recursión de pila: se requieren hacer 2 llamadas recursivas en cada uno de las soluciones, por eso el T(1) y T(0), mientras en la de cola
Análisis Empírico de Algoritmos
Una comparación de las llamadas recursivas realizadas...
n fib(n) Llamadas recursivas en Pila
Llamadas recursivas en Cola
2 1 3 1
3 2 5 2
4 3 9 3
5 5 15 4
6 8 25 5
7 13 41 6
8 21 67 7
9 34 109 8
10 55 177 9
...
35 9 227 465 29 860 703 34
Cálculos por aproximación
Forman parte del análisis numérico
● Disciplina ocupada de describir, analizar y crear algoritmos numéricos que permiten resolver problemas matemáticos, con una precisión determinada.
● Consiste en realizar una serie de cálculos sucesivos hasta obtener un resultado que se aproxime de forma “aceptable” (entre más grande la cantidad de cálculos mayor la aproximación).
● Ejemplo: calcular Pi:
3,14159265358979323846...
Sumatoria Leibniz
Portland Pi CC BY-NC-SA skylkarprimm @ Flickr
Ver este sitio donde ponen la sumatoria:
http://www.eveandersson.com/pi/gregory-leibniz?
http://www.eveandersson.com/pi/gregory-leibniz?
Concepto de Error
Es una medida de ajuste del cálculo de una magnitud con respecto al valor real o teórico que dicha magnitud tiene.
Sirve para estimar el grado de precisión que tiene una solución obtenida. (qué tanto nos aproximamos)
Un resultado es aceptable, si definimos un grado de error y se cumple que:
| Respuesta real – Aproximación (respuesta obtenida) | <= Error
Ejemplos de grados de precisión:
| 3.14159 – 3.1426 | = 0,00101
| 3.14159 – 3.14158 | = 0,00001
Depuración: Debug / Trace
La función trace es una alternativa al “debugger” utilizado hasta ahora.
● ¿Para que sirven las herramientas de depuración?
● ¿Qué sentido tiene utilizarlas?
● ¿Cuándo deben utilizarse?
def digitos(num):
if num == 0:
return 0
else:
return 1 + digitos(num//10)
Depuración: Debug / Trace
Con debugger:
Depuración: Debug / Trace
Con Trace:
● Se utiliza una biblioteca que le de “seguimiento” al “rastro” del código que se quiere revisar.
● >>> help(trace)
Ejemplo de Código:
import trace
#requiere la función dígitos implementada anteriormente
tracer = trace.Trace(count=0, trace=1, countfuncs=0, countcallers=0)
tracer.runfunc(digitos,7654)
Depuración: Debug / Trace
Al ejecutar el programa:
Ahí se muestra por cuales funciones va pasando el programa en cada una de sus recursiones.
Si les gusta la función trace lo mejor es que investiguen un poco más del funcionamiento, o si prefieren utilizar el debbuger.
Temas de Discusión en Grupos
● Las herramientas de depuración como el Debugger o la función trace deberían ser utilizados siempre, incluso cuando se piense que la solución está correcta.
● Realizar las ejecuciones manuales de las funciones es un proceso que debe realizarse solamente cuando se detecte un error en los resultados obtenidos.
● Los comentarios en el código fuente de un programa son un aspecto secundario cuando se analiza la calidad de la solución obtenida.
Ejercicios
Implemente la función de Ackerman
● Haga un cuadro con sus primeros resultados.
● Utilice el debugger y la función trace para revisar su comportamiento.
● Esboce un análisis del comportamiento de esa función.
Implemente la sumatoria Leibniz y calcule por aproximación el valor de Pi con una precisión de al menos 10 números fraccionarios correctos.
● Haga un cuadro con los resultados obtenidos
● Utilice el debugger y la función trace para revisar su comportamiento.
● Esboce un análisis del comportamiento de esa función.
Referencias y Lecturas Complementarias
● Material suministrado por el profesor Jeff Schmidt, Instituto Tecnológico de Costa Rica. I semestre 2011.
● Cálculo de Pi utilizando la aproximación de Gregory-Leibniz: http://www.eveandersson.com/pi/gregory-leibniz?
● Trace (depurador): http://docs.python.org/3/library/trace.html
● En general: http://docs.python.org/3/
32
Las presentaciones para el curso IC-1800: "Introducción a la Programación" por Ing. En Computación Alajuela se distribuyen bajo una
Licencia Creative Commons Atribución-Compartir Igual 3.0 Costa Rica.
http://creativecommons.org/licenses/by-sa/3.0/cr/http://creativecommons.org/licenses/by-sa/3.0/cr/ *La licencia de la presentación no cubre las imágenes utilizadas*