La recurrencia es una técnica de resolución de problemas y una relación de recurrencia es una expresión matemática que representa un cierto aspecto del problema en cuestión y nos ayuda a analizarlo.
Ejemplo 1:
El problema de llegar de un lugar a otro puede resolverse mediante una técnica llamada “caminar”. El acto de caminar implica dos pasos:
Paso 1: Da un paso adelante.
Paso 2: caminar.
- ¿Cuáles son ejemplos comunes de usos comunes para Ansible?
- ¿Es posible que las máquinas de vectores de soporte sean el algoritmo más apto para problemas de clasificación binaria dada la forma en que puede ajustar curvas alrededor del conjunto de datos?
- Cómo aprender el aprendizaje automático, qué idioma debo aprender y qué IDE debo usar
- ¿Cómo se mide la memoria de la computadora?
- ¿Cuándo podrán las computadoras leer el cerebro de un humano?
Lo que he hecho aquí se describe caminar usando una recurrencia. Este tipo de formulación es útil para niños dotados matemáticamente que dominan el concepto de recursividad antes de aprender a caminar. Para los adultos con una perspicacia matemática promedio que podrían leer esta respuesta, aquí hay una explicación de por qué funciona.
Digamos que intentas caminar usando las instrucciones anteriores. Estás parado en el punto A con un pequeño trozo de papel en la mano que dice “Instrucciones para caminar” en la parte superior y tiene los dos pasos de arriba garabateados debajo del título. Puedes ver el punto B justo enfrente de ti unos 10 metros más adelante y debes llegar allí. Entonces lees tu pequeño manual de instrucciones y das el primer paso: da un paso adelante. Cuando lees el segundo paso, te sientes un poco enfurecido porque simplemente dice “caminar”, pero caminar es exactamente lo que no sabías hacer. Pero, ¿qué haces cuando no sabes cómo hacer algo? Por supuesto, consulte el manual de instrucciones, que está en sus manos. Por lo tanto, consulte el manual nuevamente y siga el primer paso nuevamente: dé un paso adelante. Ahora está dos pasos más cerca del punto B. Repitiendo el mismo argumento una y otra vez, eventualmente tomará la cantidad suficiente de pasos necesarios para llegar al punto B.
Ahora digamos que quieres jugar un poco caminando y aprender algunas cosas más al respecto. Supongamos que tiene un minuto que perder antes de comenzar a trabajar y desea exprimir tanto como sea posible. Usted sabe por experiencia anterior que camina a una velocidad de 1 paso por segundo y ahora desea saber cuántos pasos podrá encajar en un minuto. Esto se puede resolver utilizando una relación de recurrencia de la siguiente manera.
Deje que T (n) denote la cantidad de pasos que dará en n segundos. Estamos interesados en T (60). Una vez que haya dado el primer paso, tendrá 59 segundos de caminata por recorrer. ¿Cuántos pasos es eso? T (59). Podemos representar este argumento con la siguiente ecuación: T (n) = T (n-1) +1.
Entonces, para encontrar el valor de T (60) usando esta relación, dices que T (60) = T (59) + 1 = T (58) + 1 + 1 = T (57) + 1 + 1 + 1 y así sucesivamente hasta obtener T (60) = 60.
Ejemplo 2
Los estudios han demostrado que la mayoría de los seres humanos encontrarán el ejemplo anterior bastante trivial y el uso de relaciones recurrentes inventadas. Así que aquí hay un uso más no trivial de las relaciones de recurrencia.
Supongamos que conoce a alguien que es gordo, calvo y tiene la cara llena de acné. Desea enviarle un correo electrónico con la siguiente oración copiada tantas veces como sea posible: “Eres feo. A nadie le gustas. Morirás solo”.
Los usuarios novatos de la tecnología informática que no son conscientes de la funcionalidad mágica de copiar y pegar escribirán cada línea una por una y, por lo tanto, se cansarán alrededor de la marca de 20-30 líneas. Las personas que conocen la funcionalidad de copiar y pegar pero no son buenas para usarla escribirán la línea una vez, la copiarán y la pegarán varias veces. Lo harán mejor que otros y probablemente puedan golpear alrededor de 1000 líneas. Los verdaderos expertos en el arte de copiar y pegar seguirán este manual de instrucciones:
Redactar un correo electrónico de n líneas:
Paso 1: redacta un correo electrónico de n / 2 líneas.
Paso 2: copie todo el correo electrónico y péguelo debajo de sí mismo.
Las personas que sigan este manual podrán obtener números astronómicos de líneas, del orden de millones. Y aquí hay una explicación usando relaciones de recurrencia.
Deje que T (n) sea la cantidad de instrucciones de copiar y pegar requeridas para componer un correo electrónico largo de n líneas. El manual de instrucciones anterior muestra claramente que T (n) = T (n / 2) + 1. Veamos el número total de instrucciones de copiar y pegar requeridas para alcanzar un número de líneas completamente arbitrario, por ejemplo, 1024. Claramente, T (1024) = T (512) + 1 = T (256) + 2 = T (128) + 3 = T (64) + 4 = T (32) + 5 = T (16) + 6 = T (8) + 7 = T (4) + 8 = T (2) + 9 = T (1) + 10 = 10.
¡Con solo 10 copias, puedes obtener 1024 líneas! Compárelo con el enfoque anterior más ingenuo en el que necesitaría 1024 pastas para obtener 1024 líneas.
