نموذج مباراة ولوج السنة الأولى من سلك المهندسين (GLSID و II-BDCC) بالمدرسة العليا لأساتذة التعليم التقني بالمحمدية (ENSET) - يوليوز 2017 - اختبار المعلوميات - الجزء الثاني فقط (الخوارزميات والبرمجة)

Ce modèle est l'épreuve d'informatique du concours d'accès en 1^re année du cycle d'ingénieurs de l'ENSET Mohammedia (filières GLSID et II-BDCC), session de juillet 2017. Durée totale : 3 heures, sans calculatrice ni documents. Le document disponible contient la page de garde et la partie 2 « Algorithmique et programmation » (2 h, notée sur 80) : un QCM de 9 questions et trois exercices. Les parties « Informatique générale » et « Techniques d'expression » ne figurent pas dans le scan. Voici une correction proposée.

💡 Méthode pour les QCM de code : déroulez le programme à la main dans un petit tableau (une colonne par variable, une ligne par tour de boucle). C'est plus sûr que de « deviner » le rôle de la fonction.

QCM (25 points)

1. C) 6. Déroulement de i à chaque tour : T[0]=1 < T[1]=5 → i=3 ; T[3]=4 < 6 → i=6 ; T[6]=44 > 10 → i=2 ; T[2]=8 > 4 → i=−2 ; 5^e tour : i<0 donc i=1, puis T[1]=5 < 8 → i=4. n vaut 5, on sort : T[4] = 6.
2. C) 34. C'est la suite de Fibonacci : la boucle tourne 8 fois (i de 1 à 8) et c prend les valeurs 1, 2, 3, 5, 8, 13, 21, 34. F(9) = 34.
3. D) 70. Algorithme de Kadane (somme maximale d'un sous-tableau contigu) : s1 = 10, 30, −5 (remis à 0), puis 35, 25, 30, 20, 40, 70. Le maximum s2 = 70 (sous-tableau 35, −10, 5, −10, 20, 30).
4. A) 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1. f(n) affiche f(n−1), puis n, puis f(n−1) (schéma des tours de Hanoï) : f(1) = « 1 », f(2) = « 1 2 1 », f(3) = « 1 2 1 3 1 2 1 », f(4) = f(3) 4 f(3), soit 15 nombres.
5. B) Θ(h). La recherche descend d'un niveau à chaque comparaison ; au pire on parcourt un chemin racine–feuille de longueur h (h ne vaut log n que si l'arbre est équilibré, et peut valoir n s'il est dégénéré).
6. Réponse probable : B) 3, 4, 7, 9, 12. Un tas restitue toujours ses éléments triés : seules B (tas-min) et D (tas-max) sont possibles. La convention la plus répandue dans les cours d'algorithmique francophones (tas utilisé comme file de priorité « min ») donne B ; avec un tas-max, ce serait D. Retenez surtout le principe : l'extraction se fait dans l'ordre trié.
7. D) 9 2 7 1 3 6 4 8 5. Le programme est un parcours infixe itératif (on empile en descendant à gauche, on affiche au dépilement, puis on passe au fils droit). Infixe de l'arbre : sous-arbre gauche (9, 2, 7, 1), racine 3, sous-arbre droit (6, 4, 8, 5).
8. A) une rotation droite. Le fils gauche 8 de la racine 24 devient la racine ; 24 descend à droite de 8, et l'ancien sous-arbre droit de 8 (12 avec 11 et 18) devient le sous-arbre gauche de 24. C'est exactement la rotation droite autour de 24.
9. C) une table de hachage. Des listes de successeurs = 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.

Exercice 1 (5 points)

Le terme général est (1+2+…+k)·2^k−1 = k(k+1)/2 · 2^k−1, pour k = 1 à n. Valeurs de contrôle : X(1)=1, X(2)=7, X(3)=31, X(4)=111.

1. Forme itérative

long calculX(int n) {
    long X = 0, somme = 0, puiss = 1;   // somme = 1+...+k, puiss = 2^(k-1)
    for (int k = 1; k <= n; k++) {
        somme += k;
        X += somme * puiss;
        puiss *= 2;
    }
    return X;
}

Une seule boucle : complexité O(n), sans recalculer la somme ni la puissance à chaque tour.

2. Forme récursive

