1 Fiche d’exercices Algorithmiques types de données élémentaires et

opérations de base
1.1 Rappels de cours
Type Taille Intervalle

byte 8 bits -128 � 127

short 16 bits -32768 � 32767

int 32 bits -2147483648 � 2147483647

long 64 bits -9223372036854775808 � 9223372036854775807

3.40282347E+28 � 1.40239846E-45
float 32 bits
Signe=1 bit, mantisse=23 bits, exposant =8bits

1.79769313486231570E+308 � 4.9406545841246544E-324
double 64 bits
Signe=1 bit, mantisse=52 bits, exposant=11 bits

1.2 Exercice
1. Définir pour un type élémentaire les notions d’amplitude, de précision locale et de taille
2. Lister les types élémentaires courants de données, en précisant pour chacun d’entre eux les
ordres de grandeur d’amplitude et de précision, ainsi que le nombre de bits utilisés pour leur
représentation dans les langages java, C et dans les langages java, C et C# :
null, byte, short, int, long, float, double, boolean, and char, Decimal, String et Array, Date.

3. Donner les conséquences possibles d’un débordement d’amplitude

4. Donner les conséquences possibles d’un manque de précision

5. Impact de la précision sur la division entière
6. Définition de l’epsilon de la machine
7. Pseudo-comparaison des réels

Cours algorithmique, tous droits réservés. Copie pour utilisation exclusive des étudiants de
Polytechnique1
1.3 Exercice
1) Quels sont les résultats des opérations suivantes en java ou en C(on pourra essayer certaines de
ces opérations sous Excel ou avec une calculatrice) :

a. Y=(1/2)*3 =……. ; Y=1*3/2=…….Y=1*(3/2) …..Y=1.0*3/2……….

b. Y=100 000 000 + 1.0/3 -1.0/3 =……. Double Y=100 000 000.0+ 1.0/3 -1.0/3

2) Quelle est la précision locale en x=1030 pour un réel double en java ? en C ?.

3) On considère l’algorithme qui calcule la racine carrée d’un nombre, en utilisant la suite de
newton.

a. Quel type de donnée convient pour la déclaration d’un tel nombre ?

b. Quel est le critère d’arrêt à utiliser pour mettre fin aux itérations ?

c. Quel est le critère à utiliser dans le programme de test pour vérifier la validité de notre
algorithme ?

4) Quel est le plus grand entier qui peut être représenté

a. sous forme de réel double avec une précision locale de 1 ?

b. sous forme de réel simple avec une précision locale de 1 ?

1.4 Exercice : Clés de bd.

1) Dans les bases de données, on utilise très souvent un entier (de java) comme type du champ clé
(champ servant à identifier les lignes). Pour éviter que deux clés attribuées par deux personnes
distinctes aient le même code, on donne aux clés la forme préfixe+compteur, où le préfixe est
un entier dépendant de celui qui donne la clé, et le compteur est une valeur numérique
séquentielle. Si on suppose que la longueur totale de la clé est de dix caractères, quelle est la
valeur maximale du préfixe ? Qu’adviendra-t-il si un préfixe dépassant cette valeur de 2 est
donné ?

1.5 Exercice : Somme de séries

2) Proposer un algorithme pour le calcul efficace et précis des séries suivantes :

a. Sn=somme(k=1 à n){xk/k !}

b. Sn=somme(k=1 à n){1/k2}

c. Sn=somme(k=1 à n){1/k }

Cours algorithmique, tous droits réservés. Copie pour utilisation exclusive des étudiants de
Polytechnique2
1.6 Calcul de grandes fonctions
d. Quel est le plus grand nombre dont le factoriel peut être calculé en tant que entier
long ?

e. A partir de ce nombre, quelle est l’erreur absolue et l’erreur relative maximale commise
sur l’inverse de factorielle n, factorielle étant calculée comme réel double ?

f. Proposer un algorithme pour le calcul de Ckn=combinaisons de k dans n

1.7 Comparaison de réels

1) Quels dangers potentiels pose le code suivant ?

