Matemática Discreta I · T4
Relaciones de recurrencia
Tema 04 · Johnsonbaugh, 6.ª ed., §7.1–7.3
Hay sucesiones que se definen mirando hacia atrás: cada término sale de los anteriores. El saldo de una cuenta con interés compuesto, los movimientos de la Torre de Hanói, las comparaciones que hace un programa recursivo siguen esa regla, y plantearla es casi siempre más fácil que escribir una fórmula en . Una relación de recurrencia es la regla; resolverla es encontrar esa fórmula. La guía sigue Johnsonbaugh §7.1 (plantear recurrencias), §7.2 (resolverlas) y §7.3 (usarlas para contar el costo de algoritmos que parten el problema en mitades), con las páginas citadas punto a punto. Lo que se aprendió en el Tema 3 es la herramienta de control: toda fórmula obtenida se comprueba por inducción.
- Versión
- 2.0
- Publicada
- Páginas
- 45 + 23 del solucionario
- Formato
- PDF · A4
- Enlace
( Contenido ) Temas
- relación de recurrencia
- condiciones iniciales
- interés compuesto
- Torre de Hanói
- iteración
- ecuación característica
- raíz doble
- sucesión de Fibonacci
- solución particular
- divide y vencerás
- búsqueda binaria
- fusión
- merge sort
- peor caso
( Historial ) Versiones
-
- Tema rehecho sobre Johnsonbaugh §7.1–7.3: 26 definiciones, 14 puntos, 17 figuras, ejemplos resueltos, mapa de decisión de métodos y 20 preguntas de autoevaluación.
-
v1.0 PDF Solucionario