Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ce memoire s'interesse aux proprietes statistiques de systemes fortement contraints, tous intimement lies a des problemes de pliages de reseaux bidimensionnels discrets, reguliers ou aleatoires. Dans une premiere partie, on considere le pliage de reseaux bidimensionnels proprement dit: il s'agit de plier un reseau le long de ses aretes tout en conservant ses faces non-deformees. Nous etudions en detail le cas du reseau triangulaire, pour lequel plusieurs modeles de pliage sont discutes, correspondant a plusieurs ``espaces cibles". Le lien entre les pliages, les coloriages et les gaz de boucles compactes est discute. Nous etendons finalement notre description au cas du pliage de triangulations aleatoires. La deuxieme partie s'interesse aux gaz de boucles compactes, c'est a dire passant par tous les noeuds d'un reseau. Dans le cas de reseaux aleatoires, notre etude revele comment le caractere bipartite du reseau change les proprietes statistiques du systeme. Une attention particuliere est portee aux cycles hamiltoniens, correspondant au cas ou le reseau est couvert par une boucle unique, et pour lesquels un exposant de configuration irrationnel est predit pour un probleme combinatoire apparemment anodin. Enfin, la troisieme partie s'interesse aux meandres, un probleme combinatoire apparemment simple (compter les configurations d'un circuit traversant une riviere en un nombre donne de ponts) mais qui resiste encore aujourd'hui. Apres avoir donne un quelques resultats exacts pour des variantes du probleme, nous etudions les proprietes asymptotiques (a grand nombre de ponts) des meandres. Leur formulation comme gaz de boucles compactes sur des graphes aleatoires permet de predire des exposants de configuration irrationnels qui sont testes numeriquement. Le lien entre meandres et pliages de quadrangulations aleatoires est egalement etabli.

La lithographie par double impression est une solution potentielle proposée pour l'impression des circuits des nœuds technologiques avancés (22nm et au-delà) en attendant que la lithographie Extrême Ultraviolet soit prête pour la production en masse. La technique de double impression est basée sur la décomposition en deux masques d'exposition des motifs d'un niveau donné du circuit intégré. Deux motifs voisins ayant un pas inférieur au pas minimal résolu en un procédé lithographique sont affiliés simultanément à deux masques différents. Les motifs ayant des pas supérieurs au pas critique, motifs non critiques, sont mis sur un masque ou sur un autre dans le but de générer une densité de motifs équivalente entre les deux masques d'exposition. Dans cette thèse, nous avons développé une nouvelle méthode de décomposition dite " décomposition optique ". Cette dernière est basée sur l'analyse de l'interaction des ordres de diffraction dans le plan de la pupille du système optique de projection. La décomposition optique permet d'améliorer l'affiliation des motifs non critiques à l'un des deux masques dans le but d'améliorer le contraste des deux masques lors de la double impression. Afin de valider cette nouvelle méthode de décomposition, nous l'avons appliqué au niveau contacts d'un circuit de logique du nœud 22nm.

Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliques. / This thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph

La nécessité de maximiser la durée de vie du réseau sans fil dans les réseaux ad hoc et en particulier dans les réseaux de capteurs sans fil nécessite l'utilisation d'algorithmes d'efficacité énergétique. Motivée par le fait qu'un noeud consomme le moins d'énergie lorsqu'il est en veille, nous réalisons l'efficacité énergétique vi des algorithmes d'ordonnancement des activités des noeuds. Les noeuds reçoivent des slots temporels durant lesquels ils peuvent transmettre et ils peuvent éteindre leur radio quand ils ne sont ni en train de transmettre, ni en train de recevoir. Par rapport au TDMA classique, l'utilisation de la bande passante est optimisée: deux noeuds interférents ne partagent pas les mêmes slots. Dans notre travail sur l'ordonnancement, deux cas sont étudiés. Tout d'abord, lorsque les nœuds nécessitent le même temps d'accès au canal, nous utilisons le coloriage des nœuds. Deuxièmement, lorsque les nœuds requièrent des débits hétérogènes, nous utilisons une allocation de slots " traffic aware ". Contrairement à la majorité des travaux antérieurs, nous généralisons la définition du coloriage des noeuds et les problèmes d'attribution des slots. En effet, nous considérons que la distance maximale entre deux nœuds interférents est un paramètre de ces problèmes. Nous prouvons qu'ils sont NP-complets, ce qui rend inévitable l'utilisation des heuristiques dans la pratique. Une directive centrale de cette thèse est de concevoir des solutions auto-adaptatives. Cette adaptabilité concerne de nombreux aspects tels que la mission confiée par l'application, l'hétérogénéité des demandes de trafic de nœuds, la densité du réseau, de la régularité de la topologie du réseau, et la non fiabilité des liens sans fil.

