Inicio · Parte 04 — Matemática discreta para computación
producto: |A × B| = |A| · |B|
suma (excluyentes): |A ∪ B| = |A| + |B|
entropía de una contraseña: log₂(espacio)Los dos principios básicos del conteo se distinguen por una palabra: si las decisiones son sucesivas (esto y aquello), se multiplican; si son alternativas excluyentes (esto o aquello), se suman. Casi todo error de conteo viene de aplicar uno donde correspondía el otro.
La aplicación más ilustrativa es el espacio de contraseñas. Con un alfabeto de 36 caracteres y longitud 8, hay 36⁸ ≈ 2.8·10¹² combinaciones; con solo 10 dígitos, 10⁸. La razón entre ambos es de más de 28 000, y ese factor es lo que separa una contraseña débil de una razonable frente a fuerza bruta.
Medir el espacio en bits de entropía —log₂ del número de combinaciones— es más informativo que dar el número, porque los bits se suman al añadir caracteres. Cada carácter adicional de un alfabeto de 36 símbolos añade log₂36 ≈ 5.17 bits. Esa es la cuenta que hace un estimador de fortaleza de contraseñas.
La misma regla es la que da 2ⁿ estados para n bits (clase 021), |B|^|A| funciones (clase 086) y el tamaño del espacio de búsqueda de cualquier problema combinatorio. En machine learning aparece al contar configuraciones de hiperparámetros: cinco parámetros con diez valores cada uno dan 10⁵ combinaciones, que es por lo que la búsqueda exhaustiva se abandona en favor de la aleatoria o bayesiana.
Espacio de contraseñas de 8 caracteres.
Alfanumérico (26 letras + 10 dígitos = 36 símbolos):
36⁸ = 2 821 109 907 456 ≈ 2.8·10¹²
entropía = 8·log₂(36) = 41.4 bits
Solo dígitos (10 símbolos):
10⁸ = 100 000 000 = 10⁸
entropía = 8·log₂(10) = 26.6 bits
Factor de ventaja: 2.8·10¹² / 10⁸ = 28 211
Regla del producto: 3 camisas × 4 pantalones = 12 conjuntos
Regla de la suma: 3 camisas o 4 pantalones = 7 prendasRegla del producto, de la suma y conteo de contraseñas.
python classes/part-04-matematica-discreta-para-computacion/087-principios-de-conteo/lab.py
compmath run 087regla_del_producto_3x4regla_de_la_suma_3+4contraseñas_alfanumericas_8contraseñas_solo_digitos_8factor_de_ventajabits_de_entropia{
"regla_del_producto_3x4": 12,
"regla_de_la_suma_3+4": 7,
"contraseñas_alfanumericas_8": 2821109907456,
"contraseñas_solo_digitos_8": 100000000,
"factor_de_ventaja": 28211.09907456,
"bits_de_entropia": 41.36
}Estimación de fortaleza de contraseñas, tamaño de espacios de búsqueda, conteo de configuraciones de hiperparámetros y cardinalidad de esquemas de datos.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.