Abstract FR:

Cette thèse est constituée de deux parties totalement indépendantes. La première partie est consacrée à la réalisation d'un logiciel de calcul automatique d'emploi du temps optimal, par la méthode du recuit simulé. Le premier chapitre introduit la théorie probabiliste sous-jacente : les chaînes de Markov hétérogènes. Puis nous donnons les principaux résultats permettant de valider cette méthode. Dans le second chapitre, nous présentons le logiciel qui a été développé en Common Lisp Object System, sur machine Lisp. Nous formalisons tout d'abord le problème des emplois du temps, puis nous décrivons, dans ce cadre, notre adaptation de l'algorithme du recuit simulé. Nous donnons enfin les différentes classes abstraites qui captent les propriétés et comportements des diverses entités du problème, ainsi que les méthodes associées à ces classes d'objets. La deuxième partie de ce travail est une contribution à l'algorithmique dans les algèbres de Lie libres. Le premier chapitre introduit les éléments nécessaires à la compréhension du sujet : mots de Lyndon, factorisation de Lyndon d'un monoïde libre, base de Lyndon d'une algèbre de Lie libre. Nous donnons aussi un moyen de calcul de la multiplicité d'un mot apparaissant dans le développement d'un polynôme de Lie dans l'algèbre associative libre. Dans le second chapitre, nous nous intéressons d'une part à la génération de la base de Lyndon dans l'ordre lexicographique par longueur, et, d'autre part, à la génération d'une classe d'évaluation quelconque des mots de Lyndon. Notre réponse au premier problème est basée sur un algorithme de Duval (1988) que nous adaptons pour notre propos. Nous proposons ensuite un algorithme récursif, basé sur la génération de certaines compositions d'entiers, comme solution au second problème. Pour clore ce chapitre, nous donnons un algorithme de génération des mots de Lyndon maximaux (par rapport à l'ordre lexicographique sur les mots de Lyndon) dans leur classe d'évaluation.