▼ 

Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits.

Graphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the…

Advisors/Committee Members: Trotignon, Nicolas (thesis director).

▼ 

La puissance de calcul des plus grands calculateurs ne fait qu'augmenter: de quelques centaines de cœurs de calculs dans les années 1990, on en est maintenant à plusieurs millions! Leur infrastructure évolue aussi: elle n'est plus linéaire, mais complètement hiérarchique. Les applications de calcul intensif, largement utilisées par la communauté scientifique, doivent donc se munir d'outils permettant d'utiliser pleinement l'ensemble de ces ressources de manière efficace. La simulation numérique repose bien souvent sur d'importants calculs dont le coût, en termes de temps et d'accès mémoire, peut fortement varier au cours du temps: on parle de charge de calcul variable. Dans cette Thèse, on se propose d'étudier les outils actuels de répartition des données et des calculs, afin de voir les raisons qui font que de tels outils ne sont pas pleinement adaptés aux fortes variations de charge ainsi qu'à la hiérarchie toujours plus importante des nouveaux calculateurs. Nous proposerons alors un nouveau modèle d'ordonnancement et de partitionnement, basé sur des interactions physiques, particulièrement adapté aux applications basées sur des maillages réguliers et présentant de fortes variations de charge au cours du temps. Nous validerons alors ce modèle en le comparant à des outils de partitionnement de graphes reconnus et largement utilisés, et verrons les raisons qui le rendent plus performant pour des applications aussi bien parallèles que distribuées. Enfin, nous proposerons une interface nous permettant d'utiliser cette méthode d'ordonnancement dans des calculateurs toujours plus hiérarchiques.

Computing capability of largest computing centers is still increasing: from a few hundred of cores in the90's, they can now exceed several million of cores! Their infrastructure also evolves: it is no longerlinear, but fully hierarchical.High Performance applications, well used by the scientific community, require on tools that allow themto efficiently and fully use computing resources.Numerical simulations mostly rely on large computations chains for which the cost (computing load), either acomputing time or a memory access time, can strongly vary over time: it is referred to as dynamic computing loadevolution.In this thesis, we propose to study actual data partitioning and computing scheduling tools, and to explore theirlimitations with regards to strong and repetitive load variation as well as the still increasing cluster hierarchy.We will then propose a new scheduling and partitioning model, based on physical interactions, particularlysuitable to regular mesh based applications that produce strong computing load variations over time.We will then compare our model against well-known and widely used graph partitioning tools and we will see thereasons that make this model more reliable for such parallel and distributed applications.Lastly, we will propose a multi-level scheduling interface that is specially designed to allow to use ourmodel in even more hierarchical clusters.

Advisors/Committee Members: Bouché, Daniel (thesis director).

▼ 

Dans cette thèse nous avons étudié la diffusion de l'information dans les grands graphes de terrain, en se focalisant sur les patterns structurels de la propagation. Sur le plan empirique, il s'est avéré difficile de capturer la structure des cascades de diffusion en termes de mesures simples. Sur le plan théorique, l'approche classique consiste à étudier des modèles stochastiques de contagion. Néanmoins, l'analyse formelle de ces modèles reste limité, car les graphes de terrain ont généralement une topologie complexe et le processus de diffusion se produit dans une fenêtre de temps limitée. Par conséquent, une meilleure compréhension des données empiriques, des modèles théoriques et du lien entre les deux est également cruciale pour la caractérisation de la diffusion dans les grands graphes de terrain. Après un état de l'art sur les graphes de terrain et la diffusion dans ce contexte au premier chapitre, nous décrivons notre jeu de données et discutons sa pertinence au chapitre 2. Ensuite, dans le chapitre 3, nous évaluons la pertinence du modèle SIR simple et de deux extensions qui prennent en compte des hétérogénéités de notre jeu de données. Dans le chapitre 4, nous explorons la prise en compte du temps dans l'évolution du réseau sous-jacent et dans le modèle de diffusion. Dans le chapitre 5, nous évaluons l'impacte de la structure du graphe sous-jacent sur la structure des cascades de diffusion générées avec les modèles étudiés dans les chapitres précédents. Nous terminons la thèse par un bilan des résultats et des perspectives ouvertes par les travaux menés dans cette thèse.

Understanding information diffusion on complex networks is a key issue from a theoretical and applied perspective. Epidemiology-inspired SIR models have been proposed to model information diffusion. Recent papers have analyzed this question from a data-driven perspective. We complement these findings investigating if epidemic models calibrate with a systematic procedure are capable of reproducing key spreading cascade properties. We first identify a large-scale, rich dataset from which we can reconstruct the diffusion trail and the underlying network. Secondly, we examine the simple SIR model as a baseline model and conclude that it was unable to generate structurally realistic spreading cascades. We found the same result examining model extensions to which take into account heterogeneities observed in the data. In contrast, other models which take into account time patterns available in the data generate qualitatively more similar cascades. Although one key property was not reproduced in any model, this result highlights the importance of taking time patterns into account. We have also analyzed the impact of the underlying network structure on the models examined. In our data the observed cascades were constrained in time, so we could not rely on the theoretical results relating the asymptotic behavior of the epidemic and network topological features. Performing simulations we assessed the impact of these common topological properties…

Advisors/Committee Members: Latapy, Matthieu (thesis director), Tarissan, Fabien (thesis director).

▼ 

La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielle.

The class of P5-free graphs, namely the graphs without induced chains with five vertices, is of particular interest in graph theory. Indeed, it is the smallest class defined by only one forbidden connected induced subgraph for which the complexity of the Maximum Independent Set problem is unknown. This problem has many applications in planning, CPU register allocation, molecular biology... In this thesis, we first give a complete state of art of the methods used to solve the problem in P5-free graphs subclasses; then we study and solve this problem in a particular subclass, the class of 3-colorable P5-free graphs. We also bring solutions to recognition and coloring problems of these graphs, each time in linear time. Finally, we define, characterize, and are able to recognize "chain-probe" graphs, namely the graphs for which we can add edges between particular vertices such that the resulting graph is bipartite and P5-free. Problems of this type come from genetics and have application in I.A.

Advisors/Committee Members: Szigeti, Zoltán (thesis director), Maffray, Frédéric (thesis director).

▼ 

Au cours des quinze dernières années, le développement de plateformes embarquées intelligentes et les progrès des protocoles de communication radio ont permis l'émergence de réseaux de capteurs sans-fils (WSN). D'autre part, la démocratisation d'Internet et du Web, ainsi que l'augmentation des débits ont contribué à l'essor d'un nouveau paradigme : le Cloud computing. L'Internet des Objets, (IoT) ou Internet des Objets réalise la convergence entre les réseaux de capteurs et le Cloud computing. De nombreux travaux adressant les problématiques de l'IoT ont étés menés ces dix dernières années, cependant ces propositions manquent ne tiennent pas suffisamment compte des problématiques de sécurité et de protection des données. D'après Gartner, 70 % des plateformes déployées ne disposent pas d'une solution de sécurité efficace, les rendant vulnérables aux attaques. Dans le domaine des monnaies numériques, Bitcoin propose en son sein une nouvelle structure de données authentifiée et trustless permettant la décentralisation de l'enregistrement de transactions en s'appuyant sur un protocole permettant d'obtenir un consensus : la blockchain. Cette thèse se focalise sur l'utilisation de cette nouvelle structure de données dans les WSN dans un contexte IoT, comme base pour la définition d'une architecture sécurisée et adaptative basée sur la blockchain. Le but de cette architecture est d'intégrer les solutions existantes pour l'organisation du réseau et l'accès aux services de manière innovante afin de réaliser l'intégration des WSN avec l'infrastructure web; mais aussi d'y adjoindre une solution répondant aux nouveaux besoins de sécurités et contraintes spécifiques des réseaux de capteurs. Nous proposons pour cela un framework nommé Network Service Loader (NSL) en charge de la gestion de services et d'agents mobiles, auquel s'adjoint notre solution Blockchain Authentication and Trust Module (BATM) en charge de l'authentification, du contrôle d'accès, ainsi que des évaluations de confiance via l'algorithme Maximum Likelihood Trust Estimator (MLTE).

