Centrale Option Informatique MP 2007

Les deux parties sont complètement indépendantes.

L'objectif de ce problème est de comparer les complexités temporelles (et dans une moindre mesure spatiale) d'algorithmes de calcul numérique de suites entières vérifiant une relation de récurrence linéaire. Les entiers manipulés pourront être arbitrairement longs (ce qui n'est a priori le cas ni en Caml ni en Pascal). Dans les calculs de complexité, on demande des ordres de grandeur du nombre d'opérations élémentaires sur les bits.

Exemple 1 : l'algorithme naturel pour sommer deux entiers de bits demande opérations élémentaires (additions bit-à-bit, propagation de retenue).

On ne demande pas d'équivalents, mais des majorants asymptotiques.
Lorsque et , on pourra noter , ce qui est plus précis que .
Exemple 2 : Le "tri-bulle" d'un tableau de valeurs effectue comparaisons de valeurs, et réalise échanges dans le tableau.

Les candidats rédigeant en Caml devront donner le type de chaque fonction écrite.
Notation : désignera modulo , c'est-à-dire le reste dans la division euclidienne de par .
I.A - Questions préliminaires
I.A.1) Évaluer le nombre d'opérations élémentaires sur des bits requises pour effectuer le produit de deux entiers de bits avec une méthode élémentaire (que l'on décrira sommairement).
I.A.2) Donner un algorithme effectuant une multiplication d'entiers avec une meilleure complexité. Le décrire, et donner (sans justification) sa complexité temporelle.
I.A.3) Décrire très sommairement l'algorithme d'exponentiation rapide. Justifier son intérêt par rapport à un algorithme élémentaire.
I.B - Diverses façons de calculer

La suite de Fibonacci est définie par les relations , et pour tout : .
I.B.1) En utilisant les résultats standards sur les suites vérifiant une relation de récurrence linéaire d'ordre 2 , à coefficients constants, donner la valeur de , et l'ordre de grandeur de sa représentation binaire (écriture en base 2). En déduire un minorant pour le temps de calcul de tout programme calculant .
I.B.2) Écrire une fonction récursive fibo prenant en entrée un entier et retournant en appliquant directement la définition de .
I.B.3) Prouver que le nombre d'appels récursifs effectués pour calculer avec la fonction précédente est exponentiel en .
I.B.4) Écrire une nouvelle fonction fibo2 réalisant le calcul de de façon itérative, en calculant de proche en proche les pour . Donner le nombre d'additions d'entiers qui seront effectuées lors du calcul de , et évaluer la dépendance du temps de calcul par rapport à , ainsi que la place en mémoire requise (on supposera que les entiers calculés restent inférieurs au plus grand entier représentable en Caml ou en Pascal).
I.B.5) On observe qu'en notant et , on a pour tout , puis : . Estimer le temps de calcul et la place en mémoire requise pour calculer en exploitant cette relation.
I.B.6) Si on cherche à calculer modulo un entier "petit" (dans un sens à préciser par le candidat), quelle méthode peut-on utiliser, et quels sont le temps et l'espace requis par cette méthode?
I.C - Utilisation d'automates
I.C.1) Vérifier que pour tout .
I.C.2) En déduire des expressions simples de et en fonction de et .
I.C.3) Construire et représenter un automate fini déterministe d'ensemble d'états et une fonction tels qu'en lisant depuis l'état initial la représentation binaire d'un entier depuis le bit de poids fort jusqu'au bit de poids faible, on arrive
dans un état tel que [2].
I.C.4) À l'aide de l'automate précédent, donner la valeur de .
I.C.5) Prouver que la suite définie par [2] est 3-périodique et retrouver le résultat de la question précédente.
I.C.6) Construire et représenter un automate permettant de déterminer le reste modulo 3 d'un entier , en lisant la représentation binaire de , du bit de poids fort vers le bit de poids faible. Comparer avec l'automate de la question I.C.3??
I.D - Une généralisation

On considère maintenant, pour fixé, la suite de premiers termes et , et vérifiant la relation de récurrence : pour tout est la somme des deux nombres et .
I.D.1) Écrire une fonction prenant en entrée et , et retournant en appliquant simplement la relation définissant . Donner un ordre de grandeur du temps d'exécution (on ne demande pas une preuve formelle du résultat).
I.D.2) On se place pour cette question seulement dans le cas . Écrire une fonction g3 prenant en entrée et retournant .
On écrira un programme itératif calculant les différents termes de proche en proche, en ne stockant que "quelques" termes de la suite.
I.D.3) Écrire maintenant une fonction itérative g prenant en entrée et , et retournant en faisant additions.
On utilisera un tableau pour stocker des valeurs successives de .
I.D.4) Si ce n'est pas déjà le cas dans la question précédente, écrire une fonction calculant en additions et affectations de variables (y compris dans des tableaux). Cette fonction utilisera un tableau dont la taille est de l'ordre de .
I.D.5) Proposer une façon raisonnable de calculer modulo 3 , avec .

Par "raisonnable" on entend : retournant le résultat en moins d'une journée de calcul sur un ordinateur de bureau de puissance et de capacité de stockage moyens en 2007 !

L'objectif de cette partie est d'analyser un algorithme permettant de calculer, pour , le plus petit multiple commun de tous les entiers .
Il s'agit de , avec la suite (strictement croissante) des nombres premiers compris au sens large entre 2 et et pour chaque est l'unique
entier tel que . Par exemple, .
Plus précisément, on souhaite calculer tous les , pour , en exploitant au maximum les calculs précédents. Pour cela, on va utiliser une structure de tas.
Un tas est un arbre binaire dont les nœuds sont étiquetés par des éléments distincts d'un ensemble complètement ordonné. Chaque nœud possède une étiquette strictement plus petite que les étiquettes de ses éventuels fils. Les adjonctions et éventuelles suppressions de nœuds doivent préserver cette propriété, ainsi que le fait que «tous les niveaux de l'arbre sont remplis, sauf éventuellement celui de profondeur (hauteur de l'arbre), qui est lui-même rempli de la gauche vers la droite». Par exemple, un tas possédant six nœuds sera constitué d'une racine, deux nœuds de profondeur 1, et 3 nœuds de profondeur 2. La structure de données utilisée en machine pour stocker et manipuler ces tas n'importe pas ici : on ne demande pas de programmer effectivement les algorithmes.
Ici, les nœuds sont étiquetés par des couples ( ), avec premier. Après le calcul de , sont stockés dans le tas tous les couples d'entiers ( ) tels que est un nombre premier inférieur ou égal à et est le plus petit entier tel que . Par exemple, après avoir calculé , on trouve dans le tas les couples , et .
Les couples sont ordonnés de la façon suivante : si et seulement si . Pour cet algorithme, le tas ne contient jamais deux couples ayant la même première composante, de sorte que les étiquettes sont toujours comparables.
L'algorithme est itératif. On stocke dans une variable Res le ppcm calculé jusque là. Au départ, Res=2 est le ppcm des entiers et le tas est constitué d'un seul nœud indexé par . Après avoir calculé (qui est alors présent dans Res), on calcule de la façon suivante :