2. Historia y aplicaciones de la matemática discreta

2.1 Introducción

La matemática discreta no surgió como una única disciplina en un día determinado. Se formó a partir de problemas que exigían contar posibilidades, estudiar números enteros, describir conexiones, razonar con proposiciones y manipular símbolos. Estas preguntas existían mucho antes de la informática.

La computadora encontró en esas ideas un lenguaje natural. Un programa ejecuta pasos definidos, almacena datos finitos y toma decisiones lógicas; una red conecta nodos; un cifrado trabaja con propiedades de números enteros. Por eso los avances históricos de esta área son también parte de la historia de la computación.

2.2 Una línea de tiempo de ideas fundamentales

Esta cronología no es una lista de temas aislados. Cada idea aportó una manera de representar y resolver problemas que después se incorporó a las ciencias de la computación.

2.3 Números enteros y el algoritmo de Euclides

El estudio de los números enteros es una de las fuentes más antiguas de la matemática discreta. Un resultado clásico es el algoritmo de Euclides, que permite hallar el máximo común divisor de dos enteros mediante divisiones sucesivas.

Además de ser una técnica elegante, el algoritmo muestra dos rasgos propios de la disciplina: trabaja con una sucesión finita de enteros y reduce el problema en cada paso. Esa misma estructura reaparece en muchos algoritmos modernos.

function mcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);

  while (b !== 0) {
    const resto = a % b;
    a = b;
    b = resto;
  }

  return a;
}

console.log(mcd(252, 105)); // 21

2.4 Combinatoria: contar sin enumerar todo

La combinatoria estudia cómo contar configuraciones. Es importante porque muchos problemas tienen demasiadas posibilidades como para listarlas una por una. Las reglas de suma y producto permiten calcular cantidades a partir de la estructura del problema.

Si una aplicación permite elegir una letra mayúscula, una minúscula y un dígito para formar un código, existen 26 × 26 × 10 combinaciones. No necesitamos generar las 6 760 opciones para conocer su cantidad.

function cantidadDeCodigos(letrasMayusculas, letrasMinusculas, digitos) {
  return letrasMayusculas * letrasMinusculas * digitos;
}

const total = cantidadDeCodigos(26, 26, 10);
console.log(`Cantidad de códigos posibles: ${total}`); // 6760

Los principios combinatorios se usan para estimar el espacio de claves, generar casos de prueba, analizar juegos, diseñar algoritmos de búsqueda y medir el número de configuraciones de una estructura.

2.5 Euler y el nacimiento de la teoría de grafos

Uno de los hitos más conocidos ocurrió en el siglo XVIII, cuando Leonhard Euler estudió si era posible recorrer los siete puentes de Königsberg cruzando cada puente exactamente una vez. La clave fue ignorar distancias y formas geográficas para conservar solo las zonas de tierra y los puentes que las conectaban.

Ese cambio de representación produjo un grafo: las zonas se convirtieron en vértices y los puentes en aristas. El problema dejó de ser geográfico para convertirse en una pregunta sobre conexiones.

Hoy los grafos representan mapas, redes sociales, enlaces web, dependencias de paquetes, conexiones eléctricas y rutas de entrega. La lección metodológica de Euler sigue vigente: un buen modelo puede convertir un problema complejo en uno tratable.

2.6 El álgebra de Boole y la lógica digital

En el siglo XIX, George Boole desarrolló un álgebra para trabajar con proposiciones que pueden ser verdaderas o falsas. Sus operaciones básicas se parecen a las condiciones que usamos en un programa: conjunción (AND), disyunción (OR) y negación (NOT).

function puedePublicar(usuarioActivo, tienePermiso, estaBloqueado) {
  return usuarioActivo && tienePermiso && !estaBloqueado;
}

console.log(puedePublicar(true, true, false)); // true
console.log(puedePublicar(true, false, false)); // false

Décadas después, se observó que los valores verdadero y falso podían implementarse físicamente con dos estados eléctricos. Esta relación convirtió el álgebra de Boole en la base conceptual de los circuitos digitales.

2.7 Conjuntos, relaciones y rigor matemático

