Mines-Ponts 2023 MPI Informatique 1 : sujet en PDF

Sujet de l'épreuve de Informatique 1 du Concours commun Mines-Ponts, France, session 2023, filière MPI, en 3 heures. Thème : Listes à accès direct : représentation binaire gauche, arbres binaires parfaits et listes gauches en C.

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

Ce que traite le sujet, partie par partie

• Section 1 : représentation binaire gauche des entiers naturels. Écriture des entiers avec les poids 2^(n+1) - 1 et les chiffres 0, 1, 2 : plus grand entier représentable, unicité, invariant de la structure C, conversion, incrémentation et décrémentation en temps constant.
  À revoir : Langage C : types, tableaux, pointeurs, allocation, Algorithmes, discipline de programmation, validation et tests, Architecture de l'ordinateur et représentation des nombres
• Section 2 : arbres binaires parfaits. Hauteur et construction de nœuds avec assertion sur l'allocation, nombre de nœuds d'un arbre parfait, test de perfection, accès au k-ième nœud en ordre préfixe et complexité moyenne par un calcul d'espérance.
  À revoir : Langage C : types, tableaux, pointeurs, allocation, Récursivité
• Section 3 : listes gauches. Suites d'arbres parfaits associées à la représentation gauche du cardinal : accès, modification, empilement et dépilement en tête avec leurs complexités, puis course critique entre fils d'exécution et problème des producteurs et consommateurs avec verrou et sémaphores.
  À revoir : Langage C : types, tableaux, pointeurs, allocation

Chapitres à revoir avant de traiter ce sujet

• Langage C : types, tableaux, pointeurs, allocation
• Algorithmes, discipline de programmation, validation et tests
• Architecture de l'ordinateur et représentation des nombres
• 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.