Section : N° d'inscription : S érie : Signature des

surveillants
Nom et prénom :

Date et lieu de naissance :

Épreuve Algorithmique et Programmation - Section : Sciences de l ’informatique - Session de contrôle 2022

Le sujet comporte 4 pages numérot ées de 1/4 à 4/4 .

La page 1/4 est à remplir par le candidat et à rendre avec sa copie

Exercice 1 (3,5 points)

Soient le tableau de déclaration des nouveaux types ( TDNT) et le tableau de d éclaration des objets (TDO )
suivants :

TDNT TDO
Types Objet Type/Nature
Renseignements = Enregistrement F Texte
Nom : Chaî ne E Renseignements
Num : Octet P Bool éen
Etat Civil : Caractère B Octet
Fin Renseignements M Réel
Elève = Fichier de Renseignements Felv Eleve
Fent = Fichier d ’entiers
Fe Fent
Tsec = Tableau de 50 Renseignements
T Tsec

Ullli
Dans le tableau ci -dessous, valider chacune des instructions en mettant dans la case correspondante de la 2
colonne la lettre V si l’ instruction est valide ou la lettre F dans le cas contraire. Justifier la réponse si
l’ instruction est invalide.
Instruction Valide/Invalide Justification

B Fin Fichier(F)

Ecrire (F, [Link] Civil )

—
P < [Link] > 10

Ecrire (Felv, [Link])

Ecrire (Fe, M)

T[2] <- [Link]

Page 1 sur 4
 EXAMEN DE BACCALAUR ÉAT - SESSION 2022
R ÉPUBLIQUE TUNISIENNE
Session de contrô le NOUVEAU R ÉGIME
É preuve : Section :
MINISTÈ RE DE L’É DUCATION
Algorithmique et Programmation Sciences de l'informatique
Durée : 3h Coefficient de l’épreuve : 2

~
N° d'inscription [

^ Exercice 2 (5,5 points)

Pour évaluer a “ an = a * a * a ... * a ), avec a et n deux entiers naturels, on a besoin de n-1 multiplications.
(
En informatique, l’algorithme d ’exponentiation rapide est un algorithme utilisé pour calculer rapidement des
grandes puissances entières. Le principe de cet algorithme est basé sur le fait qu’on a :
an = an/,z * an /,z lorsque n est pair et an = a * a ”-1 2 * a n-1 2 lorsque n est impair.
^ ^ ^ ^
D’où :
1 si n = 0
a" =J a "72 « a"72 si n est pair
a * a ( n-l )/2 a n-l )/2
(
1
si n est impair

Travail demand é :
1 ) Ecrire une fonction récursive Exporapide (a ,n ) qui permet de calculer a ” en utilisant le principe décrit
précédemment.
_
2) En faisant appel à la fonction Expo rapide de la question 1, écrire une fonction Exponentielle(x) qui
permet de calculer une valeur approch ée de ex ( l ’exponentielle d’ un entier naturel x) à epsilon prés
x2
... + — avecn! représente la factorielle
3
( epsilon - 10 5), sachant que
'
ex = =1+x+—
2!
+ *—
3!
de n .
N .B. : La factorielle d’ un entier naturel n not é n ! est définie par la formule n ! = n * ( n - l )* (n -2)* . . . * l
avec 0! = 1 et 1! = 1
3) Soit la fonction / définie par :
1
/ 00 = Xn * ex
Afin de vérifier que lim f [ x ) = 0 , utiliser les modules définies précédemment pour écrire un
algorithme d ’une procédure Verif ( FLim , n ) qui permet de stocker dans un fichier texte FLim , les
valeurs de / (*) en commen çant par x = 1 et en faisant varier x d ’ un pas égal à 1. L’écriture dans le
5
fichier FLim s’arrête lorsque f ( x ) devient inférieure ou égale à 10 .
'

N .B. :
• Chaque valeur /(x) sera stockée dans une ligne du fichier FLim.
• Le candidat n’est pas appelé à saisir l’entier naturel n .
Exercice 3 (4 ,5 points)
En math ématique, une matrice carrée M de dimension n x n est dite stochastique (ou encore matrice de
Markov ) lorsque chaque é l ément de la matrice est un réel de l’intervalle |0, 1] et la somme des é l éments de
chaque ligne est égale à 1.

Page 2 sur 4
Un tableau T de n réels est dit stable pour une matrice stochastique M lorsque le tableau P résultat du produit
de T et M vérifie P = T ( T x M = P = T), sachant que le tableau P est obtenu comme suit :
n- l
p\j ] = YjM [ i t j ] * T [ i ]
i =0
avec 0 < j n- 1

Exemple : Pour la matrice carrée M de dimension 3x3 et le tableau T de 3 é l éments suivants :

o 1 2
o 0.5 0,3 0,2
M I 0 , 2 0,8 0
2 0,3 0,3 0,4

