Cómo leer fórmulas matemáticas en algoritmos

Muchos programadores sienten rechazo o inseguridad frente a enunciados repletos de símbolos griegos, sumatorias dobles o notación formal.

La realidad es simple: la notación matemática formal es pseudocódigo comprimido. Una vez que aprendés a mapear cada símbolo a su estructura de control equivalente (bucles for, acumuladores, condicionales if y arreglos), leer fórmulas se vuelve tan directo como leer código.

1. Sumatorias ($\sum$) $\longrightarrow$ Bucles for con Acumulador

El símbolo sigma mayúscula $\sum$ representa una suma acumulada de términos sobre un rango de índices.

Sumatoria simple

// Arreglo 'a' de tamaño n + 1 (1-indexed)
long long suma = 0;
for (int i = 1; i <= n; i++) {
    suma += a[i];
}

# Lista 'a' de tamaño n + 1 (1-indexed)
suma = sum(a[i] for i in range(1, n + 1))

Sumatoria doble (Bucles anidados)

long long total = 0;
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        total += (a[i] + a[j]);
    }
}

total = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        total += (a[i] + a[j])

Sumatoria condicional (Notación de corchetes de Iverson $[P]$)

El corchete $[P]$ vale $1$ si la condición $P$ es verdadera y $0$ si es falsa. En código equivale a un condicional if:

long long suma_positivos = 0;
for (int i = 1; i <= n; i++) {
    if (a[i] > 0) {
        suma_positivos += a[i];
    }
}

suma_positivos = sum(a[i] for i in range(1, n + 1) if a[i] > 0)

2. Productorias ($\prod$) $\longrightarrow$ Acumulador Multiplicativo

El símbolo pi mayúscula $\prod$ representa el producto de una secuencia de factores.

const long long MOD = 1e9 + 7;
 
long long producto = 1;
for (int i = 1; i <= n; i++) {
    producto = (producto * i) % MOD; // Módulo preventivo contra desbordes
}

MOD = 10**9 + 7
 
producto = 1
for i in range(1, n + 1):
    producto = (producto * i) % MOD

3. Aritmética Modular ($\equiv, \pmod m$) $\longrightarrow$ Operador %

La expresión $a \equiv b \pmod m$ (se lee “a es congruente con b módulo m”) significa que $a$ y $b$ dejan el mismo resto al dividirse por $m$, o equivalentemente, que $(a - b)$ es divisible por $m$.

Propiedades algebraicas en código

Definimos la constante usual de competencias:

const long long MOD = 1e9 + 7;

• Suma modular: $(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$.
• Resta modular: $(a - b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$. (El $+ m$ es crucial en C++ y Java para garantizar que el resultado no sea negativo).
• Multiplicación modular: $(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$.

Inverso Modular ($a^{-1} \pmod m$)

En aritmética modular no existe la división directa. Para calcular $\frac{a}{b} \pmod m$, multiplicamos por el inverso modular de $b$:

Por el Pequeño Teorema de Fermat, si $m$ es un número primo y $b$ no es múltiplo de $m$ ($\gcd(b, m) = 1$):

#include <cassert>
 
const long long MOD = 1e9 + 7;
 
long long power(long long base, long long exp, long long mod = MOD) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}
 
long long modInverse(long long b, long long mod = MOD) {
    long long b_mod = ((b % mod) + mod) % mod;
    assert(b_mod != 0 && "El inverso modular no existe para múltiplos de mod");
    return power(b_mod, mod - 2, mod);
}

MOD = 10**9 + 7
 
def power(base: int, exp: int, mod: int = MOD) -> int:
    return pow(base, exp, mod)
 
def mod_inverse(b: int, mod: int = MOD) -> int:
    b_mod = b % mod
    assert b_mod != 0, "El inverso modular no existe para múltiplos de mod"
    return pow(b_mod, mod - 2, mod)

[!NOTE] En C++, res * base entra en un long long siempre que mod $\le 3 \cdot 10^9$ (ya que $(3 \cdot 10^9)^2 \approx 9 \cdot 10^{18} < 2^{63}-1$). Para módulos mayores a $3 \cdot 10^9$ se debe recurrir a __int128. En Python los enteros tienen precisión arbitraria automática.

4. Coeficientes Binomiales ($\binom{n}{k}$) $\longrightarrow$ Combinatoria “n en k”

El símbolo $\binom{n}{k}$ (se lee “n en k” o “número combinatorio”) representa la cantidad de subconjuntos de $k$ elementos que se pueden formar a partir de un conjunto de $n$ elementos:

Identidad de Pascal (Base de Programación Dinámica)

const int MAXN = 1000;
const long long MOD = 1e9 + 7;
 
// Tabla de (MAXN + 1) x (MAXN + 1): ocupa ~8 MB de memoria
long long C[MAXN + 1][MAXN + 1];
 
void build_pascal() {
    for (int n = 0; n <= MAXN; n++) {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; k++) {
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD;
        }
    }
}

MAXN = 1000
MOD = 10**9 + 7
 
C = [[0] * (MAXN + 1) for _ in range(MAXN + 1)]
 
def build_pascal():
    for n in range(MAXN + 1):
        C[n][0] = C[n][n] = 1
        for k in range(1, n):
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD

5. Funciones Piso ($\lfloor x \rfloor$) y Techo ($\lceil x \rceil$) $\longrightarrow$ División Entera

• Piso ($\lfloor x \rfloor$): Redondea hacia abajo al entero menor o igual ($\lfloor 3.8 \rfloor = 3$, $\lfloor -2.2 \rfloor = -3$).
• Techo ($\lceil x \rceil$): Redondea hacia arriba al entero mayor o igual ($\lceil 3.1 \rceil = 4$).

Cálculo de Techo sin usar Punto Flotante

Para $a \ge 0$ y $b > 0$:

1. Fórmula estándar:

   $$\left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a + b - 1}{b} \right\rfloor$$

   En código: (a + b - 1) / b

