| Resumé |
Cette thèse présente trois travaux liés à la conception d'algorithmes efficaces applicables à des graphes de grande taille. Dans le premier travail, nous nous plaçons dans le cadre du calcul centralisé, et ainsi la question de la généralisation des décompositions modulaires et de la conception d'un algorithme efficace pour ce problème. La décomposition modulaire et la détection de module, sont des moyens de révéler et d'analyser les propriétés modulaires de données structurées. Comme la décomposition modulaire classique est bien étudiée et possède un algorithme de temps linéaire optimal, nous étudions d'abord les généralisations de ces concepts en hypergraphes. C'est un sujet peu étudié mais qui permet de trouver de nouvelles structurations dans les familles de parties. Nous présentons ici des résultats positifs obtenus pour trois définitions de la décomposition modulaire dans les hypergraphes de la littérature. Nous considérons également la généralisation en permettant des erreurs dans les modules de graphes classiques et présentons des résultats négatifs pour deux telles définitions. Le deuxième travail est sur des requêtes de données dans un graphe. Ici, le modèle diffère des scénarios classiques dans le sens que nous ne concevons pas d'algorithmes pour résoudre un problème original, mais nous supposons qu'il existe un oracle fournissant des informations partielles sur la solution de problème initial, où les oracle ont une consommation de temps ou de ressources de requête que nous modélisons en tant que coûts, et nous avons besoin d'un algorithme décidant comment interroger efficacement l'oracle pour obtenir la solution exacte au problème initial. L'efficacité ici concerne le coût de la requête. Nous étudions un problème de la méthode de dichotomie généralisée pour lequel nous calculons une stratégie d'interrogation efficace afin de trouver une cible cachée dans le graphe. Nous présentons les résultats de nos travaux sur l'approximation de la stratégie optimale de recherche en dichotomie généralisée sur les arbres pondérés. Notre troisième travail est sur la question de l'efficacité de la mémoire. La configuration dans laquelle nous étudions sont des calculs distribués et avec la limitation en mémoire. Plus précisément, chaque nœud stocke ses données locales en échangeant des données par transmission de messages et est en mesure de procéder à des calculs locaux. Ceci est similaire au modèle LOCAL / CONGEST en calcul distribué, mais notre modèle requiert en outre que chaque nœud ne puisse stocker qu'un nombre constant de variables w.r.t. son degré. Ce modèle peut également décrire des algorithmes naturels. Nous implémentons une procédure existante de repondération multiplicative pour approximer le problème de flux maximal sur ce modèle. D'un point de vue méthodologique, les trois types d'efficacité que nous avons étudiées correspondent aux trois types de scénarios suivants: - Le premier est le plus classique. Considérant un problème, nous essayons de concevoir à la main l'algorithme le plus efficace. - Dans le second, l'efficacité est considérée comme un objectif. Nous modélisons les coûts de requête comme une fonction objectif, et utilisons des techniques d'algorithme d'approximation pour obtenir la conception d'une stratégie efficace. - Dans le troisième, l'efficacité est en fait posée comme une contrainte de mémoire et nous concevons un algorithme sous cette contrainte. |