0 1 2
T I 3 M I i I
• M est une matrice stochastique puisque les é l éments de M sont tous des réels de l ’intervalle |0,1] et la
somme des éléments de chaque ligne est égale à 1.
En effet :
La somme des é l éments de la l ère ligne est égale à M[ 0,0] + M[ 0, 1 ] + M [0,2] = 0,5+0,3+0,2 = 1
La somme des é léments de la 2eme ligne est égale à M [ 1 ,0] + M [ 1 , 1 ] + M[ l ,2] = 0,2+0,8+0 = 1
La somme des éléments de la 3cme ligne est égale à M [2,0] + M[ 2, l ] + M[2,2] = 0,3+0,3+0,4 - 1
• P, le tableau résultat du produit M x T est :
0 i 2~
p
!
3 I 6 P 1
En effet :
P[0] = M[ 0,0]*T[0] + M[ 1 ,0]*T[ 1 ] + M[2,0]*T[ 2] = 0,5*3+0,2*6+0,3* 1 = 3 qui est égal à T|0 J
- -
P[ l ] M[0,1]*T[0] + M[1,1 ]*T[ 1] + M[ 2,1 ]*T[2] 0,3*3+0,8*6+0,3* 1 = 6 qui est égal à T[ l ]
P[ 2] = M[0,2]*T[ 0] + M[ 1,2]*T[ 1 ] + M [ 2,2]*T[2] = 0,2*3+0*6+0,4* l = 1 qui est égal à T[2]
• T est dit stable pour M car M est stochastique et le produit P de T et M est égal à T .
Travail demand é :
1 ) Déclarer un type pour chacune des variables M et T.
2) Ecrire un algorithme d’une fonction Stochastique( M ,n ) qui permet de vérifier si la matrice carrée M
de dimension n x n est stochastique .
.
N B. : Le candidat n’est pas appelé à saisir M et n .
3) Ecrire un algorithme d’une fonction M _Stable( M,n ,T) qui permet de v érifier si un tableau T de n
réels est stable pour la matrice carrée M de dimension il x n .
N.B. : Le candidat n ’est pas appelé à saisir M, n et T et on supposera que la matrice M est
stochastique.

^ Exercice 4 (6,5 points)

On se propose de réaliser la conversion d ’ un entier naturel strictement positif N dans une base B donnée
(avec 2 < B < 16).
Pour cela on effectue des divisions euclidiennes par B, les restes successifs seront rangés dans un tableau
Restes à Rmax é l éments (avec Rmax = 15) puis on inverse les é l éments du tableau Restes et on les
concatène tout en convertissant les valeurs supérieures ou égales à 10 (dans le cas où la base B > 10) en leurs
équivalents dans la base B.
Travail demand é :
1) Ecrire un algorithme d’une procédure SAISIE(P, Binf, Bsup) qui permet de saisir un entier naturel P
tel que Binf < P < Bsup (avec Binf et Bsup deux entiers naturels).

Page 3 sur 4
Voir suite au verso <3r
2) Ecrire un algorithme d ’ une procédure RANGER ( N , B, RESTES, NbreR ) qui permet de :
> Ranger dans un tableau RESTES les restes successifs de la suite des divisions euclidiennes
par B jusqu ’à obtenir un quotient égal à 0 (dans la première division euclidienne on divise N
par B, puis on divise le quotient obtenu par B , etc.).
> Calculer le nombre des restes NbreR.
3) Ecrire un algorithme d ’ une procédure RENVERSER ( RESTES, NbreR ) qui renverse les NbreR
éléments rangés dans le tableau RESTES.
-
( Permuter RESTES [0] avec RESTES |NbreR l ] , RESTES [ IJ avec RESTES|NbreR-2 ], etc.)
4) Ecrire un algorithme d’ une fonction CONVERT(C) qui permet de retourner le caractère qui
correspond à l’entier C (avec 0 < C < 15).
Exemples : CONVERT (0) retourne le caract è re "0", CONVERT (9) retourne le caractè re "9",
CONVERT (10) retourne le caractè re " A ", CONVERT (15) retourne le caractè re "F"
5) Ecrire un algorithme d’ une procédure CONCATENATION ( RESTES, NbreR ) qui , en utilisant la
fonction CONVERT et la procédure RENVERSER , affiche l’équivalent du nombre N dans la base
B en concaténant les é l éments du tableau RESTES.
6) En faisant appel uniquement aux modules d éjà définis, écrire un algorithme d’un programme
principal intitulé CONVERSION qui permet de saisir un entier naturel N (avec 100 < N < 20000) et
une base B (avec 2 < B < 16) et d’afficher le résultat de la conversion du nombre d écimal N dans la
base B.
Exemple : Pour N =4008 et B= 16
• On procède à des divisions successives par B.

Après appel de la procédure RANGER, le tableau RESTES sera :

I
8 I
10 15I I
• Après appel de la procédure RENVERSER, le tableau RESTES sera :
F' I ' I
3 0 8 1
• Après appel de la procédure CONCATENATION , le résultat affich é est : "FA8".
En effet :
CONVERT(15) retourne "F” , CONVERT( IO) retourne "A " et CONVERTI) retourne ”8” .

Page 4 sur 4