.

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

.

Le modèle multigraphe. Les principales étapes et l'objectif du processus de conception de systèmes de bases de données. La transformation d'un ensemble de relations en une structure réseau de type SOCRATE ou CODASYL. La mise en œuvre à partir du modèle multigraphe du processus de transformation d'un ensemble de relation en une structure réseau en termes de SGDB actuels.

.

.

Les entreprises se focalisent de plus en plus sur les aspects organisationnels qui leur permettent de se structurer en processus complexes. ainsi, de nouveaux besoins apparaissent pour mieux définnir, coordonner et contrôler les équipes et les activités coopératives. L'objet de cette étude est la définition d'un cadre qui permette d'assister le travail coopératif en apportant aux acteurs une aide à la coopération et à l'activité de groupe. La définition de ce cadre s'inspire de la démarche d'amélioration de processus du CMM (Capability Maturity Model), repris par l'ISO 15504 (ISO SPICE). L'approche est décomposée en 4 axes qui correspondent aux actions progressives à mettre en oeuvre pour définir une organisation adéquate des activités coopératives. L'axe 1 concerne la structuration des activités : analyse des dépendances entre activités, regroupement et/ou décomposition en tâches, planification des groupes de travail. L'axe 2 concerne la caractérisation des activités en fonction des interactions dans les groupes de travail : définition des rôles interactionnels et gestion des interfaces entre groupes de travail. L'axe 3 concerne l'évaluation d'une organisation de travail en fonction du nombre d'itérations entre activités : estimation des durées, charges et coûts. L'axe 4 concerne l'optimisation d'une organisation de travail en fonction des résultats d'évaluation : mise en œuvre de différentes solutions d'organisation et d'exécution des activités. Des méthodes principalement issues de la théorie des graphes et des techniques de partitionnement et d'évaluation de performance sont proposées en support dans chaque axe. Un outil logiciel mettant en œuvre ces propositions a été développé. Il permet d'analyser, de décomposer et d'évaluer des processus complexes, ce qui en fait un support efficace pour l'aide à la décision en management, le contrôle dynamique des processus coopératifs, pour la définition et la reconfiguration d'architecture informatique ...

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.

Les cartes sont des objets combinatoires apparaissant en physique comme discrétisation naturelle des surfaces aléatoires employées pour la gravité quantique bidimensionnelle ou la théorie des cordes, ainsi que dans les modèles de matrices. Après rappel de ces relations, nous établissons des correspondances entre diverses classes de cartes et d'arbres, autres objets combinatoires de structure simple. Un premier intérêt mathématique de ces constructions est de donner des preuves bijectives, élémentaires et rigoureuses, de plusieurs résultats d'énumération de cartes. Par ailleurs, nous accédons ainsi à une information fine sur la géométrie intrinsèque des cartes, conduisant à des résultats analytiques exacts grâce à une propriété inattendue d'intégrabilité. Nous abordons enfin la question de l'existence d'une limite continue universelle.