2020-D1 L'information génétique est contenue dans les génomes que l'on peut voir formellement comme des textes linéaires sur l'alphabet des quatre nucléotides {A,C,G,T}. Le produit ``final'' que sont les protéines se replie dans l'espace en une structure dite tertiaire. Nous proposons d'étudier des propriétés formelles d'une structure intermédiaire dite secondaire lorsqu'elle est planaire.

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.

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é.

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 À 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.