informatique commune

Corrigé du contrôle d’informatique

Exercice 1 Représentation machine des entiers relatifs

a) Le codage en complément à deux sur 8 bits permet de représenter les entiers compris entre −27 = −128 et 27 − 1 = 127.
b) Le premier bit indique le signe donc 00110101 est la représentation de (110101)2 = 53 et 10110101 la représentation
de (10110101)2 − 28 = 181 − 256 = −75.
c) 97 est positif donc il est représenté par sa décomposition binaire c’est à dire 01100001.
−34 est négatif donc est représenté par la décomposition binaire de 28 − 34 = 222 c’est à dire 11011110.
d) On obtient la représentation de l’opposé de x en procédant ainsi :
(i) remplacer dans la représentation de x tous les bits égaux à 0 par des 1 et réciproquement ;
(ii) additionner 1 au résultat obtenu ;
(iii) ne garder que les 8 derniers bits.
L’entier −128 est représenté par la décomposition binaire de 28 − 128 = 128, soit 10000000. Appliqué à cette représentation
l’algorithme ci-dessus renvoie 01111111 + 1 = 10000000, autrement dit la représentation de −128, qui se trouve être
son propre opposé (ce qui est vrai modulo 256).
e) D’après le bit de signe x et y sont des nombres négatifs ; plus exactement x = −126 et y = −85.
L’addition de leurs représentations occupe 9 bits : 100101101 ; le neuvième bit est tronqué donc z est représenté par
00101101 et z = 45.
On a bien entendu x + y , z puisque x + y < ~−128, 127, mais z = x + y + 256.

Exercice 2 Exponentiation binaire

a) On définit la fonction :

def power1(x, n):

y = x
for k in range(n−1):
y = y * x
return y

b) Cette fonction réalise l’itération des trois suites définies par les valeurs initiales u0 = n, y0 = x, z0 = 1 et les relations de
récurrence : 
zk
 si uk est pair
yk+1 = yk2

zk+1 =  uk+1 = buk /2c.
yk zk si uk est impair


k
c) On en déduit bien évidemment que yk = x2 .
d) Lorsque n = (bp bp−1 · · · b1 b0 )2 on a bn/2c = (bp bp−1 · · · b1 )2 . De ceci il résulte que uk = (bp bp−1 · · · bk )2 .
e) Ainsi, up = (bp )2 = 1 , 0 et up+1 = 0 donc l’algorithme se termine (la condition de la boucle conditionnelle cesse d’être
vérifiée) et renvoie la valeur de zp+1 .
Sachant que uk mod 2 = bk , la relation de récurrence qui régit l’évolution de la suite (zk ) peut aussi s’écrire : zk+1 =
b k
zk × yk k = zk × xbk 2 . Ainsi,
p
Y k Pp k
zp+1 = z0 xbk 2 = x k=0 bk 2 = xn
k=0

ce qui justifie la validité de cet algorithme.

f) Notons c(n) le nombre de multiplications réalisées par cet algorithme. La boucle conditionnelle est réalisée p + 1 fois.
Durant cette exécution, l’opération y = y * y est réalisée à chaque fois, et l’opération z = z * y à chaque fois que bk = 1.
Le nombre de valeurs de bk égales à 1 est compris entre 1 et p + 1 donc p + 2 6 c(n) 6 2(p + 1).
On a c(n) = p + 2 lorsque seul bp est égal à 1. On a alors n = (100 · · · 000)2 = 2p .
On a c(n) = 2(p + 1) lorsque tous les bk sont égaux à 1. On a alors n = (111 · · · 111)2 = 2p+1 − 1.

page 1
Exercice 3 Codage de Fibonacci
a) Il suffit d’itérer deux suites ui = fi et vi = fi+1 jusqu’à obtenir la condition d’arrêt ui 6 n < vi .

def pgf(n):
u, v = 0, 1
while v <= n:
u, v = v, u + v
return u

