Contact: cliquez ici
MàJ: 2010-12-16
Hébergeur:
eNiX
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.