Algorithmique et programmation Travaux dirigés, 26 et 29 octobre 1998

Louis Granboulan

1 Structures de données

1. Files et piles

Rappels : une file est munie de deux opérations, enfiler et défiler et d’un test vide. Fonctionnement FIFO (first in, first out). Une pile munie de deux opérations, push et pop et d’un test vide. Fonctionnement LIFO (last in, first out).

(a) Trouvez une méthode pour simuler une file avec des piles, telle que la complexité amortie d’une opération sur la file soit une constante.

2. Arbres binaires

Rappels : tout nœud d’un arbre binaire a éventuellement un fils gauche et un fils droit. Si on complète cet arbre en rajoutant des fils à tous les nœuds qui n’en ont pas deux, on obtient un arbre binaire complet et les nœuds rajoutés sont les feuilles de l’arbre. On note n la taille d’un arbre binaire, c’est-à-dire le nombre de ses nœuds. L’arbre binaire complet correspondant a donc n + 1 feuilles. On se propose de calculer le nombre C_{n} d’arbres binaires de taille n, appelé nombre de Catalan.

(a) Commencez par établir une correspondance entre les arbres binaires complets de taille n dont un nœud ou une feuille est distingué et les arbres binaires complets de taille n + 1 dont une feuille est distinguée. En déduire que (n + 2)C_{n+1} = 2(2n + 1)C_{n}.

(b) En déduire que C_{n} = \frac{1}{n+1} \binom{2n}{n}.

(c) Donner un algorithme de génération aléatoire et équiprobable d’un arbre binaire de taille n.

2 Fractions égyptiennes

On appelle fraction égyptienne l’inverse d’un nombre entier.

1. Trouvez plusieurs algorithmes différents pour décomposer un rationnel positif en une somme de fractions égyptiennes distinctes.

2. Réfléchir au nombre minimum de termes pour représenter un rationnel et à la minimisation du plus grand dénominateur d’une représentation.

http://www.ics.uci.edu/~eppstein/numth/egypt/.