Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.

Il existe de nombreux démonstrateurs automatiques qui effectuent des raisonnements modulo une théorie équationnelle, c'est-à-dire enconsidérant non pas des termes, mais des classes d'équivalence de termes. En général, les travaux accomplis dans ce domaine ont pour but de concevoir des techniques pour faire de la déduction modulo une théorie particulière. Dans [Avenhaus & Plaisted, 2001], Jürgen Avenhaus et David Plaisted ont cherché à déterminer des techniques qui pourraient être employées dans le traitement non plus d'une théorie particulière, mais de toute une classe de théories équationnelles: les théories permutatives. Les auteurs ont introduit les notions de terme stratifié et d'ensemble stratifié, et décrit les procédures qui devraient être implémentées dans un démonstrateur automatique basé sur ces termes stratifiés. Les propriétés de régularité de ces théories font qu'il est possible d'employer des techniques efficaces de théorie algorithmique des groupes pour les traiter. Les auteurs espéraient que l'efficacité de ces techniques contrebalancerait le nombre élevé de clauses qui pourraient être générées dans un démonstrateur automatique basé sur ces termes stratifiés. Cependant, les algorithmes proposés pour faire de la déduction avec des termes stratifiés sont basés sur une énumération explicite des éléments des groupes, et sont donc exponentiels. Dans ce mémoire, nous développons les travaux d'Avenhaus et Plaisted, et modifions leur formalisme pour pouvoir faire l'usage le plus intensif possible des techniques de théorie algorithmique des groupes.

Ce travail porte sur la verification formelle de programmes paralleles. Parmi les methodes habituellement utilisees, nous nous interessons aux methodes basees sur la construction d'un modele du programme a verifier; la verification proprement dite s'effectue sur ce modele. Cette approche est limitee par l'explosion de la taille du modele, des que le programme traite est de complexite realiste. Notre but est l'etude et la mise en oeuvre de techniques permettant d'effectuer la verification malgre cette explosion. Les techniques que nous presentons sont liees par une caracteristique commune : l'utilisation de methodes symboliques de representation du modele. Nous etudions en premier lieu des techniques de reduction de modeles. Ces reductions s'operent par rapport a des relations d'equivalence basees sur la notion de bisimulation. Nous etudions en particulier un algorithme de minimisation de modele (\em pendant ) sa generation(Generation de Modele Minimal). Dans une seconde partie, nous nous interessons a deux techniques symboliques de representation de modeles. Il s'agit d'une part de Graphes de Decision Binaires, qui permettent la manipulation efficace de formules booleennes, et d'autre part de systemes d'inequations lineaires, connus sous le nom de polyedres convexes, pour la manipulation de variables entieres. L'utilisation de ces techniques permet de representer et manipuler des modeles de taille souvent prohibitive pour des methodes enumeratives classiques. Nous presentons la mise en oeuvre de methodes de comparaison et reduction de modeles aves les Graphes de Decision Binaires, avec en particulier l'algorithme de Generation de Modele Minimal. L'application de l'outil correspondant a plusieurs exemples de programmes lotos a permis de montrer l'interet, mais aussi les limites de l'utilisation de cette representation symbolique. Enfin, nous presentons une methode d'analyse statique de protocoles, basee sur l'utilisation des polyedres convexes. Cette analyse permet le calcul d'approximations superieures d'invariants du programme et de verifier la veracite de proprietes definies en termes de variables du programme.

Nous présentons une nouvelle méthode pour exploiter la relation entre différents niveaux de représentation d'image afin de compléter le modèle de graphe visuel. Le modèle de graphe visuel est une extension du modèle de langue classique en recherche d'information. Nous utilisons des régions d'images et des points d'intérêts (associées automatiquement à des concepts visuels), ainsi que des relations entre ces concepts, lors de la construction de la représentation sous forme de graphe. Les résultats obtenus sur catégorisation de la collection RobotVision de la compétition d'ImageCLEF 2009 et la collection STOIC-101 montrent que (a) la procédure de l'induction automatique des concepts d'une image est efficace, et (b) l'utilisation des relations spatiales entre deux niveaux de représentation, en plus de concepts, permet d'améliorer le taux de reconnaissance.

