• Author / Uploaded
• Ana Milena Diaz

Citation preview

ELEMENTOS EN TEORIA DE LA COMPUTACION Conceptos Iniciales y Relación de Recurrencia

ALUMNOS: ANA MILENA DIAZ CARVAJAL

COD:812011645

XXXXXXX

COD:

XXXXXX

COD:

XXXXX

COD:

POLITECNICO GRANCOLOMBIANO INGENIERIA Y DISEÑO E INNOVACION Bogotá D.C. 2020

Realizar un documento siguiendo estas instrucciones:

1. Presentar un contexto sobre el cual algunos datos presentan una relación de recurrencia. En matemática, una relación de recurrencia es una ecuación que define una secuencia recursiva; cada término de la secuencia es definido como una función de términos anteriores} relación de recurrencia para una sucesión {a0, a1, a2, a3, . . . } es una fórmula que expresa cada termino a n, a partir de cierto n0 ∈ N , en función de uno o más de los términos que le preceden. Los valores de los términos necesarios para empezar a calcular se llaman condiciones iniciales. Se dice que una sucesión es una solución de la relación de recurrencia si su término general verifica dicha relación. Ejemplo de relaciones de recurrencia de la forma 

a n=an −1 +d (progresión aritmética) Ejemplo: sea u0 =a, u1 =a+d , u 2=a+2 d , … ,u n=a+ nd ... , de donde se optiene la ecuación un +1=un +d De esta ecuación no se tiene una relación por lo cual vamos a tomar dos valores consecutivos de n operando con ellos y obtendremos un +2=un +1+ d y un+ 1=un +d Y restando tendremos un +2−un +1=un +1+u n y decimos que un +2=2 un+1−u n la progresión aritmética son sucesiones recurrentes de segundo orden



a n=ra n−1 (progresión geométrica). sea u0 =a, u1 =a r ,u 2=ar 2 ,... , un=ar n ,... de donde se optiene laecuación un +1=un r la progresión geométrica es una sucesión recurrente de primer orden

Sus soluciones son, respectivamente, a n=a0 + dn y a n=a o r n Por otra parte, uno de los ejemplos más estudiados es la sucesión de Fibonacci Sucesión de Fibonacci la sucesión de Fibonacci es una sucesión matemática infinita que consta de una serie de números naturales que se suman de a 2, a partir de 0 y 1. Básicamente, la sucesión de Fibonacci se realiza sumando siempre los últimos 2 números, todos los números presentes en la sucesión se llaman números de Fibonacci de la siguiente manera: 0,1,1,2,3,5,8,13,21,34.. La sucesión de Fibonacci es conocida desde hace miles de años, pero fue Fibonacci (Leonardo de Pisa) quien la dio a conocer al utilizarla para resolver un problema. El primer y segundo término de la sucesión son a 0=0 a 1=¿1 Los siguientes términos se obtienen sumando los dos términos que les preceden: El tercer término de la sucesión es a 2=a0 +a 1=¿ ¿ 0+1=1

El cuarto término es a 3=a1 +a 2=¿ ¿ 1+1=2 El quinto término es a 4=a2+ a3=¿ ¿ 1+2=3 El sexto término es a 5=a3 +a 4=¿ ¿ 2+3=5 El (n+1) (n+1) séptimo término es a n=an −2 +a n−1=¿

2. Representar matemáticamente la relación de recurrencia expuesta.