Es Sigma $\Sigma$ ¿una forma matemática de hacer un bucle for?

Question

Soy programador desde hace diez años, y hace tiempo se me daban bien las matemáticas. Esos días ya han pasado. Estoy tomando algunas clases en línea y ahora me encuentro con la necesidad de recordar las matemáticas que aprendí en la universidad y todo se ha ido al traste.

En concreto, tengo una pregunta sobre $\Sigma$ (Sigma):

En un $\Sigma$ hay una N por encima de la ecuación $\Sigma$ y un $i = 1$ (o algún número) abajo. Si alguien puede ayudar a mi mente de programador - esto parece un para el bucle en la programación. ¿Es eso esencialmente lo que está pasando con todo dentro de la $()$ de la $\Sigma$ ? Simplemente calcula todos los valores para cada iteración de $i$ a N y luego los suma todos?

Answer 1

Pues sí, algo así como . Pero no realmente , OMI.

Lo que hacen la mayoría de los lenguajes de programación es una torpeza, matemáticamente hablando. Un bucle for imperativo incrementa una variable . Eso no debería ser posible: las matemáticas no saben tiempo . Si defines algo una vez, entonces se mantendrá conceptualmente siempre es decir, si se empieza con $i = 0$ no es posible tener después $i=3$ .

Lo que realmente sucede, matemáticamente, es que se escribe un abstracción una expresión para todos $i$ . A continuación, se aplica a esa expresión la operación de orden superior "suma sobre todas esas $i$ en algún rango". La variable $i$ nunca tiene un valor particular, es sólo un marcador de posición para "considerar el valor aquí".

Existe un marco matemático adecuado que puede expresar de forma agradable cálculos como una suma. Se llama cálculo lambda . En esto, tal abstracción sobre alguna variable se llama expresión lambda , escrito como * $$ \lambda i \mapsto \frac1{2^i} $$ Más comúnmente, este tipo de abstracción se llamaría función y escrito $$ f : \mathbb{N}\to\mathbb{Q}, \quad f(i) = \frac{1}{2^i} $$ o, en los lenguajes de programación, algo como

double f(int i) {
  return 1.0 / 2**i;
}

Ahora bien, lo que hace un operador de suma es que toma dicha función lambda y arroja un número igual a la función evaluada con todos los argumentos posibles en un rango y sumados. Por ejemplo, $$ S = \sum_{i=0}^{5}\frac1{2^i} $$ es, en cierto modo, una notación abreviada de algo $$ S = \Sigma(0,5,f). $$ Tenga en cuenta que no he escrito $f(i)$ pero sólo $f$ Esto es no el resultado de aplicar $f$ a cualquier $i$ pero el objeto de la función $f$ en sí mismo. No es un número, sino una función.

No es necesario dar primero $f$ un nombre y luego usarlo en la suma, también puedo simplemente poner la expresión lambda: $$ S = \Sigma(0,5,\lambda i\mapsto 1/2^{i}). $$ Entiendo las sumas como una forma especial de escribir esta expresión.

Ahora bien, ¿cómo se puede implementar el operador de suma en un ordenador? Bueno: en un lenguaje imperativo, un bucle for sería sin duda una forma razonable de hacerlo. Como † ,

double sumFromTo(int i0, int iend, function<double(int)> f) {
  int i;
  double result;
  for(i=0; i<=iend; ++i) {
    result += f(i);
  }
  return result;
}

Pero como dije, matemáticamente no tiene sentido cambiar el valor de una variable. Sin embargo, es posible definir el equivalente de un bucle de este tipo directamente en el cálculo lambda: mediante recursividad . Esto requiere algunas definiciones un poco extrañas para utilizarlo en el entorno matemático/lógico original, pero también puede escribirse en lenguajes de programación:

double sumFromTo_rec(int i, int iend, function<double(int)> f) {
  if (i<=iend)
    return f(i) + sumFromTo_rec(i+1, iend, f);
   else
    return 0;
}

Ahora, en la llamada recursiva, i tendrá el valor de i+1 de la llamada exterior. Así que, ¿estoy haciendo una mutación matemática poco sólida aquí de nuevo? No, en realidad ¡! El i El argumento de la función es sólo una abstracción. En la llamada a la función interna, es simplemente una diferente que casualmente también se llama i (pero eso es un detalle de implementación irrelevante).

Puede que le parezca una tontería. Si el ordenador puede simplemente reutilizar la misma variable i incrementándola, ¿por qué deberíamos molestarnos en definir una nueva? En cierto modo tendrías razón. sumFromTo_rec sería de hecho ineficiente en un lenguaje como C, porque el ordenador tendría que asignar un nuevo entero real en la pila en cada llamada a la función.

Sin embargo, desde un punto de vista práctico, la mutación de variables también abre numerosas posibilidades de errores de programación. Lenguaje de programación funcional por lo tanto, evitar (o prohibir por completo ) esto. Estos lenguajes han llegado con varias optimizaciones como llamadas de cola para evitar la sobrecarga de asignar nuevas variables en cada llamada recursiva (así que, básicamente, escribes una semántica matemática limpia pero bajo el capó la misma memoria se reutiliza en realidad, como lo haría en un lenguaje imperativo).

