CCINP 2023 MP Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2023, filière MP, en 4 heures. Thème : Sélection du (k+1)e plus petit élément, clique de célébrités et famille d'automates A_k,p.

Ce que traite le sujet, partie par partie

• Partie I : programmation en OCaml, sélection du (k+1)e plus petit élément. Fonctions récursives sur les listes sans trait impératif, tri par insertion, paquets de cinq et médians, partage autour d'un pivot, traduction de l'algorithme de sélection diviser pour régner, et majoration linéaire de sa complexité.
• Partie II : recherche d'une clique de célébrités. Cliques d'un graphe et propriétés de la clique de célébrités, puis algorithme en Python sur des listes d'adjacence et preuve par récurrence sur le nombre de sommets.
• Partie III : étude d'une famille d'automates. Automates déterministes A_k,p sur l'alphabet {0,1}, qui calculent la parité des 1 placés aux positions congrues à k modulo p : état atteint après lecture d'un mot, mots reconnus, reconnaissance par un autre automate de la famille, compatibilité avec le ou exclusif de deux mots, effet de l'ajout de zéros en tête ou en fin de mot.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Complexité des algorithmes itératifs et récursifs
• Tri par fusion et tri rapide
• Bases de Python : expressions, types, instructions, fonctions

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.