During the last fifteen years, the rise of smart and wireless enabled embedded devices lead to the development of wireless sensor networks (WSN). In the same time, the emerging of Cloud computing with the development of the Internet and the Web as an everyday technology thanks to the rise of bandwidth and processing power leads to new network paradigms. The Internet of Things (IoT) primary goal is to bridge the gap between these technologies and bring WSN sensing and actuating abilities to Cloud applications. We count a significant amount of work targetting the IoT in the last decade, however they lack proper solutions to ensure data privacy and security. Gartner investigations shows that 70 % of connected and smart devices provide little or no security policies and solutions, making both user and devices vulnerable to attackers. In the field of digital currencies, Bitcoin proposed a new authenticated and trustless data structure dedicated to transactions logging in a decentralized…

Advisors/Committee Members: Baril, Jean-Luc (thesis director), Darties, Benoît (thesis director).

▼ 

Le problème des singularités en relativité générale remonte à la première solution exacte de la théorie obtenue en 1915, à savoir celle du trou noir de Schwarzschild. Qu'elles soient de coordonnée ou de courbure, ces singularités ont longtemps questionné les physiciens qui parvinrent à mieux les caractériser à la fin des années 1960. Cela conduisit aux fameux théorèmes sur les singularités, s'appliquant à la fois aux trous noirs et en cosmologie, basés sur un comportement classique du contenu en matière de l'espace-temps résumé par des conditions d'énergie. La violation de ces conditions dans les processus quantiques pourrait indiquer que les singularités doivent être vues comme des limitations de la relativité générale, pouvant ainsi disparaître dans une théorie plus générale de la gravité quantique.Dans l'attente d'une telle théorie, nous avons pour objectif dans cette thèse d'étudier les espaces-temps de trous noirs dépourvus de toute singularité ainsi que leurs conséquences observationnelles. A cette fin, nous considérons à la fois des modifications de la relativité générale et le couplage de la théorie à des contenus en matière exotiques. Dans le premier cas nous montrons qu'il est possible de retrouver des trous noirs réguliers à symétrie sphérique connus, tout d'abord en principe avec la théorie tenseur-scalaire de gravité mimétique, puis implicitement par le biais d'une déformation de la contrainte hamiltonienne en relativité générale inspirée des techniques de gravitation quantique à boucles. Dans le second cas nous restons dans le cadre de la relativité générale, et considérons des tenseurs énergie-impulsion effectifs. Ils sont en premier lieu associés à un modèle régulier à la Hayward en rotation fournissant dans un certain régime un premier exemple de trou noir en rotation exempt de toute singularité, puis à un espace-temps dynamique décrivant la formation et l'évaporation d'un trou noir sans singularité. Pour ce dernier, nous montrons que tout modèle basé sur l'effondrement gravitationnel de coquilles de genre lumière visant à décrire l'évaporation de Hawking est voué à violer les conditions sur l'énergie dans une région non compacte de l'espace-temps. Enfin, l'étude théorique de la métrique de Hayward en rotation est accompagnée de simulations numériques d'un tel objet au centre de la Voie Lactée, obtenues à l'aide du code de calcul de trajectoires de particules Gyoto en reproduisant les propriétés connues de la structure d'accrétion du trou noir présumé Sgr A*. Ces simulations permettent d'illustrer deux régimes très différents de la métrique, avec ou sans horizon, et soulignent la difficulté d'affirmer avec certitude la présence d'un horizon à partir d'images en champ fort telles que celles obtenues par l'instrument Event Horizon Telescope.

The issue of singularities in General Relativity dates back to the very first solution to the equations of the theory, namely Schwarzschild's 1915 black hole. Whether they be of coordinate or curvature nature, these singularities have long puzzled physicists,…

Advisors/Committee Members: Langlois, David (thesis director).

▼ 

Nous proposons des méthodes pour caractériser efficacement les arêtes au sein de réseaux complexes. Dans les graphes simples, les nœuds sont liés par une sémantique unique, tels deux utilisateurs amis dans un réseau social. De plus, ces arêtes sont guidées par la similarité entre les nœuds (homophilie). Ainsi, les membres deviennent amis à cause de caractéristiques communes. En revanche, les réseaux complexes sont des graphes où chaque arête possède une sémantique parmi k possibles. Ces arêtes sont de plus basées à la fois sur une homophilie et une hétérophilie partielle. Cette information supplémentaire permet une analyse plus fine de graphes issus d’applications réelles. Cependant, elle peut être coûteuse à acquérir, ou même être indisponible. Nous abordons donc le problème d’inférer la sémantique des arêtes. Nous considérons d'abord les graphes dont les arêtes ont deux sémantiques opposées, et où seul une fraction des étiquettes est visibles. Ces «graphes signés» sont une façon élégante de représenter des interactions polarisées. Nous proposons deux biais d’apprentissage, adaptés respectivement aux graphes signés dirigés ou non, et plusieurs algorithmes utilisant la topologie du graphe pour résoudre un problème de classification binaire. Ensuite, nous traitons les graphes avec k > 2 sémantiques possibles. Dans ce cas, nous ne recevons pas d’étiquette d’arêtes, mais plutôt un vecteur de caractéristiques pour chaque nœud. Face à ce problème non supervisé, nous concevons un critère de qualité exprimant dans quelle mesure une k-partition des arêtes et k vecteurs sémantiques expliquent les arêtes observées. Nous optimisons ce critère sous forme vectorielle et matricielle.

We develop methods to efficiently and accurately characterize edges in complex networks. In simple graphs, nodes are connected by a single semantic. For instance, two users are friends in a social networks. Moreover, those connections are typically driven by node similarity, according to homophily. In the previous example, users become friends because of common features. By contrast, complex networks are graphs where every connection has one semantic among k possible ones. Those connections are moreover based on both partial homophily and heterophily of their endpoints. This additional information enable finer analysis of real world graphs. However, it can be expensive to acquire, or is sometimes not known beforehand. We address the problems of inferring edge semantics in various settings. First, we consider graphs where edges have two opposite semantics, and where we observe the label of some edges. These so-called signed graphs are a common way to represent polarized interactions. We propose two learning biases suited for directed and undirected signed graphs respectively. This leads us to design several algorithms leveraging the graph topology to solve a binary classification problem that we call edge sign prediction. Second, we consider graphs with k > 2 available semantics for edge. In that case of multilayer graphs, we are not provided with…

Advisors/Committee Members: Tommasi, Marc (thesis director), Vitale, Fabio (thesis director).

▼ 