La teoría de conjuntos proporcionó un lenguaje común para describir colecciones de objetos. Una relación permite expresar vínculos entre elementos: «pertenece a», «es amigo de», «depende de» o «tiene permiso sobre».

Para un programador, estas nociones ayudan a separar conceptos que a veces se mezclan en el código. Un conjunto no registra duplicados; una función asigna a cada entrada una única salida; una relación puede asociar varios elementos entre sí.

Estas ideas reaparecen en esquemas de bases de datos, control de acceso, APIs, modelos de dominio y pruebas de propiedades.

2.8 La pregunta «¿qué puede calcularse?»

En el siglo XX, la lógica matemática planteó preguntas profundas: ¿puede existir un procedimiento mecánico que resuelva cualquier problema de una clase dada? Para analizarlas se crearon modelos abstractos de cálculo, entre ellos las máquinas de Turing y el cálculo lambda.

Un modelo abstracto no es una computadora física. Es una descripción simplificada que permite demostrar límites: hay problemas que pueden resolverse mediante algoritmos y otros para los que no existe un algoritmo general que siempre termine con la respuesta correcta.

La teoría de la computación estudia estos límites y también clasifica problemas según los recursos que necesitan. Es el fundamento de los temas de autómatas, lenguajes formales y complejidad.

2.9 Shannon: de la lógica a los circuitos

Claude Shannon mostró que el álgebra de Boole podía usarse para analizar y diseñar circuitos de conmutación. Una señal encendida o apagada puede representar 1 o 0; al combinar interruptores se implementan operaciones lógicas.

Esta conexión permitió pasar de fórmulas booleanas a puertas lógicas y, finalmente, a componentes digitales. Un procesador moderno contiene enormes cantidades de circuitos, pero en su base siguen apareciendo operaciones lógicas elementales.

La teoría de la información también introdujo herramientas para medir mensajes, detectar errores y transmitir datos con fiabilidad. Estas ideas están presentes en redes, archivos comprimidos y comunicaciones digitales.

2.10 Aplicación: diseño y análisis de algoritmos

La aplicación más directa de la matemática discreta en programación es el diseño de algoritmos. Las estructuras discretas definen qué datos se manejan; las demostraciones justifican corrección; el conteo y las recurrencias permiten analizar el costo.

Cuando una entrada crece de 1 000 a 1 000 000 de datos, las diferencias entre algoritmos se vuelven decisivas. El análisis asintótico permite anticiparlas sin depender de una computadora particular.

2.11 Aplicación: estructuras de datos y bases de datos

Las estructuras de datos son representaciones concretas de objetos discretos. Un arreglo representa una secuencia indexada; una pila impone un orden de acceso; un árbol organiza jerarquías; una tabla hash asocia claves con valores.

Las bases de datos, por su parte, se apoyan en relaciones y conjuntos. Una consulta filtra filas, combina tablas y proyecta columnas. Las restricciones impiden estados inválidos, por ejemplo, que una clave foránea apunte a un registro inexistente.

const usuarios = new Map([
  [101, "Ana"],
  [102, "Bruno"],
  [103, "Carla"]
]);

console.log(usuarios.has(102)); // true
console.log(usuarios.get(102)); // Bruno

La elección entre una lista, un árbol, un grafo o una tabla hash cambia qué operaciones son naturales y qué costo tienen. Por eso la modelización matemática precede a la implementación.

2.12 Aplicación: redes, mapas y dependencias

Las redes se modelan con grafos. Un vértice puede ser una computadora, una ciudad, una persona o un módulo de software. Una arista puede representar un cable, una ruta, una amistad o una dependencia.

El siguiente ejemplo usa una lista de adyacencia, una representación común de un grafo. La función muestra los vecinos de un nodo y, por lo tanto, produce una salida visible al ejecutarse.

const red = {
  servidor: ["api", "baseDeDatos"],
  api: ["servidor", "cache"],
  baseDeDatos: ["servidor"],
  cache: ["api"]
};

function mostrarVecinos(grafo, nodo) {
  const vecinos = grafo[nodo] ?? [];
  console.log(`${nodo} se conecta con: ${vecinos.join(", ")}`);
}

mostrarVecinos(red, "api"); // api se conecta con: servidor, cache

