نموذج مباراة ولوج السنة الأولى من سلك المهندسين GLSID - المدرسة العليا لأساتذة التعليم التقني بالمحمدية (ENSET) - دورة يوليوز 2015 - اختبار التخصص: الخوارزميات والبرمجة

استُخرج هذا النص آلياً من صور الامتحان وقد يحتوي على أخطاء في القراءة — الصور أعلاه هي المرجع.

— صفحة 1 —
ROYAUME DU MAROC
MINISTER NEMENT
St .DEL IERCHE ‏وزارة التعليم العالي والبحث العلمي‎
SCIENTIFIQUE ET DE LA FORMATION ‏وتكوين الاطر‎
DES CADRES
—— ‏اا‎
Université Hassan ١١ de Casablanca
Ecole Normale Supérieure
de l'Enseignement Technique Mohammedia
جامعة الحسن الثاني بالدار البيضاء
المدرسة العليا لأساتذة التعليم التقني
المحمدية
Concours d’accès en première année du cycle d’ingénieurs
Génie du Logiciel et des Systèmes Informatiques Distribués (GLSID)
Session : Juillet 2015
Epreuve de spécialité
Algorithmique et programmation
Durée : 3 heures
|
Remarques importantes :
L'usage de la calculatrice ou de tout autre appareil électronique est interdit.
- Aucun document n’est autorisé.
Les réponses à toutes les questions doivent être rédigées dans les feuilles de réponses.
Chaque question du QCM ne peut avoir qu’une seule bonne réponse parmi les quatre propositions.
Toutes les réponses au QCM doivent être reportées dans la feuille de réponse de la page 9 en plaçant
pour chaque question une coche au centre de la case de la bonne colonne (A, B, C ou D).
Les solutions algorithmiques peuvent être rédigées en utilisant un pseudo langage algorithmique ou
l’un des langages de programmation suivants : C, CH#, CH, Java.
La clarté et la précision de vos solutions algorithmiques seront prises en considération.
- L'épreuve est notée sur un total de 100 points.
ل
À
Page 1 sur 9
As

— صفحة 2 —
“الله
QCM : (20 points )
Reporter dans les feuilles de réponses, la lettre qui corres
pond à la bonne réponse :
1. I
-aquelle de ces étapes ne fait Pas partie de la stratégie « diviser pour régner » ?
A) diviser le problème, C) résoudre les sous-problèmes,
B) trier les sous-problèmes, D) recombiner les résultats.
Quel est le nombre d'appels à la fonction 10 suite à l’exécution du code suivant ?
for(int i=0; i<n; Î+=2) for(int j=1; j<n; f(, j*=2) ;
A) 8(n), |
B) 6(nlog(n)),
C) 8(n?),
D) 4(log(n)).
En plus d’un (ou plusieurs) appel à lui-même, que doit toujours comporter un algorithme
récursif ?
A) une boucle for, C) une condition de terminaison,
B) une étape de division, D) une étape de fusion.
4. Quel est l’algorithme de tri qui est O(n log n) dans le cas moyen ?
A) Tri par sélection,
B) Tri à bulle,
C) Tri par monceau,
D) Tri par insertion.
5. Le tri fusion d’un tableau de n éléments se fait dans le meilleur cas en :
A) 8(n), C) 8(n?),
B) O(nlog(n)), D) @(log(n)).
6.
Laquelle de ces structures de données est à utiliser pour implémenter efficacement une pile
sans avoir à gérer les problèmes de dépassement de capacité (stack overflow) ?
A) un tableau, C) une liste chaînée,
B) un arbre binaire, D) untas.
Laquelle de ces opérations ne s’effectue pas en temps constant sur une liste chaînée de ‏م‎
‎éléments ?
A) insertion en tête, C} suppression de l’élément en tête,
B) insertion à la position courante, D) accès à l’élément à la position n/2.
8. Partant d’une file vide, on effectue les opérations suivantes : enfiler(3), enfiler(7), defiler(),
enfiler(17), defiler(), enfiler(11). Quelle valeur devrait renvoyer un nouvel appel à defiler() ?
A) 3, B) 7, C) 11, D} 17.
Page 2 sur 9
ا ‎à ٠‏ .ددا انم لان ‎D'OR‏