Les systèmes ouverts reconfigurables sont aujourd'hui omniprésents dans le paysage informatique : réseaux mobiles, calculs et données dans “le nuage”, etc. Une particularité de ces systèmes est que leur topologie de communication évolue dynamiquement - nous parlerons de reconfiguration - en conséquence d'activités concurrentes internes ou externes. Les systèmes de transitions étiquetées pour les systèmes ouverts permettent de prendre en considération l'environnement extérieur de façon implicite.Les systèmes ouverts reconfigurables sont souvent modélisés par des formalismes inspirés ou dérivés du π-calcul. Le passage de nom permet de modéliser la dynamique des topologies de communication. Dans cette thèse, nous introduisons les π-graphs, une variante du π-calcul qui possède, entre autre, une interprétation graphique naturelle. De plus, le formalisme a été conçu pour servir de langage intermédiaire entre le π-calcul abstrait et des formalismes plus concrets, en particulier dans la famille des réseaux de Petri de haut-niveau.Nous proposons tout d'abord une traduction formelle et prouvée des π-graphes vers des réseaux de Petri de haut niveau supportés par des outils de modélisation et de vérification courants. Nous montrons que cette traduction peut-être élevée au rang d'isomorphisme entre les deux formalismes. Ainsi, les outils prototypes que nous avons développés dans le cadre des π-graphes peuvent travailler de concert avec des outils plus stables et plus généraux basés sur les réseaux de Petri.En se basant sur cette traduction bi-directionnelle, nous développons une extension de la logique temporelle linéaire (LTL) - la logique des systèmes ouverts reconfigurables - permettant de spécifier des propriétés portant sur la dynamique d'évolution de la topologie de communication dans le cadre d'environnements ouverts. Les propositions atomiques de cette logique caractérisent précisément les propriétés d'état des π-graphs.Un prototype d'outil a été développé dans le cadre de cette thèse pour valider expérimentalement l'approche proposée. Cet outil fournit un simulateur pour les modèles exprimés dans le formalisme des π-graphes. Ces modèles peuvent être compilés en réseaux de Petri de haut niveau et manipulés dans le cadre de l'outil SNAKES. Enfin, nous proposons une traduction de la logique des systèmes ouverts reconfigurables vers la logique de plus bas niveau supportée par le vérificateur de modèle NECO. Grâce à notre prévue constructive d'isomorphisme entre les π-graphes et leur traduction en réseaux de Petri, les contre-exemples générés pour les réseaux de Petri en cas d'invalidation de proposition par NECO peuvent être réinterprétées et expliquées dans les termes des π-graphes.

Today we witness the rapid spread of highly dynamic reconfigurable and distributed infrastructures that we group under the common name of open reconfigurable systems. The communication topology of those systems can dynamically change - or reconfigure - as a consequence of an internal or external concurrent activity. Labelled transition…

Advisors/Committee Members: Klaudel, Hanna (thesis director), Peschanski, Frédéric (thesis director).

▼ 

Depuis que les dimensions des nano-dispositifs ont atteint l’échelle nanométrique, la simulation quantique est devenue incontournable dans le domaine de la nanoélectronique. Parmi les différents phénomènes physiques, l’interaction électron-phonon représente un processus majeur limitant la mobilité des porteurs de charge à température ambiante. En combinant la théorie multibandes k.p avec le formalisme quantique des fonctions de Green hors-équilibre, nous avons étudié et comparé deux types de dispositifs double-grille dopés p: le transistor MOS «conventionnel» et celui dit «sans jonction». L’influence de l’orientation cristalline, du matériau semi-conducteur, de la longueur de grille et de l’épaisseur du substrat a été étudiée afin d’optimiser les performances de ces dispositifs aux dimensions ultimes. D’un point de vue plus fondamental, l’interaction avec les phonons est habituellement implémentée à partir de l’approche auto-cohérente de Born (SCBA). Nous avons exploré la validité des approches non auto-cohérentes numériquement moins coûteuse qui conservent le courant : Lowest Order Approximation (LOA). Une comparaison entre SCBA, LOA et son prolongement analytique (LOA+AC) en modèle multi-bande a été menée.

Device simulation has attracted large interest since the dimensions of electronic devices reached the nanoscale. Among the new physical phenomena observed we focus on interaction-induced effects. Particular emphasis is placed on electron-phonon interactions as it is one of the most important carrier mobility-limiting mechanisms in nanodevices. Using the k.p multiband theory combined with the Non-Equilibrium Green's Function formalism, we model 2 types of double-gate devices: p-type MOSFETs and junctionless p-type MOSFETs. The 2D architecture of the double-gate device enables us to investigate the influence of confinement in one direction, infinite propagation in the other direction and connection to semi-infinite reservoirs in the last one. Different crystallographic orientation, channel materials, gate lengths and channel widths are investigated. From a fundamental point of view, phonon scattering is usually implement via the so-called Self-Consistent Born Approximation (SCBA°. We explore the validity of a one shot current conserving method based on the Lowest Order Approximation (LOA). A comparison between SCBA, LOA and its analytic continuation (LOA+AC) in multiband models is discussed.

Advisors/Committee Members: Lannoo, Michel (thesis director).

▼ 

Dans le domaine de l'Optimisation Combinatoire, la résolution de manière optimale de problèmes de grande taille par le biais d'algorithmes Branch-and-Bound requiert un nombre très élevé de ressources de calcul. De nos jours, de telles ressources sont accessibles grâce aux grilles de calcul, composées de grappes de clusters réparties sur différents sites géographiques. Ces environnements parallèles posent de nombreux défis scientifiques, notamment en termes de passage à l'échelle, de la prise en compte de l'hétérogénéité des ressources ainsi qu'en termes de tolérance aux pannes. La plupart des approaches existantes pour l'algorithme Branch-and-Bound parallèle sont basées sur une architecture de type Maître-Esclave, où un processus maître répartit les tâches à accomplir auprès de processus esclaves en charge de les traiter. L'utilisation d'une telle entité centrale constitue un obstacle majeur en ce qui concerne le passage à l'échelle. Dans cette thèse, nous proposons de relever ces défis ainsi que de surmonter cet obstacle grâce à une approche innovante et complètement distribuée, basée sur une architecture Pair-à-Pair (P2P). Celle-ci repose sur un seul type de processus (le pair), qui a pour mission d'explorer son propre ensemble de tâches, de le partager avec d'autres pairs et de diffuser l'information globale. Nous définissons des mécanismes adaptés en lien avec l'algorithme Branch-and-Bound, qui traitent de la répartition de la charge, de la diffusion de la meilleure solution trouvée et de la détection de la terminaison des calculs. En plus de multiples expérimentations sur le problème d'ordonnancement du Flow-Shop sur la grille de calcul Grid'5000, nous proposons une preuve formelle de la correction de notre approche. Par ailleurs, nous traitons une problématique souvent ignorés dans les travaux relatifs au calcul P2P, qui est l'importance de la topologie du réseau P2P. Généralement, une topologie très simple est utilisée. Les résultats obtenus montrent que notre approche permet le déploiement de réseaux de calculs à de très grandes échelles, constitués potentiellement de centaines de milliers de coeurs de calcul. Notre dernière contribution consiste en une approche Pair-à-Pair tolérante aux pannes afin de prendre en compte la nature généralement très volatile des ressources de calcul. Les résultats obtenus prouvent la robustesse de l'approche dans des environnements à la fois réalistes et sujets à de nombreux dysfonctionnements.

In the field of Combinatorial Optimization, the resolution to optimality of large instances of optimization problems through the use of Branch-and-Bound algorithms require a huge amount of computational resources. Nowadays, such resources are available from computing grids, which are sets of computing nodes geographically distributed over multiple sites. These parallel environments introduces multiples challenges related to the scalability, the heterogeneity of resources and the fault tolerance. Most of the existing approaches for the Branch-and-Bound algorithm are based on the…

Advisors/Committee Members: Melab, Nouredine (thesis director), Derbel, Bilel (thesis director).

