A. Sigayret : Algorithmique

Exercices d'algorithmique : série 3

N.B. Rechercher sur Wikipedia (ou autre) les définitions inconnues nécessaires à la résolution des exercices.

Exercice 3.1.
algorithme 31
Entrée : un réel positif.
Sortie : un entier n tel que ...
n← 0;
Tantque (n+1)*(n+1)≤x faire n← n+1;
a) Que fait l'algorithme ci-dessus ?
b) Faites en les preuves (si possible avec un invariant).
c) Quel est la complexité de l'algorithme ?
d) Ecrire un algorithme qui fait la même chose, mais en utilisant un Répéter au lieu d'un Tantque.

Exercice 3.2.
algorithme Diagonale
Entrée : un tableau T de n valeurs.
Sortie : un tableau U de n×n valeurs tel que U[i,i]=T[i].
Initialement : U[i,j]=0 pour tous i,j∈[1..n].
i← 1;
Tantque i≤n faire
j← 1;
Tantque j≤n faire
Si i=j alors U[i,j]← T[i];
i←i+1; i←j+1;
a) L'algorithme ci-dessus fait-il bien ce qu'il annonce ?
b) Pourquoi les boucles Tantque ne sont-elles pas adaptées pour cet algorithme ?
c) Ecrire un algorithme équivalent qui remplace les Tantque par des structures de contrôle plus adaptées.
d) Quelle est la complexité de cette algorithme (non compris l'initialisation) ?
e) Montrer que le problème peut être résolu avec une meilleure complexité.

Exercice 3.3.
algorithme 33
Donnée : Deux entiers naturels n et p.
Résultat : x tel que...
// T et F sont deux tableaux
i← 1;
T[i]← n;
F[i]← p;
Tantque T[i]>1 faire
T[i+1]← T[i] div 2;
F[i+1]← F[i]+F[i]; i← i+1;
x← 0;
Tantque i>0 faire
Si T[i] est impair alors x← k+F[i];
i← i−1;
a) Faire tourner l'algorithme avec n=35 et p=17.
b) Que fait ce algorithme ? Comment le prouver ?
c) Quelle est sa complexité ?
d) On veut formaliser l'algorithme qui permet à un écolier français d'effectuer la multiplication de deux entiers n et p.
  Comment modéliser n et p et le résultat np ?
  Comment écrire l'algorithme ?

Exercice 3.4.
fonction Euclide
Entrée : deux entiers naturels non nuls n et p.
Sortie : le PGCD de n et p.
Si n<p alors Echanger n et p; Si p=1 alors Retourner n;
n← n mod p;
Euclide(n,p);
a) faire tourner cet algorithme pour n=273 et p=429.
b) Quelle peut être la complexité de cet algorithme ?
c) Ecrire une version itérative de cet algorithme.

Exercice 3.5.
Dans cet exercice, on représente une chaine de caractères comme en langage C : un tableau de caractères ASCII dont on ne connait pas a priori la taille mais dont la fin est indiquée par un code conventionnel 0 de caractère inutilisé.
a) Ecrire un algorithme robuste qui donne la longueur d'une chaine s de caractères.
b) Ecrire un algorithme qui donne le nombre d'occurrence d'un caractère k donné dans une chaine s.
c) Ecrire un algorithme qui teste si un caractère k appartient à une chaine s.
d) Ecrire un algorithme qui teste si une chaine s contient au moins une majuscule.
e) Ecrire un algorithme qui teste si une chaine s contient au plus une majuscule.
f) Ecrire un algorithme qui donne la valeur d'un entier naturel représenté par une chaine de caractères.
g) Donner les preuves et les complexités de ces algorithmes.

Exercice 3.6.
algorithme 35
Donnée : un entier n.
Résultat : un entier z.
z← 0;
a← n;
Tantque (a>0) faire
Si a mod 2 = 1
alors a← a−1
sinon
a← a div 2;
z← z+1.
a) Faire tourner l'algorithme ci-dessus pour n=1000 (oui, mille!).
b) Combien d'étape de moins y a-t-il pour n=500, de plus pour n=4000 ?
c) Quelle est la complexité de cet algorithme ?
d) Que fait-il ?

Exercice 3.7.
a) Ecrire un algorithme qui donne l'écriture binaire d'un entier naturel n.
b) Ecrire un algorithme qui donne l'écriture en base b d'un entier naturel n.
c) Ecrire un algorithme qui donne le codage binaire IEEE 754 simple précision (32 b) d'un nombre réel x en écriture "flottante".
d) Ecrire un algorithme qui donne la chaine s de caractères nécessaire à l'affichage d'un entier relatif p.
e) On veut recherche si une valeur x se trouve dans la liste de nombres contenus dans un fichier F. On dispose des fonctions élémentaires ouvrirLecture(F) pour commencer la lecture d'un fichier, lirenombre(F) pour lire le nombre suivant, et estfini(F) pour tester si on a atteint la fin du fichier.
Ecrire deux algorithmes pour ce problème, un avec un Tantque, l'autre avec un Répéter. Un des deux algorithmes est-il préférable ?
f) Donner les preuves et les complexité de ces algorithmes.

Exercice 3.8.
a) Utiliser le théorème ci-dessous pour proposer un algorithme qui calcule la partie entière inférieure de la racine carrée d'un nombre. Faire tourner avec x=18. Donner un schéma de preuve pour l'algorithme.
Théorème : 1+2+...+n = (n(n+1))/2.
b) On dispose d'une fonction aléatoire alea(n) qui donne un entier aléatoire compris entre 0 et n. Ecrire un algorithme qui appelle autant de fois que nécessaire cette fonction afin d'obtenir un nombre supérieur à n/2. Pourquoi ne peut-on donner de complexité en pire cas à un tel algorithme . c Ecrire un algorithme qui détermine une valeur approchée du logarithme en base 2 d'un entier n avec une précision d'au moins deux chiffres après la virgule.
d) On recherche une approximation de la somme de Bâle B(∞)=Σi=1→∞ (1/i2). Ecrire un algorithme qui, pour un entier naturel k donné, détermine la valeur n minimale telle que la différence entre B(n)=Σi=1→n (1/i2) et B(∞) soit inférieure à 10−k.
e) Utiliser la formule e=Σi=0→∞ (1/i!) pour écrire un algorithme qui détermine la valeur de e avec une précision de k chiffres après la virgule. Peut-on déterminer la complexité de l'algorithme en fonction de k ?
f) La suite (Pn), définie par P1=2 et Pn+1= (4 n2 Pn) / (4 n2 −1) converge vers π. Utiliser cette suite pour écrire un algoritme qui détermine la valeur de π avec une précision x donnée.

Exercice 3.9.
a)Ecrire un algorithme qui donne à deviner un entier qu'il a choisi au hasard. Il répondra "trop" petit" "gagné" ou "trop grand" selon le nombre choisi par l'utilisateur et s'arrêtera quand le nombre sera deviné ou que l'utilisateur aura fait une erreur de raisonnement (donner par exemple un nombre plus grand que le précédent quand l'ordinateur a répondu "trop grand").
b) Quelle peut être la complexité de votre algorithme ?