b) Montrons par récurrence sur n > 1 que n peut être décomposé en sommes de termes distincts et non consécutifs de la
suite de Fibonacci.
– C’est clair pour n = 1 puisque n = f2 .
– Si n > 2, supposons le résultat acquis jusqu’au rang n−1 et considérons le plus grand terme fk de la suite de Fibonacci
vérifiant la condition fk 6 n.
On a fk 6 n < fk+1 donc 0 6 n − fk < fk−1 . Si n = fk le résultat est acquis au rang n ; sinon on a 1 6 n − fk < fk−1 et par
hypothèse de récurrence n − fk peut être décomposé en somme de termes distincts et non consécutifs de la suite de
Fibonacci. De plus, l’encadrement précédent montre que fk−1 ne peut faire partie de cette décomposition donc le
résultat est bien acquis pour n = fk + (n − fk ).
Remarque. La justification de l’unicité de cette décomposition (non demandée) consiste à prouver le lemme suivant :
la somme de tout ensemble de termes de la suite de Fibonacci distincts et non consécutifs et dont le plus grand
élément est fk est strictement inférieure à fk+1 .
Ceci se prouve par récurrence sur k :
– c’est bien le cas pour k = 0 ;
– Si k > 1, supposons le résultat acquis jusqu’au rang k −1 et considérons un tel ensemble S. Par hypothèse de récurrence
la somme des termes de S \ {fk } est strictement inférieure à fk−1 donc la somme des termes de S est strictement
inférieure à fk + fk−1 = fk+1 .
c) Le décodage est simple : on parcours la suite de Fibonacci en additionnant les termes de la suite associés aux caractères
'1' de la représentation :

def decode(s):
u, v = 1, 1
x = 0
for c in s:
if c == '1':
x += v
u, v = v, u + v
return x

d) Pour le codage on s’inspire de la démarche établie à la question 2 : on détermine le plus grand terme fk de la suite de
Fibonacci qui soit inférieur ou égal à n puis on décompose n − fk .

def code(n):
u, v = 1, 1
while v <= n:
u, v = v, u + v
s = '1'
x = n − u
while u > 1:
u, v = v − u, u
if u <= x:
s = '1' + s
x = x − u
else:
s = '0' + s
return s

e) la relation xfk = xfk−1 · xfk−2 montre que le couple (xfk , xfk−1 ) peut être calculé à partir du couple (xfk−1 , xfk−2 ) à l’aide
d’une seule multiplication. Sachant que le calcul de (xf2 , xf1 ) = (x, x) ne nécessite aucune multiplication, on prouve alors
par récurrence que le calcul de (xfk , xfk−1 ) ne nécessite que k − 2 multiplications.

page 2
Si n est représenté par la chaîne de caractères d0 d1 d2 · · · dk−1 le calcul de xn consiste à effectuer le produit des xfi+2
correspondant aux valeurs de di qui valent 1 :

def puissance(x, s):

u, v = x, x
y = 1
for c in s:
if c == '1':
y *= v
u, v = v, u * v
return y

Exercice 4 Décomposition sur la base factorielle

a) Pour décoder l’expression d’un nombre décomposé sur la base factorielle, il suffit de maintenir les invariants : uk = k!
et vk = ak k! + · · · + a1 1! + a0 . Ceux-ci se définissent par les relations :

u0 = 1, v 0 = a0 et uk+1 = (k + 1)uk , vk+1 = vk + ak+1 uk+1 .

def decode(s):
u, v = 1, s[0]
for k in range(1, len(s)):
u = u * k
v = v + u * s[k]
return v

b) Puisque a0 ∈ ~0, 1~ on a nécessairement a0 = 0.

Pour tout i > 2, i! est divisible par 2 donc k − a1 ! − a0 = k − a1 est pair. On a donc a1 = k mod 2.
1 1
Pour tout i > 3, i! est divisible par 6 donc (k − a2 2! − a1 1! − a0 ) est divisible par 3. On a donc a2 = (k − a0 − a1 1!) mod 3.
2! 2!
i−1 i−1
1 1
 X   X 
Plus généralement, k− aj j! ≡ ai mod (i + 1) donc ai = k− aj j! mod (i + 1).
i! i!
j=0 j=0
c) Ceci conduit à la fonction :

def code(n, k):

a = [0]
for i in range(1, n):
a.append(k % (i+1))
k = k // (i+1)
return a

d) Il suffit de suivre la description de l’énoncé :

def permutation(n, k):

a = code(n, k)
ell = [i for i in range(n)]
sigma = []
for i in range(n):
sigma.append(ell[a[n−i−1]])
del ell[a[n−i−1]]
return sigma

page 3