Saltar al contenido ForoHackers

Combinatoria: por dónde empezar

Combinatoria
#910 · Ophuscado · · Denunciar

La combinatoria es el arte de contar: cuántas disposiciones, selecciones o estructuras cumplen una condición, y si existe alguna. En informática dice cuán grande es un espacio de búsqueda, cuántos casos necesita una prueba y cómo crece el trabajo de un algoritmo. También da las herramientas detrás del hashing, la codificación y la probabilidad.

Conceptos clave

  • Principios de conteo: las reglas de la suma y del producto, las permutaciones y combinaciones y los coeficientes binomiales.
  • Inclusión-exclusión: contar una unión sumando y restando las intersecciones.
  • Principio del palomar: con más objetos que cajas, alguna caja tiene dos; demuestra la existencia sin construir nada.
  • Recurrencias y funciones generadoras: problemas de conteo convertidos en ecuaciones sobre sucesiones.
  • Doble conteo y biyecciones: contar un conjunto de dos maneras, o emparejarlo con otro más fácil de contar.

Vocabulario

  • Permutación y combinación: una selección de elementos con orden o sin él.
  • Coeficiente binomial: el número de maneras de elegir k elementos de n.
  • Números de Catalan: una sucesión que cuenta paréntesis balanceados, árboles binarios y muchas otras estructuras.
  • Partición: una manera de dividir un conjunto, o de escribir un número como suma.

Qué estudiar, en orden

  1. Permutaciones, combinaciones y el teorema del binomio, con ejemplos pequeños comprobados por fuerza bruta.
  2. Escribe un programa que enumere todos los subconjuntos o permutaciones y compara su cuenta con la fórmula.
  3. Usa la inclusión-exclusión y el principio del palomar en acertijos.
  4. Resuelve problemas de conteo con recurrencias y programación dinámica.
  5. Conoce las funciones generadoras y úsalas para resolver una recurrencia en forma cerrada.

Etiquetas relacionadas

#discrete-math #probability #graph-theory #algorithms #puzzles

Inicia sesión o únete para responder.