Relation de récurrence : X(0) = 0 et X(n) = X(n−1) + n(n+1)/2 · 2ⁿ⁻¹.

long puissance2(int p) { return (p == 0) ? 1 : 2 * puissance2(p - 1); }

long calculXRec(int n) {
    if (n == 0) return 0;
    return calculXRec(n - 1) + (long)n * (n + 1) / 2 * puissance2(n - 1);
}

Exercice 2 (20 points) — algorithme KM (k-moyennes)

1) Exécution sur A(1), B(3), C(5), D(9), E(11), F(7), G(4)

Départ : C1 = 1, C2 = 3. Chaque point va au centre le plus proche, puis on recalcule les moyennes.

Détail des basculements : à l'itération 2, B(3) est à 2 de C1 et à 3,5 de C2 ; à l'itération 3, G(4) est à 2 de C1 et à 3,2 de C2 ; à l'itération 4, C(5) est à 2,33 de C1 et à 3 de C2 ; à l'itération 5, F(7) reste dans G2 (3,75 contre 2). Deux itérations successives donnent les mêmes groupes : l'algorithme s'arrête.

Résultat : G1 = {1, 3, 4, 5} (A, B, G, C), centre 3,25 ; G2 = {7, 9, 11} (F, D, E), centre 9. Sur la copie, dessinez à chaque itération les deux ellipses G1 et G2 avec les abscisses qu'elles contiennent.

2) Généralisation à n points et k groupes

// x[0..n-1] : abscisses ; k groupes ; grp[i] = numéro du groupe du point i
void kmoyennes(double x[], int n, int k, int grp[]) {
    double c[k], somme[k]; int nb[k], change = 1;
    for (int j = 0; j < k; j++) c[j] = x[j];        // k points initiaux (ou tirés au hasard)
    for (int i = 0; i < n; i++) grp[i] = -1;
    while (change) {
        change = 0;
        for (int i = 0; i < n; i++) {                  // étape 2 : affectation
            int best = 0;
            for (int j = 1; j < k; j++)
                if (fabs(x[i] - c[j]) < fabs(x[i] - c[best])) best = j;
            if (grp[i] != best) { grp[i] = best; change = 1; }
        }
        for (int j = 0; j < k; j++) { somme[j] = 0; nb[j] = 0; }
        for (int i = 0; i < n; i++) { somme[grp[i]] += x[i]; nb[grp[i]]++; }
        for (int j = 0; j < k; j++)                      // étape 3 : recalcul des centres
            if (nb[j] > 0) c[j] = somme[j] / nb[j];
    }                                                    // étape 4 : arrêt si aucun changement
}

Pour un espace à plusieurs dimensions, on remplace |x − c| par la distance euclidienne et la moyenne par la moyenne coordonnée par coordonnée. Coût d'une itération : O(n·k).

Exercice 3 (30 points) — réseau routier

1. Déclarations

#define MAX 100
typedef struct {
    char   nom[50];
    double latitude, longitude, altitude;   // degrés, degrés, mètres
    long   population;
} Ville;

typedef struct {
    int    n;                 // nombre de villes
    Ville  NOEUDS[MAX];
    double M[MAX][MAX];       // M[i][j] = longueur de la route i -> j, -1 si pas de route
} Reseau;

Une route bidirectionnelle se traduit par M[i][j] = M[j][i] ; une route à sens unique par une seule des deux cases.

2. Distance linéaire entre i et j

On calcule la distance à vol d'oiseau sur la sphère terrestre (formule de haversine), puis on tient compte de l'écart d'altitude.

#include <math.h>
#define R 6371000.0   // rayon terrestre en mètres
double rad(double d) { return d * M_PI / 180.0; }

double distanceLineaire(Reseau *r, int i, int j) {
    Ville a = r->NOEUDS[i], b = r->NOEUDS[j];
    double dlat = rad(b.latitude - a.latitude), dlon = rad(b.longitude - a.longitude);
    double h = sin(dlat/2)*sin(dlat/2)
             + cos(rad(a.latitude))*cos(rad(b.latitude))*sin(dlon/2)*sin(dlon/2);
    double sol = 2 * R * asin(sqrt(h));           // distance au sol
    double dz  = b.altitude - a.altitude;
    return sqrt(sol*sol + dz*dz);
}

