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

Ce modèle est l'épreuve d'informatique du concours d'accès en 1^re année du cycle d'ingénieurs GLSID (Génie du logiciel et des systèmes informatiques distribués) de l'ENSET Mohammedia, session de septembre 2014. Durée : 3 heures, sans calculatrice ni documents, notée sur 100 points : un QCM de 10 questions (10 points) et six exercices d'algorithmique. Les solutions peuvent être écrites en pseudo-code ou en C, C++, C#, Java ; la correction ci-dessous utilise le C. Voici une correction proposée.

💡 Ce que le jury regarde : un algorithme juste, lisible et commenté, avec sa complexité justifiée. Annoncez toujours vos hypothèses (indices à partir de 0, traitement des bords, cas d'égalité).

QCM (10 points)

1. A) 9, 7, 12, 3, 4. Une pile est LIFO : le dernier entré sort le premier, donc l'ordre d'insertion est inversé.
2. Réponse probable : B) 3, 4, 7, 9, 12. Un tas restitue ses éléments triés : B pour un tas-min, D pour un tas-max. La convention la plus courante (tas-min utilisé comme file de priorité) donne B.
3. C) une table de hachage. Un tableau indexé par les sommets dont chaque case pointe sur une liste chaînée : c'est la structure d'une table de hachage à chaînage.
4. C) Θ(h). La recherche suit un seul chemin depuis la racine ; au pire elle descend jusqu'à la profondeur h.
5. A) une rotation droite. Le fils gauche 8 devient la racine, 24 passe à sa droite, et le sous-arbre 12 (avec 11 et 18) passe de la droite de 8 à la gauche de 24.
6. B) On écrit l'équation de récurrence du coût (par exemple T(n) = 2T(n/2) + n) puis on la résout.
7. B) Pile. Le parcours en profondeur explore d'abord le dernier nœud découvert (LIFO), qu'on l'écrive avec une pile explicite ou par récursivité (pile des appels).
8. C) Le tri rapide. Il partitionne autour d'un pivot puis trie récursivement les deux parties : diviser pour régner.
9. B) Bellman-Ford. Plus courts chemins depuis une source avec poids négatifs (sans cycle absorbant) : Dijkstra ne s'applique pas aux poids négatifs, le tri topologique exige un graphe sans cycle, et Floyd-Warshall traite toutes les paires (plus coûteux, O(n³)).
10. C) sa complexité en pire cas. Le tri par tas est en O(n log n) même dans le pire cas (le tri rapide peut dégénérer en O(n²)), tout en triant sur place.

Exercice 1 (10 points) — développement limité de sin x

1. Algorithme

On ne recalcule ni la puissance ni la factorielle à chaque terme : chaque terme se déduit du précédent par t_k+1 = −t_k · x² / ((2k+2)(2k+3)), avec t₀ = x. Le développement à l'ordre n contient les termes de degré 2k+1 ≤ n.

double dlSinus(double x, int n) {
    double terme = x, somme = 0;
    int k = 0;
    while (2 * k + 1 <= n) {
        somme += terme;
        terme = -terme * x * x / ((2 * k + 2) * (2 * k + 3));
        k++;
    }
    return somme;
}

Contrôle : pour x = 0,5 et n = 7, on obtient 0,47942553, contre sin 0,5 = 0,47942554.

2. Complexité

La boucle tourne ⌊(n+1)/2⌋ fois avec un nombre constant d'opérations : O(n). Une version naïve qui recalcule x^k et k! à chaque terme coûterait O(n²).

Exercice 2 (16 points) — suite de Fibonacci

1. Algorithme récursif

long U(int n) {
    if (n <= 1) return n;          // U(0)=0, U(1)=1
    return U(n - 2) + U(n - 1);
}

2. Arbre des appels pour U(5)

U(5)
├── U(3)
│   ├── U(1)
│   └── U(2)
│       ├── U(0)
│       └── U(1)
└── U(4)
    ├── U(2)
    │   ├── U(0)
    │   └── U(1)
    └── U(3)
        ├── U(1)
        └── U(2)
            ├── U(0)
            └── U(1)

