Ce travail est axé autour de l'analyse assistée par ordinateur, dans un cadre musicologique ciblant la musique contemporaine. Une approche computationnelle de l'analyse musicale pose la question de sa modélisation et de sa formalisation, puisque touchant à une activité souvent empirique et dont la pratique n'est pas définie à l'aide de normes communes. Cette question implique la mesure de l'importance de la représentation graphique dans l'interprétation analytique. Face au rôle croissant de la représentation, nous nous intéressons d'une part à la manière dont elle relie l'analyse et la composition en proposant, à partir d'une analyse connue des Structures IA de Pierre Boulez réalisée par le compositeur György Ligeti, des modèles de machinerie informatique en vue de générer des pièces musicales sous deux interfaces, OpenMusic et Rubato. Parmi ces deux environnements de programmation visuelle, le second se base sur un puissant paradigme mathématique reposant sur la théorie des catégories. Ce paradigme constitue également une base pour modéliser les K-réseaux, outil d'analyse reposant sur des graphes décrivant les relations entre les notes. Ces relations sont formalisées dans la Set Theory d'Allen Forte qui propose une méthode de classification des structures musicales à partir des douze hauteurs de la gamme chromatique occidentale. Une application de ces réseaux et plus généralement l'apport des structures de graphe est abordée ensuite dans la modélisation de l'analyse d'une autre pièce, le Klavierstück III de Karlheinz Stockhausen : cette analyse a été faite par le théoricien David Lewin en deux étapes que nous étudierons dans leurs aspects à la fois computationnel et d'interface-homme machine. En premier lieu, la segmentation, non expliquée par l'analyste, fait l'objet d'une reconstitution dans laquelle nous tentons de la retrouver par le biais d'une exploration dans un ensemble de segmentations possibles. Il s'agit ainsi non seulement de reconstituer mais également de voir s'il est possible de la dépasser et l'améliorer selon des critères comme la couverture de la partition. Nous verrons dans ce cadre si les K-réseaux peuvent affiner cette analyse et en constituer un angle d'attaque pertinent. En second lieu, Lewin organise ses segments selon un réseau qui ne suit plus un quelconque agencement chronologique mais une disposition spatiale qui offre un nouveau parcours de la pièce. Cette difficulté s'inscrit dans le contexte plus général de la sélection et de la formation d'un graphe décrivant la structure d'une oeuvre musicale, que nous envisageons à l'intérieur du problème de l'utilisation d'un réseau en analyse computationnelle.

L'objet de cette thèse est d'obtenir une description des plongements élémentaires (au sens de la logique du premier ordre) dans un groupe hyperbolique sans torsion. Le résultat principal décrit ces plongements en terme d'une structure définie par Sela dans sa solution au problème de Tarski: la structure de tour hyperbolique. Ainsi, si H est plongé élementairement dans un groupe hyperbolique sans torsion G, on peut obtenir G en amalgamant successivement des groupes de surfaces à bord à un produit libre de H avec des groupes libres et des groupes de surfaces sans bord. Ceci permet en corollaire de montrer qu'un sous-groupe plongé élémentairement dans un groupe libre de type fini est un facteur libre. Les techniques utilisées pour obtenir cette description sont essentiellement géométriques: actions sur des arbres réels ou simpliciaux, existence de décompositions JSJ. On s'appuie également sur des résultats d'existence d'ensembles de factorisation qui affirment que pour certains groupes A de type fini, étant donné un groupe hyperbolique sans torsion G, il existe un ensemble fini de quotients de A tel que tout morphisme non injectif de A vers G se factorise par l'un de ces quotients après précomposition par un automorphisme de A. On expose une preuve de ces résultats, y compris une version complète et détaillée du shortening argument de Rips et Sela. Le shortening argument montre, grâce à l'analyse de Rips des actions sur des arbres réels, que si une suite d'action d'un groupe A sur des espaces hyperboliques converge vers un A-arbre réel d'un certain type, alors une infinité de ces actions peuvent être raccourcies.

<p>Autonomous agent systems are systems in which many simple entities, called “agents”, interact with each other. The behaviour resulting from such interactions can be much more complex than that of the individual agents. A group of interacting agents can for example accomplish tasks that no single agent could.</p> <p>Nature provides several examples of autonomous agent systems, such as flocks of birds and insects, schools of fish, and anthills. Progresses in robotics, electronics and telecommunications make it now also possible to design such systems in order to accomplish particular tasks, such as the surveillance or exploration of areas, or the maintenance of some environments.</p> <p>In this thesis, we analyze two issues related to autonomous agent systems, and more precisely, to the influence of the inter-agent communication network on the system behaviour. In a first part, we consider the problem of preserving the shape of a multi-agent formation by explicitly maintaining the distances between some agents constant. We study the case of distance constraints that are unilateral, that is, constraints for which the responsibility is given to a one of the two agents concerned. This leads to the notions of persistence and constraint consistence. The second part is devoted to the consensus problems: agents have a value which they update by averaging that of other agents. Eventually, all agents may obtain a common value, in which case we say that the system reaches a consensus. One major difficulty in the study of such system is the possible dependence of the interaction and communication topology on the values of the agents. We study two paradigmatic systems in which this dependence can be taken into account, and obtain results on their convergence and on the stability of their equlibria.</p>

Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.

