Dans ce problème, on va s'intéresser à des chansons dont les paroles peuvent être générées par des algorithmes, et on va analyser le temps qu'il faut pour les chanter. Les notions utilisées sont présentées dans le chapitre Introduction à l'analyse des algorithmes.

99 DM à rendre pour lundi...¶

On considère la chanson suivante :

Algorithme : DMàRendre

Entrée : \(n \in \N\)

Paroles :

Pour i allant de n à 1
- Chanter « i DM à rendre pour lundi »
- Chanter « prends-en un, fais-le, i-1 DM à rendre pour lundi »
Chanter « plus de DM à rendre pour lundi »
Chanter « je retourne en cours, n DM à rendre pour lundi »

On considère ici que chaque instruction Chanter a une complexité linéaire dans le nombre de mots chantés.

On supposera dans tout ce sujet, sauf contre-indication, qu'un entier est un unique mot.

Question 1

Quelle est la complexité de cette chanson ?

Corrigé

On peut noter \(a\) le nombre de mots chantés dans une itération de la boucle et \(b\) le nombre de mots de la conclusion, qui ne dépendent pas de \(n\).

L'appel DMàRendre(n) va donc chanter \(b + na = O(n)\) mots, et même \(\Theta(n)\) mots. Sa complexité est linéaire.

Alouette¶

Algorithme : Alouette

Entrées :

\(n \in \N\) ;
un tableau t de \(n\) chaînes de caractères comportant chacune un mot.

Paroles :

Chanter « Alouette, gentille alouette, alouette, je te plumerai. »
Pour i allant de 0 à n-1
- Chanter « Je te plumerai t[i]. Je te plumerai t[i]. »
- Pour j allant de i-1 à 0
  - Chanter « Et t[j] ! Et t[j] ! »
- Chanter « Alouette ! Alouette ! Aaaaaaaa.... »
- Chanter « ...alouette, gentille alouette, alouette, je te plumerai. »

Question 2

Quelle est la complexité de cette chanson en fonction de \(n\) ?

Corrigé

On note :

\(a\) le nombre de mots de la première ligne ;
\(b\) le nombre de mots chantés dans une itération de la boucle principale, sans compter ceux de la boucle intérieure.

Pour une valeur de \(i\), la boucle intérieure effectue \(i\) itérations de 4 mots chacune. On a alors \(a + n b + 4 (0 + 1 + \dots + (n-1)) = a + n b + 4 \frac{n(n-1)}{2} = a + nb + 2n(n-1) = \Theta(n^2)\) mots chantés : la complexité est quadratique.

N days of Christmas¶

Algorithme : NDaysOfChristmas

Entrées :

\(n \in \N^*\) ;
un tableau gifts de \(n-1\) chaînes de caractères comportant chacune un mot.

Paroles :

Pour i allant de 1 à n
- Chanter « On the ith day of Christmas, my true love gave to me »
- Pour j allant de i à 2
  - Chanter « j gifts[j-2] »
- Si i > 1
  - Chanter « and »
- Chanter « a partridge in a pear tree. »

Question 3

Quelle est la complexité de cette chanson en fonction de \(n\) ?

Corrigé

Si on compte le nombre de mots chantés qui ne sont pas « j » ou un nom de cadeau, on a \(12 + 6 = 18\) mots par itération, plus le « and » des \(n-1\) dernières itérations, soit \(18 n + n - 1 = 19n - 1 = O(n)\) mots.

Le cadeau gifts[k], pour \(k \in \range{0}{n-2}\), est mentionné lors des itérations pour \(i\) allant de \(k+2\) à \(n\), donc \(n-k-1\) fois.

Ainsi, en tout, les cadeaux sont mentionnés \(\sum_{k=0}^{n-2} (n - k - 1) = \sum_{q=1}^{n-1} q = \frac{n(n-1)}{2}\) fois.

On remarque que chaque mention d'un cadeau est précédée du nombre j : on prononce donc autant de nombres que de cadeaux dans la boucle intérieure. Le nombre de mots chantés est donc \(19n - 1 + 2 \cdot \frac{n(n-1)}{2} = n^2 + 18n - 1 = \Theta(n^2)\).

The TELNET song¶

Remarque

Petit historique sur telnet : il s'agit d'un programme, ancêtre de ssh, permettant de se connecter sur d'autres machines en ligne de commande.

Tout ce qu'on écrit est transmis à la machine distante comme des appuis au clavier, sauf si on l'échappe avec un caractère spécial, noté ici ^] (dans la chanson, il est désigné par control-uparrow).

C'est notamment le cas de la commande permettant de quitter une session : ^]Q.

