Récurrences et génération de fonctions dans les algorithmes

La combinatoire joue un rôle important en informatique. Nous utilisons fréquemment des méthodes combinatoires à la fois dans l'analyse et la conception dans les algorithmes. Par exemple, une méthode pour trouver un ensemble de couvertures -vertex dans un graphique pourrait simplement inspecter tous les sous-ensembles \ binom {n} {k} possibles. Alors que les fonctions binomiales croissent de façon exponentielle, si k est une constante fixe, nous nous retrouvons avec un algorithme de temps polynomial par analyse asymptotique.$k$$\binom{n}{k}$$k$

Souvent, les problèmes réels nécessitent des mécanismes combinatoires plus complexes que nous pouvons définir en termes de récurrences. Un exemple célèbre est la séquence de fibonacci (naïvement) définie comme:

$f(n) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n = 0 \\ f(n-1) + f(n-2) & \text{otherwise} \end{cases}$

Maintenant, le calcul de la valeur du $n$ ème terme croît de façon exponentielle en utilisant cette récurrence, mais grâce à la programmation dynamique, nous pouvons le calculer en temps linéaire. Désormais, toutes les récurrences ne se prêtent pas à DP (au contraire, la fonction factorielle), mais c'est une propriété potentiellement exploitable lors de la définition de certains comptes comme une récurrence plutôt qu'une fonction génératrice.

La génération de fonctions est une manière élégante de formaliser un certain nombre pour une structure donnée. La fonction de génération binomiale la plus connue est peut-être la suivante:

$(x + y)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k}x^{\alpha - k}y^k$

Heureusement, cela a une solution sous forme fermée. Toutes les fonctions de génération ne permettent pas une description aussi compacte.

Maintenant, ma question est la suivante: à quelle fréquence les fonctions de génération sont-elles utilisées dans la conception d'algorithmes? Il est facile de voir comment ils peuvent être exploités pour comprendre le taux de croissance requis par un algorithme via l'analyse, mais que peuvent-ils nous dire sur un problème lors de la création d'une méthode pour résoudre un problème?

Si plusieurs fois le même nombre peut être reformulé comme une récurrence, il peut se prêter à une programmation dynamique, mais là encore, la même fonction de génération a peut-être une forme fermée. Il n'est donc pas coupé de façon aussi uniforme.

La génération de fonctions est utile lorsque vous concevez des algorithmes de comptage. Autrement dit, non seulement lorsque vous recherchez le nombre d'objets ayant une certaine propriété, mais également lorsque vous recherchez un moyen d'énumérer ces objets (et, peut-être, de générer un algorithme pour compter les objets). Il y a une très bonne présentation dans le chapitre 7 de Concrete Mathematics par Ronald Graham, Donald Knuth et Oren Patashnik . Les exemples ci-dessous sont tirés de ces livres (les erreurs et le manque de clarté sont les miens).

Supposons que vous cherchiez les moyens de faire des changements avec un ensemble de pièces donné. Par exemple, avec les coupures américaines courantes¹, les pièces possibles sont . Pour donner ¢ 42 en monnaie, une possibilité est ; une autre possibilité est . Nous écrirons . Plus généralement, nous pouvons écrire une fonction génératrice pour toutes les façons d'apporter du changement: En termes plus techniques, est un terme dans l'espace des séries de puissance sur les cinq 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 ] $42 \langle [25][10][5][1]^2 \rangle = \langle [10]^4 [1]^2 \rangle$