▼ 

Parmi les évolutions majeures de l'informatique, nous distinguons l'émergence des technologies mobiles sans fil. Le développement actuel de ces technologies permet de réaliser des communications ad-hoc directes entre de nombreux types d'entités mobiles, comme des véhicules, des robots terrestres ou des drones. Dans un réseau de tels équipements, l'ensemble des liens de communication qui existe à un instant donné dépend des distances entre les entités et la topologie du réseau change continuellement lorsque les entités se déplacent. Les hypothèses habituelles sur la connexité du réseau n'ont pas leur place ici, néanmoins, une autre forme de connexité appelée connexité temporelle est souvent disponible à travers le temps et l'espace. L'objectif de cette thèse a été de développer des algorithmes pour les flottes d'appareils dans le cas des réseaux tolérant aux délais (DTN). De manière simplifiée, les réseaux tolérants aux délais sont des réseaux pour lesquels certaines parties peuvent se retrouver isolées pendant un moment sans que cela pose problème. Nous nous intéressons, en particulier, au cas où ces appareils sont organisés sous la forme de groupes, et où la notion de groupe elle même survit à ces déconnexions transitoires. Ainsi, une grande partie de la thèse s'articule autour de la notion des groupes tolérant aux délais (groupe DTN). Dans notre cas cet éloignement est limité dans le temps et nous parlons alors de "diamètre temporel borné" au sein du groupe. Le fait de borner le diamètre temporel du groupe lui permet de distinguer entre l'éloignement temporaire d'un noeud et sa perte définitive (crash ou autre).

Among the major developments in computer science, we distinguish the emergence of mobile wireless technologies. The current development of these technologies allows for direct ad-hoc communications between many types of mobile entities, such as vehicles, land robots or drones. In a network of such devices, the set of communication links that exists at a given instant depends upon the distances between the entities. As a result, the topology of the network changes continuously as the entities move. The common assumption on connectivity may not be relevant in this case, but another kind of connectivity called temporal connectivity is often alvailable over time and space. The goal of this thesis has been the development of algorithms for fleets of mobile devices in the case of delay-tolerant networks. In a simpler way, the delay-tolerant networks are networks where some parts can be isolated during a certain time without problems. We are interested, in particular, in the case where the devices are organised as groups, and where the notion of group itself survives to these deconnections. Hence, a big part of this thesis relates to the notion of delay-tolerant groups (DTN groups). In our case, these deconnections are limited in time and we speak of a "bounded temporal diameter" within the group. The fact of limiting the temporal diameter of the group enables it to distinguish between temporary deconnections…

Advisors/Committee Members: Chaumette, Serge (thesis director), Johnen, Colette (thesis director).

▼ 

Nous étudions la clôture algébrique et définissable dans les groupes libres. Les résultats principaux peuvent être résumés comme suit. Nous montrons un résultat de constructibilité des groupes hyperboliques sans torsion au-dessus de la clôture algébrique d'un sous-ensemble engendrant un groupe non abélien. Nous avons cherché à comprendre la place qu'occupe la clôture algébrique acl_G(A) dans certaines décompositions de G. Nous avons étudié la possibilité de la généralisation de la méthode de Bestvina-Paulin dans d'autres directions, en considérant les groupes de type fini qui agissent d'une manière acylindrique (au sens de Bowditch) sur les graphes hyperboliques. Enfin, nous avons étudié les relations qui existent entre les différentes notions de clôture algébrique et entre la clôture algébrique et la clôture définissable

In Chapter 1 we give basics on combinatorial group theory, starting from free groups and proceeding with the fundamental constructions: free products, amalgamated free products and HNN extensions. We outline a synthesis of Bass-Serre theory, preceded by a survey on Cayley graphs and graphs of groups. After proving the main theorem of Bass-Serre theory, we present its application to the proof of Kurosh subgroup theorem. Subsequently we recall main definitions and properties of hyperbolic spaces. In Section 1.4 we define algebraic and definable closures and recall a few other notions of model theory related to saturation and homogeneity. The last section of Chapter 1 is devoted to asymptotic cones. In Chapter 2 we prove a theorem similar to Bestvina-Paulin theorem on the limit of a sequence of actions on hyperbolic graphs. Our setting is more general: we consider Bowditch-acylindrical actions on arbitrary hyperbolic graphs. We prove that edge stabilizers are (finite bounded)-by-abelian, that tripod stabilizers are finite bounded and that unstable edge stabilizers are finite bounded. In Chapter 3 we introduce the essential notions on limit groups, shortening argument and JSJ decompositions. In Chapter 4 we present the results on constructibility of a torsion-free hyperbolic group from the algebraic closure of a subgroup. Also we discuss constructibility of a free group from the existential algebraic closure of a subgroup. We obtain a bound to the rank of the algebraic and definable closures of subgroups in torsion-free hyperbolic groups. In Section 4.2 we prove some results about the position of algebraic closures in JSJ decompositions of torsion-free hyperbolic groups and other results for free groups. Finally, in Chapter 5 we answer the question about equality between algebraic and definable closure in a free group. A positive answer has been given for a free group F of rank smaller than 3. Instead, for free groups of rank strictly greater than 3 we found some counterexample. For the free group of rank 3 we found a necessary condition on the form of a possible counterexample.

Advisors/Committee Members: Ould Houcine, Abderezak (thesis director), Zambella, Domenico (thesis director).

▼ 

The classical field theory of Schwinger pair creation can be described using an effective Schrodinger equation with an inverted harmonic oscillator Hamiltonian. It is a well known fact that the inverted harmonic oscillator admits a canonical transformation to a Q.P type Berry-Keating Hamiltonian. In this thesis we demonstrate that the classical field theory of Schwinger pair creation has a hidden scale invariance described by the quantum mechanics of an attractive inverse square potential in the canonically rotated (Q,P) coordinates of the inverted harmonic oscillator. The quantum mechanics of the inverse square potential is well known because of the problem of fall to the center and the associated ambiguities in the boundary condition. It is also well known as a description of the physics of pair creation in the presence of an event horizon and black hole decay. We use point particle effective field theory (PPEFT) to derive the boundary condition which describes pair creation. This leads to the addition of an inevitable Dirac delta function with imaginary coupling to the inverse square potential, describing the physics of the source. This non-hermitian physics leads to the Klein paradox. The conservation loss is due to the charged pairs being produced during tunneling.

Thesis

Master of Science (MSc)

Advisors/Committee Members: O'Dell, Duncan, Physics.

▼ 

Les travaux exposés dans cette thèse portent sur une contribution aux techniques de projection de graphes, appliquées à la reconnaissance de formes, visant à tirer parti de la richesse des méthodes structurelles et de l’efficacité des outils statistiques. Nous présentons une nouvelle projection s’inscrivant dans la catégorie des sondages de graphes. La première contribution de cette thèse porte sur l’encapsulation de la topologie du graphe dans une représentation vectorielle, en s’appuyant sur le dénombrement de motifs (sous-graphes) issus d’un lexique généré indépendamment du contexte. Ces motifs permettent de minimiser les pertes de l’information topologique lors de la projection. La deuxième contribution porte sur l’intégration de l’information relative aux étiquettes au sein de notre projection par l’adjonction de leurs dénombrements. Aux problèmes liés à la nature et la variabilité des attributs, nous proposons deux solutions dans le but de constituer des classes d’étiquettes moins nombreuses. La première consiste à discrétiser les attributs numériques puis à les combiner. La deuxième vise à former ces classes par un partitionnement global de l’ensemble des étiquettes. Ces propositions sont ensuite évaluées sur différentes bases de graphes et dans différents contextes.

