La réservation de ressources dans un réseau de communication est un domaine d'application très vaste, qui implique des problèmes algorithmiques nombreux et variés. La modélisation d'un réseau sous la forme d'un graphe permet, indépendamment de sa nature physique, de développer des algorithmes pour déterminer quels sont les noeuds et/ou les liens du réseau qui doivent être réservés. Il s'agit de gérer au mieux l'attribution de ces ressources pour les membres qui inter-agissent via le réseau. Pour la résolution de problèmes liés à la réservation de ressources au niveau d'un lien particulier, c'est la modélisation sous la forme d'un ordonnancement qui est alors particulièrement adaptée. Dans ce type de problèmes, il n'est pas toujours possible de connaître à l'avance toutes les données à traiter. En effet, les demandes de membres amenés à communiquer via le réseau ainsi que les demandes de réservation au niveau des liens arrivent en pratique au fils de l'eau. Pour prendre en compte cette difficulté, nous nous plaçons dans le contexte de l'algorithmique on-line (en ligne). Les données du problème à traiter ne sont donc pas connues dès le départ, mais révélées au fur et à mesure, sans aucune connaissance du futur. Pour chacun des problèmes on-lines traités, nous proposons des algorithmes que nous évaluons analytiquement, en fonction d'un (ou parfois plusieurs) critère(s) de performance.

Ce travail de thèse traite du maintien dynamique de représentations géométriques de graphes. Le manuscrit met en avant des connexions fortes entre trois types de représentation de graphes : les décompositions de graphes, les modèles géométriques et les représentations arborescentes à degrés de liberté (PQ-arbres, PC-arbres et autres structures du même type). De nouvelles relations entre ces objets sont mises en évidence et d'autres déjà connues sont approfondies. Notamment, il est établi une équivalence mathématique et algorithmique entre la décomposition modulaire des graphes d'intervalles et le PQ-arbre de leurs cliques maximales.<br /><br />Les connexions entre les trois types de représentation précités sont exploitées pour la conception d'algorithmes de reconnaissance entièrement dynamiques pour les cographes orientés, les graphes de permutation et les graphes d'intervalles. Pour les cographes orientés, l'algorithme présenté est de complexité optimale, il traite les modifications de sommet en temps O(d), où d est le degré du sommet en question, et les modifications d'arête en temps constant. Les algorithmes pour les graphes de permutation et les graphes d'intervalles ont la même complexité : les modifications d'arête et de sommet sont traitées en temps O(n), où n est le nombre de sommets du graphe. Une des contributions du mémoire est de mettre en lumière des similarités très fortes entre les opérations d'ajout d'un sommet dans un graphe de permutation et dans un graphe d'intervalles. <br />L'approche mise en oeuvre dans ce mémoire est assez générale pour laisser entrevoir les mêmes possibilités algorithmiques pour d'autres classes de graphes définies géométriquement.

Plusieurs travaux sur l'estimation des paramètres de certains modèles bilinéaires ont été réalisé avec quelques applications et simulations.<br />Notre objectif dans cette thèse était alors, d'édifier un nouvel algorithme d'estimation des paramètres de ces modèles, et leur utilisation dans la modélisation des données issues de phénomènes réels.<br />Notre avons développé notre nouvelle technique d'estimation en se basant sur la méthode du maximum de vraisemblance et l'algorithme du filtre de Kalman, ce dernier requiert une représentation en espace d'état de ces modèles. nous avons pour cela utilisé la représentation affine en état polynomiale en entrée introduite par Guégan et la représentation de Hamilton.<br />Pour exhiber la bonne performance de notre approche nous avons généré plusieurs simulations.<br />Notre algorithme d'estimation a été implémenté dans un outil logiciel, que nous avons conçu au profit de certains modèles bilinéaires particuliers.

Utilisée à la fois pour l'apprentissage et l'exploitation des vecteurs conceptuels, l'analyse sémantique de texte est centrale à nos recherches. L'amélioration qualitative du processus d'analyse entraîne celle des vecteurs. En retour, cette meilleure pertinence a un effet positif sur l'analyse. Parmi les différentes voies à explorer pour obtenir ce cercle vertueux, l'une des pistes les plus intéressantes semble être la découverte puis l'exploitation des relations lexicales entre les mots du texte. Ces relations, parmi lesquelles la synonymie, l'antonymie, l'hyperonymie, la bonification ou l'intensification, sont modélisables sous la forme de fonctions lexicales. Énoncées essentiellement dans un cadre de production par Igor Mel'čuk, nous cherchons, dans cette thèse, à les adapter à un cadre d'analyse. Nous introduisons ici deux classes de Fonctions Lexicales d'Analyse. Les premières, les FLA de construction permettent de fabriquer un vecteur conceptuel à partir des informations lexicales disponibles. Les secondes, les FLA d'évaluation permettent de mesurer la pertinence d'une relation lexicale entre plusieurs termes. Ces dernières sont modélisables grâce à des informations thématiques (vecteurs conceptuels) et/ou grâce à des informations lexicales (relations symboliques entre les objets lexicaux).<br /><br />Les informations lexicales sont issues de la base lexicale sémantique dont nous introduisons l'architecture à trois niveaux d'objets lexicaux (item lexical, acception, lexie). Elles sont matérialisées sous la forme de Relations Lexicales Valuées qui traduisent la probabilité d'existence de la relation entre les objets. L'utilité de ces relations a pu être mis en évidence pour l'analyse sémantique grâce à l'utilisation du paradigme des algorithmes à fourmis. Le modèle introduit dans cette thèse, utilise à la fois les vecteurs conceptuels et les relations du réseau lexical pour résoudre une partie des problèmes posés lors d'une analyse sémantique.<br /><br />Tous nos outils ont été implémentés en Java. Ils reposent sur Blexisma (Base LEXIcale Sémantique Multi-Agent) une architecture multi-agent élaborée au cours de cette thèse dont l'objectif est d'intégrer tout élément lui permettant de créer, d'améliorer et d'exploiter une ou plusieurs Bases Lexicales Sémantiques. Les expériences menées ont montré la faisabilité de cette approche, sa pertinence en termes d'amélioration globale de l'analyse et ouvert des perspectives de recherches fort intéressantes.