Les services Web sont des briques de bases logicielles s‟affranchissant de toute contrainte de compatibilité logicielle ou matérielle. Ils sont mis en oeuvre dans une architecture orientée service. A l‟heure actuelle, les travaux de recherche se concentrent principalement sur la découverte et la composition. Cependant, la complexité de la structure de l‟espace des services Web et son évolution doivent nécessairement être prises en compte. Ceci ne peut se concevoir sans faire appel à la science des systèmes complexes, et notamment à la théorie des réseaux complexes. Dans cette thèse, nous définissons un ensemble de réseaux pour la composition sur la base de services décrits dans des langages syntaxique (WSDL) et sémantique (SAWSDL). L‟exploration expérimentale de ces réseaux permet de mettre en évidence les propriétés caractéristiques des grands graphes de terrain (la propriété petit monde et la distribution sans échelle). On montre par ailleurs que ces réseaux possèdent une structure communautaire. Ce résultat permet d‟apporter une réponse alternative à la problématique de la classification de services selon les domaines d‟intérêts. En effet, les communautés regroupent non pas des services aux fonctionnalités similaires, mais des services qui ont en commun de nombreuses relations d‟interaction. Cette organisation peut être utilisée entre autres, afin de guider les algorithmes de recherche de compositions. De plus, en ce qui concerne la classification des services aux fonctionnalités similaires en vue de la découverte ou de la substitution, nous proposons un ensemble de modèles de réseaux pour les représentations syntaxique et sémantique des services, traduisant divers degrés de similitude. L‟analyse topologique de ces réseaux fait apparaître une structuration en composantes et une organisation interne des composantes autour de motifs élémentaires. Cette propriété permet une caractérisation à deux niveaux de la notion de communauté de services similaires, mettant ainsi en avant la souplesse de ce nouveau modèle d‟organisation. Ces travaux ouvrent de nouvelles perspectives dans les problématiques de l‟architecture orientée service.

L'application des mesures d'importance de type PageRank aux graphes du Web est le sujet de cette thèse, qui est divisée en deux parties. La première introduit une famille particulière de grands graphes, les graphes du Web. Elle commence par définir la notion de Web indexable, puis donne quelques considérations sur les tailles des portions de Web effectivement indexées. Pour finir, elle donne et utilise quelques constatations sur les structures que l'on peut observer sur les graphes induits par ces portions de Web. Ensuite, la seconde partie étudie en profondeur les mesures d'importance à la PageRank. Après un rappel sur la théorie des chaînes de Markov est présentée une classification originale des algorithmes de PageRank, qui part du modèle le plus simple jusqu'à prendre en compte toutes les spécificités liées aux graphes du Web. Enfin, de nouveaux algorithmes sont proposés. L'algorithme BackRank utilise un modèle alternatif de parcours du graphe du Web pour un calcul de PageRank plus rapide. La structure fortement clusterisée des graphes du Web permet quant à elle de décomposer le PageRank sur les sites Web, ce qui est réalisé par les algorithmes FlowRank et BlowRank.

Les travaux de cette thèse portent sur l'analyse syntaxique et sémantique de la phrase, en utilisant pour l'analyse syntaxique un formalisme grammatical lexicalisé polarisé et en prenant comme exemple les grammaires d'interaction. Dans les formalismes grammaticaux lexicalisés, les polarités permettent de contrôler explicitement la composition des structures syntaxiques. Nous exploitons d'abord le besoin de composition exprimé par certaines polarités pour définir une notion faible de réduction de grammaire applicable à toute grammaire lexicalisée polarisée. Nous étudions ensuite la première phase de l'analyse syntaxique des formalismes lexicalisés: l'étiquetage grammatical. Nous exploitons là encore le besoin de composition de certaines polarités pour concevoir trois méthodes symboliques de filtrage des étiquetages grammaticaux que nous implantons sur automate. Nous abordons enfin l'interface syntaxe-sémantique des formalismes lexicalisés. Nous montrons comment l'utilisation de la réécriture de graphes comme modèle de calcul permet concrètement d'utiliser des structures syntaxiques riches pour calculer des représentations sémantiques sous-spécifiées.

