Chaque année, le jury décide de rendre publics certains textes. Vous trouverez plus bas La liste de ces textes. Bien entendus, ces textes ne seront plus utilisés lors des prochaines sessions du concours.
Tous ces textes sont au format PDF. Ce document précise les particularités de l'épreuve de modélisation
lien | RÉSUMÉ | |
2005-A1 | Chaque mois, le gérant d’un magasin doit contrôler le niveau du stock d’un produit donné, vendu à l’unité. Au vu du niveau restant du mois précédent, il doit décider de commander ou non un certain nombre d’unités. L’objectif est d’optimiser la stratégie de commande, connaissant la loi de probabilité de la demande mensuelle, les prix d’achat et de vente, ainsi que le coût de stockage des objets. Thème applicatif, mots clefs : Modèles en économie. Chaînes de Markov, optimisation. | |
2008-A1 | La monnaie en euros est frappée par chacun des états européens qui ont choisi d’abandonner leur monnaie nationale, et le côté face permet de déterminer l’origine d’une pièce. Peu à peu, les pièces franchissent les frontières et se mélangent. On construit un modèle élémentaire, markovien, de ce processus d’échange. On cherche à déterminer le temps qu’il faut au système pour parvenir à “l’équilibre statistique”. Mots clefs : Chaîne de Markov, mesure invariante. | |
2008-A2 | Une population bisexuée se reproduit selon un mécanisme qui généralise les processus de Galton–Watson classiques. Sous l’hypothèse que la loi de reproduction inter-générationnelle possède une propriété de sur-additivité, on établit que l’extinction de la population est quasi-certaine selon qu’une quantité intrinsèque au modèle, interprétée comme le taux moyen de croissance espéré, n’excède pas ou dépasse la valeur critique 1. Cette propriété est établie dans le cadre du modèle de Daley. Elle est illustrée par d’autres modèles sur-additifs. Mots clefs : Processus de branchement, chaîne de Markov, loi des grands nombres, martingale, fonction analytique. | |
2008-A3 | En classification supervisée, un label est associé à une observation. Ce label, obtenu par exemple à l’aide d’un avis d’expert, est censé représenter la nature de l’observation. En récoltant plusieurs observations, on peut ainsi réunir un échantillon de données -appelé échantillon d’apprentissage- constitué des observations et de leurs labels. Le but de l’apprentissage en classification supervisée est alors de construire une méthode (ou règle) de classification automatique pour une nouvelle observation, celle-ci se passant d’une nouvelle consultation d’un expert. Le texte est consacré à la modélisation de ce type de problématique et à la construction de 2 règles de classification. Mots clefs : Échantillon, espérance conditionnelle, convergence. | |
2009-A1 | On s’intéresse à un modèle de génétique des populations, ce qui nous conduit à l’étude d’une chaîne de Markov. Lorsque le nombre n de gènes considérés est très important, certains calculs sont facilités par des passages à la limite lorsque n tend vers l’infini. On obtient ainsi des équations différentielles dont les solutions sont les limites, lorsque n tend vers l’infini, de certaines caractéristiques de la chaîne probabilités d’absorption, mesure invariante. Mots clefs : Chaîne de Markov, état absorbant, équation différentielle. | |
2009-A2 | On étudie un modèle de battage de cartes. On cherche en particulier à déterminer le plus précisément possible le nombres de battages nécessaires pour obtenir un mélange satisfaisant du paquet. Mots clefs : Chaîne de Markov, convergence vers une loi stationnaire, groupe symétrique. | |
2009-A3 | Ce texte présente un modèle de répartition de composés chimiques avec forte répulsion et un algorithme qui permet de simuler une répartition typique de ces composés. La méthode est basée sur la simulation d’une chaîne de Markov auxilaire et sur une méthode de couplage. Mots clefs : Simulation de variables aléatoires, chaîne de Markov, probabilité invariante. | |
2015-A1 | On analyse un problème issu de l’informatique consistant à répartir de manière équitable un grand nombre de tâches entre deux processeurs parallèles. Mathématiquement, il s’agit de répartir une suite de variables aléatoires X 1 , . . . , X N indépendantes et uniformément distribuées en deux sous-ensembles disjoints de telle manière que les sommes de ces variables calculées sur les deux sous ensembles soient les plus proches possible. Mots clefs : Convergence en loi, théorème de la limite centrale, fonction caractéristique. | |
2015-A2 | Nous abordons certaines questions relatives à l’inférence statistique de données issues de modèles de survie, lorsque ces données sont censurées, c’est à-dire partiellement observées. Mots clefs : Loi exponentielle, loi du Chi-deux, simulation de variables aléatoires, intervalle de confiance, test. | |
2015-A3 | On étudie comment, dans un espace métrique initialement grand, les distances peuvent être fortement diminuées si on ajoute quelques “raccourcis” aléatoires. Cela peut modéliser diverses situations concrètes (réseaux sociaux, internet, propagation d’épidémies etc.). Mots clefs : distance, loi binomiale, inégalité de Markov | |
2015-A4 | On présente un modèle unimensionnel de déposition de particules, que l’on assimile à une chute de neige, pour lequel on recherche le comportement asymptotique de la hauteur. Mots clefs : Lois des grands nombres, loi de Poisson, loi géométrique. | |
2015-A5 | En informatique, il est courant de manipuler des listes de nombres. Leur classement en ordre croissant, la recherche du k-ième élément (le plus petit, avec k ∈ N∗ ) figurent parmi les procédures les plus usuelles. Nous allons présenter dans ce texte des algorithmes aléatoires permettant d’effectuer ces opérations, puis nous aborderons l’étude de leurs performances. Mots clefs : Algorithme aléatoire, bornes de Tchebychev, martingale à temps discret. | |
2015-A6 | L’objet de ce texte est de présenter une méthode non paramétrique pour estimer un signal entaché d’erreurs dans le cadre d’un modèle de régression avec dispositif expérimental régulier. Un exemple en vibrométrie laser est donné. Mots clefs : Régression, estimation, projection. | |
2015-A7 | On étudie plusieurs modèles du déplacement des fourmis. On tente en particulier de comprendre comment l’algorithme aléatoire qu’elles utilisent les amène à choisir un chemin parmi tous ceux leurs sont offerts et à s’y tenir. Mots clefs : Marches au hasard, martingales. | |
2015-A8 | On présente quatre algorithmes de génération de permutations aléatoires. Les trois premiers construisent des permutations quelconques et le quatrième produit des permutations à cycles de longueur paire. L’analyse de ces algorithmes permet d’étudier les lois de certaines quantités liées à ces permutations : rangs relatifs, nombres de points fixes, nombres de cycles, longueurs de ces cycles. Mots clefs : Cycle, permutation, loi de Poisson, fonction caractéristique, fonction génératrice, convergence en loi | |
2015-A9 | Ce texte présente une modélisation d’un paysage politique au moyen de partitions aléatoires. On considère un pays imaginaire constitué d’un grand nombre de citoyens, que l’on suppose infini. Ces citoyens se regroupent progressivement en partis politiques avec un mécanisme aléatoire tenant compte de l’ambition. Le paysage politique correspond à la répartition des citoyens en partis politiques. Le texte a pour but la modélisation et l’étude probabiliste de l’évolution de ce paysage et de son comportement asymptotique, ainsi que l’estimation statistique d’un paramètre lié à l’ambition. Mots clefs : Partition aléatoire, loi de Bernoulli, estimateur, chaîne de Markov. | |
2018-A1 | Le gérant d’un casino s’intéresse à l’évolution de son capital en fonction du temps. Il souhaite en particulier étudier la probabilité qu’il puisse un jour être ruiné. Mots clefs : Loi de Poisson, lois exponentielles, marches aléatoires, conditionnement, théorèmes asymptotiques. | |
2018-A2 | Nous nous intéressons au comportement de la vitesse de propagation d'un polluant dans un écoulement d'eau en sous-sol rocheux stratifié. On considère un modèle plan qui est constitué de strates horizontales homogènes. Un modèle stochastique est proposé pour deux mécanismes qui définissent l'évolution du polluant : les collisions avec les particules du fluide d'une part, le transport passif dû à l'écoulement d'autre part. Mots clefs : Marche aléatoire, théorèmes limites, variables non indépendantes. | |
2018-A3 | Étant donné un ensemble aléatoire de points dans l'espace, on cherche une méthode pour estimer l'agrégation de ces points ou au contraire leur dispersion. Mots clefs : Loi uniforme, loi binomiale, loi de Poisson, estimation, tests. | fichier de données |
lien | RÉSUMÉ |
2005-B1 | On considère une corde formé de ressorts enchaînés les uns aux autres. Thème applicatif, mots clefs : propagation d’ondes |
2006-B1 | On montre sur un exemple simple, comment on peut, sous certaines conditions, tuer une onde se propageant dans un domaine Ω, en agissant sur une partie Γ0 du bord du domaine Ω. Mots Clefs: Equation des ondes, Séries de Fourier. |
2006-B2 | On se propose ici de modéliser le trafic routier en identifiant chaque véhicule à un point, dont la vitesse dépend de sa distance au véhicule qui le précède. Cette approche conduit à un système d’équations différentielles. Mots clefs : Problème de Cauchy, méthodes à un pas. |
2008-B? | On s'intéresse à des questions de valeurs propres qui interviennent de façon cruciale dans le fonctionnement des moteurs de recherche sur Internet. Mots clefs : valeurs propres et vecteurs propres de matrice, systèmes linéaires. |
2008-B? | On s'intéresse à la modélisation et au calcul numérique du pouls sanguin. Mots clefs : équations aux dérivées partielles, méthode des différences finies. |
2008-B? | On présente un modèle de transport-diffusion-réaction d'anticorps dans une tumeur. Mots clefs : équations aux dérivées partielles, différences finis, stabilité. |
2009-B? | On étudie les phénomènes électriques accompagnant le battement cardiaque, ou plus précisément, le comportement électrique d'une cellule cardiaque, en essayant de mettre en évidence des propriétés mathématiques significatives. Mots clefs : comportement qualitatif des équations différentielles, méthodes numériques pour la solution des équations différentielles. |
2009-B? | On présente un modèle simplifié décrivant la propagation de l'influx nerveux dans un neurone. Mots clefs : équations différentielles, espace de phases, étude qualitative, équations aux dérivées partielles, différences finies. |
2009-B? | Dans ce texte, on cherche à déterminer la configuration géométrique de N atomes formant une molécule d'énergie minimale. Mots clefs : optimisation, algorithme de gradient. |
2010-B1 | On s’intéresse à des propriétés de fonctions propres pour approcher la solution d’une équation des ondes et au lien entre valeurs propres du Laplacien et caractéristiques géométriques d’un domaine Mots clefs : Mécanique, équation des ondes, différences finies, recherche de valeurs propres |
2010-B2 | Issu de considérations statistiques, le krigeage est une technique d’interpolation qui permet de retrouver d’autres méthodes classiques comme les splines Mots clefs : Interpolation, approximation, moindres carrés |
2011-B1 | Ce texte présente l’étude d’un modèle du phénomène d’agglomération des globules rouges. En introduisant une force qui dépend de la distance entre deux globules voisins, on aboutit à un système d’équations différentielles du second ordre, que doivent satisfaire les positions des centres des globules Mots clefs : Systèmes différentiels, aspects numériques du problème de Cauchy, points fixes. |
2011-B2 | On s’intéresse à un modèle simplifié qui exhibe les difficultés essentielles posées par les équations de la dynamique des gaz. Thème applicatif, mots clefs : Mécanique des fluides. Equations aux dérivées partielles. Equation de transport. Différences finies |
2012-B1 | On cherche ici à déterminer numériquement la composition chimique d’un mélange de gaz à pression et température données. Mots clefs : Optimisation, multiplicateurs de Lagrange, méthode de Newton, convexité. |
2012-B2 | On étudie des systèmes d’équations différentielles ordinaires du premier ordre issus de la mécanique ayant une structure bien précise. On s’intéresse en particulier au comportement qualitatif des méthodes numériques pour ces systèmes. Mots clefs : Mécanique. Equations différentielles ordinaires. Aspects numériques du problème de Cauchy. |
2013-B1 | On s’intéresse au comportement asymptotique d’une famille de solutions d’équations différentielles dont les coefficients oscillent rapidement. Mots clefs : Equations aux dérivées partielles. Problème aux limites. Analyse asymptotique. |
2013-B2 | On étudie le modèle de Leontieff, qui permet de caractériser les situations d’équilibre dans des secteurs de l’économie d’un pays. Mots clefs : Valeurs propres, vecteurs propres. Résolution de systèmes linéaires. |
2014-B1 | On présente un exemple de système de deux espèces en compétition dans un environnement périodique. On montre que le comportement qualitatif des solutions est très différent de celui obtenu dans un environnement modélisé par des coefficients constants, moyennés. En particulier on détermine des solutions périodiques : les oscillations du système peuvent permettre la coexistence des deux espèces dans un régime oscillatoire même si le système moyenné correspondant aurait forcé une des deux espèces à l’extinction. Mots clefs : Comportement qualitatif des équations différentielles. Méthodes numériques d’approximation des équations différentielles. |
2014-B2 | On s’intéresse à la modélisation et au calcul numérique de l’évolution d’un réacteur biologique. Mots clefs : Équations différentielles non linéaires. Aspects numériques du problème de Cauchy. Étude qualitative des solutions. |
2014-B3 | On s’intéresse à des modèles linéaires et non-linéaires de dynamique des populations, à travers une optique de structuration par tranches d’âge. Mots clefs : Algèbre linéaire. Éléments propres de matrices. Systèmes dynamiques discrets. |
2014-B4 | On considère une application contractante dans « l’espace des images », qui permet de construire des ensembles fractals et de faire de l’interpolation. Mots clefs : Fonctions itérées. Points fixes. Interpolation. |
2014-B5 | On étudie le modèle de Leontieff, qui permet de caractériser les situations d’équilibre dans des secteurs de l’économie d’un pays. Mots clefs : Valeurs propres, vecteurs propres. Résolution de systèmes linéaires. |
2015-B1 | On se propose ici de formaliser et de déterminer numériquement dans quelques exemples la composition chimique d’un mélange de gaz à pression et température données. Mots clefs : Systèmes non-linéaires. Optimisation sous contraintes. Méthode de Newton. |
2015-B2 | On s’intéresse à certains modèles et algorithmes utilisés par les moteurs de recherche sur internet pour évaluer la pertinence des résultats d’une recherche et permettre ainsi d’afficher les résultats par ordre d’importance. Les méthodes employées sont issues de l’algèbre linéaire et peuvent présenter des interprétations en terme de théorie des graphes. Mots clefs : Algèbre linéaire. Éléments propres de matrices. |
2015-B3 | L’objectif de ce texte est de calculer la position optimale d’une charge suspendue à une corde afin de minimiser les risques de rupture de ses points d’attache. Le modèle de base est constitué d’une équation aux dérivées partielles linéaire en dimension 1 dont le terme source dépend d’un paramètre. On cherche alors à trouver la valeur optimale de ce paramètre à travers une méthode de gradient. Mots clefs : Équations aux dérivées partielles. Problème aux limites. Optimisation. Méthodes de gradient. Différences finies. |
2015-B4 | On s’intéresse à la possibilité de rendre instable un équilibre stable d’un pendule oscillant en variant la longueur de ce dernier. Mots clefs : Équations différentielles ordinaires. Propriétés qualitatives des solutions. Dépendance par rapport aux paramètres. |
2016-B1 | On s’intéresse à l’utilisation de méthodes d’analyse numérique matricielle dans le cadre de la gestion de bases de données bibliographiques. Mots clefs : Algèbre linéaire. Éléments propres de matrices. Moindres carrés. |
2016-B2 | On s’intéresse à un modèle de combustion ; on met en place une stratégie de résolution numérique adaptée afin de décrire l’évolution du front consumé. Mots clefs : Équations aux dérivées partielles. Problème d’évolution. Différences finies. |
2016-B3 | On s’intéresse à un modèle mathématique de l’évolution de l’encéphalopathie spongiforme. On décrit notamment comment le comportement asymptotique des solutions correspond soit à un état sain, soit à un état infecté. Mots clefs : Équations différentielles. Équations aux dérivées partielles. Comportement asymptotique des solutions. |
2016-B4 | On s’intéresse à un modèle mathématique de dépollution de lac. Le principe consiste à pomper de l’eau polluée, à la nettoyer dans un bioréacteur et à la réinjecter dans le lac, tout cela en circuit fermé. Le modèle sous-jacent repose sur des équations différentielles, puis sur une optimisation de paramètre qui permet de rendre le processus industriel le plus performant possible. Mots clefs : Équations différentielles. Propriétés qualitatives. Schémas numériques. |
2017-B1 | Dans ce texte, nous introduisons un modèle simple d’optimisation de réseaux d’antennes. Ce modèle fait apparaître naturellement des matrices ayant une structure particulière pour lesquelles différents algorithmes plus efficaces que les méthodes usuelles peuvent être utilisés. Mots clefs : Algèbre linéaire. Méthodes itératives. Transformée de Fourier discrète. |
2017-B2 | On s’intéresse à un modèle d’écoulement en milieux poreux. Mots clefs : Équations aux dérivées partielles. Différences finies. Systèmes non linéaires. |
2018-B1 | Résumé : On s’intéresse à un modèle mathématique décrivant la cuisson de certaines céréales. De tels modèles sont basés sur des équations différentielles et aux dérivées partielles. Mots clefs : Equations aux dérivées partielles. Equations différentielles ordinaires. Aspects numériques du problème de Cauchy. |
2018-B2 | Résumé : On étudie un modèle mathématique de la dynamique des relations amoureuses expliquant les difficultés à maintenir une vie de couple dans la durée, en minimisant une fonctionnelle et en se ramenant à un système d’équations différentielles. Mots clefs : Equations différentielles ordinaires. Propriétés qualitatives. Optimisation. |
2018-B3 | Résumé : On s’intéresse à un modèle mathématique décrivant l’évolution de la criminalité dans une ville. On est ainsi conduit à considérer d’abord un système dynamique discret, puis un système d’équations de réaction-diffusion permettant de mettre en évidence la for- mation de « points chauds » de haute criminalité. Mots clefs : Systèmes dynamiques discrets. Équations aux dérivées partielles. Différences finies. |
2018-B4 | Résumé : On s'intéresse au problème consistant à amener la solution d'un problème d'évolution d'un état initial donné à un état final désiré par la construction d'un terme de « contrôle » adéquat. On étudiera cette question dans le cadre d'un système différentiel d'origine mécanique et pour une équation aux dérivées partielles décrivant le transfert de chaleur. Mots clefs : Interpolation. Équations différentielles. Équation de la chaleur. Développement en série entière. |
2018-B5 | Résumé : on étudie diverses stratégies permettant à un investisseur d'optimiser ses placements. Pour cela, on optimise une fonction de risque sous contraintes et on en propose une résolution numérique. |
2018-B6 | Résumé : l'évolution d'une population est décrite par une équation de réaction-diffusion. On étudie l'existence de solutions en ondes progressives puis on propose un schéma de type différences finies semi-implicite en temps pour le calcul d'une solution approchée. |
lien | RÉSUMÉ |
2005-C1 | Ce texte décrit le code de Shannon en le présentant comme un tour de prestidigitation : trouver en sept questions un nombre compris entre 0 et 15, en permettant de mentir à l’une des questions. Il présente aussi les définitions de base des codes (distance, etc.). Thème applicatif, mots clefs : Codes correcteurs, code de Shannon. |
2005-C2 | Ce texte comporte deux parties : dans la première, on expose l’exemple du code RSA, qui repose sur le fait qu’on ne sait pas factoriser rapidement un nombre entier. Dans la seconde, on présente l’algorithme ρ de Pollard, qui permet de factoriser un entier n en O N 1 4 opérations "élémentaires" (alors que l’algorithme naïf, qui consiste à diviser N par les entiers N, est en N 1 2 telles opérations.) Thème applicatif, mots clefs : Cryptographie, RSA, factorisation d’entiers, méthode ρ de Pollard. |
2005-C3 | On propose un procédé linéaire universel d’accélération de convergence de séries alternées, simple à mettre en œuvre, qui conduit à une convergence de type géométrique pour une large classe de séries lentement convergentes. Thème applicatif, mots clefs : séries alternées, resommation, polynômes orthogonaux. |
2005-C4 | Soit S un ensemble de Rn donné par des inégalités polynomiales. On construit explicitement une variété (si possible irréductible) de Rn 1 dont la projection sur Rn est S. Thème applicatif, mots clefs : géométrie effective. |
2008-C1 | On étudie le problème de l’arrondi correct des valeurs numériques de certaines fonctions ; on cherche en particulier à estimer la précision minimale nécessaire pour les calculs intermédiaires. Mots clefs : représentation et manipulation de structures algébriques, Z/nZ. |
2008-C2 | Ce texte est consacré à l’étude de la géométrie d’une molécule, en fonction des données imposées par les liaisons chimiques (longueurs, angles). Mots clefs : élimination, géométrie effective, polynômes |
2010-C1 | On étudie des problèmes de mise en commun de secrets. Mots clefs : polynômes, interpolation, corps finis |
2010-C2 | Le texte introduit et étudie la moyenne arithmético-géométrique. On montre comment elle intervient dans le calcul des intégrales elliptiques. Ces dernières permettent, en particulier, d’exprimer la période d’oscillation d’un pendule. Mots clefs : méthodes usuelles de calcul d’intégrales, polynômes |
2013-C1 | Dans ce texte, on présente une méthode de compression de fichiers, utilisée notamment en photographie numérique, et souvent plus efficace que les méthodes traditionnelles basées sur la transformée de Fourier. Mots clefs : algèbre linéaire, polynômes |
2013-C2 | Le tracé d’une courbe sous forme implicite F(X,Y ) = 0 produit souvent des artefacts qui ne correspondent pas réellement à la géométrie de la courbe. Le texte décrit une méthode qui permet, dans certains cas, de calculer une paramétrisation rationnelle de la courbe qui permet un tracé beaucoup plus conforme à la réalité. Mots clefs : géométrie, élimination, polynômes. |
2016-C1 | On présente un problème qui se rencontre dans de nombreuses applications pratiques, et qui est connu sous le nom de “design”. Pour le résoudre, on introduira des techniques arithmétiques et matricielles, et on déduira de ces constructions multiples un résultat classique de théorie des groupes. Mots clefs : algèbre linéaire, corps finis. |
2016-C2 | Le texte propose un modèle pour localiser le gène responsable d’une maladie génétique. L’étude mathématique de ce modèle conduit à traiter un problème d’élimination délicat, pour lequel une solution ad hoc est construite. Mots clefs : algèbre linéaire, élimination. |
2016-C3 | On étudie la mise en place d’un système de transmission à base d’antennes multiples ; cela nous conduit à étudier des sous-groupes du groupe des matrices unitaires de dimension n. Mots clefs : groupe unitaire, algèbre linéaire. |
2017-C1 | On étudiera certains codes linéaires dont le polynôme des poids est stable par l’action d’un groupe afin d’en déduire des contraintes sur les poids. Mots clefs : codes correcteurs d’erreur, groupes agissant sur un ensemble. |
2017-C2 | On étudie un protocole de mise en commun de secrets utilisant des matrices à coefficients dans un corps fini. Nous construisons ensuite deux attaques contre ce protocole, dont nous étudions le comportement afin de se protéger contre de mauvais choix de paramètres. Mots clefs : algèbre linéaire, valeurs propres, corps finis. |
2017-C3 | On s’intéresse à l’étude d’une famille de codes correcteurs d’erreurs pour une métrique différente de la classique distance de Hamming. Cela mène à l’étude d’un anneau non-commutatif de polynômes pour lesquels on arrive tout de même à définir une division euclidienne qui permet un décodage rapide. Mots clefs : corps finis, codes correcteurs, polynômes |
2018-C1 | On étudiera les relations entre des configurations de points sur une droite ou dans le plan et leur diagramme des distances Mots clefs : géométrie, arithmétique des polynômes |
2018-C2 | On considère quelques attaques contre le cryptosystème RSA.
Mots clefs : arithmétique des entiers
analyse du texte par le jury |
lien | RÉSUMÉ |
2006-D1 | On s’intéresse à la résolution et à la création de problèmes de Su Doku. Mots clefs : Parcours d’arborescences, coloration de graphes, calculs de complexité. |
2006-D2 | on définit le problème du tranport d’un produit à travers un réseau dont les capacités sont limitées, et on présente des algorithmes permettant de résoudre ce problème de façon optimale en termes de quantité transportée ou de coût du transport. Mots clefs : graphes et réseaux, plus court chemin. |
2008-D1 | Étude de diverses méthodes pour gérer une équipe de robots qui doivent coopérer Mots clefs : automates, graphes |
2008-D2 | Ce texte décrit et étudie le jeu de taquin, et s’intéresse en particulier à la recherche de solutions optimales. Mots clefs : parcours de graphes Il est rappelé que le jury n’exige pas une compréhension exhaustive du texte. Vous êtes laissé(e) libre d’organiser votre discussion comme vous l’entendez. Des suggestions de développement, largement indépendantes les unes des autres, vous sont proposées en fin de texte. Vous n’êtes pas tenu(e) de les suivre. Il vous est conseillé de mettre en lumière vos connaissances à partir du fil conducteur constitué par le texte. Le jury appréciera que la discussion soit accompagnée d’exemples traités sur ordinateur. |
2010-D1 | on définit deux méthodes de représentation des nombres entiers relatifs et on étudie la complexité de l’implantation des opérations usuelles entre nombres entiers ainsi représentés. Mots clefs : circuits élémentaires. |
2010-D2 | Modélisation d’un tissu cellulaire lors d’une contamination. Mots clefs : Automates, Algorithme et Réécriture |
2012-D1 | Modélisation et solutions approchées d’un problème d’éclairage de graphe. Mots clefs : graphe, arbre, complexité algorithmique, algorithmique géométrique, calcul propositionnel |
2012-D2 | Les figures que l’on peut réaliser lorsqu’on jongle avec des balles peuvent être représentées par des mots, appelés alors mots jonglables. Le texte est consacré à la modélisation du problème et à l’étude de certaines propriétés du langage des mots jonglables. Mots clefs : langages, automates finis, réécriture |
2012-D3 | Ce texte étudie la modélisation informatique, des méthodes de résolution et une utilisation possible de jeux à deux joueurs antagonistes pour lesquels chaque joueur a, à tout moment, une vision globale de la partie en cours. Mots clefs : algorithmes de graphes, combinatoire, complexité Il est rappelé que le jury n’exige pas une compréhension exhaustive du texte. Vous êtes laissé(e) libre d’organiser votre discussion comme vous l’entendez. Des suggestions de développement, largement indépendantes les unes des autres, vous sont proposées en fin de texte. Vous n’êtes pas tenu(e) de les suivre. Il vous est conseillé de mettre en lumière vos connaissances à partir du fil conducteur constitué par le texte. Le jury appréciera que la discussion soit accompagnée d’exemples traités sur ordinateur. |
2012-D4 | le problème du rangement de boîtes est un des classiques de l’optimisation combinatoire. Dans ce problème, on veut ranger un ensemble de boîtes, de volumes variés, dans des conteneurs ayant tous le même volume. Nous nous proposons d’étudier diverses propriétés du rangement optimal. L’obtention d’un tel rangement optimal constitue un problème NP-complet. Nous analysons ensuite diverses stratégies (ou heuristiques) donnant un résultat pas trop éloigné de l’optimum : rangement séquentiel (next fit), puis stratégie first fit. Le cas où cette dernière stratégie est appliquée à une instance décroissante fait l’objet d’une étude particulière. Mots clefs : optimisation combinatoire, NP-complétude |
2012-D5 | A partir du problème de la représentation des droites sur un écran d’ordinateur, on étudie la notion de droite discrète, et le mot binaire périodique associé. On met en évidence la relation biunivoque entre droites discrètes et certains mots binaires, puis entre ces mots et les nombres rationnels de [0, 1]. Mots clefs : algorithmes, géométrie discrète, mots binaires, topologie |
2012-D6 | La métamathématique étudie la correction des textes mathématiques à l’aide de raisonnements “finitistes”. Au niveau le plus élémentaire, il s’agit d’algorithmique sur des mots bien formés. Le texte aborde également les propriétés énumératives des mots bien formés. Mots clefs : formules, évaluation, pile, énumération, séries génératrices |
2018-D1 | Le coût en temps de l'évaluation d'une expression arithmétique est fonction linéaire de sa taille. Le coût en espace dépend de la structure de l'arbre sous-jacent. En mode interprété, l'évaluation se fait au fil de la lecture, mais en mode compilé on peut optimiser l'allocation d'espace. Le texte analyse et compare les coûts dans ces deux situations. Mots-clefs : expression arithmétique, évaluation, complexité en moyenne. |
2018-D2 | Nous nous intéressons à l'évaluation du signe d'expressions polynomiales en arithmétique flottante, et à la certification du résultat. Les questions sont illustrées sur des prédicats géométriques. Mots-clefs : précision numérique, représentation approchée des réels, géométrie. |