Les peptides non-ribosomiaux sont des molécules produites par les micro-organismes et présentant un large éventail d'activités biologiques et pharmaceutiques. Par exemple, ils peuvent présenter des activités antibiotiques, immuno-modulatrices ou anti-tumorales. Ces peptides sont synthétisés par de grands complexes multi-enzymatiques, appelés synthétases ou NRPS (NonRibosomal Peptide Synthetases). Deux traits caractéristiques distinguent ces peptides des peptides ribosomiaux classiques : le premier est que leur structure primaire n'est pas toujours linéaire mais peut être totalement ou partiellement cyclique, branchée voir même poly-cyclique, et le second est la diversité des monomères incorporés au sein de ces peptides qui dépasse largement les vingt acides aminés protéogéniques. Nous avons développé Norine, la première ressource publique entièement dédiée aux peptides nonribosomiaux. Norine contient actuellement plus de 1 000 peptides, modélisés par des graphes étiquetés non-orientés, ainsi que des outils informatiques permettant leur analyse, comme la comparaison de compositions en monomères, la recherche de motifs structuraux ou la recherche par similarité. Des analyses statistiques sur les données contenues dans Norine ont permis de mettre en évidence des caractéristiques biologiques intéressantes comme la spécificité des monomères en fonction de l'activité biologique qui nous a conduit à l'élaboration d'un outil d'aide à la prédiction de la fonction biologique d'un peptide à partir de sa composition monomérique. En trois ans, Norine est devenue la ressource internationale pour les peptides non-ribosomiaux.

L'estimation de la pose du corps humain ou son suivi grâce à la vision par ordinateur se heurte à la diffi culté d'explorer un espace de grande dimension. Les approches par apprentissage et particulièrement celles qui font appel aux régressions vers des espaces de dimension réduits comme les LLE [RS00] ou les GPLVM [Law03] permettent de résoudre cette diffi culté dans le cas de gestes cycliques [UFF06] sans parvenir à généraliser le suivi pour des poses quelconques. D'autres techniques procèdent directement par la comparaison de l'image test avec une base d'apprentissage. Dans cet esprit, le PSH [SVD03] permet d'identi fier rapidement un ensemble de poses similaires dans une grande base de données. Cependant, même en intégrant des techniques d'extrapolation qui permettent de générer d'autres poses à partir de celles apprises, les approches uniquement basées sur l'apprentissage ne parviennent généralement pas à couvrir de façon assez dense l'espace des poses [TSDD06]. D'autres voies consistent à mettre en oeuvre une méthode déterministe ou stochastique. Les méthodes déterministes [PF03] fournissent souvent une solution sous-optimale en restant piégées sur un optimum local du fait des ambiguïtés issues de la vision monoculaire. Les approches stochastiques tentent d'explorer la probabilité a posteriori mais là encore, la grande dimension de l'espace des poses, notamment dans le cas des méthodes à base de simulation par échantillonnage, exige de multiplier le nombre des tirages a n d'avoir une chance d'explorer le mode dominant. Une solution intéressante consiste à utiliser un modèle de corps à membres indépendants [SBR+04] pour restreindre l'exploration aux sous espaces dé nis par les paramètres de chacun des membres. L'infl uence d'un membre sur les autres s'exprime grâce à la propagation des croyances [KFL01] pour fournir une solution cohérente. Dans ce travail de thèse, cette dernière solution est retenue en l'associant au fi ltre à particules pour générer un espace discret où s'e ectue la propagation des croyances [BCMC06]. Ce procédé est préférable à la modélisation paramétrique des messages par un échantillonneur de Gibbs, un procédé coûteux en ressources dérivé de l'algorithme PAMPAS [Isa03]. Parallèlement à cette solution, le développement d'un suivi robuste du haut du corps, même en 2D [NB07b], exige une fusion de plusieurs indices extraits de l'image. La vraisemblance des hypothèses émises vis-à-vis de l'image est évaluée à partir d'indices tirés des gradients et de la couleur combinés avec une soustraction de fond [NB06] et une détection du mouvement. L'interprétation de la profondeur pour le passage en 3D constitue une di fficulté majeure du suivi monoculaire. La fusion d'indices évoquée précédemment devient insu sante pour contraindre la pose. Cependant, du fait des contraintes articulaires, l'espace réel des poses occupe un sous-espace très réduit dans l'espace théorique. Le codage de ces contraintes dans l'étape de propagation des croyances associé à la fusion d'indices permet alors d'aboutir à de bonnes performances, même dans les cas d'environnements non contraints (lumière, vêtements...) [NB07a]. Une meilleure gestion des occultations est mise en oeuvre en ajoutant un terme de compatibilité des hypothèses basé sur l'apprentissage. Avec le modèle utilisé [SBR+04], ce sont des membres indépendants plutôt que des poses complètes qui sont stockées dans la base d'apprentissage. Ceci permet d'obtenir une couverture satisfaisante de l'espace des poses avec un nombre raisonnable d'exemples appris. La propagation des croyances assure un assemblage cohérent des membres pour arriver au résultat et le processus de sélection des exemples dans la base peut-être accéléré grâce au PSH [SVD03].

