La combinatoria juega un papel importante en la informática. Con frecuencia utilizamos métodos combinatorios tanto en el análisis como en el diseño de algoritmos. Por ejemplo, un método para encontrar un conjunto de portadas de vértices en un gráfico podría inspeccionar todos los subconjuntos posibles . Mientras que las funciones binomiales crecen exponencialmente, si es una constante fija, terminamos con un algoritmo de tiempo polinómico mediante análisis asintótico. k
Muchas veces los problemas de la vida real requieren mecanismos combinatorios más complejos que podemos definir en términos de recurrencias. Un ejemplo famoso es la secuencia de Fibonacci (ingenuamente) definida como:
Ahora calcular el valor del º plazo crece exponencialmente el uso de esta recurrencia, pero gracias a la programación dinámica, podemos calcular que en un tiempo lineal. Ahora, no todas las recurrencias se prestan a DP (por supuesto, la función factorial), pero es una propiedad potencialmente explotable cuando se define un recuento como una recurrencia en lugar de una función generadora.
Las funciones de generación son una forma elegante de formalizar algún recuento para una estructura dada. Quizás la más famosa es la función de generación binomial definida como:
Afortunadamente, esto tiene una solución de forma cerrada. No todas las funciones generadoras permiten una descripción tan compacta.
Ahora mi pregunta es esta: ¿con qué frecuencia se utilizan las funciones generadoras en el diseño de algoritmos? Es fácil ver cómo pueden ser explotados para comprender la tasa de crecimiento requerida por un algoritmo a través del análisis, pero ¿qué pueden decirnos sobre un problema al crear un método para resolver algún problema?
Si muchas veces el mismo recuento puede reformularse como una recurrencia, puede prestarse a la programación dinámica, pero quizás la misma función generadora tenga una forma cerrada. Por lo tanto, no está tan uniformemente cortado.
fuente
Respuestas:
Generar funciones es útil cuando diseña algoritmos de conteo. Es decir, no solo cuando busca el número de objetos que tienen una determinada propiedad, sino también cuando busca una forma de enumerar estos objetos (y, tal vez, generar un algoritmo para contar los objetos). Hay una muy buena presentación en el capítulo 7 de Matemáticas concretas por Ronald Graham, Donald Knuth y Oren Patashnik . Los siguientes ejemplos son de estos libros (los errores y la falta de claridad son míos).
Suponga que está buscando formas de hacer cambios con un conjunto de monedas dado. Por ejemplo, con denominaciones comunes de EE. UU., Las monedas posibles son . Para dar ¢ 42 en cambio, una posibilidad es ; otra posibilidad es . Escribiremos . De manera más general, podemos escribir una función generadora para todas las formas de dar cambio: En términos más técnicos, es un término en el espacio de series de potencia sobre las cinco variables[ 25 ] [ 10 ] [ 5 ] [ 1 ] [ 1 ] [ 10 ] [ 10 ] [ 10 ] [ 10 ] [ 1 ] [ 1 ] 42 ⟨ [ 25 ] [ 10 ][ 1 ] , [ 5 ] , [ 10 ] , [ 25 ] , [ 100 ] [ 25 ] [ 10 ] [ 5 ] [ 1 ] [ 1 ] [ 10 ] [ 10 ] [ 10 ] [ 10 ] [ 1 ] [ 1 ] H = Σ h ≥ 0 Σ q ≥ 0 Σ d ≥ 0 Σ n ≥ 0 Σ p ≥ 0 [ 100 ] h [ 25 ] q [ 10 ] d [ 5 ] n [ 1 ] p42 ⟨ [ 25 ] [ 10 ] [ 5 ] [ 1 ]2⟩ = ⟨ [ 10 ]4 4[ 1 ]2⟩
Un ejemplo más difícil: suponga que desea estudiar todas las formas de mosaico de rectángulos con dominó 2 × 1. Por ejemplo, hay dos formas de colocar un rectángulo de 2 × 2, ya sea con dos fichas de dominó horizontales o con dos fichas de dominó verticales. Contar el número de formas de enlosar un rectángulo es bastante fácil, pero el caso rápidamente no se hace evidente. Podemos enumerar todas las posibles inclinaciones de una banda horizontal de altura 3 al unir las fichas de dominó, lo que produce rápidamente patrones repetitivos:2 × n 3 × n
Nuevamente, lea Matemáticas concretas para una presentación menos apresurada³.
¹ Sé que mi lista está incompleta; suponga un EE. UU. simplificado adecuado para ejemplos matemáticos.²
² Además, si aparece, suponga monedas esféricas.
³ Y mejor composición tipográfica.
fuente
Recuerdo un problema que tuve que resolver durante un concurso de programación estudiantil en 2001. El problema era este:
Comencé con bucles anidados, pero rápidamente golpeé una pared. Luego me di cuenta de que tenía que comenzar enumerando lo que se podía hacer con las masas más ligeras antes de continuar con las más pesadas. Podría resolver el problema con muchos bucles sin procesar.
Si no hubiera sido jovenmente arrogante y autosuficiente en ese momento (y si hubiera sabido y practicado la generación de funciones), podría haber definido el problema de generar funciones como tal:
Defina como el OGF para la cantidad de formas en que se puede pesar un peso dado el conjunto de masas.F( x ) norte
¿Qué peso en la bandeja derecha puedo pesar con una sola masa de 1?
Tres posibilidades:
Entonces, hay una forma de pesar , una forma de pesar y una forma de pesar . La función generadora de esta masa es algo así como , que corresponde a:- 1 0 0 1 X- 1+ 1 + x
La función generadora para una sola masa es , que es:metro X- m+ 1 + xmetro
Dado un conjunto múltiple de masas, se expresa como el producto de las funciones generadoras de masa individuales:METRO F
Ahora, dado un paquete que puede realizar operaciones en polinomios, solo tiene que:
Y tu estas listo. Ahora su polinomio tiene la cantidad de formas de pesar en el índice . La única entrada es el conjunto múltiple de masas .w Mw ≥ 0 w METRO
Diseñé el algoritmo usando componentes matemáticamente sólidos. La parte principal del algoritmo, que es una división polinómica con el grado más bajo primero, es lineal y puede implementarse mediante un paquete estándar. Puede que no sea óptimo, pero ciertamente funciona mejor que lo que hice en el concurso, y de una manera menos propensa a errores.
Si observa detenidamente el proceso de división, verá rápidamente que el resto puede verse como el "estado oculto actual" en cada estado del proceso, y el cociente como resultado. El proceso finaliza cuando el "estado oculto actual" llega a cero en todas partes.
Puede implementar polinomios como matrices o, si son realmente escasos, como listas ordenadas de coeficientes de índice, y esto no cambiará el algoritmo.
fuente
fuente
Quizás el estudio extenso de Quicksort, y sus muchas variantes, es el ejemplo más claro. Hay consideraciones combinatorias que rigen la consideración de alternativas, y analizar las soluciones a ecuaciones bastante complejas muestra ventajas de rendimiento (o no) de ellas.
fuente