Imaginons que l'on soit connecté à une machine A en telnet et que sur cette machine, on se connecte à une machine B en telnet. Si on tape ^]Q, c'est interprété localement et cela ferme la connexion à A. Comment envoyer des commandes au telnet qui tourne sur A et qui nous relie à B ? Pour cela, on peut doubler l'échappement : ^]^] est transmis comme un ^] littéral. Ainsi, quand on tape ^]^]Q, la machine A reçoit ^]Q et ferme la connexion à B, et on peut poursuivre par ^]Q pour quitter la connexion à A.

Et si on s'est connecté sur C depuis B ? Il faut doubler le doublement : ^]^]^]^]Q^]^]Q^]Q !

Et ainsi de suite, ce qui a donné à l'informaticien Guy L. Steele l'idée de la chanson The TELNET Song (1984).

Les paroles de cette chanson, qui dépendent d'un entier \(N\) (l'auteur recommande \(N = 4\)), sont elles-mêmes écrites comme un programme. On en résume ici la structure :

Algorithme : TelnetSong (structure)

Entrée : \(N \in \N\)

Chanter deux couplets d'introduction, de longueur fixe.
Pour I allant de 1 à N
- Chanter un couplet de longueur fixe, qui se termine par \(2^I\) fois « control-uparrow » suivis de « Q ».
Chanter un couplet de transition, de longueur fixe.
Pour I allant de N à 1
- Chanter un autre couplet de longueur fixe, qui se termine lui aussi par \(2^I\) fois « control-uparrow » suivis de « Q ».
Chanter les couplets de conclusion, de longueur fixe (ils contiennent un nombre constant de « control-uparrow »).

Question 4

Quelle est la complexité de cette chanson ?

Corrigé

Ici, on a \(O(1)\) mots chantés hors des boucles, et \(O(N)\) mots dans les boucles sans compter les control-uparrow.

Le nombre de control-uparrow dans les boucles est \(2 \sum_{i=1}^N 2^i = 2 (2^{N+1}-2) = 2^{N+2} - 4\), et chacun compte un nombre constant de mots.

Ainsi, en tout, le nombre de mots chantés est en \(\Theta(2^N)\) : la complexité est exponentielle.

Chanter des entiers¶

L'hypothèse faite sur le fait que chanter \(i\in \N\) est en temps constant est peu réaliste. Il suffit de comparer le temps mis entre le fait de prononcer 1 et 123456789.

On va considérer ici le nombre de mots réellement présents dans la lecture d'un entier. Comme il y a des traits d'union, on considère que saute-mouton comporte deux mots.

Par exemple,

3 se lit trois et comporte un mot ;
123 se lit cent vingt-trois et comporte 3 mots (vingt-trois compte comme deux mots) ;
123 456 789 se lit cent vingt-trois millions quatre cent cinquante-six mille sept cent quatre-vingt-neuf et comporte donc 14 mots.

On pourra utiliser : chiffre en lettre.

Question 5

Exprimer sous la forme \(O(f(n))\) le nombre de mots dans la lecture de l'entier \(n\).

Note : on pourra faire une majoration grossière tant qu'elle est tout de même réaliste.

Corrigé

On peut regrouper les chiffres par paquets de trois : un élément de la forme \((10^2 a + 10 b + c) 10^{3k}\), avec \(a, b, c \in \range{0}{9}\), se lit avec au plus 7 mots :

au plus 2 mots pour \(10^2 a\) : « \(a\) cent » ;
au plus 4 mots pour \(10 b + c\) : par exemple « quatre-vingt-dix-sept » ou « soixante et onze » ;
1 mot pour \(10^{3k}\) : « mille », « millions », etc.

Un entier \(n \ge 1\) comporte \(\lfloor \log_{1000} n \rfloor + 1\) paquets de trois chiffres. Ainsi, on peut majorer le nombre de mots dans la lecture de \(n\) par \(7 (\lfloor \log_{1000} n \rfloor + 1) = O(\log n)\).

Remarquons qu'on aurait la même complexité en le lisant en binaire, avec \(\lfloor \log_2 n \rfloor + 1\) chiffres : c'est une bonne manière de ressentir la constante.

Question 6

En déduire des complexités affinées des chansons DMàRendre et NDaysOfChristmas.

Corrigé

Dans DMàRendre on fait \(n\) itérations de boucle où on va prononcer deux nombres inférieurs ou égaux à \(n\). Donc on chante \(O(n \log n)\) mots maintenant qu'on prononce réellement les nombres.
Dans NDaysOfChristmas c'est dans la boucle intérieure, qui s'effectue \(\frac{n(n-1)}{2}\) fois, qu'on va prononcer un nombre \(j \le n\), donc \(O(n^2 \log n)\) mots (le « ith » de la boucle principale n'ajoute que \(O(n \log n)\) mots).