The work exposed in this thesis focuses on a contribution to techniques of graph embedding, applied to pattern recognition, aiming to take advantages of the richness of structural methods and the efficiency of statistical tools. We present a new embedding, joining the category of graph probing. The first contribution of this thesis deals with the embedding of the graph topology in a vectorial representation, based on the counting of patterns (subgraphs) stemming of a lexicon generated independently of the context. These patterns permit the minimization of losses of the topological information during the embedding. The second contribution focuses on the integration of the information related to labels inside our embedding by adding their counting. To deal with problems linked to the nature and the variability of the attributes, we suggest two solutions to reduce the number of label classes. The first one consists of discretizing numeral attributes and combining them The second one aims to build these classes by a global clustering on the set of labels. Then, these proposals are evaluated on different datasets of graphs and in different contexts.

Advisors/Committee Members: Ramel, Jean-Yves (thesis director), Héroux, Pierre (thesis director).

▼ 

Dans ce mémoire, nous utiliserons l’approche de Pólya pour dénombrer et énumérer des graphes répondant à certaines conditions. Nous étendons ensuite ce résultat pour des graphes plus spécifiques comme des réseaux, et des réseaux de type "feed-forward". Finalement, nous supposons ensuite que deux sommets d’un graphe puissent être connectés ou non, et étant donné une probabilité de connexion donnée, nous étudions, en tant que variables aléatoires, certaines propriétés que l’on aimerait retrouver parmi ces graphes. Le but de ce mémoire est donc d’étendre la portée du théorème de Pólya afin de dénombrer efficacement plusieurs familles de graphes. Le chapitre 1 servira à l’étude de ce théorème, des rappels nécessaires et suffisants de la théorie des groupes jusqu’à la démonstration du théorème de Pólya. Le chapitre 2 nous permettra de voir la flexibilité du résultat primordial développé au chapitre précédent. Finalement, au chapitre 3, nous abordons une approche plus probabiliste du problème d’énumération de graphes.

In this memoir, we use Pólya approach to count and enumerate graphs under a set of conditions. We then extend the reach of this result for some particular types of graphs, namely networks and feed forward networks. Finally, given probabilistic constraints, e.g. two nodes are connected with probability p, we find the probability that a random graph meets those constraints. The objective of this memoir is thus to remind necessary and sufficient notions of group theory in order to state and prove Pólya Enumeration Theorem, an extremely efficient theorem as for counting objects. We then use this result throughout chapter 2 to enumerate many types of graphs. Chapter 3 is where we get more probabilistic.

Advisors/Committee Members: Doyon, Nicolas.

▼ Dans ce mémoire nous nous intéressons au problème qui, étant donné un graphe simple G, interroge l'existence de sous-arbres induits de taille i ayant le plus grand nombre de feuilles. Un tel sous-arbre induit s'il existe est dit pleinement feuillu. Ce problème d'optimisation que nous nommons SAIPF pour sous-arbres induits pleinement feuillus, est associé au problème de décision SAIF, pour sous-arbres induits feuillus, que nous pouvons énoncer ainsi : étant donné un graphe simple G et deux entiers positifs i et f, est-ce qu'il existe un sous-arbre induit dans G avec i sommets et f, feuilles? Nous démontrons que ce problème est NP-complet dans le cas général, ce qui fait du problème SAIPF un problème NP-difficile. Ces problèmes n'étant probablement pas résolubles avec des algorithmes en temps polynomial, comme alternative, nous nous intéressons plutôt à des familles de graphes spécifiques où de tels algorithmes ont plus de chance d'exister. Nous considérons donc une sous-famille de graphes planaires, la famille particulière des graphes séries-parallèles, où le problème est "facile". Cette famille est définie récursivement par une succession de compositions en série ou en parallèle. Cette définition qui nous a permis, entre autres, de suivre la construction d'un graphe série-parallèle, nous a aussi permis d'énoncer un résultat essentiel de préservation d'optimalité dans ce processus de construction. Résultat qui a motivé et a inspiré la formulation d'équations récursives qui couvrent tous les cas possibles de construction de sous-arbres induits pleinement feuillus. Il s'avère que ces équations cachent des algorithmes de complexité temporelle polynomiale. Nous avons donc traduit ces équations en algorithmes qui prennent en paramètre d 'entrée la représentation arborescente d 'un graphe série-parallèle, appelée arbre de construction, et qui fournissent en sortie le nombre maximal de feuilles qu'un sous-arbre induit, s'il existe, peut réaliser pour un nombre de sommets donné. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Graphe série-parallèle, sous-arbre induit, feuille, pleinement feuillu, arbre de construction, graphe planaire

▼ 

Cette thèse est centrée sur l’étude d’équations issues de la théorie cinétique des gaz. Dans tous les problèmes qui y sont explorés, une analyse des problèmes linéaires ou linéarisés associés est réalisée d’un point de vue spectral et du point de vue des semi-groupes. A cela s’ajoute une analyse de la stabilité non linéaire lorsque le modèle est non linéaire. Plus précisément, dans une première partie, nous nous intéressons aux équations de Fokker-Planck fractionnaire et Boltzmann sans cut-off homogène en espace et nous prouvons un retour vers l’équilibre des solutions de ces équations avec un taux exponentiel dans des espaces de type L1 à poids polynomial. Concernant l’équation de Landau inhomogène en espace, nous développons une théorie de Cauchy de solutions perturbatives dans des espaces de type L2 avec différents poids (polynomiaux ou exponentiels) et nous prouvons également la stabilité exponentielle de ces solutions.Nous démontrons ensuite pour l’équation de Boltzmann inélastique inhomogène avec terme diffusif le même type de résultat dans des espaces L1 à poids polynomial dans un régime de faible inélasticité. Pour finir, nous étudions dans un cadre général et uniforme des modèles qui convergent vers l’équation de Fokker-Planck du point de vue de l’analyse spectrale et des semi-groupes.

The topic of this thesis is the study of models coming from kinetic theory. In all the problems that are addressed, the associated linear or linearized problem is analyzed from a spectral point of view and from the point of view of semigroups. Tothat, we add the study of the nonlinear stability when the equation is nonlinear. More precisely, to begin with, we treat the problem of trend to equilibrium for the fractional Fokker-Planck and Boltzmann without cut-off equations, proving an exponential decay to equilibrium in spaces of type L1 with polynomial weights. Concerning the inhomogeneous Landau equation, we develop a Cauchy theory of perturbative solutions in spaces of type L2 with various weights such as polynomial and exponential weights and we also prove the exponential stability of these solutions. Then, we prove similar results for the inhomogeneous inelastic diffusively driven Boltzmann equation in a small inelasticity regime in L1 spaces with polynomial weights. Finally, we study in the same and uniform framework from the spectral analysis point of view with a semigroup approach several Fokker-Planck equations which converge towards the classical one.

Advisors/Committee Members: Mischler, Stéphane (thesis director).

▼ Program debugging is a process to locate and fix the bugs or defects responsible for a symptom violation in a computer program, thus making it behave as expected. Pair programming is a methodology in which two programmers share the same employed device and environment, collaboratively working on the same design, algorithm, code, and test. Most academic effort in pair programming has been spent on how pair programmers design a program system and how they implement it, rather than on how they debug it. In our study, we recruited two kinds of groups, solo and pair, to perform a program-debugging task in a time-restricted lab session. Based on our collected study data, we carefully examined the performance and strategy differences between the solo and pair programmer. We found evidence that working collaboratively may more efficient, not only when programming, but also when debugging. Further more, we present several methodologies, that can be adopted during academic practice to help students improve their debugging skills.