— صفحة 3 —
‎quel progrurune parmi les suivants la pile serait la structure de données fondamentale ?‏ سو
‎A) Un correcteur orthographique, C) Un opérateur de complétion,‏
‎B) {Un ordonnançceur de tâches, Dj Un analyseur syntaxique.‏
‎10 Pour un arbre binaire parfait de hauteur ‏به‎ le nombre de nœuds est :
A} 2 0 2+1:
8) 2"*1—1, D) nlog(n).
‎11. Soit un arbre binaire de recherche contenant des valeurs entières. On désire chercher la valeur
42. Quelle séquence parmi les suivantes, ne pourrait pas être une suite de nœuds parcourus ?
‎A) 18-27-60-47-29-42, © 30-38-40-48 -44 - 42,
‎8) 57-18-53-55-48 -42, D) 36-46-38-44-40- 42.
‎12. Pour supprimer un élément dans un arbre binaire de recherche :
Aj On le remplace par son fils gauche ou son fils droit,
8( On le remplace par le plus petit élément de son fils gauche,
© On le remplace par le plus grand élément de son fils gauche, ou le plus petit élément
de son fils droit, et on remplace celui-ci par son fils,
‎D) On le remplace par le plus petit élément de son fils droit.
‎13. Parmi les arbres binaires de recherche suivants, lequel n’est pas un arbre AVL ?
‎© ‘4: D)
‎14. Laquelle de ces structures de données permet de mieux implémenter une file de priorité ?
A) Une liste, C) Une table de hachage,
8) Untas, D) Un graphe.
‎Page 3 sur 9

— صفحة 4 —
15. Pour insérer un élément dans un tas :
A} on l'insère à la racine et on le fait descendre à sa place,
8) on cherche sa place et on l'y insère en déplaçant le nœud présent,
© on l’insère à la fin du tas et on le fait remonter à sa place,
D) on cherche une feuille plus grande que lui, et on l'insère comme son fils gauche.
16. Laquelle de ces opérations s'effectue toujours en temps constant dans une table de hachage ?
A) Recherche,
B) Suppression,
© Insertion, .
D) aucune des trois propositions.
17. On veut insérer l'élément x={cle , info) dans une table de hachage tab dont la fonction de
hachage est h. La fonction inserer(v, L) insère l'élément V dans la liste L. Laquelle de ces
opérations est la bonne ?
A) inserer(cle, tablinfo]), C) inserer(tab[cle], h (info)),
8) inserer(h(x), tab[clel), D) inserer(x, tab{h(cle)]).
18. Pour une implémentation standard de tas avec un tableau, lequel des tableaux suivants, ne
représente pas un tas bien ordonné ?
A) [55 [24 | 18 | 14 | 11 | 16 | 10 © 714618613413003 ]
8) [66 | 17 ] 50 | 16 | 10 ‘ D) [37[23[23[17[25[n] |
19. Soit G un graphe orienté non valué, quasi complet, dont on cherche à parcourir les nœuds pour
les énumérer. Quelle est la meilleure représentation possible des arcs de G?
A) Une matrice,
B) Une table de listes chaînées,
© Une liste chaînée,
D) Un tas.
20. On considère un graphe orienté possédant n arcs et m sommets. Quel espace mémoire occupe
sa représentation par liste de successeurs ?
A) O(n), © 8(n+m),
B) O(m°), D) O(n x m).
Page 4 sur 9