Los algoritmos de grafos permiten encontrar caminos, detectar ciclos de dependencia, calcular componentes conectados y distribuir recursos en una red.

2.13 Aplicación: criptografía y ciberseguridad

La criptografía moderna se apoya principalmente en teoría de números, aritmética modular, combinatoria y probabilidad. La seguridad de diversos sistemas depende de que ciertas operaciones sean fáciles de calcular, pero difíciles de invertir sin información adicional.

Por ejemplo, el algoritmo de Euclides extendido permite obtener inversos modulares; los números primos intervienen en sistemas de clave pública; las funciones hash convierten entradas de longitud variable en valores de tamaño fijo.

Entender las bases discretas ayuda a evitar errores graves, como usar espacios de claves demasiado pequeños, repetir valores aleatorios o implementar de forma incorrecta operaciones de seguridad.

2.14 Aplicación: compiladores y validación de texto

Un compilador necesita reconocer si un texto cumple las reglas de un lenguaje. Para ello utiliza conceptos de lenguajes formales, expresiones regulares, autómatas y gramáticas. El mismo enfoque aparece al validar formularios, interpretar comandos o procesar protocolos.

function clasificarToken(texto) {
  if (/^\d+$/.test(texto)) return "entero";
  if (/^[A-Za-z_][A-Za-z0-9_]*$/.test(texto)) return "identificador";
  return "no reconocido";
}

console.log(clasificarToken("2026")); // entero
console.log(clasificarToken("total_final")); // identificador
console.log(clasificarToken("total-final")); // no reconocido

Una expresión regular reconoce un patrón limitado. Para definir construcciones con anidamiento, como paréntesis balanceados o bloques de código, se necesitan modelos más potentes, como las gramáticas libres de contexto.

2.15 Aplicación: inteligencia artificial y optimización

La inteligencia artificial utiliza tanto matemática continua como discreta. En el lado discreto aparecen árboles de decisión, grafos de conocimiento, búsqueda de estados, satisfacción de restricciones, planificación y optimización combinatoria.

Un sistema de planificación puede representar cada situación como un estado y cada acción como una arista hacia otro estado. Encontrar una secuencia de acciones para alcanzar una meta es un problema de búsqueda en grafos.

También se usan técnicas discretas para asignar recursos, elegir horarios, agrupar datos y resolver problemas con reglas que deben cumplirse simultáneamente.

2.16 Aplicación: sistemas distribuidos

Cuando varios procesos intercambian mensajes, no existe necesariamente un reloj global perfecto. La matemática discreta ayuda a modelar eventos, orden parcial, consenso, exclusión mutua y tolerancia a fallas.

Por ejemplo, en una aplicación colaborativa importa saber si una edición ocurrió antes, después o de forma concurrente con otra. Las relaciones de orden y los grafos permiten describir estas dependencias sin confundir el tiempo físico con el orden lógico de los eventos.

2.17 Una misma idea en distintos campos

Las aplicaciones cambian, pero los modelos suelen repetirse. Reconocer esa repetición permite reutilizar conocimiento y soluciones.

La matemática discreta es valiosa precisamente porque abstrae: conserva la estructura relevante y deja de lado detalles que no cambian la solución.

2.18 Qué debes recordar de este tema

• La matemática discreta se desarrolló a partir de la teoría de números, el conteo, la lógica, los conjuntos y los grafos.
• El algoritmo de Euclides, la teoría de grafos de Euler y el álgebra de Boole siguen teniendo aplicaciones directas.
• Los modelos de computación y los lenguajes formales permiten estudiar qué problemas son resolubles y cómo reconocer textos válidos.
• Los algoritmos, las estructuras de datos, las bases de datos, las redes y la criptografía se apoyan en conceptos discretos.
• Un mismo modelo matemático puede resolver problemas de áreas aparentemente distintas.

2.19 Conclusión

La historia de la matemática discreta muestra que las ideas más útiles de la informática no aparecieron únicamente con las computadoras. Se construyeron durante siglos al estudiar números, reglas lógicas y conexiones. La informática les dio nuevos problemas, velocidad y escala.

En el próximo tema distinguiremos con más precisión los objetos discretos de los objetos continuos y veremos cómo elegir el modelo adecuado para cada problema.