Les réseaux sont très largement utilisés dans de nombreux domaines scientifiques afin de représenter les interactions entre objets d'intérêt. Ainsi, en Biologie, les réseaux de régulation s'appliquent à décrire les mécanismes de régulation des gènes, à partir de facteurs de transcription, tandis que les réseaux métaboliques permettent de représenter des voies de réactions biochimiques. En sciences sociales, ils sont couramment utilisés pour représenter les interactions entre individus. Dans le cadre de cette thèse, nous nous intéressons à des méthodes d'apprentissage non supervisé dont l'objectif est de classer les noeuds d'un réseau en fonction de leurs connexions. Il existe une vaste littérature se référant à ce sujet et un nombre important d'algorithmes ont été proposés depuis les premiers travaux de Moreno en 1934. Notre point de départ est le modèle à blocs stochastiques, Stochastic Block Model (SBM) (Nowicki et Snijders, 2001) en anglais, qui permet la recherche de classes topologiques hétérogènes. Nous considérons un contexte Bayésien et proposons un algorithme de type variational Bayes pour approcher la loi a posteriori des paramètres. Cette approche permet d'obtenir un nouveau critère de sélection de modèles afin d'estimer le nombre de composantes dans un réseau. Par ailleurs, il apparaît que SBM ainsi que la plupart des modèles existants de classification sont limités puisqu'ils partitionnent les noeuds dans des classes disjointes. Or, de nombreux objets d'étude dans le cadre d'applications réelles sont connus pour appartenir à plusieurs groupes en même temps. Par exemple, en Biologie, des protéines appelées moonlighting proteins en anglais ont plusieurs fonctions dans les cellules. Nous introduisons donc un nouveau modèle de graphe aléatoire que nous appelons modèle à blocs stochastiques chevauchants, Overlapping Stochastic Block Model (OSBM) en anglais. Il autorise les noeuds d'un réseau à appartenir à plusieurs groupes simultanément et peut prendre en compte des topologies de connexion très différentes. Deux algorithmes d'estimation sont proposés ainsi qu'un critère de sélection de modèles.

Cette dernière décennie, la modélisation des villes 3D est devenue l'un des enjeux de la recherche multimédia et un axe important en reconnaissance d'objets. Dans cette thèse nous nous sommes intéressés à localiser différentes primitives, plus particulièrement les fenêtres, dans les façades de Paris. Dans un premier temps, nous présentons une analyse des façades et des différentes propriétés des fenêtres. Nous en déduisons et proposons ensuite un algorithme capable d'extraire automatiquement des hypothèses de fenêtres. Dans une deuxième partie, nous abordons l'extraction et la reconnaissance des primitives à l'aide d'appariement de graphes de contours. En effet une image de contours est lisible par l'oeil humain qui effectue un groupement perceptuel et distingue les entités présentes dans la scène. C'est ce mécanisme que nous avons cherché à reproduire. L'image est représentée sous la forme d'un graphe d'adjacence de segments de contours, valué par des informations d'orientation et de proximité des segments de contours. Pour la mise en correspondance inexacte des graphes, nous proposons plusieurs variantes d'une nouvelle similarité basée sur des ensembles de chemins tracés sur les graphes, capables d'effectuer les groupements des contours et robustes aux changements d'échelle. La similarité entre chemins prend en compte la similarité des ensembles de segments de contours et la similarité des régions définies par ces chemins. La sélection des images d'une base contenant un objet particulier s'effectue à l'aide d'un classifieur SVM ou kppv. La localisation des objets dans l'image utilise un système de vote à partir des chemins sélectionnés par l'algorithme d'appariement.

Les travaux présentés dans cette thèse portent sur l'exécution d'applications sur les environ- nements hétérogènes et distribués que sont les grilles de calcul. Nous étudions de bout en bout le processus permettant à des utilisateurs d'exécuter des applications scientifiques complexes. Les contributions de cette thèse se situent donc à plusieurs niveaux. 1) Déploiement d'inter- giciel hiérarchique : nous proposons dans un premier temps un modèle d'exécution pour les intergiciels hiérarchiques. À partir de ce modèle, nous présentons plusieurs heuristiques pour définir automatiquement la meilleure hiérarchie en fonction des exigences des utilisateurs et du type de plate-forme. Nous évaluons la qualité de ces heuristiques en conditions réelles avec l'intergiciel Diet. 2) Partitionnement de graphe : nous proposons un algorithme distribué et auto-stabilisant pour partitionner un graphe quelconque ayant des arêtes pondérées entre les nœuds. Le partitionnement est réalisé en fonction des distances pondérées entre les nœuds et forme des grappes au sein desquelles les nœuds sont à une distance maximale k d'un nœud élu dans la grappe. 3) Ordonnancement : nous étudions l'ordonnancement de tâches indépen- dantes sous des contraintes de limitation d'utilisation des ressources. Nous définissons des formulations en programme linéaire pour résoudre ce problème dans deux cas : lorsque les tâches arrivent toutes en même temps et lorsqu'elles ont des dates d'arrivée. 4) Simulations cosmologiques : nous avons étudié le comportement d'applications nécessaires à l'exécution de workflows de simulations cosmologiques. Puis, en se basant sur l'intergiciel de grille Diet, nous avons mis en place une infrastructure complète permettant à des utilisateurs non expérimentés de soumettre facilement des simulations cosmologiques sur une grille de calcul.