¿Dónde aprender cómo funcionan los números?

Question

He conocido las matemáticas muy básicas (aritmética básica, fracciones y exponentes). Nunca he aprendido bien las matemáticas en el instituto porque mis profesores de matemáticas no están acostumbrados a enseñar a alumnos ciegos.

Pero ahora estoy leyendo un libro de programación (Estructura e interpretación de programas de ordenador) que proporciona muchos programas matemáticos. Algunas fórmulas son:

Nota: Las he escrito como pseudocódigo tal y como las entiendo en los programas. Ambas funciones son recursivas.

Encontrar la secuencia de Fibonacci: fórmula matemática real aquí https://mitpress.mit.edu/sicp/chapter1/node13.html

fib(n) = fib(n-1)+fib(n-2)

Exponenciación con cuadratura sucesiva: Fórmula matemática real aquí https://mitpress.mit.edu/sicp/chapter1/node15.html

if n is 0, return 1
if n is even, find exponents of (b^(n / 2))^2
if n is odd,          (b * (find exponents of  b^(n - 1)))

Ahora entiendo perfectamente lo que hacen y cómo lo hacen. Puedo escribirlos en cualquier lenguaje de programación que conozca, puedo memorizar el algoritmo en mi cabeza para encontrar rápidamente el siguiente fib o lo que es 2^1000 rápidamente con sólo conocer la fórmula. Pero no sé en absoluto cómo se crean esas soluciones (por ejemplo, creo que las multiplicaciones son sumas repetidas y las divisiones son restas repetidas). Es decir, realmente no sé por qué los algoritmos anteriores son correctos. ¿Qué rama de las matemáticas necesito para encontrar cómo se encuentran las soluciones de arriba?

Answer 1

Aquí tienes dos preguntas concretas, una sobre la exponenciación por cuadrados repetidos, y otra sobre en qué rama de las matemáticas hacerlo.

En primer lugar, quieres una prueba de que la exponenciación se puede realizar mediante la elevación al cuadrado repetida. Por supuesto, te das cuenta de que la exponenciación $a^b$ puede calcularse multiplicando $b$ copias de $a$ . Otra forma de decir esto a la SICP de Sussman, es que:

$$a^b = a \times a^{b-1}, a^0 = 1$$

(esto no es más que una forma recursiva de cadena en una lista de $a$ de longitud $b$ ).

El algoritmo de cuadratura repetida consigue la exponenciación porque (y creo que esto es lo único importante por lo que tienes curiosidad) también consigue una lista de $a$ de longitud $b$ Sólo que de una manera un poco más complicada. La explicación es la siguiente: $b$ es par o impar (bastante obvio, ¿verdad?). Tomemos esos dos casos por separado.

• Si $b$ es par, entonces $a^b = a^{b/2} \times a^{b/2}$ ¿cierto? (porque $b$ es incluso se puede dividir por 2, y también, $a^x \times a^y = a^{x+y}$ una propiedad básica de los exponenciales. (Obsérvese que $b/2$ puede ser par o impar, no lo sabemos).Y esto es lo mismo que $a^{b/2}$ al cuadrado. Ahí es donde las repetidas cuadrando viene de.

• si $b$ es impar, entonces $a^b = a \times a^{b-1}$ (la fórmula habitual). (Tenga en cuenta que $b-1$ debe ser incluso ahora).

Porque $b$ es par o impar (y nunca ambos) esto cubre todos los casos (no hay más posibilidades que par o impar) y podemos siempre Obtenga $a^b$ utilizando algunos exponentes menores.

Y como siempre estamos obteniendo exponentes más pequeños, nosotros siempre bajar a un exponente de 1, sin importar el exponente.

¡Y ya está!

(¿por qué querríamos complicar las cosas de esta manera? Bueno, (a menudo) estamos dividiendo por 2, por lo que el número de multiplicaciones es como el logaritmo de $b$ en lugar de $b-1$ (que es mucho menos).

En cuanto a su segunda pregunta, ¿qué rama de las matemáticas se necesita para ello? Los hechos que utilizamos fueron algunas propiedades de la exponenciación, algo de teoría de números (propiedades de impar y par) y algo de aritmética. Todo esto suele enseñarse, al menos en el sistema educativo estadounidense, en el primer o segundo año de álgebra de la escuela secundaria.

Hay un paso de la prueba que es más o menos el pegamento lógico que lo mantiene todo unido y pone la última pequeña pieza del rompecabezas para resolverlo y ese fue el último paso, que siempre se obtiene un exponente menor y se llega a 1. La matemática para eso es la inducción, que es exactamente lo que Sussman está enseñando con este ejemplo. La inducción se enseña a menudo en la escuela secundaria en varias clases, tal vez en el álgebra, tal vez en el precálculo.

Una nota al margen: si sabe de binarios, considere $b$ en binario. El algoritmo del cuadrado repetido sigue entonces los dígitos binarios hacia atrás. Si $b$ termina en 0 (es par) entonces divide $b$ por 2 y elevar al cuadrado el resultado. Si $b$ termina en 1, entonces cambia el 1 por un 0 (resta 1) y multiplica por uno $a$ . A continuación, trabaje recursivamente en los dígitos restantes.

Answer 2

No creo que esta sea la respuesta que buscas, pero igual puede ser útil. Le haré algunos comentarios sobre algunos aspectos generales y le daré una recomendación. Dejaré que otras personas se centren en la secuencia de Fibonacci sobre la que preguntas específicamente.

Dices (en los comentarios) que quieres saber cómo se derivan las fórmulas. No sólo quieres saber cuál es la fórmula, sino por qué es así. Para esto específicamente yo señalaría dos cosas.

1. Algunas fórmulas son una cuestión de definición. Con la secuencia de Fibonacci la "fórmula" se define así. Hay todo tipo de relaciones con el mundo real que dejan claro que esta secuencia de números es "interesante". Y así es a menudo. Una fórmula puede ser una cuestión de definición, pero puede estar motivada por el mundo que nos rodea. Cómo sucede esto en general es probablemente demasiado amplio para entrar en él.

2. Otras fórmulas consisten en relacionar cosas ya definidas. Aquí la fórmula tendrá una prueba que justifique que la fórmula es verdadera. La prueba dependerá, por supuesto, de lo que se intente demostrar. Así, si te encuentras con una fórmula, puedes preguntarte cuál es la prueba para la fórmula es.

Una rama útil de las matemáticas que puede resultar interesante es el área del álgebra (abstracta). Aquí estudiamos conjuntos con operaciones. Estudiamos, por ejemplo, los grupos, que son conjuntos con una operación, y los anillos, que son conjuntos con dos operaciones. Creo que es en el álgebra donde se encuentra la definición precisa de cómo funcionan las cosas. Aquí puedes, por ejemplo, demostrar que $(-1)$ veces $(-1)$ es igual a $1$ simplemente a partir de los axiomas de un anillo. Pero primero hay que entender qué es exactamente un número menos. Uno hace esto más general para que los enteros puedan ser vistos como un ejemplo de un concepto más general. Así que mi recomendación sería estudiar un poco la teoría de grupos y la teoría de anillos.