— صفحة 5 —
ةفص . .أ ا ا اذ الس »سسب
Exercice 1 : (12 points)
ecrire un algorithme qui calcule le développement limité (DL) à l'ordre 2n+3 de la fonction
arctan(x) définie par :
3 5 7 op ‏ا‎
‏ا ا لبتم واو‎ DE 2+3
(x) Re PT + O(x2"**)
2. Evaluer la complexité de votre solution.
3. Modifier l'algorithme de la question 1 pour obtenir un algorithme qui calcule la valeur
approchée de 7 sachant |” expression suivante : e = arctan(1). L'algorithme doit s’arrêter
lorsque l'erreur relative en valeur absolue est inférieure à une précision €.
4. Sachant que le schéma de calcul basé sur le DL converge très lentement, quels risques encouré
votre algorithme ? Proposer une alternative (sans la coder) pour éviter ces risques.
Exercice 2 : (18 points)
On cherche à étudier le problème de calcul de x", étant donnés un réel x et un entier positif #. On
souhaite faire ce calcul en se basant sur la règle suivante : Partant de yo = x, et si on a déjà calculé pr,
y2, … et pi-1, ON 06 calculer y: comme produit de deux résultats précédents arbitraires : Yi = YjYk»
avec 0 <j,k<i.
Le but est alors de calculer x” le plus vite possible en minimisant i tel que y: = x
En appliquant la règle précédente, plusieurs schémas de calcul peuvent être trouvés. Parmi lesquels
on distingue les deux schémas suivants :
e Schéma l: Yi = YoYi-1
‎siiest pair :‏ 2 درلا
‎+ Schéma2:YiT { ‏ار‎ Jura Siiest impair
‎Où [i/21 désigne la partie entière du rapport i/2.
‎1. Ecrire un algorithme itératif qui calcule x" selon le schéma 1,
2. Ecrire un algorithme récursif qui calcule x" selon le schéma 2,
3. Votre solution récursive représente-t-elle une récursivité terminale ? Justifier votre réponse,
‎4, Evaluer la complexité des deux algorithmes,
‎Page 5 sur 9

— صفحة 6 —
‎di S 1 1‏ ِ
م ‎“LÉ hd.‏ لضن ال :
لا بكر ‎CT‏ الحا مسا اما لاسا
‎3. Donner la forme itérative équivalente à votre solution récursive,
‎6. Etant donné un ordinateur équipé d'un processeur 1GHz, donner une approximation du temps
‎machine (en Secondes) que fera cet ordinateur pour calculer x”! par les deux algorithmes quand
‎ils sont appelés pour x=1 et n=1e30. On supposera que le processeur est utilisé à son entière
Capacité pour ce traitement et que l'opération de multiplication réelle coutera 10 cycles
horloge, Pour simplifier les calculs, on fera lapproximation 3l0g,(10) & 10. Quelle
‎conclusion faites-vous en comparant les deux résultats ?
‎Exercice 3 : (10 points)
‎Soient T1 et T2deux tableaux d’entiers ordonnés de tailles respectives #1 et #2. Ecrire un algorithme
en O(n) qui permet de trouver la Première Plus Longue Sous Chaîne Non Vide Commune à T1 et
T2. Le résultat nommé PPLSCNVC, est un tableau de trois éléments représentant dans l’ordre l’indice
de début de la sous chaîne dans 77, son indice de début dans T2 et sa longueur. Dans le cas où aucune
sous chaine non vide n’est trouvée, l’algorithme doit produire le résultat PPLSCNVC= {0, 0, 0}.
Exemple :
‎9 7 3 3 4 5 6 7 8 9 10 11
| TI 5 | 5 5 90 11 | 13 | 14 | 14 [ 15 | 20 | 30 | 0
‎0 1 2 3 4 5 6 7 8 9
12 | 1 3 4 > 9 11 | 13 | 15 | 30 | 30
‎dt de, à à
‎Le résultat doit être :
‎PPLSCNVC | 2 [ 3 | 4
‎Exercice 4 : (20 points)
‎On considère une image couleur constituée des trois couches RGB. Les données de l’image sont
‎stockées dans un tableau à trois dimensions : la première dimension correspond à la couleur (L'indice
0 pour la composante rouge, l'indice 1 pour la composante vert et l'indice 2 pour la composante bleu),
‎la seconde correspond à la coordonnée selon # et la troisième à la coordonnée selon ÿ. Ainsi, les
‎dimensions du tableau sont : 3 x M1 x N où M représente le nombre de pixels selon # et MN le nombre
‎de pixels selon y. La valeur associée à chaque composante de couleur est un entier compris entre 0 et
‎255. La figure 1 du schéma suivant illustre la structure d’une image RGB.
‎Pour permettre facilement certains traitements sur l’image (classification, filtrage, reconnaissance,
‎-.) des transformations préalables sont requises parmi lesquelles on s’intéresse aux suivantes :
‎Page 6 sur 9

— صفحة 7 —
اسح الله عد قيال 7 # سمس اسابل ‎Vlan‏ سالا نل شال سبالمل مسقاو
R VB
0
1
‏لي‎ i
y P
Figure 1 : Structure d’une image RGB Figure 2 : Structure d’une image à palette de couleurs
+ La transformation d’une image RGB de taille 3 x M x N en une image à palette de couleurs
mémorisée sous forme d’une matrice de taille M x N d’entiers, chaque entier correspondant à
un index dans une palette de couleurs qui est une matrice de taille P x 3 où P désigne le nombre
de couleurs distinctes contenues dans l’image. les trois colonnes de la matrice correspondent
dans l’ordre aux composantes de rouge, de vert et de bleu (figure 2 du schéma ci-dessus).
e La transformation d’une image RGB de taille 3 x M x N en une image en niveau de gris
mémorisée sous forme d’une matrice de taille M x N contenant des valeurs entières comprises
entre 0 et 255 (0 = noir à 255 = blanc). On adoptera la règle de calcul suivante pour calculer les
aR+BV+yB
a+B+y
niveaux de gris : g =
Où a, Bet y sont des entiers compris entre 0 et 255 tel que ‏م‎ + B+ y = 255
e Transformation d’une image niveau de gris de taille M x N en une image binaire mémorisée
sous forme d’une matrice de taille M x N contenant des valeurs0 et 1 (0 = noir à 1 = blanc). En
fixant un seuil s entier compris entre 0 et 255, la valeur de l’image binaire transformée d’un
niveau de gris ‏ع‎ est définie à 0 (noir) si ‏ع‎ est inférieur à s et à 1 (banc) si non.
1. Proposer des types pour les trois formes d’images : £_ imgRGB, t_imgPalette, t_imgNvGris et
t_imgBinaire,
2. Ecrire la fonction imgRGB2imgPalette qui reçoit une image RGB et qui retourne sa
transformée en format palette de couleurs,
3. Ecrire la fonction imgPalette2imgRGB qui reçoit une image en format palette de couleurs et
qui retourne sa transformée en format RGB,
4. Ecrire la fonction imgRGB2imgNvGris qui reçoit une image RGB et qui retourne sa
transformée en format niveau de gris, On prendra pour ‏عم‎ =54, B=182 et y=19,
Ecrire la fonction éngNvGris2imgBinaire qui reçoit une image niveaux de gris et un seuil s
et qui retourne sa transformée en format binaire.
Page 7 sur 9

— صفحة 8 —
‎ae À dé‏ ام كس لاسا ثلا شاللا
‏وا
‎/
‎Exercice 5 : (20 points)
‎On souhaite implémenter la structure de donnée d’une pile de mots (de type texte) dans le but de‏ و0
‎réaliser un module d'évaluation d'expressions arithmé iques en notation postfixe (notation
‎polonaise). Cette structure permet de stocker des données selon le principe LIFO (Last In First Out).
‎La structure de données choisie pour l'implémentation de la pile est la structure de liste simplement
chainée. Ainsi un élément de la pile sera composé d’un mot (un texte) qui constitue la donnée stockée
par la pile et un pointeur (ou une référence) qui indique l’élément suivant dans la pile. Le schéma
‎suivant illustre la structure de donnée d’une pile sous forme de liste chaînée :
‎Debut mot suivant
:t_pile _element
‎| 1. Donner la déclaration des types £_ element et t pile
‏ات
‎Ecrire la fonction estVide qui permet ‏عل‎ tester si une pile P est vide,
Ecrire la fonction empiler qui permet d’empiler un mot ‏دم‎ dans une pile P
‎Ecrire la fonction depiler qui permet de dépiler le mot au sommet d’une pile P
‎HE ‏ا‎
‎On souhaite utiliser cette structure de pile pour permettre l'évaluation d’une expression
arithmétique entière en notation postfixe fournie sous forme d’une chaine de texte et dont les
éléments (opérandes et opérateurs) sont obligatoirement séparés par au moins un espace.
a. Ecrire une fonction decomposer qui décompose le texte d’une expression arithmétique
‎posifixe E en un tableau de mots (opérandes et opérateurs).
‎Exemple :
‎SiE="32 24 + 3 15 - *" ‏عو[‎ résultat produit par la fonction décomposer sera :
‎32 24 + 3 15 = * |
‎b. Ecrire une fonction ge{Operateur qui reçoit un mot m et qui retourne le code opérateur
‎correspondant. On convient de coder les opérateurs +, - et * respectivement par 1,2et3.
La fonction doit retourner 0 si le mot reçu ne correspond à aucun opérateur arithmétique.
c. Ecrire une fonction getNombre qui reçoit un mot ‏ا‎ et qui retourne le nombre
correspondant lorsque m n’est composé que de chiffres. Si non une exception (erreur)
‎doit être soulevée selon une notation à convenir.
‎d. Ecrire une fonction evaluerExpression qui reçoit le texte d’une expression arithmétique
postfixe ‏كا‎ et qui retourne le résultat Correspondant si l’expression est bien formée si non
‎une erreur doit être soulevée selon une notation à convenir.
‎Page 8 sur 9
‎je ‏لاا اي ثيب الا‎ 1 Ale