▼ 

newlineThe objective of this research work is to formulate certain criteria to newlineanalyse stability of complex polynomials that arise in engineering systems In newlinegeneral a characteristic equation with real coefficients is employed for newlinestability analysis of a linear time invariant systems But certain class of newlineapplications like relative and aperiodic stability analysis in linear timeinvariant newlinecontinuous systems involves complex coefficient polynomials In the newlinecase of certain time delay systems as well as two dimensional systems the newlineanalysis is done with complex polynomials The applications of complex newlinepolynomials also arise in case of nonlinear systems and systems with newlineinduction machines newlineIn this thesis two different algebraic schemes are formulated to handle newlinethe complex polynomials for analysing system stability In both the schemes newlinetermed as Sign Pair Criteria SPC I and SPC II Routh like table is developed newlineand the elements in the first column are utilized for stability analysis In the newlineproposed first scheme the first two rows are formed directly using complex newlinecoefficients while in the second scheme the real and imaginary parts of the newlinegiven complex polynomial are separated and the coefficients of real and newlineimaginary parts are entered in the first two rows of Routh like table newlineThese two sign pair criteria are applied to linear time invariant newlinecontinuous systems represented by complex polynomials having onedimension newlineas well as two dimensions for inferring stable and unstable newlinesituation including certain design problem newline newline

reference p168-178.

Advisors/Committee Members: Sivanandam S N.

▼ Ion-pair behavior describes the partial association of oppositely charged ions in electrolyte solutions. Previous study mainly focused on the ion-pair behavior between simple ions, such as ion pairing in NaCl solution as well as ion-pair interactions in supramolecular complexes and biological associations. However, very few attentions have been placed on the solution system with particle sizes in between.Recently, a group of well-defined, huge anionic cluster named polyoxometalates (POMs) have been synthesized and well characterized. The size of POMs is around nanometer scale, which is exactly between simple ions and large colloids. The solution behavior for POMs is much different form simple electrolyte solutions or large colloids. As a result, it is interesting to study the ion-pair behavior for POMs in solution. Herein, ion-pairs between Lacunary Keggin type POMs and alkali metal cations are investigated. The result showed that ion-pairs are formed between alkali cations and the “pocket” area on the surface of Lacunary Keggin type POMs – K7PW11O39. Electrostatic interaction and the entropy gain during the solvation shell lost were considered major driving forces during the ion-pair formation. Smaller alkali cations (e.g., Li+ and Na+) tended to form contact ion-pair (CIP) which result in an elevated enthalpy change measured by Isothermal Titration Calorimetry (ITC). Larger alkali cations (e.g., Rb+ and Cs+) favored a loose type of ion-pair – solvent separated ion-pair (2SIP) and solvent shared ion-pair (SIP). Size exclusion between the “pocket” area on K7PW11O39 POM surface and alkali cation also played a significant role in determining the ion-pair structure. Results were further confirmed by Nuclear Magnetic Resonance Spectroscopy (NMR). Advisors/Committee Members: Liu, Tianbo (Advisor).

▼ 

La solution des équations d'Einstein–Maxwell décrivant le trou noir le plus général a été découverte par Plebański et Demiański en 1976. Cette thèse accomplit plusieurs étapes en vue d'intégrer une généralisation de cette solution en supergravité jaugée N = 2. Le contenu bosonique de cette dernière comprend la métrique assortie de champs de jauge et de deux types de champs scalaires (appelés scalaires-vecteurs et hyperscalaires); cela implique qu'il est beaucoup plus compliqué de trouver une solution générale et l'on doit se restreindre à des classes particulières de solutions ou bien utiliser des algorithmes pour générer des solutions.Dans la première partie de cette thèse nous approchons ce problème grâce à la première stratégie en nous restreignant aux solutions BPS.Dans un premier temps nous étudions les jaugeages abéliens qui impliquent les hyperscalaires afin de comprendre quelles sont les conditions nécessaires pour obtenir des vides N = 2 adS4 ainsi que des géométries de proche-horizon associées à des trous noirs statiques.Par la suite nous décrivons une solution générale et analytique pour des trous noirs (extrémaux) 1/4-BPS qui possèdent une masse, une charge de NUT, des charges dyoniques et des champs scalaires non-triviaux dans le contexte de la supergravité N = 2 jaugée à la Fayet–Iliopoulos.Dans la seconde partie nous obtenons une extension de l'algorithme de Janis-Newman afin de prendre en compte tous les champs bosoniques de spin inférieur à 2, les horizons topologiques et le cas des autres dimensions.Ainsi cela met à disposition tous les outils nécessaires pour appliquer cet algorithme à la supergravité (jaugée ou non).

The most general black hole solution of Einstein–Maxwell theory has been discovered by Plebański and Demiański in 1976.This thesis provides several steps towards generalizing this solution by embedding it into N = 2 gauged supergravity.The (bosonic fields of the) latter consists in the metric together with gauge fields and two kinds of scalar fields (vector scalars and hyperscalars); as a consequence finding a general solution is involved and one needs to focus on specific subclasses of solutions or to rely on solution generating algorithms. In the first part of the thesis we approach the problem using the first strategy: we restrict our attention to BPS solutions, relying on a symplectic covariant formalism. First we study the possible Abelian gaugings involving the hyperscalars in order to understand which are the necessary conditions for obtaining N = 2 adS4 vacua and near-horizon geometries associated to the asymptotics of static black holes.A preliminary step is to obtain covariant expressions for the Killing vectors of symmetric special quaternionic-Kähler manifolds. Then we describe a general analytic solutions for 1/4-BPS (extremal) black holes with mass, NUT, dyonic charges and running scalars in N = 2 Fayet–Iliopoulos gauged supergravity with a symmetric very special Kähler manifold. In the second part we provide an extension of the Janis–Newman algorithm to all bosonic…

Advisors/Committee Members: Halmagyi, Nick (thesis director).

▼ 

La télémédecine consiste en la pratique d’actes médicaux à distance par l’usage des nouvelles technologies de l’information et de la communication. Parmi ces actes médicaux, nous nous sommes intéressés à la téléexpertise qui est une sorte d’activité collaborative consistant aux recueils d’avis d’experts médicaux face à un problème de santé donné. Dans notre travail, nous avons fait le choix de modéliser ces activités collaboratives par le système d’argumentation de Dung basé sur des fondements mathématiques et qui permet d’illustrer les interactions entre les différentes parties prenantes et par la même occasion fournir des outils mathématiques de prises de décisions. Nous avons opté pour une modélisation sémantique avec des graphes conceptuels car l’un de nos objectifs est de garantir une interopérabilité sémantique. Cette modélisation peut inclure souvent des incohérences (mauvaises relations d’attaques dans le système d’argumentation) qui seront vérifiées par l’usage des contraintes en graphes conceptuels. Pour résoudre ces problèmes d’incohérences deux solutions majeures ont été proposées : (i) la pondération des arguments des différents professionnels de santé, (ii) la modélisation de quelques aspects de droit médical comme contraintes. Ce travail démontre une application informatique du raisonnement logique dans un cadre médical judiciaire où il apporte des éclairages sur la vérification d’information, l’argumentation et l’interaction. Il vise ainsi à garantir une bonne collaboration dans le but de se prémunir d’éventuelles conséquences financières et juridiques.