15 appels au total ; U(3) est calculé 2 fois, U(2) 3 fois, U(1) 5 fois. Résultat : U(5) = 5.

3. Complexité exponentielle

Soit C(n) le nombre d'appels : C(0) = C(1) = 1 et C(n) = 1 + C(n−1) + C(n−2). Posons A(n) = C(n) + 1 : A(n) = A(n−1) + A(n−2), avec A(0) = A(1) = 2. Notons φ = (1+√5)/2, qui vérifie φ² = φ + 1.

• Majoration : montrons A(n) ≤ 2φⁿ. Vrai pour n = 0 (2 ≤ 2) et n = 1 (2 ≤ 2φ). Si c'est vrai aux rangs n−1 et n−2 : A(n) ≤ 2φⁿ⁻¹ + 2φⁿ⁻² = 2φⁿ⁻²(φ + 1) = 2φⁿ⁻²·φ² = 2φⁿ.
• Minoration : de même A(n) ≥ φⁿ⁻¹ (vrai pour n = 0 et 1, et l'hérédité utilise la même identité φ + 1 = φ²).

Donc C(n) = Θ(φⁿ) ≈ Θ(1,618ⁿ) : le coût est exponentiel.

4. Inconvénients

• Temps exponentiel : les mêmes termes sont recalculés un très grand nombre de fois (U(1) est calculé U(n) fois).
• Consommation de la pile d'appels (profondeur n), risque de débordement ; temps d'appel de fonction non négligeable.

5. Solution itérative

long Uiter(int n) {
    if (n <= 1) return n;
    long a = 0, b = 1, c;              // a = U(i-2), b = U(i-1)
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

6. Complexité

O(n) en temps (une addition par tour) et O(1) en mémoire.

7. Convergence du rapport U(n−1)/U(n)

On calcule les rapports successifs et on s'arrête quand deux rapports consécutifs diffèrent de moins d'une précision ε. La limite est 1/φ = (√5 − 1)/2 ≈ 0,618034.

double convergence(double eps, int *rang) {
    long a = 1, b = 1, c;               // U(1), U(2)
    double r = (double)a / b, ancien;
    int n = 2;
    do {
        ancien = r;
        c = a + b; a = b; b = c; n++;   // b = U(n), a = U(n-1)
        r = (double)a / b;
        printf("n=%d  U(n-1)/U(n)=%.10f\n", n, r);
    } while (fabs(r - ancien) >= eps);
    *rang = n;
    return r;
}

Justification de la limite : si r_n = U(n−1)/U(n) tend vers ℓ, alors 1/r_n+1 = U(n+1)/U(n) = 1 + r_n, d'où ℓ = 1/(1 + ℓ), soit ℓ² + ℓ − 1 = 0 et ℓ = (√5 − 1)/2.

Exercice 3 (12 points) — fusion de deux listes triées

// T doit avoir au moins N1 + N2 cases
void fusion(int T1[], int N1, int T2[], int N2, int T[]) {
    int i = 0, j = 0, k = 0;
    while (i < N1 && j < N2) {          // on prend le plus petit des deux en tête
        if (T1[i] <= T2[j]) T[k++] = T1[i++];
        else                T[k++] = T2[j++];
    }
    while (i < N1) T[k++] = T1[i++];     // reste de T1
    while (j < N2) T[k++] = T2[j++];     // reste de T2
}

Sur l'exemple : 1 (T1), 5, 6 (T2), 7 (T1), 8 (T2), 9, 15 (T1), puis le reste de T2 : 18, 22 → T = {1, 5, 6, 7, 8, 9, 15, 18, 22}. Chaque élément est copié une seule fois : complexité O(N1 + N2).

Exercice 4 (16 points) — les deux éléments les plus proches

1. Tableau non trié

Sans tri, il faut comparer toutes les paires. Les « éléments distincts » s'entendent de valeurs différentes : dans l'exemple, les deux 100 (positions 0 et 2) ont un écart nul mais ne sont pas retenus. Avec la comparaison stricte, la première paire d'écart minimal rencontrée est gardée : (3, 7) avant (4, 5), conformément au résultat attendu.

void plusProches(int T[], int n, int *p1, int *p2, int *ecart) {
    *ecart = -1;                                  // -1 : aucune paire trouvée
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++) {
            int d = abs(T[i] - T[j]);
            if (d > 0 && (*ecart == -1 || d < *ecart)) {
                *ecart = d; *p1 = i; *p2 = j;
            }
        }
}

Sur l'exemple : écart 1 entre T[3] = 17 et T[7] = 18, positions 3 et 7.

2. Complexité

n(n−1)/2 comparaisons : O(n²).

3. Version avec tri préalable

Après tri, les deux valeurs les plus proches sont forcément voisines : un seul parcours suffit. Pour rendre les positions d'origine, on trie un tableau d'indices (ou des couples valeur–position) plutôt que les valeurs seules.

typedef struct { int val; int pos; } Elem;

void plusProchesTri(int T[], int n, int *p1, int *p2, int *ecart) {
    Elem E[n];
    for (int i = 0; i < n; i++) { E[i].val = T[i]; E[i].pos = i; }
    Tri_Rapide(E, n);                       // tri selon le champ val : O(n log n) en moyenne
    *ecart = -1;
    for (int i = 0; i < n - 1; i++) {        // un seul parcours des voisins
        int d = E[i + 1].val - E[i].val;
        if (d > 0 && (*ecart == -1 || d < *ecart)) {
            *ecart = d; *p1 = E[i].pos; *p2 = E[i + 1].pos;
        }
    }
}

4. Complexité et conclusion

O(n log n) pour le tri + O(n) pour le parcours = O(n log n) en moyenne. Conclusion : pour n grand, trier d'abord est nettement plus efficace que la comparaison de toutes les paires en O(n²) (pour n = 10⁶ : environ 2·10⁷ opérations contre 5·10¹¹). Remarque : en cas d'égalité d'écarts, la paire rendue peut différer de la version 1 (ici, (4, 5) au lieu de (3, 7)), les deux étant correctes.

Exercice 5 (18 points) — histogramme et filtre de Sobel

1. Matrice → vecteur (ligne par ligne)

void matriceVersVecteur(int N, int M, int img[N][M], int vect[]) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            vect[i * M + j] = img[i][j];      // le pixel (i, j) va à l'indice i*M + j
}

