Pruesse et Ruskey ont présenté un algorithme pour la génération de leur code Gray pour les idéaux d'un poset (ensemble partiellement ordonné) où deux idéaux adjacents diffèrent par un ou deux éléments. Leur algorithme fonctionne en temps amorti de O(n) par idéal. Squire a présenté une récurrence pour les idéaux d'un poset qui lui a permis de trouver un algorithme pour générer ces idéaux en temps amorti de O(log n) par idéal, mais pas en code Gray. Nous utilisons la récurrence de Squire pour trouver un code Gray pour les idéaux d'un poset, où deux idéaux adjacents diffèrent par un ou deux éléments. Dans le pire des cas, notre algorithme a la même complexité que celle de l'algorithme de Pruesse et Ruskey et dans les autres cas, sa complexité est meilleure que celle de leur algorithme et se rapproche de celle de l'algorithme de Squire. Squire a donné une condition pour obtenir cette complexité. Nous avons trouvé une condition moins restrictive que la sienne. Cette condition nous a permis d'améliorer la complexité de notre algorithme. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Poset, Extension linéaire, Cycle hamiltonien, Code Gray, Algorithme, Complexité.

Avec l'arrivée des données moléculaires vers la fin des années 70, nous avons assisté à la découverte de nouveaux mécanismes d'évolution primordiaux dont l'échange du matériel génétique entre les espèces. Un tel échange peut se faire horizontalement, quand l'organisme intègre le matériel génétique provenant d'un autre organisme qui n'est pas son descendant direct, ou verticalement, quand l'organisme reçoit du matériel génétique à partir de son ancêtre le plus proche. Le problème de la détection et de la classification des transferts horizontaux de gènes (THG) est parmi les plus ardus en bioinformatique. Dans cette thèse, nous décrivons cinq nouveaux algorithmes pour la détection de THGs complets ou partiels qui seront basés sur des comparaisons topologiques et métriques entre un arbre d'espèces et un arbre de gène inférés pour le même ensemble d'espèces. Ces algorithmes incluent l'algorithme de détection de THGs complets ainsi que ses versions interactive et consensus. Les deux algorithmes de détection de transferts partiels que nous avons proposés peuvent être vus comme une généralisation de l'algorithme de détection de transferts complets. Ils peuvent être utilisés pour identifier des gènes mosaïques. Nous présentons aussi dans cette thèse une version parallèle de l'algorithme de détection de THGs complets, ainsi qu'une plateforme pour la transformation semi-automatique de programmes bioinformatiques séquentiels en programmes parallèles. Une interface Web intégrant tous les programmes développés dans le cadre de ce projet doctoral a aussi été mise au point. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithmes bioinformatiques, arbre phylogénétique, programmation parallèle, réseau réticulé, transfert horizontal de gènes (THG).

La problématique développée dans la thèse est d'estimer, dans une démarche prospective et dans un but d'anticipation, les impacts en puissance induits par les ruptures technologiques et comportementales qui ne font pas aujourd'hui l'objet de mesures dans les panels. Pour évaluer les modifications sur les appels de puissance du parc résidentiel engendrées par ces profondes transformations,un modèle paramétrique, bottom-up, techno-explicite et agrégatif est donc nécessaire. Celui-ci serait donc destiné à la reconstitution, de manière non tendancielle, de la courbe de charge électrique résidentielle. Il permettrait ainsi de conduire la simulation de différents scénarios d'évolution contrastés. L'élaboration d'un tel modèle constitue le sujet de ce doctorat.Pour répondre à cette problématique, nous proposons une méthode conceptuelle originale de reconstitution de courbe de charge. Sa mise en application centrée sur la génération de foisonnement d'origine comportementale a conduit à la modélisation d'un certain nombre de concepts. Ce travail a abouti à l'élaboration d'un algorithme stochastique destiné à représenter le déclenchement réalistedes appareils domestiques. Différents cas d'application ont pu être testés et les résultats en puissance ont été étudiés. Plus particulièrement pour analyser le foisonnement visible à un niveau agrégé, nous avons mis en place une méthodologie nouvelle basée sur une distance adaptée aux courbes de charge. Finalement, nous avons cherché à identifier des comportements réels d'usage des appareils. Pour cela, nous avons conduit différents travaux de classification de courbes de charge.