Telemedicine involves the practice of medical procedures remotely through the use of new information and communications technology. Among these medical procedures, we looked at the tele-expertise which is a kind of collaborative activity consisting of collecting the opinions of medical experts facing a particular health problem. In our work, we have chosen to model these collaborative activities by Dung argumentation system based on mathematical foundations and illustrates the interactions between the different stakeholders and at the same time provides mathematical tools decisions. We opted for a semantic modeling with conceptual graphs as one of our objectives is to ensure semantic interoperability. This modeling can often include inconsistencies (poor relations of attacks in argumentation system) which will be verified by the use of constraints in conceptual graphs. To solve these inconsistency problems, two major solutions have been proposed : (i) the weight of the arguments of different health professionals, (ii) modeling some aspects of medical law as constraints. This work demonstrates a computer application of logical reasoning in a judicial medical setting where it sheds light on the verification of information, argumentation and interaction. It aims to ensure good cooperation in order to guard against possible financial and legal consequences.

Advisors/Committee Members: Kamsu-Foguem, Bernard (thesis director), Kenfack, Hugues (thesis director).

▼ 

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.

An oriented graph is a directed graph with no cycle of length at most two. A homomorphism of an oriented graph to another oriented graph is an arc preserving vertex mapping. To push a vertex is to switch the direction of the arcs incident to it. An orientable graph is an equivalence class of oriented graph with respect to the push operation. An orientable graph [−→G] admits a homomorphism to an orientable graph [−→H] if an element of [−→G] admits a homomorphism to an element of [−→H]. A signified graph (G, Σ) is a graph whose edges are assigned either a positive sign or a negative sign, while Σ denotes the set of edges with negative signs assigned to them. A homomorphism of a signified graph to another signified graph is a vertex mapping such that the image of a positive edge is a positive edge and the image of a negative edge is a negative edge. A signed graph [G, Σ] admits a homomorphism to a signed graph [H, Λ] if an element of [G, Σ] admits a homomorphism to an element of [H, Λ]. The oriented chromatic number of an oriented graph −→G is the minimum order of an oriented graph −→H such that −→G admits a homomorphism to −→H. A set R of vertices of an oriented graph −→G is an oriented relative clique if no two vertices of R can have the same image under any homomorphism. The oriented relative clique number of an oriented graph −→G is the maximum order of an oriented relative clique of −→G. An oriented clique or an oclique is an oriented graph whose oriented chromatic number is equal to its order. The oriented absolute clique number of an oriented graph −→G is the maximum order of an oclique contained in −→G as a subgraph. The chromatic number, the relative chromatic number and the absolute chromatic number for orientable graphs, signified graphs and signed graphs are defined similarly. In this thesis we study the chromatic number, the relative clique number and the absolute clique number of the above mentioned four types of graphs. We specifically study these three parameters for the family of outerplanar graphs, of outerplanar graphs with given girth, of planar graphs and of planar graphs with given girth. We also try to investigate the relation between the four types of graphs and prove some…

Advisors/Committee Members: Sopena, Eric (thesis director), Pêcher, Arnaud (thesis director), Raspaud, André (thesis director).

▼ Beaucoup de données du monde réel peuvent être représentées par des graphes hétérogènes qui sont composés de plus d'un type de noeuds et de liens. À titre d'exemple de graphes hétérogènes, on trouve les graphes bipartis. Contrairement à la représentation standard de graphes où les noeuds et les liens sont de même type, les graphes bipartis sont caractérisés par la présence de deux types de nœuds reliés par un seul type de liens. L'analyse des graphes bipartis est l'un des nouveaux défis apparus en forage de données. Parmi les problématiques fondamentales étudiées dans ce domaine, on trouve la détection de communautés dont le but consiste à identifier des groupes de noeuds densément connectés entre eux et faiblement liés avec les noeuds d'autres groupes. Ces communautés ont souvent des caractéristiques similaires, ou des centres d'intérêt commun non connus à priori. La problématique de détection de communautés a été bien étudiée dans le cadre des graphes homogènes. Cependant, dans le contexte des graphes bipartis, cette problématique demeure une question de recherche ouverte. Cela est dû, d'une part, au fait que la structure topologique du graphe biparti est différente de celle du graphe ordinaire/ homogène, et d'autre part, l'absence d'une définition universellement acceptée quant à la notion de communauté dans les graphes bipartis. Un certain nombre d'approches a été proposé afin d'identifier des communautés dans les graphes bipartis. Toutefois, ces travaux existants souffrent d'au moins un des problèmes suivants : (1) la perte d'information à la suite de la transformation du graphe biparti en graphes homogènes (2) la sensibilité à la présence des nœuds non discriminants qui cachent la structure de communautés (3) la nécessité de spécifier manuellement le nombre de communautés ainsi que la restriction liée au fait que les deux types de noeuds du graphe biparti doivent avoir le même nombre de communautés. Afin de pallier les limites des approches existantes (mentionnées ci-dessus), nous présentons dans le cadre de ce mémoire, une nouvelle approche de détection de communautés dans les graphes bipartis. L'approche proposée se base sur une stratégie de détection de communautés qui relate la pertinence des noeuds combinée à une heuristique d'optimisation de la modularité bipartie afin d'identifier les structures de communautés finales. L'efficacité de l'approche proposée est comparée à d'autres méthodes récemment présentées sur des réseaux autant réels que synthétiques. Les résultats de cette comparaison montrent que notre approche offre une performance meilleure et parfois compétitive par rapport aux autres approches. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Graphes bipartis, Détection de communautés, Clustering

▼ 

Les programmes sont partout dans notre vie quotidienne : les ordinateurs et les téléphones, mais aussi les frigo, les avions et ainsi de suite. L'acteur principal dans la création de ces programmes est humain les êtres. Aussi minutie qu'ils peuvent être, les humains sont connus pour faire des erreurs involontaires sans leur conscience. Ainsi, une fois une phase déjà difficile d'écriture d'un programme, ils doivent faire face à la phase de maintenance sur laquelle ils doivent faire face aux erreurs qu'ils ont eu précédemment réalisé. Toute la durée de leur tâche de développement, les développeurs doivent faire face continuellement leurs erreurs (ou leurs collègues). Cette observation clé soulève la nécessité d'aider les développeurs dans leurs tâches de développement / maintenance.

Programs are everywhere in our daily life: computers and phones but also fridges, planes and so on. The main actor in the process of creating these programs is human beings. As thorough as they can be, humans are known to make involuntary errors without their awareness. Thus, once finished an already hard phase of writing a program. they have to face the maintenance phase on which they have to deal with errors they had previously made. All long their development task, developers have to continuously face their (or their colleagues) errors. This key observation arises the need of aiding developers in their development/maintenance tasks.

Advisors/Committee Members: Preux, Philippe (thesis director).

▼ 

Nous retracerons le parcours de la topologie dans l’enseignement lacanien : de la topologie algébrique, nous traiterons des figures topologiques (tore, bande de Mœbius, bouteille de Klein, cross-cap) pour en arriver à la topologie nodale dont le paradigme est le nœud borroméen. Nous considérerons alors les conséquences théoriques qu’elle implique : de l’inconscient freudien ou l’inconscient symbolique nous passerons à l’inconscient réel et l’une-bévue, et du symptôme nous envisagerons le sinthome et sa logique. Nous affinerons ainsi le double rapport du sujet au signifiant et à la jouissance mettant en avant l’importance du corps pris comme vivant. Pour ce faire, nous étudierons plus précisément le rapport du sujet au trou, manque fondamental qui le constitue, à la fois extérieur et intérieur. Nous verrons comment, dans son creux et dans ses bords, le sujet y loge sa singularité, son « x ». Nous l’articulerons à la clinique afin de révéler l’apport qu’elle représente dans la pratique.