2. Histogramme

void histogramme(int vect[], int N, int M, int h[256]) {
    for (int g = 0; g < 256; g++) h[g] = 0;
    for (int p = 0; p < N * M; p++)
        h[vect[p]]++;
}

Complexité O(N·M).

3. Contour par l'opérateur de Sobel

Pour chaque pixel intérieur (les pixels du bord n'ont pas leurs 8 voisins ; on les met à 0), on applique la formule de l'énoncé Gx(i, j) = Σ_k Σ_l H(k, l)·A(i+k, j+l), de même pour Gy avec V, puis G = √(Gx² + Gy²), borné à 255.

int H[3][3] = {{-1, 0, 1}, {-2, 0, 2}, {-1, 0, 1}};
int V[3][3] = {{ 1, 2, 1}, { 0, 0, 0}, {-1,-2,-1}};

void sobel(int A[], int N, int M, int G[]) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if (i == 0 || j == 0 || i == N - 1 || j == M - 1) { G[i * M + j] = 0; continue; }
            int gx = 0, gy = 0;
            for (int k = -1; k <= 1; k++)
                for (int l = -1; l <= 1; l++) {
                    int a = A[(i + k) * M + (j + l)];
                    gx += H[k + 1][l + 1] * a;   // indices k,l de -1..1 décalés en 0..2
                    gy += V[k + 1][l + 1] * a;
                }
            int g = (int) sqrt((double)(gx * gx + gy * gy));
            G[i * M + j] = (g > 255) ? 255 : g;
        }
}

Le résultat est écrit dans un vecteur G distinct de A (sinon les pixels déjà traités fausseraient les suivants). Complexité : 9 multiplications par filtre et par pixel, soit O(N·M).

Exercice 6 (18 points) — polynômes en liste doublement chaînée