2. Alternativa segura contra desborde: Si $a$ puede estar cerca del valor máximo de long long (LLONG_MAX), sumar $b - 1$ causaría un integer overflow. En ese caso, usá:

   $$\left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a}{b} \right\rfloor + [a \bmod b \neq 0]$$

   En código: a / b + (a % b != 0)

6. Notación Asintótica ($\mathcal{O}, \Omega, \Theta$) vs Escenarios de Entrada

Ejemplo con Quicksort clásico:

• El peor caso de Quicksort es $\Theta(n^2)$ (y por ende también $\mathcal{O}(n^2)$).
• El mejor caso de Quicksort es $\Theta(n \log n)$ (y por ende también $\Omega(n \log n)$).
• El caso promedio es $\Theta(n \log n)$.

Tabla de referencia: Complejidad vs $N$ para 1 Segundo ($10^8$ operaciones)

7. Conjuntos, Lógica Formal y Operadores Bitwise

Pertenencia y Cuantificadores

• $x \in S$: $x$ pertenece al conjunto $S$ (S.contains(x) en C++20, S.count(x) > 0 en C++ clásico o x in S en Python).
• $A \subseteq B$: $A$ es subconjunto de $B$.
• $A \cup B$: Unión de conjuntos.
• $A \cap B$: Intersección de conjuntos.
• $A \setminus B$: Diferencia de conjuntos (elementos en $A$ que no están en $B$).
• $\forall x \in S$: “Para todo elemento $x$ de $S$” (bucle donde todos deben cumplir la condición).
• $\exists x \in S$: “Existe al menos un elemento $x$ en $S$” (bucle con interrupción al hallar el primero).
• $\{ x \in S \mid P(x) \}$: “El conjunto de elementos $x$ de $S$ que cumplen el predicado $P(x)$”.

Operadores Lógicos vs Operadores Bitwise

8. Recurrencias de Programación Dinámica

Las fórmulas de DP definen el valor de un estado a partir de subproblemas más pequeños.

Ejemplo: Problema de la Mochila 0/1

Desglose paso a paso:

1. Dimensiones del estado: $dp[i][w]$ es la ganancia máxima considerando los primeros $i$ objetos con capacidad restante $w$.
2. Caso 1 ($w < \text{peso}_i$): El objeto $i$ es demasiado pesado para la capacidad actual; obligatoriamente se ignora ($dp[i-1][w]$).
3. Caso 2 ($w \ge \text{peso}_i$): Podemos elegir entre no tomarlo ($dp[i-1][w]$) o tomarlo ($dp[i-1][w - \text{peso}_i] + \text{valor}_i$). La función $\max$ selecciona la opción más rentable.

// peso y valor están 1-indexed (tamaño n + 1)
vector<vector<long long>> dp(n + 1, vector<long long>(W + 1, 0));
 
for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        if (w < peso[i]) {
            dp[i][w] = dp[i - 1][w];
        } else {
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - peso[i]] + valor[i]);
        }
    }
}

# peso y valor están 1-indexed (tamaño n + 1)
dp = [[0] * (W + 1) for _ in range(n + 1)]
 
for i in range(1, n + 1):
    for w in range(W + 1):
        if w < peso[i]:
            dp[i][w] = dp[i - 1][w]
        else:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - peso[i]] + valor[i])

9. Álgebra de Bits en Fórmulas

• $2^k$: Potencia de 2 $\implies$ Corrimiento de bits a la izquierda: 1LL << k en C++ o 1 << k en Python.
• Representación binaria como sumatoria: $$x = \sum_{b=0}^{B-1} 2^b \cdot \text{bit}_b(x)$$
• Cantidad de bits encendidos (popcount): $\sum_{b} \text{bit}_b(x)$
  • En C++20: std::popcount(static_cast<unsigned long long>(x)) (incluyendo <bit>).
  • En C++ clásico (GCC/Clang): __builtin_popcountll(x).
  • En Python: x.bit_count() (en Python 3.10+) o bin(x).count("1") (versiones anteriores).

10. Método en 4 Pasos para Programar Cualquier Fórmula

1. Paso 1: Tipos de datos e indexación: Verificá rangos numéricos. Si los resultados intermedios exceden $2 \cdot 10^9$, utilizá long long. Declarar arreglos con tamaño $n + 1$ para mantener coincidencia con los índices de la fórmula.
2. Paso 2: Localizar el caso base: ¿Qué valor toma la expresión cuando el índice vale $0$ o $1$? Esos valores inicializan tus arreglos o variables acumuladoras.
3. Paso 3: Estructura de bucles: Mapeá cada sumatoria o cuantificador exterior a un bucle for, y colocá la expresión central en el cuerpo más interno.
4. Paso 4: Factorización y optimización: Buscá si la fórmula permite separar variables independientes para reducir la complejidad temporal. Por ejemplo: $$\sum_{i=1}^n \sum_{j=1}^n a_i \cdot b_j = \left( \sum_{i=1}^n a_i \right) \cdot \left( \sum_{j=1}^n b_j \right)$$ Transforma un algoritmo de $\mathcal{O}(N^2)$ a $\mathcal{O}(N)$ precalculando sumas parciales.