Une réponse plus simple (distance euclidienne sur des coordonnées projetées) est en général acceptée si l'hypothèse est énoncée.

3. Longueur d'un chemin

// chemin[0..k-1] : liste des nœuds traversés ; renvoie -1 si un tronçon n'existe pas
double longueurChemin(Reseau *r, int chemin[], int k) {
    double L = 0;
    for (int p = 0; p < k - 1; p++) {
        double d = r->M[chemin[p]][chemin[p+1]];
        if (d < 0) return -1;
        L += d;
    }
    return L;
}

4. Tous les chemins de i vers j (chemins élémentaires)

Parcours en profondeur avec retour arrière ; un tableau visite empêche de repasser par une ville (sinon le nombre de chemins serait infini à cause des cycles, par exemple 0 → 1 → 0).

int chemin[MAX], visite[MAX];

void tousLesChemins(Reseau *r, int u, int j, int prof) {
    chemin[prof] = u; visite[u] = 1;
    if (u == j) {                                  // chemin complet : on l'affiche
        for (int p = 0; p <= prof; p++) printf("%d ", chemin[p]);
        printf(" (longueur %.1f)\n", longueurChemin(r, chemin, prof + 1));
    } else {
        for (int v = 0; v < r->n; v++)
            if (r->M[u][v] > 0 && !visite[v])
                tousLesChemins(r, v, j, prof + 1);
    }
    visite[u] = 0;                                 // retour arrière
}
// appel : mettre visite[] à 0 puis tousLesChemins(r, i, j, 0);

5. Plus court chemin de i vers j (Dijkstra)

Les distances sont positives : l'algorithme de Dijkstra s'applique.

double plusCourtChemin(Reseau *r, int i, int j, int pred[]) {
    double dist[MAX]; int fixe[MAX];
    for (int v = 0; v < r->n; v++) { dist[v] = INFINITY; fixe[v] = 0; pred[v] = -1; }
    dist[i] = 0;
    for (int t = 0; t < r->n; t++) {
        int u = -1;                                   // sommet non fixé le plus proche
        for (int v = 0; v < r->n; v++)
            if (!fixe[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (u == -1 || dist[u] == INFINITY) break;
        fixe[u] = 1;
        if (u == j) break;
        for (int v = 0; v < r->n; v++)                // relâchement des arcs sortants
            if (r->M[u][v] > 0 && dist[u] + r->M[u][v] < dist[v]) {
                dist[v] = dist[u] + r->M[u][v];
                pred[v] = u;
            }
    }
    return dist[j];   // INFINITY si j est inaccessible ; le chemin se lit à rebours via pred[]
}

Exemple sur la matrice de l'énoncé : de 0 vers 4 il n'y a pas de route directe ; Dijkstra donne 0 → 2 → 4, longueur 4 + 4 = 8 (contre 0 → 2 → 3 → 4 = 12). Complexité O(n²) avec la matrice.

6. Réseau enrichi

A) On remplace la simple distance par une structure « tronçon » :

typedef struct {
    int    existe;          // 0 si pas de route i -> j
    double distance;        // km
    double vitesseMax;      // km/h
    double debit;           // véhicules par seconde (valeur instantanée, mise à jour)
    int    stationService;  // 0/1
    char   nomStation[50];
} Troncon;

typedef struct {
    int     n;
    Ville   NOEUDS[MAX];
    Troncon T[MAX][MAX];
} ReseauRoutier;

B) Contraintes pour le chemin le plus rapide :

• Le poids d'un arc n'est plus la distance mais un temps de parcours : au minimum distance / vitesseMax, augmenté selon le débit (congestion) ; il faut donc un modèle temps = f(distance, vitesse, débit).
• Le débit est instantané : les poids changent dans le temps ; le calcul doit être refait régulièrement, ou bien utiliser un graphe dépendant du temps (le temps d'un tronçon dépend de l'heure à laquelle on y arrive).
• Des contraintes de faisabilité s'ajoutent : autonomie du véhicule et présence de stations de service sur l'itinéraire, sens de circulation, tronçons fermés.
• Les poids restent positifs : Dijkstra (ou A* avec la distance linéaire de la question 2 comme heuristique) reste utilisable, mais plusieurs critères (temps, distance, carburant) sont en concurrence : il faut soit les pondérer dans un coût unique, soit chercher un compromis.