Convention : les monômes sont rangés par degré décroissant, sans coefficient nul ni deux monômes de même degré (comme dans l'exemple {(4,7) ; (−7,3) ; (6,0)}).

1. Monôme

typedef struct {
    double coef;
    int    degre;
} Monome;

2. Polynôme

typedef struct Noeud {
    Monome m;
    struct Noeud *prec, *suiv;
} Noeud;

typedef struct {
    Noeud *tete;     // monôme de plus haut degré
    Noeud *queue;    // monôme de plus bas degré
} Polynome;

// ajout en fin de liste (utilisé quand on produit les termes par degré décroissant)
void ajouterFin(Polynome *P, double c, int d) {
    if (c == 0) return;
    Noeud *nd = malloc(sizeof(Noeud));
    nd->m.coef = c; nd->m.degre = d; nd->suiv = NULL; nd->prec = P->queue;
    if (P->queue) P->queue->suiv = nd; else P->tete = nd;
    P->queue = nd;
}

3. Somme

Même principe que la fusion de deux listes triées (exercice 3) :

Polynome somme(Polynome P, Polynome Q) {
    Polynome S = {NULL, NULL};
    Noeud *p = P.tete, *q = Q.tete;
    while (p && q) {
        if (p->m.degre > q->m.degre)      { ajouterFin(&S, p->m.coef, p->m.degre); p = p->suiv; }
        else if (p->m.degre < q->m.degre) { ajouterFin(&S, q->m.coef, q->m.degre); q = q->suiv; }
        else { ajouterFin(&S, p->m.coef + q->m.coef, p->m.degre); p = p->suiv; q = q->suiv; }
    }
    for (; p; p = p->suiv) ajouterFin(&S, p->m.coef, p->m.degre);
    for (; q; q = q->suiv) ajouterFin(&S, q->m.coef, q->m.degre);
    return S;
}

Complexité O(|P| + |Q|). Les termes qui s'annulent ne sont pas ajoutés (test c == 0).

4. Produit

On multiplie P par chaque monôme de Q et on additionne les résultats partiels :

Polynome produit(Polynome P, Polynome Q) {
    Polynome R = {NULL, NULL};
    for (Noeud *q = Q.tete; q; q = q->suiv) {
        Polynome partiel = {NULL, NULL};          // P × (c·x^d) : degrés toujours décroissants
        for (Noeud *p = P.tete; p; p = p->suiv)
            ajouterFin(&partiel, p->m.coef * q->m.coef, p->m.degre + q->m.degre);
        R = somme(R, partiel);                    // (libérer l'ancien R et partiel)
    }
    return R;
}

Complexité O(|P|·|Q|²) avec cette méthode simple (chaque somme parcourt R).

5. Racines réelles dans [a, b]

Il n'existe pas de formule générale pour les racines d'un polynôme de degré quelconque : on procède numériquement. On évalue P par le schéma de Horner adapté à la liste, on découpe [a, b] en petits pas, et on affine par dichotomie chaque intervalle où P change de signe.

double evaluer(Polynome P, double x) {
    double r = 0; int dPrec = P.tete ? P.tete->m.degre : 0;
    for (Noeud *p = P.tete; p; p = p->suiv) {
        for (int k = p->m.degre; k < dPrec; k++) r *= x;   // Horner avec degrés manquants
        r += p->m.coef; dPrec = p->m.degre;
    }
    for (int k = 0; k < dPrec; k++) r *= x;
    return r;
}

void racines(Polynome P, double a, double b, double pas, double eps) {
    for (double x = a; x < b; x += pas) {
        double g = x, d = (x + pas < b) ? x + pas : b;
        double fg = evaluer(P, g), fd = evaluer(P, d);
        if (fg == 0) { printf("racine : %g\n", g); continue; }
        if (fg * fd < 0) {                           // changement de signe : dichotomie
            while (d - g > eps) {
                double m = (g + d) / 2;
                if (fg * evaluer(P, m) <= 0) d = m; else { g = m; fg = evaluer(P, g); }
            }
            printf("racine : %g\n", (g + d) / 2);
        }
    }
    if (evaluer(P, b) == 0) printf("racine : %g\n", b);
}

Limite à signaler : une racine double (sans changement de signe) ou deux racines dans le même pas peuvent échapper à la recherche ; on réduit le pas, ou l'on cherche aussi les racines de la dérivée P' pour isoler chaque racine.