Int n=8;

double h=1/n ; double x=0;

int i=0 ;

While(x !=1) {x=h*i;i=i+1;}

2) Le modifier pour avoir un code correct

1.8 Exercice
1) Enoncer le principe DRY

2) Donner les règles d’application du principe DRY pour les constantes et pour les blocs de codes

3) Proposer un fragment de code non conforme au principe DRY. Le modifier pour en assurer la
conformité.

1.9 Pb de représentation (TP)

A essayer avec des valeur initiales pour a et b qui sont des puissances de 4 + 0.1, pour d’autres
valeurs, ou en changeant les double en float ...( [Link]
[Link]/Prog/Java/CoursJava/[Link])

public void xxx(){

double a = 64.1;
double b = 63.1;
// pour d’autres valeurs de a et b
// la suite des x est (1, 1, 1, ...
double x = 1.0;
for (int i=1; i <= 14; i++){
[Link](""+i+" "+x);
x = a*x - b;// b = a-1 donc x = b*(x-1)+x
// x initial = 1, donc x = x = 1
}
}

Cours algorithmique, tous droits réservés. Copie pour utilisation exclusive des étudiants de
Polytechnique3
1.10 Pb de conversion (TP)
double d = 12345.6;

byte b = (byte)d; // b vaut 57

1.11 algorithms de base

1) proposer un algorithme qui calcule xn en O(lnn)

2) proposer un algorithme qui calcule a*b en O(min(a,b)) où a et b sont deux entiers naturels. On
admet que les seules opérations arithmétiques et logiques qui existent déjà sont la division par
deux, la multiplication par 2, le modulo 2, l’affectation, la comparaison.

3) Exercice I. suites de fibonnacci. On a la suite Un+2=Un+1+Un

Proposer un algorithme pour calculer Un en O(n)

4) ………………………………………………………………………………………………

5)

Cours algorithmique, tous droits réservés. Copie pour utilisation exclusive des étudiants de
Polytechnique4
 Exercices collections
Exercice 1 :

1.12 Connaissance des collections

0) Pour chacune des implémentations de collections données dans le tableau ci-dessous,
donner la complexité de chaque opération de base.

Structure Complexité Complexité Complexité Complexité Complexité Complexité Complexité

recherche insertion insertion insertion suppression suppression suppression
quelconque début fin début quelconque fin
Tableau
statique non
trié
Tableau
dynamique
non trié
Tableau
statique trié
Tableau
dynamique
trié
Arbre
binaire de
recherche
Table de
hachage
Liste
simplement
chaînée
Liste
doublement
chainée
X=ne s’applique pas.

1) Définir une collection

2) Lister les opérations de base réalisables sur une collection, en précisant le résultat attendu
3) Donner pour chacune des collections suivantes ses spécifications contractuelles : Ensemble,
liste, Pile, Dictionnaire, Collection ordonnée.
4) Citer les collections les plus appropriées du point de vue complexité pour répondre à la
requête consistant à fournir les éléments contenus dans une plage.
5) Lister en donnant leur rôle les collections EnumSet, EnumMap, WeakHashMap,
ConcurrentHashMap, SKIPLIST

1.13 Utilisation des collections

1) Compter les mots : on suppose qu’on vous donne le discours du Président. Vous devez
proposer un algorithme pour compter le nombre d’apparitions de chaque mot dans le texte.
Cours algorithmique, tous droits réservés. Copie pour utilisation exclusive des étudiants de
Polytechnique5
 2) Déterminer le nombre d’articles : on vous donne le discours du président. On vous demande
de compter le nombre d’articles dans son discours. On admet comme articles {le, la, un,
une}

3) Découpe de barres : on dispose d’un stock de barres de diverses longueurs, et on doit

couper de ce stock un certain nombre de barres de diverses longueurs. Lorsqu’on coupe
une barre, on met ce qu’il en reste dans le stock, pour les coupes ultérieures. Une
heuristique est de trier les barres par ordre de taille décroissante, avant de faire les choix de
coupe. Quelle structure de donnée proposez-vous pour représenter le stock ? Justifier votre
réponse.