L'hypothèse du liage temporel par synchronie suscite un intérêt important en neurobiologie, car elle permet d'expliquer comment différentes structures du cerveau peuvent établir entre elles un lien fonctionnel, en rapport avec une fonction cognitive. Cependant, il n'existe pas de modèle permettant de faire communiquer différents groupes de neurones par le biais de leurs émissions. <br /><br />Nous avons développé un modèle de réseau de neurones impulsionnels, dont la topologie est modifiée par un algorithme évolutionniste. Le critère de performance utilisé pour l'algorithme évolutionniste est évalué par l'intermédiaire du comportement d'un individu contrôlé par un réseau de neurones impulsionnels, et placé dans un environnement virtuel. L'utilisation du neurone impulsionnel, ayant la propriété de détection de synchronie, oblige l'évolution à construire un système utilisant cette propriété au niveau global, d'où l'émergence de la synchronisation neuronale à large-échelle. Les propriétés topologiques et dynamiques du réseau de neurones ne sont pas prises en compte dans le calcul de la performance, mais sont étudiées a posteriori, en comparant les individus avant et après évolution. <br /><br />D'une part, grâce aux outils de la théorie des réseaux complexes, nous montrons l'émergence d'un certain nombre de propriétés topologiques, notamment la propriété de réseau ``petit-monde''. Ces propriétés topologiques sont similaires à celles observées au niveau de l'anatomie des systèmes nerveux en biologie. D'autre part, au niveau de la dynamique, nous établissons que la propriété de synchronisation neuronale à large-échelle, résultant de la présentation d'un stimulus, est présente chez les individus évolués. Pour ce faire, nous nous appuyons sur les outils classiquement utilisés en électrophysiologie, et nous les étendons pour pouvoir interpréter la grande quantité de données obtenue à partir du modèle. <br /><br />Le modèle montre que l'on peut construire des réseaux de neurones basés sur l'hypothèse du liage temporel en ayant recours à l'évolution artificielle, en se basant sur un critère de performance écologique, c.à.d. le comportement de l'individu dans son environnement. D'autre part, les outils développés pour l'analyse des propriétés du modèle peuvent être utilisés dans d'autres domaines, en premier lieu en électrophysiologie. En effet, à cause des progrès techniques sur les enregistrements électrophysiologiques, la quantité de données se rapproche singulièrement de celle issue du modèle.

Ce travail de thèse s'inscrit dans le cadre d'une collaboration industrielle avec la société Volume Software pour le développement du module d'ordonnancement du logiciel "DirectPlanning". Dans ce travail, nous étudions le problème de job shop flexible multicritère et le problème de job shop multiressource multicritère. Notre objectif est de déterminer une approximation du front de Pareto. Nous avons proposé des algorithmes de résolution approchés et plus particulièrement des algorithmes de recherche Tabou et des algorithmes génétiques. Nous avons proposé différentes versions de nos méthodes pour les deux problèmes considérés. Des expérimentations ont été réalisées et montrent les bonnes performances de nos algorithmes, à la fois d'un point de vue qualité des résultats et d'un point de vue de la rapidité des méthodes.

Le développement des technologies sub-microniques a permis un regain d'intérêt pour les capteurs d'images CMOS, qui inondent aujourd'hui le marché des capteurs. Les approches conventionnelles pour la conception de machines de vision sont en général basées sur des architectures connectées à une caméra. L'approche proposée dans ce travail consiste à associer, dans un même circuit – une rétine CMOS -, les photocapteurs et des fonctions de pré-traitement de l'image, permettant ainsi de répartir et d'optimiser le traitement. Ces rétines ont des performances en vitesse, en intégration et en consommation meilleures que les solutions classiques (capteurs puis traitements logiciels et/ou matériels). Cette thèse porte plus précisément sur l'intégration d'un algorithme d'estimation du mouvement en transposant le calcul numérique fortement itératif en une structure de calcul électronique. Après avoir réalisé un circuit permettant d'acquérir des connaissances dans le domaine des capteurs d'images CMOS, nous avons conçu un circuit de vision estimant le mouvement. Cette estimation de mouvement est basée sur une méthode robuste de mise en correspondance de blocs de pixels, comprenant une phase de pré-codage des pixels suivi<br />d'une recherche de ce codage dans une fenêtre de destination potentielle. Cette approche est novatrice car elle propose une rétine CMOS pouvant traiter (électroniquement) des scènes fortement texturées, et à luminosité changeante, en s'appuyant sur une méthode jusqu'alors réservée aux approches numériques (FPGA, DSP) ou logicielles.