Si eres un programador interesado en las matemáticas (o un matemático interesado en la computación) te recomiendo que consultes Haskell . Es un lenguaje de programación funcional moderno con una semántica muy limpia, pero con un gran rendimiento y una buena compatibilidad con las "aplicaciones del mundo real". La suma recursiva anterior se vería en Haskell tan simple como

sumFromTo i iEnd f
    | i<=iEnd   = f i + sumFromTo (i+1) iEnd f
    | otherwise  = 0

Esto es bastante similar a cómo la rigurosa definición recursiva de $\sum$ en notación matemática sería: $$ \sum_{i=i_0}^{i_{\text{end}}} f(i) = \begin{cases} f(i_0) + \sum_{i=i_0+1}^{i_{\text{end}}}f(i) & \text{if $i_0 < i_{\text{end}}$} \\ 0 & \text{otherwise} \end{cases} $$ Observe que $f(i)$ como tal nunca se evalúa realmente: siempre es $f(i_0)$ (sin embargo, esa variable tiene un valor diferente en cada nivel de recursión). Esto se refleja mejor en un lenguaje de programación que en la notación matemática: los primeros realmente hacen un punto de no aplicando $f$ a cualquier cosa cuando se habla de la función en sí misma, y no del resultado de aplicar esa función a un argumento concreto.

---

* _{La notación estándar clásica en el cálculo lambda es en realidad $\lambda i.\ 1/{2^i}$ pero creo que la flecha aclara más lo que ocurre que el punto. La mayoría de los lenguajes de programación utilizan un símbolo de flecha si ofrecen funciones lambda, por ejemplo, en Haskell se escribiría}

sumFromTo 0 6 (\i -> 1/2^i)

† _{A diferencia de las matemáticas, en la programación se prefiere generalmente (excepto en Fortran y Matlab, que no considero muy bien diseñados) expresar el rango <em>con el límite superior excluido </em>. Esta resulta ser la convención más útil en la práctica; véase <a href="https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html" rel="noreferrer">lo que el famoso Dijkstra escribió al respecto </a>.}

Answer 2

Sí, más o menos. Por definición (recursiva), $$\sum_{i=0}^0 a_i := a_0 $$ y $$\sum_{i=0}^n a_i :=\sum_{i=0}^{n-1} a_i + a_n $$ o, descuidadamente, $$\sum_{i=0}^n a_i :=a_0 + a_1+ \dots +a_n$$

Answer 3

En Mathematica a menudo cambio entre los comandos Sum y Table como en estos ejemplos:

Ejemplo 1:

$\sum\limits_{n=1}^{n=1} 1 = 1 = 1 $

$\sum\limits_{n=1}^{n=2} 1 = 2 = 1+1 $

$\sum\limits_{n=1}^{n=3} 1 = 3 = 1+1+1 $

$\sum\limits_{n=1}^{n=4} 1 = 4 = 1+1+1+1 $

$\sum\limits_{n=1}^{n=5} 1 = 5 = 1+1+1+1+1 $

Sum[1,{n,1,5}]

que sale: 5

en comparación con:

Table[1,{n,1,5}]

que da como resultado: {1,1,1,1,1}

Ejemplo 2:

$\sum\limits_{n=1}^{n=1} n = 1 = 1 $

$\sum\limits_{n=1}^{n=2} n = 3 = 1+2$

$\sum\limits_{n=1}^{n=3} n = 6 = 1+2+3$

$\sum\limits_{n=1}^{n=4} n = 10 = 1+2+3+4$

$\sum\limits_{n=1}^{n=5} n = 15 = 1+2+3+4+5$

Sum[n,{n,1,5}]

que da salida: 15

en comparación con:

Table[n,{n,1,5}]

que da como resultado: {1,2,3,4,5}

Ejemplo 3:

$\sum\limits_{n=1}^{n=1} \frac{n(n+1)}{2} = 1 = 1$

$\sum\limits_{n=1}^{n=2} \frac{n(n+1)}{2} = 4 = 1+3$

$\sum\limits_{n=1}^{n=3} \frac{n(n+1)}{2} = 10 = 1+3+6$

$\sum\limits_{n=1}^{n=4} \frac{n(n+1)}{2} = 20 = 1+3+6+10$

$\sum\limits_{n=1}^{n=5} \frac{n(n+1)}{2} = 35 = 1+3+6+10+15$

Sum[n*(n+1)/2,{n,1,5}]

que sale: 35

en comparación con:

Table[n*(n+1)/2,{n,1,5}]

que da como resultado: {1, 3, 6, 10, 15}

Sin embargo, no sé si es una buena respuesta a su pregunta.

Answer 4

Sí, en efecto.

Por ejemplo:

$$\sum_{i = 1}^n\frac{x_i}{n}$$

se considera generalmente la media de una serie $\{x_1, x_2, x_3, x_4, ... x_i\}$ .

Eso se traduciría en un foreach sobre un array que divide todos los valores por el array.length y los resume a todos.

Espero que esto haya servido de ayuda.

Answer 5

Definitivamente sí.

El matemático lo escribiría así:

$\sum\limits_{i=m}^n f(i)$

Y el programador lo escribiría así:

result = 0
for (i=m; i<=n; i++) {
    result += f(i)
}

Puedes pensar en m como el start index y n como el end index .