Parallélisation de quelques algorithmes d'algèbre linéaire à l'aide du formalisme du graphe des taches

Description du prototype d'un système multimicroprocesseur adapté au traitement des algorithmes parallèles dont une étude des différentes architectures multiprocesseurs et de leur classification permet de le situer au sein des MIMD. Son architecture modulaire permet la connexion d'un grand nombre de processeurs sur un bus commun par un circuit d'arbitrage asynchrone. Une évaluation des performances du système dans le traitement des programmes utilisant les différents types de parallélisme est présentée.

Ce travail présente l'étude d'une structure de données qui s'efface d'allier souplesse de représentation et de traitement lors de la traduction automatique. On montre la formalisation de la structure (un réseau) et de ses notions principales (sous-structures, ordres, etc), puis on passe a l'analyse de quelques transformations de la structure. On décrit l'implémentation d'un prototype réduit programme en PROLOG et enfin on donne des algorithmes pour une programmation plus efficace de prototype

Cette thèse se situe dans le cadre de la vérification de systèmes distribués. Plus précisément, nous nous intéressons aux méthodes de preuve de convergence d'algorithmes distribués s'exécutant sur des réseaux en anneau de taille paramétrée. Cette étude distingue de plus le cas des algorithmes probabilistes de celui des algorithmes déterministes.

Après un état de l'art sur l'ordonnancement en général et l'ordonnancement temps réel en particulier permetttant de préciser les notions utilisées par la suite et après avoir motivé l'intérêt d'une nouvelle contrainte temps réel de latence, nous proposons un modèle qui formalise les systèmes temps réel avec contraintes de précédences, de périodicités et de latences. Dans ce modèle, les précédences sont définies par un graphe orienté acyclique infiniment répété. Pour le cas monoprocesseur, on étudie trois problèmes d'ordonnancement : celui des systèmes avec contraintes de précédences et de périodicités, celui des systèmes avec contraintes de précédences et de latences et enfin celui des systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème on étudie la cohérence entre les différentes contraintes, on donne des conditions d'ordonnançabilité et on propose un algorithme prouvé optimal dans le sens où s'il y a un ordonnancement, l'algorithme le trouvera. On passe ensuite au cas multiprocesseur où l'architecture est définie par un graphe non-orienté. On étudie trois problèmes d'implantation (distribution et ordonnancement) dans les mêmes cas qu'en monoprocesseur en tenant compte des temps de communications. On prouve que ces trois problèmes sont NP-difficiles et on propose, donc, des heuristiques. Les performances de chaque heuristique sont comparées à celles d'algorithme exacte de type "branch and bound", en utilisant des simulations numériques.

Nous présentons dans cette thèse une étude sur des<br />algorithmes distribués asynchrones et déterministes de<br />contröle. Un système distribué consiste en un réseau<br />de sites (processeurs, ordinateurs ou réseaux locaux). Dans cette<br />thèse, nous ne considérons que des réseaux de sites<br />communicants n'ayant ni mémoire partagée ni horloge globale.<br />De nombreux problèmes de l'algorithmique distribuée sont<br />réductibles à la construction d'un Arbre Couvrant qui est la<br />structure de contrôle qui nous intéresse.<br /><br />Nous étudions deux types d'algorithmes~: ceux utilisant<br />la notion de phase logique et les autres qui ne considèrent aucun<br />mécanisme de synchronisation. Ces derniers ont des comportements<br />imprévisibles améliorant la tolérance aux fautes. Nous<br />présentons un nouvel algorithme de ce type associé à une<br />élection qui n'est pas une recherche d'extremum contrairement<br />à l'usage. Cet algorithme est comparable au meilleur<br />algorithme connu qui utilise des jetons et des phases logiques<br />induisant un comportement plus "séquentiel".<br /><br />D'autres algorithmes, construisant des AC contraints, sont<br />considérés. En particulier l'AC de Diamètre Minimum qui<br />est, à notre connaissance, un problème qui n'a jamais<br />été étudié dans ce domaine. Le diamètre d'un<br />graphe est la somme des poids des arêtes du plus long des plus<br />courts chemins. Si nous considérons la complexité temporelle,<br />cette contrainte est d'un intérêt &vident. Nous proposons<br />différents algorithmes suivant que la tolérance aux fautes est<br />nécessaire ou non.<br /><br />Finalement, l'étude pratique des algorithmes distribués sur<br />des réseaux de grande taille nous a conduit à la construction<br />d'un simulateur. Il permet l'exécution d'un même code source<br />sur des machines séquentielles ou parallèles.