Cette thèse traite de l'utilisation des algorithmes évolutionnaires (AE) pour résoudre des problèmes de satisfaction de contrainte (CSP) en domaines finis sans spécialisation ni hybridation particulière. Après avoir présenté les CSP et les méthodes couramment utilisées pour les résoudre (chapitres 1 et 2), nous présentons le paradigme évolutionnaire et ses applications (chapitres 3 et 4). Ensuite, nous proposons une comparaison entre les méthodes de recherche arborescente et les métaheuristiques sur des coloriages de graphe sur-contraints, dans un contexte de réglage des paramètres minimal (chapitre 5). Nous étudions le paysage de recherche pour comprendre les raisons des différences d'efficacité des méthodes. Enfin, nous proposons de nouveaux opérateurs génétiques (croisement, mutation, diversification) dont le paramétrage est moins fastidieux qu'avec les opérateurs classiques (chapitre 6). Nous concluons sur l'intérêt d'exploration des réseaux de neutralité.

La lithographie par double impression est une solution potentielle proposée pour l'impression des circuits des nœuds technologiques avancés (22nm et au-delà) en attendant que la lithographie Extrême Ultraviolet soit prête pour la production en masse. La technique de double impression est basée sur la décomposition en deux masques d'exposition des motifs d'un niveau donné du circuit intégré. Deux motifs voisins ayant un pas inférieur au pas minimal résolu en un procédé lithographique sont affiliés simultanément à deux masques différents. Les motifs ayant des pas supérieurs au pas critique, motifs non critiques, sont mis sur un masque ou sur un autre dans le but de générer une densité de motifs équivalente entre les deux masques d'exposition. Dans cette thèse, nous avons développé une nouvelle méthode de décomposition dite « décomposition optique ». Cette dernière est basée sur l'analyse de l'interaction des ordres de diffraction dans le plan de la pupille du système optique de projection. La décomposition optique permet d'améliorer l'affiliation des motifs non critiques à l'un des deux masques dans le but d'améliorer le contraste des deux masques lors de la double impression. Afin de valider cette nouvelle méthode de décomposition, nous l'avons appliqué au niveau contacts d'un circuit de logique du nœud 22nm. / As the lithography EUV is not yet ready to be used for semi-conductor business needs, the double patterning lithography is a promising solution to print sub 22nm node features. The principle of the double patterning is the pitch splitting also named as the coloring of a given circuit layer's features. Two adjacent features must be assigned opposite masks or opposite colors corresponding to different exposures, if their pitch is less than the minimum resolvable pitch. However, features with pitches larger than the critical one are not critical and could be assigned to one of the two masks for density balance. In this thesis, we developed a new split called “optical split” based on the diffractive orders analysis in the pupil plane. The optical split optimizes the non critical contacts affiliation to one of the two exposure masks. The goal of the optical split is to enhance the lithographic performances of the generated masks in order to improve the double patterning process printing. In order to validate the optical split, we apply it on contact layer of the 22nm node logic.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3467. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. 9 p.

