Matematicas discretas avanzadas I: recurrencia
Una relacion de recurrencia define cada termino de una sucesion en funcion de terminos anteriores. Son fundamentales en ciencias de la computacion para analizar la eficiencia de algoritmos recursivos.
Sucesion de Fibonacci
La sucesion de Fibonacci (1, 1, 2, 3, 5, 8, 13, 21...) se define como F(n) = F(n-1) + F(n-2). Aparece en la naturaleza: espirales de caracoles, petalos de flores, y la proporcion aurea.
| n | F(n) | Razon F(n)/F(n-1) |
|---|---|---|
| 1 | 1 | - |
| 5 | 5 | 1.667 |
| 10 | 55 | 1.618 |
| 20 | 6765 | 1.618 |
Resolver recurrencias
Para resolver una recurrencia lineal, se propone una solucion de la forma r^n, se sustituye y se resuelve la ecuacion caracteristica.Funciones generadoras
Una funcion generadora codifica una sucesion como coeficientes de una serie de potencias. Permite resolver recurrencias algebraicamente.Aplicaciones
Analisis de algoritmos recursivos, compresion de datos, criptografia, y modelado de poblaciones biologicas.
Paso 1 de 3
Leonardo de Pisa (Fibonacci) introdujo esta sucesion en Europa en 1202 con su problema de los conejos, pero los matematicos indios ya la conocian siglos antes.
Piensa y responde
¿Cual es el siguiente termino de 1, 1, 2, 3, 5, 8?
La razon entre terminos consecutivos de Fibonacci tiende a la proporcion aurea.
La recurrencia de Fibonacci es F(n) = F(n-1) + F(n-), y la proporcion aurea es aproximadamente .
Relaciona cada concepto con su descripcion:
Clasifica estas sucesiones segon su tipo:
Arrastra cada ficha a su categoría (o tócala y luego toca la categoría). También puedes usar el teclado.
Ordena los pasos para resolver una recurrencia lineal:
Coloca los elementos en orden y pulsa Comprobar.
¿Por que crees que Fibonacci aparece tantas veces en la naturaleza?
Tu texto se guarda sólo en este dispositivo.
Para dominar este tema
- Resuelve relaciones de recurrencia
- Conoce la sucesion de Fibonacci
- Comprende funciones generadoras
- Aplica en analisis de algoritmos
Recurrencia
Aquí se mira lo que ya fuiste acertando. Pulsa «Comprobar» para saber si puedes seguir.
Comentarios
Inicia sesión para comentar.
Todavía no hay comentarios. Sé la primera persona en opinar.