Présentation

• Le premier problème propose l'étude d'un algorithme efficace pour construire un arbre binaire de recherche optimal, lorsque l'on connaît pour chaque clé la probabilité qu'elle fasse l'objet d'une recherche. Il est alors avantageux de placer les clés les plus fréquemment demandées près de la racine. Nous retrouvons ici l'idée du magasinier économe de ses gestes, qui placera près de lui les articles qui ont la faveur de sa clientèle, et reléguera les rossignols au fond du magasin!
• Nous verrons que cette question entretient une forte parenté avec la recherche d'une triangulation optimale d'un polygone convexe et avec l'optimisation de l'évaluation d'un produit de plusieurs matrices.
• Dans le deuxième problème, nous nous intéressons à une relation sur des mots de même longueur: deux mots sont liés si l'on peut transformer le premier en le deuxième par retournement d'un facteur. Cette question présente un intérêt dans l'étude du génôme: des séquences appelées transposons peuvent venir s'insérer dans un brin d'ADN, dans l'un ou l'autre des deux sens de lecture.