Dans cette thèse, nous étudions divers problèmes dont l'objectif est de gérer la croissance d'internet plus efficacement. En effet celle-ci est très vive : 41% pour le pic en 2012. Afin de répondre aux défis posés par cette évolution aux divers acteurs du réseau, des protocoles de gestion et de communication plus intelligents sont nécessaires. Les protocoles de l'Internet furent conçus, point à point. Or, la part de la diffusion de média dans le trafic est prépondérante et en hausse tendancielle, et des projections indiquent qu'en 2016 80-90% du trafic sera engendré par de la diffusion vidéo. Cette divergence entraîne des inefficacités car les données parcourent plusieurs fois le réseau. Dans cette thèse, nous étudions comment tempérer cette inefficacité. Nos contributions sont organisées selon les couches et les phases de déploiement du réseau. Nous étudions le placement de caches lors de la conception du réseau. Ensuite, pour la gestion d'un réseau, nous regardons quand placer des appareils en veille, en utilisant un mécanisme de cache et en coopération avec des réseaux de distribution. Puis, au niveau de la couche application, nous étudions un problème de maintenance d'arbres équilibrés pour la diffusion de média. Enfin, nous analysons la probabilité de survie de données dans un système de sauvegarde distribuée. Notre travail se fonde à la fois sur des méthodes théoriques (Chaînes de Markov, Programmation Linéaire), mais aussi sur des outils empiriques tels que la simulation et l'expérimentation. / In this thesis we study multiple approaches to efficiently accommodating for the future growth of the Internet. The exponential growth of Internet traffic, reported to be as high as 41% in peak throughput in 2012 alone, continues to pose challenges to all interested parties. Therefore, to accommodate the growth, smart management and communication protocols are needed. The basic protocols of the Internet are point-to-point in nature. However, the traffic is largely broadcasting, with projections stating that as much as 80-90% of it will be video by 2016. This discrepancy leads to inefficiency, where multiple copies of essentially the same messages travel in parallel through the same links. In this thesis we study multiple approaches to mitigating this inefficiency. The contributions are organized by layers and phases of the network life. We look into optimal cache provisioning during network design. Next, we move to managing an existing network. We look into putting devices to sleep mode, using caching and cooperation with Content Distribution Networks. In the application layer, we look into maintaining balanced trees for media broadcasting. Finally, we analyze data survivability in a distributed backup system, which can reduce network traffic by putting the backups closer to the client than if using a data center. Our work is based on both theoretical methods, like Markov chains and linear programming, as well as empirical tools, like simulation and experimentation.

Dans cette thèse, nous étudions divers problèmes dont l'objectif est de gérer la croissance d'internet plus efficacement. En effet celle-ci est très vive : 41% pour le pic en 2012. Afin de répondre aux défis posés par cette évolution aux divers acteurs du réseau, des protocoles de gestion et de communication plus intelligents sont nécessaires. Les protocoles de l'Internet furent conçus, point à point. Or, la part de la diffusion de média dans le trafic est prépondérante et en hausse tendancielle, et des projections indiquent qu'en 2016 80-90% du trafic sera engendré par de la diffusion vidéo. Cette divergence entraîne des inefficacités car les données parcourent plusieurs fois le réseau. Dans cette thèse, nous étudions comment tempérer cette inefficacité. Nos contributions sont organisées selon les couches et les phases de déploiement du réseau. Nous étudions le placement de caches lors de la conception du réseau. Ensuite, pour la gestion d'un réseau, nous regardons quand placer des appareils en veille, en utilisant un mécanisme de cache et en coopération avec des réseaux de distribution. Puis, au niveau de la couche application, nous étudions un problème de maintenance d'arbres équilibrés pour la diffusion de média. Enfin, nous analysons la probabilité de survie de données dans un système de sauvegarde distribuée. Notre travail se fonde à la fois sur des méthodes théoriques (Chaînes de Markov, Programmation Linéaire), mais aussi sur des outils empiriques tels que la simulation et l'expérimentation.