We will trace the course of topology in Lacan’s teaching: from algebraic topology, where we will deal with topological surfaces (torus, Moebius strip, Klein bottle, cross-cap) we will reach topology whose paradigm is the Borromean knot. We will then consider the theoretical consequences implied: from the Freudian unconscious or symbolic unconscious we will move to the real unconscious and the une-bévue, and from the symptom we will consider the sinthome and its logic. We will refine the dual relationship of the subject to signifier and Jouissance, and highlight the importance of the body as living. To do this, we will study more precisely the relationship of the subject to the hole, a fundamental lack that constitutes him, both exterior and interior. We will see how, in its hollow and its edges, the subject lodges its singularity, its "x". We will link it to clinic to reveal the contribution of topology in practice.

Advisors/Committee Members: Marret, Sophie (thesis director).

▼ 

Récemment, les comportements malveillants dans les réseaux sans fil multi-sauts ont attiré l’attention de la communauté scientifique. La prolifération rapide du nombre de dispositifs sans fil ainsi que la diversification des applications basées sur ces réseaux ont grandement contribué à l’amélioration de la qualité de vie ainsi que la modernisation de la société. Cependant, la nécessité de sécuri ser ces réseaux et de garantir la robustesse de leurs services est devenue une préoccupation majeure. En effet, les caractéristiques spécifiques de ces réseaux, telles que l’absence d’infrastructure et l’absence d’une entité centrale de confiance, font que les réponses à leurs problèmes de sécurité sont tout à fait différentes de celles des réseaux filaires. De plus, le manque de confiance entre les nœuds rend ces problèmes encore plus critiques. L’objectif de cette thèse vise à contribuer au renforcement de la sécurité dans les réseaux sans fil multi-sauts. Elle se focalise sur l’étude des comportements malveillants au niveau des couches MAC et réseau. Nous nous intéressons au développement de nouvelles solutions pour faire face à l’attaque du trou noir ”Black hole” dans le contexte du protocole OLSR, ainsi qu’analyser le comportement des nœuds cupides ”Greedy” au niveau de la couche MAC, dans toutes ses versions.Une attaque de trou noir peut être menée suivant deux scénarios. Le premier scénario consiste à lancer l’attaque, exclusivement, au niveau de la couche réseau. Le second scénario consiste en une attaque multi-couches. Dans le cadre de cette thèse, nous analysons l’impact de ces deux types d’attaques et proposons des contre-mesures appropriées. Au niveau de la couche MAC, nous étudions particulièrement le comportement cupide adaptatif dans le cadre des réseaux sans fil maillés et nous proposons une solution originale baptisée, FLSAC, afin de prévenir ce type de menace. Dans le cadre des réseaux mobiles ad hoc (MANETs), nous définissons un nouveau modèle de comportement des nœuds cupides. Nous développons aussi un nouvel algorithme de backoff, dont l’avantage principal est d’assurer une détection rapide des nœuds cupides non conformes aux spécifications du protocole IEEE802.11. Cet algorithme offre un mécanisme de réaction qui incite un nœud cupide à se comporter correctement en lui donnant la chance de se repentir après détection.

While the rapid proliferation of mobile devices along with the tremendous growth of various applications using wireless multi-hop networks have significantly facilitate our human life, securing and ensuring high quality services of these networks are still a primary concern. In particular, anomalous protocol operation in wireless multi-hop networks has recently received considerable attention in the research community. These relevant security issues are fundamentally different from those of wireline networks due to the special characteristics of wireless multi-hop networks, such as the limited energy resources and the lack of centralized control. These issues are extremely hard to cope…

Advisors/Committee Members: Naït-Abdesselam, Farid (thesis director).

▼ Differential pairs may gradually replace single trace as the media transmitting high-speed signal on high-speed digital circuit. This dissertation investigates the impact on electromagnetic radiation from high-speed circuit board by the distance between differential traces and edge effect .At the same time, we use the result of measurement and simulation to make sure the measurement method correct .The result shows that,the shorter the distance is,the lower the EMI of differential pairs have .The edge effect will has the ability of destroying the suppression of EMI. Based on the consideration of measuring correctly, we use a solid kind of measurement method to search some non-ideal effects before studying EMI from differential pairs .These effect may exist on real measurement or ideal simulation. We hope to understand the environment of measurement as clearly as possible. In addition, we address one simple and fast method to investigate radiation mechanism that resulted from edge effect of differential pairs.By this method to calculate radiation, we will understand more and more the radiation mechanism. Advisors/Committee Members: Chih-Wen Kuo (chair), Tzyy-Sheng Horng (chair), Ken-Huang Lin (chair), Tzong-Lin Wu (committee member), Sheng-Fu Chang (chair).

▼ We make use of Volkov states of electron and positron for trident pair production. The periodic plane wave case shows an in nite sum over photon number in the calculations and leads to unphysical cross section. We calculate the trident pair production rate and cross section in strong laser pulses, treating nonperturbatively in strong- eld QED. We then arrive at a nite and physical results through shaping of those elds into laser pulses. With the help of the optical theorem, we make the S-matrix not to diverge and precisely identify the one-step and two-step processes. Advisors/Committee Members: Dr. S. Bhatnaga (advisor).

▼ 

Cette thèse porte sur l'étude de certains aspects du principe d'incertitude en analyse harmonique.Historiquement le principe d'incertitude fut énoncé en 1927 par Heisenberg qui a montré unepropriété fondamentale de la mécanique quantique qui dit qu'il est impossible de mesurer, avecprécision, à la fois la position et la vitesse d'une particule. Le but de cette thèse est d'étendre certainsrésultats concernant les paires annihilantes à deux contextes.Dans la première partie nous étendons le principe d’incertitude local et les principes d'incertitudede Benedicks-Amrein-Berthier, de Shubin-Vakilian-Wolff et de Logvinenko-Sereda pour latransformée de Fourier-Bessel. Ces principes font qu’on ne peut pas localiser aussi précisémentqu’on le veut une fonction et sa transformée de Fourier-Bessel.Dans la deuxième partie, nous abordons les principes d'incertitude dans le cadre discret fini, dontl'intérêt a été renouvelé par la théorie de "l'échantillonnage comprimée" qui est plus connue sous levocable anglo-saxon du "compresseve sensing". Le thème général de ce travail est l'étude desprincipes d'incertitude qualitatifs et quantitatifs pour la transformée de Fourier discrète/ discrète à fenêtre.

In this thesis we are interested in Uncertainty Principles. Published by Heisenberg in 1927, the uncertainty principle was a key discovery in the early development of quantum theory. It implies that it is impossible to simultaneously measure the present position and momentum of a particle. The aim of this thesis is to extend some results about annihilating pairs in two contexts. In the first part we extend the local uncertainty principle, the Benedicks-Amrein-Berthier uncertainty principle, the Shubin-Vakilian-Wolff uncertainty principle and the Logvinenko-Sereda uncertainty principle for the Fourier-Bessel transform. This uncertainty principles state that a function and its Fourier- Bessel transform cannot be simultaneously well concentrated. The aim of the second part is to deal with uncertainty principles in finite the dimensional settings witch is linked to the theory of compresseve sensing. Our result extends previously known qualitative uncertainty principles into more quantitative for the discrete Fourier transform/ short time Fourier transform.

Advisors/Committee Members: Jaming, Philippe (thesis director), Ben Salem, Néjib (thesis director).