Texte remanié de: Thèse de doctorat--Histoire--Paris 1, 2005. / Bibliogr. p. 285-299.

Reproduction de : Thèse de doctorat : Électronique : Lille 1 : 2005. Tesi di dottorato : Ingeneria Ellectronica e delle Comunicazioni : Politecnico di Torino : 2005. / Thèse en cotutelle. N° d'ordre (Lille 1) : 3635. Texte en anglais. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. 145-149.

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés.

Nous présentons des solutions algorithmiques pour deux problèmes liés à l'interfé-rence de réseau sans fil. D'abord on propose de ordonnancer les liens d'un ensemble de routes données en vertu de l'hypothèse d'un modèle à fort trafic. Nous considérons un protocole TDMA qu'offre une source d'intervalles de temps synchronisés et cherchent à ordonnancer les itinéraires des liens afin de maximiser le nombre de paquets qui sont livrés à leurs destinations par chaque intervalle de temps. Notre approche consiste à construire un graphe non orienté $G$ et à obtenir multiples colorations pour les noeuds de $G$ qui peuvent induire aux ordonnancement de liens efficaces. En $G$ chaque noeud représente un lien à être ordonnancer et les arcs sont mis en place pour représenter toutes les interférences possibles pour un ensemble d'hypothèses d'interférence. Nous présentons deux heuristiques de multiples colorations et étudions leurs performances grâce à de nombreuses simulations. L'un des deux heuristiques est fondée sur l'assouplissement des dynamiques de multiples colorations en exploitant la disponibilité des possibilités de communication qui seraient autrement perdues. Nous avons constaté que, par conséquent, sa performance est nettement supérieure à la celle des autres. Dans la deuxième proposition, nous considérons les réseaux maillés sans fil et le problème de routage bout à bout du trafic sur les chemins multiples pour la même paire origine-destination avec un minimum d'interférences. Nous introduisons une heuristique pour la détermination des chemins avec deux caractéristiques distinctives. Tout d'abord, il fonctionne par le raffinage d'un ensemble existant de chemins, préalablement déterminée par un algorithme de routage de multiples chemins. Deuxièmement, il est tout à fait locale, dans le sens où il peut être exécuté par chacune des origines sur l'information qui est disponible plus loin dans le réseau de voisinage immédiat du noeud. Nous avons mené de nombreuses expériences avec la nouvelle heuristique, en utilisant le protocole OLSR et AODV ainsi que leurs variantes de chemins multiples. Nous avons démontré que la nouvelle heuristique est capable d'améliorer le débit moyen du réseau à l'échelle en utilisant un protocole TDMA sous l'exécution d'un algorithme de ordonnancement des liens orienté à routes et de deux différents paramètres de fonctionnement du protocole CSMA 802.11. En travaillent à partir des trajectoires générées par le chemin provenaient de algorithmes de multiples chemins, l'heuristique est également capable de fournir un modèle de trafic plus équitablement répartie.

Thèse (M.A.)--Université Laval, 2006. / Bibliogr.: f. 112-116. Publié aussi en version électronique dans la Collection Mémoires et thèses électroniques.

Diss.--Basel--Universität, 1989.

Diss.--Universität Bochum, 1995. / Bibliogr. p. 591-594.

No description available.

