Mines-Ponts 2025 MPI Informatique 1 : sujet en PDF

Sujet de l'épreuve de Informatique 1 du Concours commun Mines-Ponts, France, session 2025, filière MPI, en 3 heures. Thème : Tableaux associatifs en C : arbres binaires de recherche, ramasse-miettes, skip lists et analyse syntaxique.

Lire le sujet 14 pages · sujet sans corrigé, reproduit sans retouche−+Télécharger le PDF (0,8 Mo)

Ce que traite le sujet, partie par partie

• Section 1 : implémentation par un arbre binaire de recherche. Chaînes en C et code ASCII en binaire et hexadécimal, copie de chaîne, nœuds d'arbre immuables, valeur d'équilibre, hauteur d'un arbre équilibré et recherche en temps logarithmique.
  À revoir : Langage C : types, tableaux, pointeurs, allocation, Architecture de l'ordinateur et représentation des nombres, Chaînes de caractères et algorithmes sur les textes
• Section 2 : ajout d'un ramasse-miettes. Algorithme de marquage puis libération : liste des nœuds alloués, marquage récursif des nœuds accessibles, libération et correction d'un parcours de liste.
  À revoir : Langage C : types, tableaux, pointeurs, allocation, Récursivité
• Section 3 : implémentation par un algorithme probabiliste. Skip lists : recherche par niveaux, tirage géométrique du niveau, insertion, caractère Las Vegas et complexité moyenne logarithmique.
  À revoir : Langage C : types, tableaux, pointeurs, allocation
• Section 4 : analyse syntaxique. Règles de production pour des chaînes de couples clef:valeur, arbre de dérivation et automate déterministe reconnaissant le langage.

Chapitres à revoir avant de traiter ce sujet

• Langage C : types, tableaux, pointeurs, allocation
• Architecture de l'ordinateur et représentation des nombres
• Chaînes de caractères et algorithmes sur les textes
• Récursivité

Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.