Ecole Préparatoire (EP) 2015-2016
Module Informatique par Dr KADJO
Informatique
Devoir N°2
Durée : 2H00
« Ordinateurs, tablette et autres téléphones interdits, Documents non autorisés » »
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa
copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Test 1
Soit une pile P de bits.
1) Ecrire une fonction permettant de donner la valeur décimale
correspondant à la séquence de bits stockée dans la pile P. On
suppose que les bits sont rangés de sorte que le bit de poids faible
se retrouve au sommet de la pile.
Déterminer la complexité de votre algorithme
2) Ecrire une fonction classer(P) permettant de mettre les 1 en premiers
et les 0 en tête de pile.
3) Ecrire une fonction ranger(P,b)permettant de ranger le bit b dans la
pile P de sorte que les 0 restent au dessus des 1.
Déterminer la complexité de votre algorithme
4) Soient deux piles P1 et P2 de bits quelconques ? Ecrire une fonction
additionBin(P1,P2) permettant d’effectuer l’opération d’addition
binaire sur les éléments des des deux piles. On suppose que les bits
sont rangés de sorte que le bit de poids faible se retrouve au sommet
de la pile.
5)
Test 2
1) Ecrire une version récursive du tri par insertion
2) Modifiez le tri fusion pour qu’il utilise le tri par
insertion en dessous d’une certaine taille de liste (moins de
10 éléments, par exemple).
Tests 1 et 2
Déterminer pour chacun des programmes suivants, le nombre d’opérations
significatives effectuées, en déduire leur complexité en fonction de n.
""" Programme1 """ """ Programme2 """ """ Programme3 """
n = 100 n = 20 n = 20
s = 1 s = 1 i = n
for i in range(n): for i in range(n): s = 0
for j in range(n): for j in range(i-5,i+5): while i > 1:
for k in range(n): s = 2*s for j in range(i):
s = 2*s s = s +1
i = i/2