$$H = \sum_{h\ge0} \sum_{q\ge0} \sum_{d\ge0} \sum_{n\ge0} \sum_{p\ge0} [100]^h [25]^q [10]^d [5]^n [1]^p$$ [ 100 ] , [ 25 ] , [ 10 ] , [ 5 ] , [ 1 ] ⟨ [ 100 ] h [ 25 ] q [ 10 ] d [ 5 ] n [ 1 ] p ⟩ = 100 h + 25 q + 10 d + 5 n + p v v H $H$$[100], [25], [10], [5], [1]$. Définissez l'évaluation d'un monôme dans cet espace par Ensuite, les façons de donner cents en variation sont le nombre de monômes dont l'évaluation est . Nous pouvons exprimer de manière incrémentale, en notant d'abord les façons dont donne le changement en centimes seulement, puis les façons en donnant le changement en centimes et nickels, et ainsi de suite. ( dire pas de pièce.) $$\langle [100]^h [25]^q [10]^d [5]^n [1]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$ $v$$v$$H$$P$I P = I + [ 1 ] + [ 1 ] 2 + [ 1 ] 3 + … = $N$$I$ $$\begin{gather*} P = I + [1] + [1]^2 + [1]^3 + \ldots = \frac{I}{I - [1]} \\ N = (I + [5] + [5]^2 + [5]^3 + \ldots) P = \frac{P}{I - [5]} \\ D = (I + [10] + [10]^2 + [10]^3 + \ldots) N = \frac{N}{I - [10]} \\ Q = (I + [25] + [25]^2 + [25]^3 + \ldots) D = \frac{D}{I - [25]} \\ H = (I + [100] + [100]^2 + [100]^3 + \ldots) Q = \frac{Q}{I - [100]} \\ \end{gather*}$$ Si vous voulez compter et non seulement énumérer les façons d'apporter des changements, alors il existe un moyen simple d'utiliser la série formelle que nous avons obtenue. Appliquer l'homomorphisme Le coefficient de dans est le nombre de façons de donner cents en monnaie. $$S: \quad [1] \mapsto X, \quad [5] \mapsto X^5, \quad [10] \mapsto X^{10}, [25] \mapsto X^{25}, [100] \mapsto X^{100}$$ $X^v$$S(C)$$v$

Un exemple plus difficile: supposons que vous vouliez étudier toutes les façons de carreler des rectangles avec des dominos 2 × 1. Par exemple, il existe deux façons de carreler un rectangle 2 × 2, soit avec deux dominos horizontaux, soit avec deux dominos verticaux. Compter le nombre de façons de carreler un rectangle est assez facile, mais le cas devient rapidement non évident. Nous pouvons énumérer tous les pavages possibles d'une bande horizontale de hauteur 3 en collant les dominos ensemble, ce qui donne rapidement des motifs répétitifs: $2 \times n$$3 \times n$

