Ecole Polytechnique de Sousse Année Universitaire : 2024 -2025
Classe : 1PI Examen S1
Matière : Algorithmique Durée : 2h00
Enseignantes : Mme. Feyrouz Hamdaoui & M. Houssen Eddine Bouzidi Date : 10/01/2025
Documents autorisés : Non Nombre de Pages : 02
Exercice 1 (12 pts) :
On désire définir une bibliothèque des fonctions/procédures algorithmiques qui permet de
manipuler des polynômes. Un polynôme est défini par un tableau de ses coefficients. L’indice
de chaque case du tableau indique un exposant.
Exemple :
P=5+ 3x+7x2+8x4 sera représenté par le tableau suivant :
5 3 7 0 8 0 0 0……..0 0 0
0 1 2 3 4 5 6 ……… Nmax-1 Nmax
Travail demandé :
On suppose avoir fait les déclarations suivantes :
DefConst Nmax = 100
G G
DefType POLY = tableau [0 . . Nmax ] de réels
Q1. Ecrire une procédure INIT qui prend en paramètres un tableau P vide de type POLY et un
entier N représentant le degré du polynôme (le plus haut coefficient du polynôme), et qui
permet de remplir le tableau P avec les coefficients du polynôme saisies de l’utilisateur.
Remplir le reste du tableau (au-delà du degré) avec des zéros.
Q2. Ecrire une fonction DEGREE qui prend en paramètre un tableau P de type POLY et qui
déduit et retourne le degré du polynôme.
Q3. Ecrire une fonction COEFF qui prend en paramètres un tableau P de type POLY et un
-
entier i et retourne le coefficient du ième terme du polynôme P.
Exemples :
• COEFF(P,2) retourne 7.
• COEFF(P,7) retourne 0.
Q4. Ecrire une fonction CALCUL qui prend en paramètres un tableau P de type POLY et un
reél X et qui permet de calculer et de retourner la valeur de P pour x égale à X.
Exemple : CALCUL (P, 1) retourne 23.
Q5. Ecrire une procédure ADD qui prend en paramètres deux polynômes P1 et P2 (deux
tableaux de type POLY), et qui permet de donner un polynôme qui représentera la somme
des deux polynômes P1 et P2.
Q6. Ecrire une procédure DERIVE qui retourne le polynôme dérivé P’ du polynôme P (de type
POLY) qui sera passé en paramètre.
Exemple : pour P= 4+6x+8x2+10x4 qui est représenté par
4 6 8 0 10 0 0 0……..0 0 0
0 1 2 3 4 5 6 ……… Nmax-1 Nmax
P’ = (6*1) + (8*2)x + (10*4)x sera représenté par :
3
6*1 8*2 0*3 10*4 0 0 0 0……..0 0 0
0 1 2 3 4 5 6 ……… Nmax-1 Nmax
1
1) Mocedure INIT (OP Poly ,
: N : entr (
Iv as
in ent
debut
pour
i de 0 à N
fau Is
Ecrire ("done le coff)
Lie (P(i])
fr por
pour
i de N + 1 c Nax
faui
Pi] = o
fi pou
fri INT
c) fonction DEGREE /P :
Poly) : ent
Vo
i : ent
debut
i = NMax
tantque Pli] fam
=
0 et i > o
i =
i =
1
fin tantque
retowns (1)
fi DEGREE
= fonction Coff (P Poly :
,
i : ent) red :
Val
debut
stounr (P(i))
fin coff
4) fonction CALCUL (PiPoly ,
X :
viel) : sel
vonede
So
Po 1
pour
i de o a' DEGREE(P) fai
Ses **
coff(P , i)
pour P
*X
fi
retowar IS)
5) procedum ADD
(Pr :
Poly , Pa : Poly ,0 P3 Poly (
:
Von
i : ent
de but
pom
i de 0 a Nan
fami
43/17 = Pr[i] + Pa[i]
In por
ADK
fr
5) procedu Derie (P Poly :
,
OPD ·
baly)
von
i : ent
debut
pour
i de a c Nuanc-1 faire
PPTi] =
P(ii) (i 1) +
fin pour
PP[Numc] > o
fri Derive
·
(M ent
fouch Soman : MAT
,
NL ,
NC :
von
S, i : ent
debut
pour
I de 1 a NL fani
pour de 1 a Nc
fair
Se S + m/i , j)
fine
Ecole Polytechnique de Sousse Année Universitaire : 2024 -2025
Exercice 2 (8 pts):
Une matrice creuse est une matrice contenant plus de 50% de valeurs nulles. La représentation
d’une matrice par un tableau à 2 dimensions, conduit à une occupation inutile de l’espace
mémoire par des 0. Dans ce problème, on travaille sur d’autres moyens de représentation des
matrices creuses dont le principe est le suivant :
Principe : Soit M une matrice d’entiers de taille NxN. On propose de représenter la matrice M
par deux tableaux Tv et Tn, tels que :
- Tv contient deux lignes : 1ère ligne contient les valeurs non nulles de M et la 2ème ligne
son numéro de colonne dans M.
- Le tableau Tn contient le nombre de valeurs non nulles de M par ligne.
Exemple d’illustration : Soit M une matrice de taille 5x5 :
5 4 0 0 1
0 5 0 0 0
0 1 0 7 0
0 0 0 0 0
0 0 3 0 0
Tv contiendra alors les valeurs suivantes :
5 4 1 5 1 7 3
1 2 5 2 2 4 3
et Tn contiendra: 3 1 2 0 1
Travail demandé :
Q1. Définir un nouveau type matrice nommé Mat pour la matrice M. Définir un nouveau type
nommé Tab-v pour le tableau Tv.
************************
On cherche à transformer M en Tv et Tn, sachant que la matrice M est déclarée et initialisée
dans l’algorithme principal et que N est une constante.
Q2. Ecrire la fonction nombreV qui calcule et retourne le nombre de valeurs non nulles de
matrice M donnée en paramètre.
Q3. Ecrire la procédure remplirTv qui remplit et retourne le tableau Tv obtenu à partir de M
donnée en paramètre.
Q4. Ecrire la procédure remplirTn qui remplit et donne le tableau Tn à partir de M donnée en
paramètre.
************************
Q5. Ecrire l’algorithme principal qui permet de saisir la matrice M en faisant appel à tous les
sous-programmes déjà implémenté pour afficher les tableaux Tv et Tn.
Bon travail