On trouvera ici les 110 énoncés des épreuves écrites de l’option informatique (de 1997 à 2020) posées aux concours des écoles scientifiques (X, Ens, Mines, Centrale, Ccp/Inp) dans la filière MP.
Cliquez (ou simplement survolez) le titre d’un problème pour en lire une description.
Classement par école
Avertissement
Les énoncés sont la propriété de leurs auteurs respectifs. Le contenu proposé ici (une organisation centralisée et la description apportée à chaque sujet) est proposé aux souscripteurs pour les aider dans leurs révisions.
Concours commun INP (1997-2020)
CCINP, option informatique, 1997Partie 1 (logique) : voyageur perdu dans le désert.
Partie 2 (automates finis) : reconnaissance de l'ensemble des préfixes d'un langage.
Partie 3 (algorithmique) : énumération des parties, et problème du sac à dos. (pdf)
CCINP, option informatique, 1998Partie 1 (logique) : inspection dans un hôpital psychiatrique.
Partie 2 (algorithmique) : partition et union d'arbres binaires de recherche.
Partie 3 (automates finis) : le théorème de Nerode. (pdf)
CCINP, option informatique, 1999Partie 1 (logique) : détection de pannes de composants logiques.
Partie 2 (algorithmique) : algorithme de Prim de recouvrement minimal d'un ensemble de points.
Partie 3 (automates et langages) : produit de deux automates finis déterministes. (pdf)
CCINP, option informatique, 2000Partie 1 (logique) : énigmes archéo-logiques de la civilisation Atlante.
Partie 2 (algorithmique) : application de la structure de tas au tri de listes d'entiers.
Partie 3 (automates et langages) : composition de deux automates finis. déterministes. (pdf)
CCINP, option informatique, 2001Partie 1 (logique) : Socrate déjouant les énigmes de Cerbère.
Partie 2 (algorithmique) : calcul de l'enveloppe convexe, algorithme de Jarvis.
Partie 3 (automates et langages) : opération d'inversion d'un automate.
inversion d'un automate. (pdf)
CCINP, option informatique, 2002Partie 1 (logique) : Alice au pays des flacons empoisonnés.
Partie 2 (automates et langages) : propriétés de composition de deux automates finis.
Partie 3 (algorithmique) : codage minimal d'une suite de caractères par la méthode de Huffman (pdf)
CCINP, option informatique, 2003Partie 1 (logique) : déjouer la protection de la tombe des Pharaons.
Partie 2 (algorithmique et langages) : analyse lexicale par des automates semi-indéterministes. (pdf)
CCINP, option informatique, 2004Partie 1 (automates et langages) : opérations de dérivation d'un langage selon un mot.
Partie 2 (algorithmique) : stratégie complète et cohérente d'interrogation d'une base de connaissances. (pdf)
CCINP, option informatique, 2005Partie 1 (automates et langages) : entrelacement de mots, de langages, d'automates finis.
Partie 2 (algorithmique) : arbres binaires de recherche équilibrés AVL. (pdf)
CCINP, option informatique, 2006Partie 1 (automates et langages) : Composition d'automates finis complets déterministes.
Partie 2 (algorithmique) : représentation d'ensembles d'entiers naturels par des tas binomiaux. (pdf)
CCINP, option informatique, 2007Partie 1 (automates et langages) : propriétés de l'opération de déterminisation d'un automate.
Partie 2 (algorithmique) : calcul d'une enveloppe convexe à l'aide d'arbres binaires enveloppants. (pdf)
CCINP, option informatique, 2008Partie 1 (logique) : interrupteurs à fermer pour sortir d'un labyrinthe.
Partie 2 (automates et langages) : composition d'automates finis complets déterministes.
Partie 3 (algorithmique) : représentation d'ensembles d'entiers par des arbres bicolores. (pdf)
CCINP, option informatique, 2009Partie 1 (logique) : respecter le protocole vestimentaire d'une civilisation extra-terrestre.
Partie 2 (algorithmique) : gestion de la mémoire par blocs, utilisant des arbres binaires. (pdf)
CCINP, option informatique, 2010Partie 1 (logique) : réussir le test d'initiation d'une association estudiantine
Partie 2 (automates et langages) : étude de propriétés de la composition de deux automates.
Partie 3 (algorithmique) : complexité du tri fusion; représentations d'ensembles avec des intervalles. (pdf)
CCINP, option informatique, 2011Partie 1 (logique) : règles de politesse d'une nouvelle espèce
labyrinthe.
Partie 2 (automates et langages) : propriétés de l'opération d'inversion d'un automate.
Partie 3 (algorithmique) : tri par arbre binaire de recherche; représentation de systèmes creux. (pdf)
CCINP, option informatique, 2012Partie 1 (logique) : deviner qui est vérifique, menteur ou changeant.
Partie 2 (automates et langages) : propriétés de l'opération de composition de deux automates. Partie 3 Partie 3 (algorithmique) : séquence croissante d'entiers, arbres binaire de recherche d'entiers, B-arbres d'entiers (pdf)
CCINP, option informatique, 2013Partie 1 (logique) : déjouer les énigmes de deux Sphynx.
Partie 2 (automates et langages) : opérations de dérivation à gauche ou à droite d'un automate fini selon un mot.
Partie 3 (algorithmique) : le tri rapide; représentation de dictionnaire avec des arbres Patricia. (pdf)
CCINP, option informatique, 2014Partie 1 (logique) : association de jeunes détectives.
Partie 2 (automates et langages) : un homomorphisme de langage préserve la structure de langage régulier.
Partie 3 (algorithmique) : le tri sélection; représentation d'images par des arbres quaternaires. (pdf)
CCINP, option informatique, 2015Partie 1 (logique) : programme réussissant le test de Turing.
Partie 2 (automates et langages) : racine carrée d'un automate fini.
Partie 3 (algorithmique) : le tri à bulles; arbres binaires d'entiers et tri par tas. (pdf)
CCINP, option informatique, 2016Partie 1 (logique) : logique propositionnelle tri-valuée.
Partie 2 (algorithmique et programmation) : recherche d'un flot maximal dans un réseau de transport; algorithme de Ford et Fulkerson. (pdf)
CCINP, option informatique, 2017Partie 1 (logique) : étudie d'une peuplade par un ethnologue.
Partie 2 (algorithmique et programmation) : recherche dichotomique dans une séquence ordonnée.
Partie 3 (automates et langages) : produit synchronisé de deux automates sur un alphabet. (pdf)
CCINP, option informatique, 2018Partie 1 (logique) : jouez à Chercher les Clés du Paradis.
Partie 2 (automates) : automate minimal reconnaissant un langage régulier.
Partie 3 (algorithmique et programmation) : étude d'une méthode de compression de données. (pdf)
CCINP, option informatique, 2019Partie 1 : inversions de permutations.
Partie 2 (automates et langages) : racine carrée d'un langage.
Partie 3 (algorithmique et programmation): algorithmique des mots sans facteur carré. (pdf)
CCINP, option informatique, 2020Partie 1 : mintermes, maxtermes, connecteur de Sheffer.
Partie 2 (algorithmique et programmation) : le problème de Freudenthal (deviner deux entiers).
Partie 3 (langages): Mots de Lyndon et de de Bruijn. (pdf)
Partie 2 (automates finis) : reconnaissance de l'ensemble des préfixes d'un langage.
Partie 3 (algorithmique) : énumération des parties, et problème du sac à dos. (pdf)
CCINP, option informatique, 1998Partie 1 (logique) : inspection dans un hôpital psychiatrique.
Partie 2 (algorithmique) : partition et union d'arbres binaires de recherche.
Partie 3 (automates finis) : le théorème de Nerode. (pdf)
CCINP, option informatique, 1999Partie 1 (logique) : détection de pannes de composants logiques.
Partie 2 (algorithmique) : algorithme de Prim de recouvrement minimal d'un ensemble de points.
Partie 3 (automates et langages) : produit de deux automates finis déterministes. (pdf)
CCINP, option informatique, 2000Partie 1 (logique) : énigmes archéo-logiques de la civilisation Atlante.
Partie 2 (algorithmique) : application de la structure de tas au tri de listes d'entiers.
Partie 3 (automates et langages) : composition de deux automates finis. déterministes. (pdf)
CCINP, option informatique, 2001Partie 1 (logique) : Socrate déjouant les énigmes de Cerbère.
Partie 2 (algorithmique) : calcul de l'enveloppe convexe, algorithme de Jarvis.
Partie 3 (automates et langages) : opération d'inversion d'un automate.
inversion d'un automate. (pdf)
CCINP, option informatique, 2002Partie 1 (logique) : Alice au pays des flacons empoisonnés.
Partie 2 (automates et langages) : propriétés de composition de deux automates finis.
Partie 3 (algorithmique) : codage minimal d'une suite de caractères par la méthode de Huffman (pdf)
CCINP, option informatique, 2003Partie 1 (logique) : déjouer la protection de la tombe des Pharaons.
Partie 2 (algorithmique et langages) : analyse lexicale par des automates semi-indéterministes. (pdf)
CCINP, option informatique, 2004Partie 1 (automates et langages) : opérations de dérivation d'un langage selon un mot.
Partie 2 (algorithmique) : stratégie complète et cohérente d'interrogation d'une base de connaissances. (pdf)
CCINP, option informatique, 2005Partie 1 (automates et langages) : entrelacement de mots, de langages, d'automates finis.
Partie 2 (algorithmique) : arbres binaires de recherche équilibrés AVL. (pdf)
CCINP, option informatique, 2006Partie 1 (automates et langages) : Composition d'automates finis complets déterministes.
Partie 2 (algorithmique) : représentation d'ensembles d'entiers naturels par des tas binomiaux. (pdf)
CCINP, option informatique, 2007Partie 1 (automates et langages) : propriétés de l'opération de déterminisation d'un automate.
Partie 2 (algorithmique) : calcul d'une enveloppe convexe à l'aide d'arbres binaires enveloppants. (pdf)
CCINP, option informatique, 2008Partie 1 (logique) : interrupteurs à fermer pour sortir d'un labyrinthe.
Partie 2 (automates et langages) : composition d'automates finis complets déterministes.
Partie 3 (algorithmique) : représentation d'ensembles d'entiers par des arbres bicolores. (pdf)
CCINP, option informatique, 2009Partie 1 (logique) : respecter le protocole vestimentaire d'une civilisation extra-terrestre.
Partie 2 (algorithmique) : gestion de la mémoire par blocs, utilisant des arbres binaires. (pdf)
CCINP, option informatique, 2010Partie 1 (logique) : réussir le test d'initiation d'une association estudiantine
Partie 2 (automates et langages) : étude de propriétés de la composition de deux automates.
Partie 3 (algorithmique) : complexité du tri fusion; représentations d'ensembles avec des intervalles. (pdf)
CCINP, option informatique, 2011Partie 1 (logique) : règles de politesse d'une nouvelle espèce
labyrinthe.
Partie 2 (automates et langages) : propriétés de l'opération d'inversion d'un automate.
Partie 3 (algorithmique) : tri par arbre binaire de recherche; représentation de systèmes creux. (pdf)
CCINP, option informatique, 2012Partie 1 (logique) : deviner qui est vérifique, menteur ou changeant.
Partie 2 (automates et langages) : propriétés de l'opération de composition de deux automates. Partie 3 Partie 3 (algorithmique) : séquence croissante d'entiers, arbres binaire de recherche d'entiers, B-arbres d'entiers (pdf)
CCINP, option informatique, 2013Partie 1 (logique) : déjouer les énigmes de deux Sphynx.
Partie 2 (automates et langages) : opérations de dérivation à gauche ou à droite d'un automate fini selon un mot.
Partie 3 (algorithmique) : le tri rapide; représentation de dictionnaire avec des arbres Patricia. (pdf)
CCINP, option informatique, 2014Partie 1 (logique) : association de jeunes détectives.
Partie 2 (automates et langages) : un homomorphisme de langage préserve la structure de langage régulier.
Partie 3 (algorithmique) : le tri sélection; représentation d'images par des arbres quaternaires. (pdf)
CCINP, option informatique, 2015Partie 1 (logique) : programme réussissant le test de Turing.
Partie 2 (automates et langages) : racine carrée d'un automate fini.
Partie 3 (algorithmique) : le tri à bulles; arbres binaires d'entiers et tri par tas. (pdf)
CCINP, option informatique, 2016Partie 1 (logique) : logique propositionnelle tri-valuée.
Partie 2 (algorithmique et programmation) : recherche d'un flot maximal dans un réseau de transport; algorithme de Ford et Fulkerson. (pdf)
CCINP, option informatique, 2017Partie 1 (logique) : étudie d'une peuplade par un ethnologue.
Partie 2 (algorithmique et programmation) : recherche dichotomique dans une séquence ordonnée.
Partie 3 (automates et langages) : produit synchronisé de deux automates sur un alphabet. (pdf)
CCINP, option informatique, 2018Partie 1 (logique) : jouez à Chercher les Clés du Paradis.
Partie 2 (automates) : automate minimal reconnaissant un langage régulier.
Partie 3 (algorithmique et programmation) : étude d'une méthode de compression de données. (pdf)
CCINP, option informatique, 2019Partie 1 : inversions de permutations.
Partie 2 (automates et langages) : racine carrée d'un langage.
Partie 3 (algorithmique et programmation): algorithmique des mots sans facteur carré. (pdf)
CCINP, option informatique, 2020Partie 1 : mintermes, maxtermes, connecteur de Sheffer.
Partie 2 (algorithmique et programmation) : le problème de Freudenthal (deviner deux entiers).
Partie 3 (langages): Mots de Lyndon et de de Bruijn. (pdf)
Concours Centrale-Supélec (1997-2020)
Centrale, option informatique, 1997Problème 1 : recherche de sous-mot. Algorithme simplifié de Knuth-Morris-Pratt.
Problème 2 : recherche d'un mot dans un dictionnaire représenté par un k-arbre. (pdf)
Centrale, option informatique, 1998Partie 1 (algorithmique) : recherche de mot dans une table, avec différentes méthodes de hachage; résolution des collisions.
Partie 2 (automates finis) : automates finis déterministes reconnaissant des langages donnés.
Partie 3 (logique) : expressions booléennes, connecteur universel. (pdf)
Centrale, option informatique, 1999Exercice 1 (logique) : forme normale exclusive, satisfiabilité, formules de Horn.
Exercice 2 (algorithmique et programmation) : problème de l'allocation mémoire (pdf)
Centrale, option informatique, 2000Partie 1 (algorithmique) : opérations sur les arbres bicolores.
Partie 2 (automates finis) : satisfaction de formules de la logique temporelle par des automates finis. (pdf)
Centrale, option informatique, 2001Partie 1 (algorithmique) : algorithmes de sélection.
Partie 2 (logique) : portes universelles et portes réversibles universelles. (pdf)
Centrale, option informatique, 2002Comment rendre la monnaie en utilisant le plus petit nombre possible de pièces ? (pdf)
Centrale, option informatique, 2003Mots bien parenthésés. Fermeture d'une parenthèse. Parenthésage hétérogène, ou colorié. (pdf)
Centrale, option informatique, 2004Partie 1 (algorithmique) : Affectation préférentielle de candidats à des postes (mariages stables).
Partie 2 (logique) : connecteurs logiques, fonctions booléennes. (pdf)
Centrale, option informatique, 2005Partie 1: Polygones simple, intérieur, extérieur.
Partie 2 : protocole de communication avec aller-retour, ou à sens unique. (pdf)
Centrale, option informatique, 2006Partie 1 (algorithmique) : un algorithme de compression de données.
Partie 2 : problème logique (Thésée et le Minotaure) et automate. (pdf)
Centrale, option informatique, 2007Partie 1: autour de la suite de Fibonacci.
Partie 2 : un calcul de ppcm; arbres binaires; primalité. (pdf)
Centrale, option informatique, 2008Partie 1 : Mots de Lukasiewic (dénombrement, régularité, capsules).
Partie 2 : recherche de motif; algorithme naïf et algorithme de Rabin-Karp. (pdf)
Centrale, option informatique, 2009Partie 1 (algorithmique): stratégie de chasse aux fantômes.
Partie 2 (automates finis) : mots répétés, logique de Presburger, automate minimal. (pdf)
Centrale, option informatique, 2010Si un langage L est un langage polynomial, alors L* l'est aussi. (pdf)
Centrale, option informatique, 2011Partie 1 : identification de sous-mots répétés dans un mot.
Partie 2 (langages et automates): ensembles dénombrables, lemme d'Arden. (pdf)
Centrale, option informatique, 2012Tri rapide d'un tableau; étude de complexité; recherche d'une pseudo médiane; gain apporté par la pseudo médiane. (pdf)
Centrale, option informatique, 2013Arbres de décision; diagrammes de décision.
Circuits logiques (multiplexeurs).
Automates (combinaisons booléennes d'équations linéaires sur les entiers). (pdf)
Centrale, option informatique, 2014Codage du jeu de Sudoku par des formules booléennes; résolution d'une grille de sudoku. (pdf)
Centrale, option informatique, 2015Graphes d'intervalles; coloration; cliques; graphes munis d'un ordre d'élimination parfait; ordre d'élimination parfait pour un graphe cordal. (pdf)
Centrale, option informatique, 2016Algorithme sur des arbres (tri par insertion, tas binaires, décomposition parfaite d'un entier, création d'une liste de tas, tri des racines). Implantation d'un algorithme de tri dans un tableau. (pdf)
Centrale, option informatique, 2017Mots synchronisants (considérations générales, algorithmes classiques, réduction SAT, existence d'un mot synchronisant). (pdf)
Centrale, option informatique, 2018Étude du jeu Ricochet Robots (déplacements dans une grille, structure de file, tables de hachage dynamiques, résolution du jeu des robots). (pdf)
Centrale, option informatique, 2019Code binaire de Gray; énumération des combinaisons; application au problème du sac à dos. (pdf)
Centrale, option informatique, 2020Un système de vote. Graphe de préférence. Recherche du vainqueur. Satisfiabilité d’une formule de logique propositionnelle. (pdf)
Problème 2 : recherche d'un mot dans un dictionnaire représenté par un k-arbre. (pdf)
Centrale, option informatique, 1998Partie 1 (algorithmique) : recherche de mot dans une table, avec différentes méthodes de hachage; résolution des collisions.
Partie 2 (automates finis) : automates finis déterministes reconnaissant des langages donnés.
Partie 3 (logique) : expressions booléennes, connecteur universel. (pdf)
Centrale, option informatique, 1999Exercice 1 (logique) : forme normale exclusive, satisfiabilité, formules de Horn.
Exercice 2 (algorithmique et programmation) : problème de l'allocation mémoire (pdf)
Centrale, option informatique, 2000Partie 1 (algorithmique) : opérations sur les arbres bicolores.
Partie 2 (automates finis) : satisfaction de formules de la logique temporelle par des automates finis. (pdf)
Centrale, option informatique, 2001Partie 1 (algorithmique) : algorithmes de sélection.
Partie 2 (logique) : portes universelles et portes réversibles universelles. (pdf)
Centrale, option informatique, 2002Comment rendre la monnaie en utilisant le plus petit nombre possible de pièces ? (pdf)
Centrale, option informatique, 2003Mots bien parenthésés. Fermeture d'une parenthèse. Parenthésage hétérogène, ou colorié. (pdf)
Centrale, option informatique, 2004Partie 1 (algorithmique) : Affectation préférentielle de candidats à des postes (mariages stables).
Partie 2 (logique) : connecteurs logiques, fonctions booléennes. (pdf)
Centrale, option informatique, 2005Partie 1: Polygones simple, intérieur, extérieur.
Partie 2 : protocole de communication avec aller-retour, ou à sens unique. (pdf)
Centrale, option informatique, 2006Partie 1 (algorithmique) : un algorithme de compression de données.
Partie 2 : problème logique (Thésée et le Minotaure) et automate. (pdf)
Centrale, option informatique, 2007Partie 1: autour de la suite de Fibonacci.
Partie 2 : un calcul de ppcm; arbres binaires; primalité. (pdf)
Centrale, option informatique, 2008Partie 1 : Mots de Lukasiewic (dénombrement, régularité, capsules).
Partie 2 : recherche de motif; algorithme naïf et algorithme de Rabin-Karp. (pdf)
Centrale, option informatique, 2009Partie 1 (algorithmique): stratégie de chasse aux fantômes.
Partie 2 (automates finis) : mots répétés, logique de Presburger, automate minimal. (pdf)
Centrale, option informatique, 2010Si un langage L est un langage polynomial, alors L* l'est aussi. (pdf)
Centrale, option informatique, 2011Partie 1 : identification de sous-mots répétés dans un mot.
Partie 2 (langages et automates): ensembles dénombrables, lemme d'Arden. (pdf)
Centrale, option informatique, 2012Tri rapide d'un tableau; étude de complexité; recherche d'une pseudo médiane; gain apporté par la pseudo médiane. (pdf)
Centrale, option informatique, 2013Arbres de décision; diagrammes de décision.
Circuits logiques (multiplexeurs).
Automates (combinaisons booléennes d'équations linéaires sur les entiers). (pdf)
Centrale, option informatique, 2014Codage du jeu de Sudoku par des formules booléennes; résolution d'une grille de sudoku. (pdf)
Centrale, option informatique, 2015Graphes d'intervalles; coloration; cliques; graphes munis d'un ordre d'élimination parfait; ordre d'élimination parfait pour un graphe cordal. (pdf)
Centrale, option informatique, 2016Algorithme sur des arbres (tri par insertion, tas binaires, décomposition parfaite d'un entier, création d'une liste de tas, tri des racines). Implantation d'un algorithme de tri dans un tableau. (pdf)
Centrale, option informatique, 2017Mots synchronisants (considérations générales, algorithmes classiques, réduction SAT, existence d'un mot synchronisant). (pdf)
Centrale, option informatique, 2018Étude du jeu Ricochet Robots (déplacements dans une grille, structure de file, tables de hachage dynamiques, résolution du jeu des robots). (pdf)
Centrale, option informatique, 2019Code binaire de Gray; énumération des combinaisons; application au problème du sac à dos. (pdf)
Centrale, option informatique, 2020Un système de vote. Graphe de préférence. Recherche du vainqueur. Satisfiabilité d’une formule de logique propositionnelle. (pdf)
Concours commun Mines-Ponts (1997-2020)
Mines-Ponts, option informatique, 1997Exercice 1 (langages) : reconnaissance de langages par des automate.
Exercice 2 (logique) : connecteur universel de Sheffer.
Exercice 3 (algorithmique) : expansion de macro-définitions. (pdf)
Mines-Ponts, option informatique, 1998Exercice 1 (logique): conception d'un circuit afficheur de chiffres.
Exercice 2 (automates): l'ensemble des mots dont une puissance k-ième est dans un langage reconnaissable est lui-même reconnaissable.
Exercice 3 (algorithmique) : addition des grands entiers. (pdf)
Mines-Ponts, option informatique, 1999Exercice 1 (langages) : nombre de mots d'une longueur donnée; caractérisation des langages minces.
Exercice 2 (logique) : échange du contenu de deux variables informatiques.
Exercice 3 (algorithmique) : conception et analyse de complexité en temps d'un algorithme de tri pour un tableau contenant des entiers. (pdf)
Mines-Ponts, option informatique, 2000Exercice : déterminisation d'un automate fini; langage reconnu; expression rationnelle.
Problème : une méthode permettant d'identifier les tautologies. (pdf)
Mines-Ponts, option informatique, 2001Problème 1 (langages) : algorithme permettant d'émonder un automate fini
Problème 2 (algorithmique) : calcul efficace de la puissance n-ième.
Problème 3 (logique): constructions de comparateurs logiques. (pdf)
Mines-Ponts, option informatique, 2002Exercice 1 (logique) : satisfiabilité d'une formule de Horn.
Exercice 2 (algorithmique) : sac à dos fractionnaire, sac à dos en 0-1.
Exercice 3 (langages) : reconnaissance de l'ensemble des conjugués des mots d'un langage rationnel. (pdf)
Mines-Ponts, option informatique, 2003Exercice (logique) : logique tri-valuée de de Lukasiewicz.
Problème (algorithmique) : bon coloriage d'un graphe, nombre et polynôme chromatique. (pdf)
Mines-Ponts, option informatique, 2004Problème 1 (algorithmique) : le tri par baquets.
Problème 2 (automates) : longueur discriminante de deux automates. (pdf)
Mines-Ponts, option informatique, 2005Problème 1 (automates) : étude de plusieurs transformations de langage.
Problème 2 (algorithmique) : descendants d'un sommet d'un graphe orienté; un problème de satisfiabilité. (pdf)
Mines-Ponts, option informatique, 2006Problème 1 (logique) : circuits logiques concentrateurs.
Problème 2 (algorithmique) : algorithme de Huffman de compression de données. (pdf)
Mines-Ponts, option informatique, 2007Expressions rationnelles, langages locaux, algorithme de Glushkov. (pdf)
Mines-Ponts, option informatique, 2008Problème 1 (automates) : deux constructions d'un automate reconnaissant l'intersection de deux langages reconnaissables.
Problème 2 (algorithmique) : problème du voyageur de commerce dans un graphe symétrique valué. (pdf)
Mines-Ponts, option informatique, 2009Problème 1 (automates) : échange des lettres dans un mot.
Problème 2 (algorithmique) : nombre d'arbres enracinés, non ordonnés et étiquetés de
nombre de nœuds donné, codage de Prüfer. (pdf)
Mines-Ponts, option informatique, 2010Le problème de la satisfiabilité logique. (pdf)
Mines-Ponts, option informatique, 2011Exercice (langages): langages des palindromes
Problème (algorithmique) : ordres pour un tournoi, méthode de Copeland, valeur de Slater d'un classement, indice de Slater d'un tournoi, méthode de Slater. (pdf)
Mines-Ponts, option informatique, 2012Exercice (langages) : langages des mots contenant plusieurs occurences d'un même facteur.
Problème (algorithmique) : couplages dans un graphe biréparti équilibré, couplage maximal, algorithme hongrois. (pdf)
Mines-Ponts, option informatique, 2013Plusieurs algorithmes de recherche d'un mot, appelé motif, dans
un texte (algorithme simple, amélioration, implémentation d'un automate, utilisation d'automates, automate des suffixes). (pdf)
Mines-Ponts, option informatique, 2014Automates : reconnaissance d'exemples d'expressions rationnelles.
Logique : suites d'implications, matrices booléennes. (pdf)
Mines-Ponts, option informatique, 2015Arbres binaires étiquetés; langages d'arbres; automates d'arbres descendants déterministes; automates descendants et langages rationnels de mots. Automates d'arbres ascendants. (pdf)
Mines-Ponts, option informatique, 2016Problème 1 : graphe du Web; crawler simple; calcul de PageRank.
Problème 2 : automates probabilistes; langages stochastiques. (pdf)
Mines-Ponts, option informatique, 2017Problème 1 (automates): automates reconnaissant un langage unaire.
Problème (algorithmique) : exponentiation rapide. (pdf)
Mines-Ponts, option informatique, 2018Algorithmes de rechercher d'occurrences d'un motif dans une chaîne; Automate de Knuth-Morris-Pratt. (pdf)
Mines-Ponts, option informatique, 2019Relations qui existent entre des automates qui
reconnaissent un même langage, grâce à la notion de morphisme d'automates. (pdf)
Mines-Ponts, option informatique, 2020Fonction de distribution des lettres d’un texte (avec un tableau exhaustif et une liste, ou une table modulaire, ou un tableau creux). Codes et codages. Arbre de code optimal. (pdf)
Exercice 2 (logique) : connecteur universel de Sheffer.
Exercice 3 (algorithmique) : expansion de macro-définitions. (pdf)
Mines-Ponts, option informatique, 1998Exercice 1 (logique): conception d'un circuit afficheur de chiffres.
Exercice 2 (automates): l'ensemble des mots dont une puissance k-ième est dans un langage reconnaissable est lui-même reconnaissable.
Exercice 3 (algorithmique) : addition des grands entiers. (pdf)
Mines-Ponts, option informatique, 1999Exercice 1 (langages) : nombre de mots d'une longueur donnée; caractérisation des langages minces.
Exercice 2 (logique) : échange du contenu de deux variables informatiques.
Exercice 3 (algorithmique) : conception et analyse de complexité en temps d'un algorithme de tri pour un tableau contenant des entiers. (pdf)
Mines-Ponts, option informatique, 2000Exercice : déterminisation d'un automate fini; langage reconnu; expression rationnelle.
Problème : une méthode permettant d'identifier les tautologies. (pdf)
Mines-Ponts, option informatique, 2001Problème 1 (langages) : algorithme permettant d'émonder un automate fini
Problème 2 (algorithmique) : calcul efficace de la puissance n-ième.
Problème 3 (logique): constructions de comparateurs logiques. (pdf)
Mines-Ponts, option informatique, 2002Exercice 1 (logique) : satisfiabilité d'une formule de Horn.
Exercice 2 (algorithmique) : sac à dos fractionnaire, sac à dos en 0-1.
Exercice 3 (langages) : reconnaissance de l'ensemble des conjugués des mots d'un langage rationnel. (pdf)
Mines-Ponts, option informatique, 2003Exercice (logique) : logique tri-valuée de de Lukasiewicz.
Problème (algorithmique) : bon coloriage d'un graphe, nombre et polynôme chromatique. (pdf)
Mines-Ponts, option informatique, 2004Problème 1 (algorithmique) : le tri par baquets.
Problème 2 (automates) : longueur discriminante de deux automates. (pdf)
Mines-Ponts, option informatique, 2005Problème 1 (automates) : étude de plusieurs transformations de langage.
Problème 2 (algorithmique) : descendants d'un sommet d'un graphe orienté; un problème de satisfiabilité. (pdf)
Mines-Ponts, option informatique, 2006Problème 1 (logique) : circuits logiques concentrateurs.
Problème 2 (algorithmique) : algorithme de Huffman de compression de données. (pdf)
Mines-Ponts, option informatique, 2007Expressions rationnelles, langages locaux, algorithme de Glushkov. (pdf)
Mines-Ponts, option informatique, 2008Problème 1 (automates) : deux constructions d'un automate reconnaissant l'intersection de deux langages reconnaissables.
Problème 2 (algorithmique) : problème du voyageur de commerce dans un graphe symétrique valué. (pdf)
Mines-Ponts, option informatique, 2009Problème 1 (automates) : échange des lettres dans un mot.
Problème 2 (algorithmique) : nombre d'arbres enracinés, non ordonnés et étiquetés de
nombre de nœuds donné, codage de Prüfer. (pdf)
Mines-Ponts, option informatique, 2010Le problème de la satisfiabilité logique. (pdf)
Mines-Ponts, option informatique, 2011Exercice (langages): langages des palindromes
Problème (algorithmique) : ordres pour un tournoi, méthode de Copeland, valeur de Slater d'un classement, indice de Slater d'un tournoi, méthode de Slater. (pdf)
Mines-Ponts, option informatique, 2012Exercice (langages) : langages des mots contenant plusieurs occurences d'un même facteur.
Problème (algorithmique) : couplages dans un graphe biréparti équilibré, couplage maximal, algorithme hongrois. (pdf)
Mines-Ponts, option informatique, 2013Plusieurs algorithmes de recherche d'un mot, appelé motif, dans
un texte (algorithme simple, amélioration, implémentation d'un automate, utilisation d'automates, automate des suffixes). (pdf)
Mines-Ponts, option informatique, 2014Automates : reconnaissance d'exemples d'expressions rationnelles.
Logique : suites d'implications, matrices booléennes. (pdf)
Mines-Ponts, option informatique, 2015Arbres binaires étiquetés; langages d'arbres; automates d'arbres descendants déterministes; automates descendants et langages rationnels de mots. Automates d'arbres ascendants. (pdf)
Mines-Ponts, option informatique, 2016Problème 1 : graphe du Web; crawler simple; calcul de PageRank.
Problème 2 : automates probabilistes; langages stochastiques. (pdf)
Mines-Ponts, option informatique, 2017Problème 1 (automates): automates reconnaissant un langage unaire.
Problème (algorithmique) : exponentiation rapide. (pdf)
Mines-Ponts, option informatique, 2018Algorithmes de rechercher d'occurrences d'un motif dans une chaîne; Automate de Knuth-Morris-Pratt. (pdf)
Mines-Ponts, option informatique, 2019Relations qui existent entre des automates qui
reconnaissent un même langage, grâce à la notion de morphisme d'automates. (pdf)
Mines-Ponts, option informatique, 2020Fonction de distribution des lettres d’un texte (avec un tableau exhaustif et une liste, ou une table modulaire, ou un tableau creux). Codes et codages. Arbre de code optimal. (pdf)
Écoles Normales Supérieures (1997-2010)
ENS, option informatique, 1997Étude de structures permettant de représenter ou de caractériser des
formes arborescentes planes; matrice de ramification; épaisseur d'une forme arborescente; évaluation d'expressions par registres et application au dessin de la forme arborescente. (pdf)
ENS, option informatique, 1998Modélisation par réseaux de Petri; Systèmes d'addition de vecteurs et réseaux de Petri; automates à multiplicités; jeu de Tetris. (pdf)
ENS, option informatique, 1999Automate cellulaires de translation; surjectivité, périodicité, finitude; graphes de de Bruijn; automates cellulaires réversibles. (pdf)
ENS, option informatique, 2000Chemins et circuits dans un multi-graphe orienté fini; transducteurs; transducteurs séquentiels. (pdf)
ENS, option informatique, 2001Morphismes et L-systèmes; mots infinis engendrés par L-systèmes; hiérarchie; mots sans carré, mots sans cube. (pdf)
ENS, option informatique, 2002Décomposition complète d'un nombre dans une base
et suites de Goodstein; relations d'ordre sur les arbres ou sur les mots. (pdf)
ENS, option informatique, 2003Algorithme de Morris et Pratt pour le problème de la recherche de motifs; arbre des suffixes. (pdf)
ENS, option informatique, 2004Accessibilité dans les graphes ET/OU; automates alternants. (pdf)
ENS, option informatique, 2005Tri par paquets et ordre lexicographique; cycles de De Bruijn; Colliers, primaires et cycles. (pdf)
ENS, option informatique, 2006Ordre topologique sur un graphe orienté; applications; fonctions booléennes et circuits booléens; bornes supérieures et bornes inférieures sur un graphe orienté. (pdf)
ENS, option informatique, 2007Chemins optimaux dans un graphe fini et orienté; stratégies dans un jeu à information parfaite, joué par deux joueurs antagonistes. (pdf)
ENS, option informatique, 2008Arbres couvrants et cycles fondamentaux dans un graphe connexe; bases minimales de l'espace des cycles. (pdf)
ENS, option informatique, 2009Rotation de mots et minimalité; repliages de mots. (pdf)
ENS, option informatique, 2010Systèmes d'addition de vecteurs; Atteignabilité d'un état acceptant. (pdf)
formes arborescentes planes; matrice de ramification; épaisseur d'une forme arborescente; évaluation d'expressions par registres et application au dessin de la forme arborescente. (pdf)
ENS, option informatique, 1998Modélisation par réseaux de Petri; Systèmes d'addition de vecteurs et réseaux de Petri; automates à multiplicités; jeu de Tetris. (pdf)
ENS, option informatique, 1999Automate cellulaires de translation; surjectivité, périodicité, finitude; graphes de de Bruijn; automates cellulaires réversibles. (pdf)
ENS, option informatique, 2000Chemins et circuits dans un multi-graphe orienté fini; transducteurs; transducteurs séquentiels. (pdf)
ENS, option informatique, 2001Morphismes et L-systèmes; mots infinis engendrés par L-systèmes; hiérarchie; mots sans carré, mots sans cube. (pdf)
ENS, option informatique, 2002Décomposition complète d'un nombre dans une base
et suites de Goodstein; relations d'ordre sur les arbres ou sur les mots. (pdf)
ENS, option informatique, 2003Algorithme de Morris et Pratt pour le problème de la recherche de motifs; arbre des suffixes. (pdf)
ENS, option informatique, 2004Accessibilité dans les graphes ET/OU; automates alternants. (pdf)
ENS, option informatique, 2005Tri par paquets et ordre lexicographique; cycles de De Bruijn; Colliers, primaires et cycles. (pdf)
ENS, option informatique, 2006Ordre topologique sur un graphe orienté; applications; fonctions booléennes et circuits booléens; bornes supérieures et bornes inférieures sur un graphe orienté. (pdf)
ENS, option informatique, 2007Chemins optimaux dans un graphe fini et orienté; stratégies dans un jeu à information parfaite, joué par deux joueurs antagonistes. (pdf)
ENS, option informatique, 2008Arbres couvrants et cycles fondamentaux dans un graphe connexe; bases minimales de l'espace des cycles. (pdf)
ENS, option informatique, 2009Rotation de mots et minimalité; repliages de mots. (pdf)
ENS, option informatique, 2010Systèmes d'addition de vecteurs; Atteignabilité d'un état acceptant. (pdf)
École Polytechnique (1997-2010)
Polytechnique, option info, 1997Simulation du problème des N corps dans un univers plan; construction d'un quadtree; calcul des forces.
(pdf)
Polytechnique, option info, 1998Motifs et automates en ligne; reconnaissance de motifs. (pdf)
Polytechnique, option info, 1999Fonctions booléennes; arbres de décision; programmation des arbres de décision. (pdf)
Polytechnique, option info, 2000Système commandé par un tableau de bord comportant N interrupteurs; énumération de parties d'un ensemble par incrément ou par code de Gray; système défaillant. (pdf)
Polytechnique, option info, 2001Flots sur des arbres binaires; vérification de la compatibilité des flots; triangulation des polygones; problème des quatre couleurs. (pdf)
Polytechnique, option info, 2002Décompositions de sommes d'argent dans un système monétaire; payer le compte exact et optimal; étude des systèmes monétaires. (pdf)
Polytechnique, option info, 2003Arbres binaires complets; arbres gauches, lourds, légers. Recherche du plus proche ancêtre commun. (pdf)
Polytechnique, option info, 2004Problème 1 : valeur médiane d'un ensemble de nombres.
Problème 2: localisation dans un polygone convexe. (pdf)
Polytechnique, option info, 2005Formes normales disjonctives; circuit PLA (Programmable Logic Array); génération de circuits combinatoires. (pdf)
Polytechnique, option info, 2006Mots, dictionnaires; dictionnaire binaire; comparaison des coûts, conversion de représentations. Mot le plus long, anagrammes. (pdf)
Polytechnique, option info, 2007Codes de correction d'erreurs de Reed-Solomon. Opérations sur les polynômes. Multiplication et division rapide. Codage de Reed Solomon par une stratégie de type diviser pour régner. (pdf)
Polytechnique, option info, 2008Préliminaires sur les mots; opérations sur les cordes vues comme arbres binaires de mots; équilibrage, équilibrage optimal. (pdf)
Polytechnique, option info, 2009Opérations sur les grands entiers; nombres dyadiques; listes à deux bouts; polynômes de Bernstein ; un polynôme est-il positif ? (pdf)
Polytechnique, option info, 2010Recherche du plus proche ancêtre commun dans un arbre binaire; opérations sur les bits des entiers primitifs; cas particulier d’un arbre binaire complet; minimum d'un ensemble de valeurs. (pdf)
Polytechnique, option info, 1998Motifs et automates en ligne; reconnaissance de motifs. (pdf)
Polytechnique, option info, 1999Fonctions booléennes; arbres de décision; programmation des arbres de décision. (pdf)
Polytechnique, option info, 2000Système commandé par un tableau de bord comportant N interrupteurs; énumération de parties d'un ensemble par incrément ou par code de Gray; système défaillant. (pdf)
Polytechnique, option info, 2001Flots sur des arbres binaires; vérification de la compatibilité des flots; triangulation des polygones; problème des quatre couleurs. (pdf)
Polytechnique, option info, 2002Décompositions de sommes d'argent dans un système monétaire; payer le compte exact et optimal; étude des systèmes monétaires. (pdf)
Polytechnique, option info, 2003Arbres binaires complets; arbres gauches, lourds, légers. Recherche du plus proche ancêtre commun. (pdf)
Polytechnique, option info, 2004Problème 1 : valeur médiane d'un ensemble de nombres.
Problème 2: localisation dans un polygone convexe. (pdf)
Polytechnique, option info, 2005Formes normales disjonctives; circuit PLA (Programmable Logic Array); génération de circuits combinatoires. (pdf)
Polytechnique, option info, 2006Mots, dictionnaires; dictionnaire binaire; comparaison des coûts, conversion de représentations. Mot le plus long, anagrammes. (pdf)
Polytechnique, option info, 2007Codes de correction d'erreurs de Reed-Solomon. Opérations sur les polynômes. Multiplication et division rapide. Codage de Reed Solomon par une stratégie de type diviser pour régner. (pdf)
Polytechnique, option info, 2008Préliminaires sur les mots; opérations sur les cordes vues comme arbres binaires de mots; équilibrage, équilibrage optimal. (pdf)
Polytechnique, option info, 2009Opérations sur les grands entiers; nombres dyadiques; listes à deux bouts; polynômes de Bernstein ; un polynôme est-il positif ? (pdf)
Polytechnique, option info, 2010Recherche du plus proche ancêtre commun dans un arbre binaire; opérations sur les bits des entiers primitifs; cas particulier d’un arbre binaire complet; minimum d'un ensemble de valeurs. (pdf)
Épreuve commune X-Ens (2011-2020)
X-ENS, option informatique, 2011Arbres binomiaux; fonctions élémentaires sur les arbres; diffusion dans les arbres; échange total dans les arbres.
(pdf)
X-ENS, option informatique, 2012Fonctions élémentaires sur les arbres combinatoires; principe de mémorisation; application au dénombrement; tables de hachage; construction des arbres combinatoires. (pdf)
X-ENS, option informatique, 2013Formules logiques temporelles; normalisation de formules logiques; rationalité des langages décrits par des formules; satisfiabilité et expressivité. (pdf)
X-ENS, option informatique, 2014Structure d’arbre croissant; opérations; analyse de la fusion; application à une méthode de tri. (pdf)
X-ENS, option informatique, 2015Ordonnancement de graphes de tâches; graphe de tâches acyclique; ordonnancement par hauteur; ordonnancement par profondeur (algorithme de Hu). (pdf)
X-ENS, option informatique, 2016Satisfiabilité des formules booléennes; résolution de 1-SAT, et de 2-SAT; résolution de k-SAT pour k arbitraire; de k-SAT à SAT. (pdf)
X-ENS, option informatique, 2017Jeux à un joueur et solutions optimales; parcours en largeur, en profondeur; parcours en profondeur avec horizon. Application au jeu du taquin. (pdf)
X-ENS, option informatique, 2018Nombre chromatique; coloriage, 2-coloriage. Algorithmes gloutons. Algorithme de Wigderson. (pdf)
X-ENS, option informatique, 2019Autour des sous-mots et des sur-mots (pdf)
X-ENS, option informatique, 2020Constructions et explorations de labyrinthes. Graphes. Construction d'un labyrinthe par mélange de Knuth. Algorithme d'Eller. Résolution d'un labyrinthe. (pdf)
X-ENS, option informatique, 2012Fonctions élémentaires sur les arbres combinatoires; principe de mémorisation; application au dénombrement; tables de hachage; construction des arbres combinatoires. (pdf)
X-ENS, option informatique, 2013Formules logiques temporelles; normalisation de formules logiques; rationalité des langages décrits par des formules; satisfiabilité et expressivité. (pdf)
X-ENS, option informatique, 2014Structure d’arbre croissant; opérations; analyse de la fusion; application à une méthode de tri. (pdf)
X-ENS, option informatique, 2015Ordonnancement de graphes de tâches; graphe de tâches acyclique; ordonnancement par hauteur; ordonnancement par profondeur (algorithme de Hu). (pdf)
X-ENS, option informatique, 2016Satisfiabilité des formules booléennes; résolution de 1-SAT, et de 2-SAT; résolution de k-SAT pour k arbitraire; de k-SAT à SAT. (pdf)
X-ENS, option informatique, 2017Jeux à un joueur et solutions optimales; parcours en largeur, en profondeur; parcours en profondeur avec horizon. Application au jeu du taquin. (pdf)
X-ENS, option informatique, 2018Nombre chromatique; coloriage, 2-coloriage. Algorithmes gloutons. Algorithme de Wigderson. (pdf)
X-ENS, option informatique, 2019Autour des sous-mots et des sur-mots (pdf)
X-ENS, option informatique, 2020Constructions et explorations de labyrinthes. Graphes. Construction d'un labyrinthe par mélange de Knuth. Algorithme d'Eller. Résolution d'un labyrinthe. (pdf)