$$\begin{cases} U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\ V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\:-} V \\ \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\:-\\=} \Lambda \\ \end{cases}$$ où les formes amusantes représentent des arrangements de dominos élémentaires: n'est pas un domino, est un domino vertical au-dessus de la partie gauche d'un domino horizontal, est un domino vertical aligné avec le bas de la bande de hauteur 3, est un domino horizontal aligné avec le haut de la bande plus deux dominos horizontaux en dessous et un pas à droite, etc. Ici, la multiplication représente la concaténation horizontale et n'est pas commutative, mais il existe des équations entre les motifs élémentaires qui forment des variables dans cette série de puissances. Comme précédemment avec les pièces, nous pouvons remplacer pour chaque domino et obtenir une série génératrice pour le nombre de pavages d'un$\mathsf{o}$$\mathsf{L}$$\substack{\strut\\\mathsf{I}}$$\substack{\:-\\=}$$X$$3 \times (2n/3)$ rectangle (c'est-à-dire que le coefficient de est le nombre de façons de carreler un rectangle de la zone , qui contient dominos et a la largeur ). La série peut également être utilisée de manière plus polyvalente; par exemple, en distinguant les dominos verticaux et horizontaux, nous pouvons compter les pavages avec un nombre donné de dominos verticaux et horizontaux.$X^{3k}$$6k$$3k$$2k$

Encore une fois, lisez Concrete Mathematics pour une présentation moins précipitée³.

¹ _{Je sais que ma liste est incomplète; supposons un US simplifié adapté aux exemples mathématiques.²}
² _{De plus, s'il apparaît, supposons des pièces sphériques.}
³ _{Et une meilleure composition.}

Je me souviens d'un problème que j'ai dû résoudre lors d'un concours de programmation étudiante en 2001. Le problème était celui-ci:

Étant donné des masses de 1, 7, 13, ... (je ne me souviens pas quelles masses, mais il y avait un ensemble fini et déterminé de masses), concevez une fonction qui détermine si un poids donné peut être pesé sur une balance avec ce ensemble de masses.

J'ai commencé avec des boucles imbriquées, mais j'ai rapidement heurté un mur. Puis j'ai réalisé que je devais commencer par énumérer ce qui peut être fait avec les masses plus légères avant de continuer avec les plus lourdes. Je pourrais résoudre le problème avec beaucoup de boucles non imbriquées.

Si je n'avais pas été arrogant et autosuffisant à ce moment-là (et si j'avais connu et pratiqué des fonctions de génération), j'aurais peut-être défini le problème de la génération de fonctions en tant que telles:

Définissez comme OGF pour le nombre de façons dont un poids peut être pesé compte tenu de l'ensemble des masses.$f(x)$$n$

Quel poids sur le plateau droit puis-je peser avec une seule masse de 1?

Trois possibilités:

• Si je mets la masse sur le plateau gauche, je peux peser 1.
• Si je mets la masse sur le plateau droit, je peux peser -1.
• Si je n'utilise pas la masse, je peux peser 0.

Il y a donc une façon de peser , une façon de peser et une façon de peser . La fonction génératrice de cette masse est quelque chose comme , ce qui correspond à:$-1$$0$$1$$x^{-1} + 1 + x$

$$\frac{1 - x^3}{x(1-x)}$$

La fonction génératrice pour une seule masse est , qui est:$m$$x^{-m} + 1 + x^m$

$$\frac{1 - x^{3m}}{x^m(1-x^m)}$$

Étant donné un ensemble de masses, est exprimé comme le produit des fonctions génératrices de masse unique:$M$$f$

$$f(x) = \frac{\prod_{m \in M}(1 - x^{3m})}{x^{\sum_{m \in M}m}\prod_{m \in M}(1 - x^{m})}$$

Maintenant, étant donné un package qui peut effectuer des opérations sur des polynômes, il vous suffit de:

• Calculez les deux produits.
• Effectuez la division de ces produits, en commençant par le degré le plus bas. (qui se termine)
• Décaler le polynôme (division euclidienne par , en gardant le quotient et en vidant le reste)$x^k$

Et tu as fini. Votre polynôme a maintenant le nombre de façons de peser à l'indice . La seule entrée est le multi -ensemble de masses .$w \ge 0$$w$$M$

J'ai conçu l'algorithme en utilisant des composants mathématiquement solides. La partie principale de l'algorithme, qui est une division polynomiale avec le degré le plus bas en premier, est linéaire et peut être implémentée par un package standard. Ce n'est peut-être pas optimal, mais il fonctionne certainement mieux que ce que j'ai fait au concours, et de manière moins sujette aux erreurs.

Si vous regardez de près le processus de division, vous voyez rapidement que le reste peut être considéré comme "l'état caché actuel" à chaque état du processus, et le quotient comme résultat. Le processus se termine lorsque «l'état caché actuel» atteint zéro partout.

Vous pouvez implémenter des polynômes sous forme de tableaux ou, s'ils sont vraiment très rares, sous forme de listes ordonnées à coefficient d'indexation, et cela ne changera pas l'algorithme.

Lors du développement d'un algorithme de maximisation sous-modulaire monotone sur un matroïde, nous avons dû résoudre la récurrence Après avoir remarqué que , nous avons réduit le problème au calcul d'une séquence universelle . Ce dernier a été accompli en utilisant des fonctions génératrices, et de là nous avons obtenu une formule explicite pour , en utilisant à nouveau des fonctions génératrices. Vous pouvez trouver la solution dans le document si vous êtes curieux, bien que nous n'ayons jamais pris la peine d'inclure cette dérivation.

$$\ell \gamma^{(m)}_{\ell+1} = (2\ell-m) \gamma^{(m)}_\ell + (m - \ell + 1) \gamma^{(m)}_{\ell-1}, \quad \gamma^{(m)}_0 = 1, \quad \gamma^{(m)}_{m+1} = e.$$ $\gamma^{(m)}_\ell = m(\gamma^{(m-1)}_\ell - \gamma^{(m-1)}_{\ell-1})$$\gamma^{(0)}$$\gamma^{(m)}$

L'étude approfondie de Quicksort et de ses nombreuses variantes est peut-être l'exemple le plus clair. Là, des considérations combinatoires ont gouverné la prise en compte des alternatives, et l'analyse des solutions à des équations assez complexes en montre les avantages (ou non) en termes de performances.