Le concept de paysage adaptatif a été introduit par S. Wright dans le domaine de la biologie de l'évolution dans les années 1930. Il est l'un des concepts pertinents pour modéliser l'évolution d'une population d'organismes. Dans le domaine de l'optimisation combinatoire par métaheuristiques, il est également utilisé et <br />permet de lier une description géométrique d'un problème d'optimisation avec la dynamique des algorithmes de recherche.<br />Deux géométries de paysage correspondant à deux dynamiques d'algorithme ont été principalement étudiées. La géométrie de paysage multimodale est liée à la présence d'optima locaux,<br />où la dynamique est une succession de marches adaptatives vers de meilleures solutions et de dégradations de performance. La géométrie des paysages adaptatifs neutres, mise en avant par la théorie de la neutralité en évolution moléculaire de Motoo Kimura,<br />est liée à la présence de plateaux ; la dynamique se caractérise alors par une dérive aléatoire entrecoupée de rares découvertes de solutions plus performantes. Cette thèse se propose d'approfondir <br />l'étude des paysages neutres dans le contexte de l'optimisation et de proposer de nouvelles métaheuristiques adaptées à ce type de paysages.<br /><br />La thèse se compose de quatre chapitres. Dans un premier chapitre,<br />nous présentons les principaux résultats concernant les paysages adaptatifs et plus particulièrement les paysages adaptatifs neutres.<br />Dans un deuxième chapitre, nous développons le concept d'ensemble de neutralité en introduisant la notion de 'nuage adaptatif' qui permet d'étudier la corrélation de performance entre solutions voisines et nous l'appliquons à la classe des paysages 'embarqués' qui regroupe les paysages NK et Max-SAT. Dans un troisième chapitre, nous résumons l'ensemble des mesures relatives aux réseaux de neutralité et nous proposons une nouvelle mesure. Une étude expérimentale est réalisée sur trois familles de paysages pour lesquelles la neutralité est ajustable et deux problèmes classiques de la littérature. Enfin, un nouvel algorithme de recherche adapté aux paysages neutres lié à la nouvelle mesure est proposé et évalué sur différents paysages neutres. Nous réalisons l'étude du paysage adaptatif massivement neutre<br />issu du problème d'apprentissage de la règle d'un automate cellulaire réalisant la tâche de classification par la densité, afin d'en améliorer les métaheuristiques connues existantes.

Des patchs en matériaux composites sont classiquement utilisés dans l'aéronautique pour la réparation des structures métalliques présentant des dommages de<br />type fissures, criques ou impacts. Une alternative à la réparation de ces structures consiste à les renforcer préventivement, avant que les défauts n'apparaissent. Le<br />contexte de ce travail est celui de la maintenance préventive de structures métalliques aéronautiques par renforts composites, dans le but de retarder l'apparition ou la propagation de fissures.<br />La conception des renforts nécessite l'utilisation d'outils spécialisés pour définir les caractéristiques optimales du patch : géométrie, nombre de plis unidirectionnels,<br />orientation des plis les uns par rapport aux autres, positionnement autour de la zone à soulager... Pour cela, un programme d'optimisation de patchs par algorithme<br />génétique a été écrit. Il est couplé à un logiciel de calcul par éléments finis : Ansys.<br />L'algorithme génétique mis en oeuvre a permis de déterminer des caractéristiques de patchs dont la géométrie extérieure est définie par une courbe spline fermée, ceci afin de réduire de manière optimale les contraintes mécaniques dans une zone donnée, et<br />ce pour différents types de sollicitations.<br />De nombreuses d´efaillances des assemblages collés patch/substrat sont liées à des concentrations de contraintes dans la colle dues à l'existence d'une zone de<br />transfert progressif d'effort du substrat vers le patch. Des approches unidirectionnelles du transfert d'effort sont classiquement utilisées dans la littérature. Elles ne<br />tiennent cependant pas compte d'effets bidimensionnels comme la différence des coefficients de Poisson qui peut exister entre le substrat et le composite. A partir des<br />équations d'équilibre, des modèles analytique et numérique bidimensionnels ont donc été développés. Des phénomènes de couplages bidimensionnels ont ainsi bien été mis en évidence.<br />Parallèlement, des essais de traction uniaxiale ont été réalisés sur des éprouvettes en aluminium renforcées par des patchs en carbone/époxyde. La méthode de la grille a été utilisée pour mesurer des champs cinématiques en surface du patch composite.<br />Cette méthode a permis d'étudier expérimentalement le transfert des efforts entre le substrat et le renfort suivant les deux dimensions du problème et de comparer les résultats obtenus avec les différents modèles développés au préalable.