Dans les zones de subduction, de nombreux indices attestent la circulation de fluides au-dessus de la plaque plongeante et dans le coin de manteau. L'interaction de péridotites avec des fluides aqueux issus de la déshydratation de la plaque plongeante favorise la formation de serpentinites à antigorite. Les interactions fluides-roche se font sous plusieurs formes : diffusion à l'état solide, percolation aux joints de grains et pression-solution. Afin d'étudier ces différentes interactions dans les conditions du coin de manteau, de l'antigorite et de l'eau ont été placées à haute pression (1.5-3.0 GPa) et haute température (315-540°C) dans une presse Belt ou une cellule à enclumes de diamant. De l'eau D2O a permis de suivre les processus d'inter-diffusion D/H dans l'antigorite et d'identifier les chemins de circulation de fluides et des traceurs de nickel ont été utilisés pour imager les recristallisations. L'analyse de monocristaux par spectroscopie Raman et nano-SIMS a permis de déterminer une loi d'inter-diffusion D/H pour l'antigorite : DD/H (m2/s) = 7.09 x 10-3 x exp(-202(-33/+70) (kJ/mol) /RT). La déformation de l'échantillon est localisées dans des zones de cisaillement ; elle augmente la porosité (jusqu'à 10 fractures/µm) et favorise les interactions fluides-roche. Des textures d'alignement de pores ont été identifiées comme des chemins actifs de circulation de fluides par la comparaison des volumes d'interaction fluides-roche et d'images MEB à haute résolution. Les recristallisations riches en nickel ont été étudiées par analyse EDX et imagerie en électrons rétrodiffusés. Les vitesses de cristallisation augmentent avec la température et la pression / In subduction zones many evidences confirm the circulation of fluids above the subducting slab and in the mantle wedge. The interaction of peridotites and water coming from the dehydration of the subducting slab favors the formation of antigorite serpentinites. Fluid-rock interactions include several processes: solid-state diffusion, percolation at grain boundaries and pressure-solution. In order to study the various interaction processes at the mantle wedge conditions, antigorite and water were interacted at high pressure (1.5-3.0 GPa) and high temperature (315-540°C) in a belt apparatus or in a diamond anvil cell. D2O-water was used as a tracer of D/H inter-diffusion processes in antigorite and in order to image circulation paths for aqueous fluids, and nickel tracers were used to image the recrystallizations. The analyses of single-crystals with a Raman spectrometer and nano-SIMS lead to a D/H inter-diffusion law in antigorite: DD/H (m2/s) = 7.09 x 10-3 x exp(-202(-33/+70) (kJ/mol) /RT). The sample deformation, due to the non-hydrostatic pressure in the belt apparatus, is localized in shear zones; it raises the porosity (up to 10 fractures/µm) and enhances the fluid-rock interactions. Textures of pore alignments were identify as active circulation paths for fluids from the comparison of maps of fluid-rock interactions and high resolution SEM images. Nickel-rich recrystallizations were studied with EDX analyses and backscattered electron imaging. Crystallization velocities raises with increasing temperature and pressure

Cette thèse porte sur différents problèmes d'optimisation combinatoire dont nous avons caractérisé la difficulté en décrivant des réductions et des algorithmes polynomiaux exacts ou approchés.En particulier, nous étudions le problème de trouver, dans un graphe orienté sans cycle dont les sommets sont étiquetés, un chemin qui passe par un maximum d'étiquettes différentes. Nous établissons qu'il n'existe pas d'algorithme polynomial avec un facteur constant pour ce problème. Nous présentons aussi un schéma qui permet d'obtenir, pour tout $epsilon >0$, un algorithme polynomial qui calcule un chemin collectant $ O(OPT^{1-epsilon})$ étiquettes.Nous étudions ensuite des variantes du problème de l'arbre couvrant de poids minimum auquel nous ajoutons des contraintes de distance et d'intermédiarité. Nous prouvons que certaines variantes se résolvent en temps polynomial comme des problèmes de calcul d'un libre de poids minimum commun à deux matroïdes. Pour une autre variante, nous présentons un algorithme d'approximation facteur 2 et nous prouvons qu'il n'existe pas d'algorithme polynomial avec un meilleur facteur constant.Enfin, nous étudions un problème d'améliorations de réseaux du point de vue du partage des coûts. Nous montrons que la fonction de coût associée à ce problème est sous-modulaire et nous utilisons ce résultat pour déduire un mécanisme de partage des coûts qui possède plusieurs bonnes propriétés. / In this thesis, we investigate several combinatorial optimization problems and characterize their computational complexity and approximability by providing polynomial reductions and exact or approximation algorithms.In particular, we study the problem of finding, in a vertex-labeled directed acyclic graph, a path collecting a maximum number of distinct labels. We prove that no polynomial time constant factor approximation algorithm exists for this problem. Furthermore, we describe a scheme that produces, for any $epsilon >0$, a polynomial time algorithm that computes a solution collecting $O(OPT^{1-epsilon})$ labels. Then, we study several variants of the minimum cost spanning tree problem that take into account distance and betweenness constraints. We prove that most of these problems can be solved in polynomial time using a reduction to the weighted matroid intersection problem. For an other problem, we give a factor 2 approximation algorithm and prove the optimality of this ratio.Finally, we study a network improvement problem from a cost sharing perspective. We establish that the cost function corresponding to this problem is submodular and use this result to derive a cost sharing mechanism having several good properties.