CCINP 2022 MP Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2022, filière MP, en 4 heures. Thème : Automates augmentés, tas binomiaux et arbre de Calkin-Wilf.

Ce que traite le sujet, partie par partie

• Partie I : automates. Automate fini non déterministe augmenté d'un sous-ensemble d'états : langage reconnu à un seuil donné, dénombrement et majoration des calculs réussis, construction d'un automate fini à (s+1)p états qui reconnaît ce langage.
• Partie II : autour des tas. En Python, arbres binomiaux et leurs propriétés par récurrence, tas binomial, recherche du minimum, insertion avec sa complexité et invariant de boucle.
• Partie III : autour de l'énumération des fractions positives. En OCaml, arbre de Calkin-Wilf et pgcd, bijection entre les entiers naturels et les rationnels positifs, suite de Stern, chemin vers un nœud, ancêtre commun et formule du successeur.

Chapitres à revoir avant de traiter ce sujet

• Arbres binaires, arbres binaires de recherche et tas
• Complexité des algorithmes itératifs et récursifs
• Langage OCaml : expressions, types, filtrage, récursivité
• Arithmétique dans l'ensemble des entiers relatifs
• 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.