4) On suppose qu’on dispose d’une matrice creuse représentée par une table de hachage. On
suppose que les clés de la table ont la forme i/j (ligne i, colonne j) et que l’on dispose de la
fonction keys(h), renvoyant la liste des clés de la table h, et de la fonction get(key)
renvoyant l’élément à la position key. Proposer (principe) un algorithme efficace de
multiplication de cette matrice par un vecteur. Nous rappelons que pour les matrices
creuses, le nombre d’éléments non nuls est un O(n), où n est la taille de la matrice, et que
par conséquent un algorithme efficace devrait s’exécuter en O(n). 2pts

5) proposer une structure de données (collection) permettant d’accéder rapidement à un

étudiant par son rang (<O(n)) ou par son nom (<O(n)).

6) soit une liste de n (petit) éléments. Quelle structure de données utiliser pour accéder
rapidement à chaque élément d’après son nom ? (on suppose connue la distribution des
probabilités d’accès)……………………………………………………………… 1pt

7) Problème : les appariements *

On considère un fichier contenant des mots. On dira que les mots a et b sont appariés si fin(a)=debut(b).
En d’autres termes, a s’écrit ax et b s’écrit xb, où x est une chaîne de caractères de longueur au moins
égale à 1. Par exemple, (bobo, bonté). (Vanité, tétu).

(Voiture, entrée), (mont, monture).

Proposer un algorithme permettant de calculer toutes les paires à partir d’un tableau de mots supposés
contenus dans le fichier. On s’efforcera d’écrire un algorithme efficace et on calculera la complexité
dudit algorithme.

Au cas où votre algorithme s’exécute en O(n2) Proposer , deux autres algorithmes, l’un s’exécutant en
O(P+nlnn), et l’autre en O(P+ n), où P est le nombre de paires fabriquées.

8) Exercice : shrinkToFIt ***

On considère un tableau ayant N colonnes et M lignes. Chaque cellule contient du texte. Tous les textes de la
même colonne ont la même police. On admet qu’il existe la fonction hauteur (chaine, police) qui calcule la hauteur
de la chaine passée en paramètre avec une police donnée, ainsi que la fonction longueur (chaine, police) qui
Cours algorithmique, tous droits réservés. Copie pour utilisation exclusive des étudiants de
Polytechnique6
calcule la longueur de la chaine passée en paramètre avec une police donnée. La fonction police(i) renvoie la police
de la colonne i, et texte (i,j) renvoie le texte de la ligne i et la colonne j du tableau.

Le problème posé est de donner les largeurs des colonnes de manière à ce que le tableau ait la hauteur la plus
petite possible. On rappelle que lorsque le texte d’une cellule est plus long que la largeur de la cellule, il y a dans la
cellule un retour à la ligne, et cela autant de fois que nécessaire. Cela a pour effet d’accroître la hauteur du
tableau.

Proposer un algorithme pour résoudre le problème.

1) Ecrire un algorithme probabiliste dans un cas simple de simulation

a. Le calcul de la moyenne d’un ensemble ayant un très grand nombre d’éléments
b. Le calcul de la distribution statistique d’un ensemble ayant un très grand nombre
d’éléments
c. Réalisation d’un tri par paquets pour des données ayant une distribution quelconque
d. Simulation d’une famille. On considère que la famille a n membres s’asseyant autour
d’une table de n chaises. Il n’y a pas de préférence de chaise, on s’assoit de manière
totalement aléatoire. Après combien de temps en moyenne chaque membre de la
famille s’est assis sur toutes les chaises. Résoudre par simulation
e. Le problème des épidémies. On suppose que dans une population les couples se font au
hasard, et que lors d’un accouplement entre un sain et un malade, la probabilité de
transmission de la maladie est p. On demande de proposer un modèle permettant par
simulation de savoir quelle sera l’évolution future de la maladie.

Cours algorithmique, tous droits réservés. Copie pour utilisation exclusive des étudiants de
Polytechnique7