L'apprentissage est une étape importante d'un processus de reconnaissance des formes pour<br />la décision. On distingue généralement l'approche supervisée de l'approche non supervisée suivant<br />que l'on dispose ou non d'une expertise des données. Dans ce travail, nous étudions le cas<br />intermédiaire d'une classification semi-supervisée où l'on dispose d'un ensemble mixte de données<br />numériques.<br />Certains éléments à traiter diffèrent du modèle a priori supposé des données et peuvent perturber<br />le processus d'apprentissage. Les méthodes robustes de classification visent à limiter l'influence<br />de ces données aberrantes soit en les modélisant explicitement, soit en utilisant des estimateurs<br />robustes. La première partie de ce travail nous a permis d'étudier la notion de robustesse à<br />travers divers algorithmes de classification. Un intérêt particulier est porté à l'utilisation des<br />M-estimateurs de Huber dans le cadre de l'estimation par le principe du maximum de vraisemblance.<br />La seconde partie de cette étude est consacrée à l'état de l'art des principales méthodes de<br />classification semi-supervisée. Nous montrons que celles-ci reposent sur la modification de la<br />fonctionnelle réalisant la classification en introduisant un terme d'accord avec la mesure d'appartenance<br />fixée par l'expert.<br />Sur la base de ces deux domaines, nous proposons un algorithme robuste de classification partiellement<br />supervisée introduisant une option de rejet. Les classes sont modélisées par un mélange<br />de deux composantes dont les paramètres sont estimées par un calcul itératif robuste. Le rejet<br />est effectué par une fonction d'affectation produisant une classe additionnelle dédiée aux points<br />aberrants. Les résultats obtenus sur divers jeux de données artificiels et réels nous ont permis de<br />valider notre approche.

Dans le domaine de l'électronique embarquée, les applications de communications numériques et de traitement d'images imposent des contraintes de temps très fortes tout en admettant une limitation en ressources et performances des unités de traitement. La restriction quant à la mémoire utilisable peut être préjudiciable pour des domaines tels que le codage vidéo. Une solution pour atteindre les objectifs d'implantation temps-réel peut passer par une distribution sur une architecture matérielle parallèle. Cette problématique constitue le cadre de ces travaux. Plus précisément, il s'agit de développer un processus de prototypage rapide dédié aux architectures parallèles à base de plusieurs processeurs de traitement numérique du signal de dernière génération (FPGA, DSP). L'aspect optimisation du point de vue de la mémoire allouée est abordé ici de manière plus précise.<br />La chaîne de prototypage a été élaborée autour de SynDEx, outil développé à l'INRIA basé sur la méthodologie AAA. Cette dernière vise à améliorer l'implantation d'un algorithme sur une architecture multi-processeurs en déterminant une distribution et ordonnancement optimaux. SynDEx réalise la phase d'adéquation proprement dite, et génère un exécutif indépendant de la cible. Nous avons dans un premier temps contribué à l'automatisation du processus sur cible multi-processeurs, en rajoutant d'une couche fonctionnelle, et en développant de nouveaux noyaux spécifiques pour des processeurs de traitement numérique du signal.<br />Dans un contexte embarqué, nos préoccupations se sont ensuite penchées sur la minimisation de la mémoire pour le code généré. C'est un problème encore très ouvert pour des architectures multi-composants. La solution trouvée, grâce aux algorithmes de coloriage de graphe, aboutit à une amélioration significative des résultats d'implantation distribuée. Le portage vers des plates-formes multi-composants est aujourd'hui automatique, notamment en intégrant directement dans l'outil SynDEx l'optimisation mémoire.<br /> Une autre partie importante de ces travaux a concerné le développement et l'intégration, à travers notre processus de prototypage, d'applications conséquentes dans les domaines du traitement des images (MPEG-4, LAR) et celui des télécommunications (MC-CDMA, UMTS). Les résultats obtenus valident l'ensemble du processus proposé, et démontrent son adaptation à des systèmes globalement orientés traitement de l'information. Le mémoire se conclut en ouvrant sur de nouvelles perspectives, en s'intéressant notamment à des systèmes multi-couches réunissant des couches « transport » de télécommunication numériques et des couches « services » de traitement des images.