Les réseaux GAI sont une représentation graphique compacte et expressive des préférences d'un décideur en Décision Multiattribut, c'est-à-dire dans des situations où les alternatives sur lesquelles portent les choix du décideur sont décrites à l'aide d'un ensemble d'attributs (de caractéristiques). L'exploitation de leur structure graphique permet de définir des procédures efficaces d'élicitation de préférences (détermination des préférences à l'aide de questionnaires) ainsi que des algorithmes assez performants de prise de décision (calcul de l'alternative préférée du décideur ou des k meilleures alternatives). Le but de cette thèse est double. Tout d'abord elle vise à étendre les algorithmes de prise de décision dans des cas où les réseaux GAI sont denses, c'est-à-dire dans des situations où leur structure ne permet pas aux algorithmes de l'état de l'art de s'exécuter en un temps raisonnable. Pour cela, une nouvelle méthode de triangulation approchée a été développée, qui produit des réseaux GAI approchés sur lesquels des mécanismes d'inférence adaptés permettent d'obtenir les alternatives optimales des réseaux GAI d'origine. Ensuite, elle propose de nouvelles méthodes d'inférence en Décision multicritère. Plus précisément, elle propose des approches pour déterminer des frontières de Pareto (exactes ou approchées avec garantie de performance) ou des frontières de Lorenz. Elle prop ose également des algorithmes pour déterminer des solutions optimales dans les cas où les critères peuvent être agrégés via des opérateurs tels que OWA (Ordered Weighted Average), l'intégrale de Choquet ou bien encore la norme de Tchebyche ff.

Dans le cadre de l'émergence des nouvelles formes organisationnelles (réseau d'entreprises, entreprise virtuelle, entreprise entendue, ...) ce travail s'intéresse plus particulièrement aux groupements de PME. Dans un environnement économique de plus en plus instable caractérisé par une concurrence accrue, les entreprises sont appelées à faire face et à répondre en conséquence pour rester concurrentielle. La coopération au sein d'une structure organisationnelle est devenue une option incontournable pour les PME. Cependant, cette option comporte des risques et doit être maîtrisée et pilotée pour être efficace et pertinente. Les entreprises doivent donc s'appuyer sur des outils et méthodes pour rationaliser leurs différents choix et prendre les bonnes décisions lors de situations critiques. Cette thèse vient s'inscrire dans cette problématique. L'objet de ce travail est de formaliser les liens de coopération inter-entreprises au sein de réseaux de PME, et de représenter leurs trajectoires d'évolution. Cette formalisation se traduit par la construction d'une cartographie organisationnelle des modes de coordination potentiels du réseau. L'évolution de cette cartographie est représentée par un arbre de scénarios. Cette modélisation est basée sur les caractéristiques structurelles des entreprises. Deux critères clés sont identifiés pour le choix d'un mode de coordination entre deux PME : la similarité des compétences et la complémentarité des activités. Ces deux critères sont appuyés par des paramètres explicatifs qui viennent enrichir l'approche proposée (paramètres internes, paramètres relationnels, proximités, ...). Finalement, un outil d'aide à la décision pour les managers et les divers acteurs économiques est proposé pour détecter des liens de coopération potentiels dans un réseau. Il permet de proposer des préconisations pour piloter la trajectoire organisationnelle du réseau. Deux études de cas viennent confronter la méthodologie proposée à la réalité.

La détermination d'une topologie d'un réseau de distribution caractérisée par des pertes Joule minimales conduit à résoudre un problème d'optimisation combinatoire, non linéaire avec des variables discrètes. Ce problème, à la charge du distributeur, s'avère critique et dépendant de nombreux facteurs tels que la présence de production décentralisée et les évolutions de la charge. Diverses approches ont été abordées. Après l'examen d'une recherche exhaustive, deux approches heuristiques et une approche méta heuristique, fondée sur la théorie des graphes et des matroïdes, ont été employées pour déterminer une topologie radiale optimale pour un état donné de charge et de production. Une procédure indiquant les permutations de branches nécessaires pour transiter entre deux topologies radiales est ensuite présentée. Afin d'identifier une topologie optimale suivant une courbe de charge, une procédure fondée sur des optimisations horaires est réalisée. Finalement, des algorithmes pour l'optimisation de topologies partiellement maillées sont présentés.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3508. Texte en anglais. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. 101-107. Liste des publications.