Mémoire (M.Ress.Renouv.)--Université du Québec à Chicoutimi, 1991. / Document électronique également accessible en format PDF. CaQCU

Mémoire (M.Ress.Renouv.)-- Université du Québec à Chicoutimi, 1994. / Document électronique également accessible en format PDF. CaQCU

Cette Thèse pose la question de la décision collective sous incertitude possibiliste. On propose différents règles de décision collective qualitative et on montre que dans un contexte possibiliste, l'utilisation d'une fonction d'agrégation collective pessimiste égalitariste ne souffre pas du problème du Timing Effect. On étend ensuite les travaux de Dubois et Prade (1995, 1998) relatifs à l'axiomatisation des règles de décision qualitatives (l'utilité pessimiste) au cadre de décision collective et montre que si la décision collective comme les décisions individuelles satisfont les axiomes de Dubois et Prade ainsi que certains axiomes relatifs à la décision collective, particulièrement l'axiome de Pareto unanimité, alors l'agrégation collective égalitariste s'impose. Le tableau est ensuite complété par une axiomatisation d'un pendant optimiste de cette règle de décision collective. Le système axiomatique que nous avons développé peut être vu comme un pendant ordinal du théorème de Harsanyi (1955). Ce résultat á été démontré selon un formalisme qui et basé sur le modèle de de Von NeuMann and Morgenstern (1948) et permet de comparer des loteries possibilistes. Par ailleurs, on propose une première tentative pour la caractérisation des règles de décision collectives qualitatives selon le formalisme de Savage (1972) qui offre une représentation des décisions par des actes au lieu des loteries. De point de vue algorithmique, on considère l'optimisation des stratégies dans les arbres de décision possibilistes en utilisant les critères de décision caractérisés dans la première partie de ce travail. On offre une adaptation de l'algorithme de Programmation Dynamique pour les critères monotones et on propose un algorithme de Programmation Multi-dynamique et un algorithme de Branch and Bound pour les critères qui ne satisfont pas la monotonie. Finalement, on établit une comparaison empirique des différents algorithmes proposés. On mesure les CPU temps d'exécution qui augmentent linéairement en fonction de la taille de l'arbre mais restent abordable même pour des grands arbres. Ensuite, nous étudions le pourcentage d'exactitude de l'approximation des algorithmes exacts par Programmation Dynamique: Il apparaît que pour le critère U-max ante l'approximation de l'algorithme de Programmation Multi-dynamique n'est pas bonne. Mais, ceci n'est pas si dramatique puisque cet algorithme est polynomial (et efficace dans la pratique). Cependant, pour la règle U+min ante l'approximation par Programmation Dynamique est bonne et on peut dire qu'il devrait être possible d'éviter une énumération complète par Branch and Bound pour obtenir les stratégies optimales. / This Thesis raises the question of collective decision making under possibilistic uncertainty. We propose several collective qualitative decision rules and show that in the context of a possibilistic representation of uncertainty, the use of an egalitarian pessimistic collective utility function allows us to get rid of the Timing Effect. Making a step further, we prove that if both the agents' preferences and the collective ranking of the decisions satisfy Dubois and Prade's axioms (1995, 1998) and some additional axioms relative to collective choice, in particular Pareto unanimity, then the egalitarian collective aggregation is compulsory. The picture is then completed by the proposition and the characterization of an optimistic counterpart of this pessimistic decision rule. Our axiomatic system can be seen as an ordinal counterpart of Harsanyi's theorem (1955). We prove this result in a formalism that is based on Von NeuMann and Morgenstern framework (1948) and compares possibilisitc lotteries. Besides, we propose a first attempt to provide a characterization of collective qualitative decision rules in Savage's formalism; where decisions are represented by acts rather than by lotteries. From an algorithmic standpoint, we consider strategy optimization in possibilistic decision trees using the decision rules characterized in the first part of this work. So, we provide an adaptation of the Dynamic Programming algorithm for criteria that satisfy the property of monotonicity and propose a Multi-Dynamic programming and a Branch and Bound algorithm for those that are not monotonic. Finally, we provide an empirical comparison of the different algorithms proposed. We measure the execution CPU times that increases linearly according to the size of the tree and it remains affordable in average even for big trees. Then, we study the accuracy percentage of the approximation of the pertinent exact algorithms by Dynamic Programming: It appears that for U-max ante criterion the approximation of Multi-dynamic programming is not so good. Yet, this is not so dramatic since this algorithm is polynomial (and efficient in practice). However, for U+min ante decision rule the approximation by Dynamic Programming is good and we can say that it should be possible to avoid a full Branch and Bound enumeration to find optimal strategies.

La factorisation des tenseurs est au coeur des méthodes d'analyse des données massives multidimensionnelles dans de nombreux domaines, dont les systèmes de recommandation, les graphes, les données médicales, le traitement du signal, la chimiométrie, et bien d'autres.Pour toutes ces applications, l'obtention rapide de la décomposition des tenseurs est cruciale pour pouvoir traiter manipuler efficacement les énormes volumes de données en jeu.L'objectif principal de cette thèse est la conception d'algorithmes pour la décomposition de tenseurs multidimensionnels creux, possédant de plusieurs centaines de millions à quelques milliards de coefficients non-nuls. De tels tenseurs sont omniprésents dans les applications citées plus haut.Nous poursuivons cet objectif via trois approches.En premier lieu, nous proposons des algorithmes parallèles à mémoire distribuée, comprenant des schémas de communication point-à-point optimisés, afin de réduire les coûts de communication. Ces algorithmes sont indépendants du partitionnement des éléments du tenseur et des matrices de faible rang. Cette propriété nous permet de proposer des stratégies de partitionnement visant à minimiser le coût de communication tout en préservant l'équilibrage de charge entre les ressources. Nous utilisons des techniques d'hypergraphes pour analyser les paramètres de calcul et de communication de ces algorithmes, ainsi que des outils de partitionnement d'hypergraphe pour déterminer des partitions à même d'offrir un meilleur passage à l'échelle. Deuxièmement, nous étudions la parallélisation sur plate-forme à mémoire partagée de ces algorithmes. Dans ce contexte, nous déterminons soigneusement les tâches de calcul et leur dépendances, et nous les exprimons en termes d'une structure de données idoine, et dont la manipulation permet de révéler le parallélisme intrinsèque du problème. Troisièmement, nous présentons un schéma de calcul en forme d'arbre binaire pour représenter les noyaux de calcul les plus coûteux des algorithmes, comme la multiplication du tenseur par un ensemble de vecteurs ou de matrices donnés. L'arbre binaire permet de factoriser certains résultats intermédiaires, et de les ré-utiliser au fil du calcul. Grâce à ce schéma, nous montrons comment réduire significativement le nombre et le coût des multiplications tenseur-vecteur et tenseur-matrice, rendant ainsi la décomposition du tenseur plus rapide à la fois pour la version séquentielle et la version parallèle des algorithmes.Enfin, le reste de la thèse décrit deux extensions sur des thèmes similaires. La première extension consiste à appliquer le schéma d'arbre binaire à la décomposition des tenseurs denses, avec une analyse précise de la complexité du problème et des méthodes pour trouver la structure arborescente qui minimise le coût total. La seconde extension consiste à adapter les techniques de partitionnement utilisées pour la décomposition des tenseurs creux à la factorisation des matrices non-négatives, problème largement étudié et pour lequel nous obtenons des algorithmes parallèles plus efficaces que les meilleurs actuellement connus.Tous les résultats théoriques de cette thèse sont accompagnés d'implémentations parallèles,aussi bien en mémoire partagée que distribuée. Tous les algorithmes proposés, avec leur réalisation sur plate-forme HPC, contribuent ainsi à faire de la décomposition de tenseurs un outil prometteur pour le traitement des masses de données actuelles et à venir. / Tensor factorization has been increasingly used to analyze high-dimensional low-rank data ofmassive scale in numerous application domains, including recommender systems, graphanalytics, health-care data analysis, signal processing, chemometrics, and many others.In these applications, efficient computation of tensor decompositions is crucial to be able tohandle such datasets of high volume. The main focus of this thesis is on efficient decompositionof high dimensional sparse tensors, with hundreds of millions to billions of nonzero entries,which arise in many emerging big data applications. We achieve this through three majorapproaches.In the first approach, we provide distributed memory parallel algorithms with efficientpoint-to-point communication scheme for reducing the communication cost. These algorithmsare agnostic to the partitioning of tensor elements and low rank decomposition matrices, whichallow us to investigate effective partitioning strategies for minimizing communication cost whileestablishing computational load balance. We use hypergraph-based techniques to analyze computational and communication requirements in these algorithms, and employ hypergraphpartitioning tools to find suitable partitions that provide much better scalability.Second, we investigate effective shared memory parallelizations of these algorithms. Here, we carefully determine unit computational tasks and their dependencies, and express them using aproper data structure that exposes the parallelism underneath.Third, we introduce a tree-based computational scheme that carries out expensive operations(involving the multiplication of the tensor with a set of vectors or matrices, found at the core ofthese algorithms) faster by factoring out and storing common partial results and effectivelyre-using them. With this computational scheme, we asymptotically reduce the number oftensor-vector and -matrix multiplications for high dimensional tensors, and thereby rendercomputing tensor decompositions significantly cheaper both for sequential and parallelalgorithms.Finally, we diversify this main course of research with two extensions on similar themes.The first extension involves applying the tree-based computational framework to computingdense tensor decompositions, with an in-depth analysis of computational complexity andmethods to find optimal tree structures minimizing the computational cost. The second workfocuses on adapting effective communication and partitioning schemes of our parallel sparsetensor decomposition algorithms to the widely used non-negative matrix factorization problem,through which we obtain significantly better parallel scalability over the state of the artimplementations.We point out that all theoretical results in the thesis are nicely corroborated by parallelexperiments on both shared-memory and distributed-memory platforms. With these fastalgorithms as well as their tuned implementations for modern HPC architectures, we rendertensor and matrix decomposition algorithms amenable to use for analyzing massive scaledatasets.

Nous étudions dans cette thèse l’algèbre de Hopf H associée à l’opérade pré-Lie. L’espace des éléments primitifs du dual gradué est muni d’une structure pré-Lie à gauche notée ⊲ définie par l’insertion d’un arbre dans un autre. Nous retrouvons la relation de dérivation entre le produit pré-Lie ⊲ et le produit pré-Lie de greffe → sur les éléments primitifs du dual gradué de l’algèbre de Hopf de Connes Kreimer HCK. Nous mettons en évidence un coproduit sur le produit tensoriel H ⊗HCK, qui en fait une algèbre de Hopf dont le dual gradué est isomorphe à l’algèbre enveloppante du produit semi-direct des deux algèbres de Lie considérées. Nous montrons que l’espace engendré par les arbres enracinés qui ont au moins une arête, muni du produit d’insertion, est une algèbre pré-Lie (non libre) engendrée par deux éléments. Nous mettons en évidence deux familles de relations. De plus nous montrons un résultat similaire pour l’algèbre pré-Lie associée à l’opérade NAP. Finalement on introduit les opérades à débit constant et on montre que l’opérade pré-Lie s’obtient comme déformation de l’opérade NAP dans ce cadre. / We investigate in this thesis the Hopf algebra structure on the vector space H spanned by the rooted forests, associated with the pre-Lie operad. The space of primitive elements of the graded dual of this Hopf algebra is endowed with a left pre-Lie product denoted by ⊲, defined in terms of insertion of a tree inside another. In this thesis we retrieve the “derivation” relation between the pre-Lie structure ⊲ and the left pre-Lie product → on the space of primitive elements of the graded dual H0CK of the Connes-Kreimer Hopf algebra HCK, defined by grafting. We also exhibit a coproduct on the tensor product H⊗HCK, making it a Hopf algebra the graded dual of which is isomorphic to the enveloping algebra of the semidirect product of the two (pre-)Lie algebras considered. We prove that the span of the rooted trees with at least one edge endowed with the pre-Lie product ⊲ is generated by two elements. It is not free : we exhibit two families of relations. Moreover we prove a similar result for the pre-Lie algebra associated with the NAP operad. Finally, we introduce current preserving operads and prove that the pre-Lie operad can be obtained as a deformation of the NAP operad in this framework.

Des mesures sur parcelles agroforestières (mélanges d'arbres et de cultures) expérimentales mettent en évidence des productivités exceptionnelles, avec des gains de plus de 30% par rapport à l'assolement de cultures pures. Nous avons mis au point et utilisé un modèle numérique dynamique en 3-D (Hi-sAFe) pour (1) tester si l'intégration spatio-temporelle du partage des ressources (lumière, eau, azote) entre espèces suffit à expliquer cette productivité et (2) évaluer l'impact de différents choix de conception ou de gestion sur cette productivité, à partir d'une compréhension des processus impliqués.Nous avons développé une méthode originale d'analyse des données simulées pour identifier et hiérarchiser les processus déterminant le rendement. Le modèle a été paramétré et calibré sur un système noyer hybride / blé dur situé sur le domaine de Restinclières (Hérault, France). Après une analyse détaillée du fonctionnement de ce système, nous avons exploré par expérimentation virtuelle sa réponse à des choix de conception: (1) traits phénologiques des espèces associées, et (2) densité et disposition des arbres sur la parcelle. Par la richesse de son comportement, Hi-sAFe permet un regard nouveau sur le fonctionnement des systèmes agroforestiers. Il éclaire la complexité du système réel. Nos résultats permettent de proposer une interprétation déterministe du rendement de chaque espèce et de la productivité totale de l'association (Land Equivalent Ratio). L'analyse des expérimentations virtuelles permet de proposer des pistes concrètes pour l'optimisation des systèmes agroforestiers. / Measurements on experimental silvoarable agroforestry plots (mixed tree-crop) showed exceptionally high productivity, with yields more than 30% higher compared to the separate crop and tree systems. We developed a 3-D process-based model (Hi-sAFe) and used it to (1) test if the spatiotemporal integration of resources sharing (light, water, nitrogen) between species could explain this productivity and (2) assess how agroforestry design or management may affect this productivity. We developed a novel method for the analysis of simulated data to identify and sort the processes determining yield by order of importance. The model was parameterized and calibrated on a hybrid walnut / durum wheat located on the Restinclières field (Hérault, France). After a detailed analysis of the functioning of this system, we explored by virtual experiments its response to design choices: (1) phenological traits of associated species, and (2) density and location of trees on the plot. The comprehensiveness of the Hi-sAFe model provides a new insight into the functioning of agroforestry systems. It clarifies the complexity of the real system. Our results put forward a deterministic interpretation of the performance of each species and of the total productivity of the crop-tree association (Land Equivalent Ratio). The analysis of virtual experiments offers practical ways for optimizing agroforestry systems.

Cette thèse étudie des modèles de populations branchantes appelés arbres de ramification, dans lesquels les individus évoluent indépendamment les uns des autres, ont des durées de vie indépendantes, identiquement distribuées (non nécessairement exponentielles), et donnent naissance à taux constant au cours de leur vie. On enrichit ces modèles en supposant que chaque individu porte un type et peut subir à la naissance une mutation, qui lui confère un nouveau type. On démontre dans le premier chapitre des résultats théoriques de convergence en loi pour des processus de Lévy bivariés sans sauts négatifs. Ces résultats sont ensuite exploités dans le deuxième chapitre pour établir un principe d'invariance pour l'arbre généalogique des populations décrites ci-dessus, enrichi de leur historique mutationnel, dans une asymptotique de grande taille de population. Enfin, on étudie dans le troisième chapitre la structure généalogique et le spectre de fréquence par site (nombre de mutations portées par un nombre donné d'individus) d'échantillons uniformes dans des populations branchantes critiques dont la limite d'échelle est un arbre brownien (par exemple, des arbres de naissance et mort critiques). Des perspectives d'applications de ces résultats à la génétique des populations sont présentées dans le quatrième chapitre. / This thesis studies branching population models called splitting trees, where individuals evolve independently from one another, have independent and identically distributed lifetimes (that are not necessarily exponential), and give birth at constant rate during their lives. We further assume that each individual carries a type, and possibly undergoes a mutation at her birth, that changes her type into a new one. In the first chapter, we prove convegence results for bivariate Lévy processes with non negative jumps. These theoretical results are used in the second chapter to establish an invariance principle for the genealogical tree of the populations described above, enriched with their mutational history, in a large population size asymptotic. Finally we study in the third chapter the genealogical structure and the site frequency spectrum (number of mutations carried by a given number of individuals) for uniform samples in critical branching populations whose scaling limit is a Brownian tree (e.g., critical birth-death trees). Possible future applications of these results to population genetics are presented in the fourth chapter.

Dans cette thèse, nous examinons différents cadres pour la théorie générale des opérades cycliques de Getzler et Kapranov. Comme le suggère le titre, nous établissons des fondements théoriques de natures syntaxiques, algébriques et catégorifiées pour la notion d’opérade cyclique. Dans le traitement syntaxique, nous proposons un langage formel à la manière du lambda-calcul, appelé mu-syntaxe, en tant que représentation légère de la structure <<entries-only >> d’opérades cycliques. Contrairement à la caractérisation originale des opérades cycliques, appelée la caractérisation <<exchangeable-output>> , selon laquelle les opérations d’une opérade cyclique ont des entrées et une sortie qui peut être << échangée >> avec une entrée, les opérades cycliques <<entries-only >> sont présentées comme des généralisations d’opérades pour lesquelles une opération n’a plus des entrées et une sortie, mais seulement des entrées (c’est-à-dire pour lesquelles la sortie est <<au même niveau>> que les entrées). Grâce aux méthodes de réécriture derrière le formalisme, nous donnons une preuve pas-à-pas complète de l’équivalence entre les définitions biaisées et non biaisées des opérades cycliques.Guidés par le principe du microcosme de Baez et Dolan et par les définitions algébriques des opérades de Kelly et Fiore, dans l’approche algébrique, nous définissons les opérades cycliques à l’intérieur de la catégorie des espèces de structures de Joyal. De cette façon, la caractérisation originale << exchangeable-output>> de Getzler et Kapranov, et la caractérisation alternative <<entries-only>> des opérades cycliques de Markl, sont toutes les deux incarnées comme monoïdes dans une catégorie monoïdale des espèces de structures. En s’appuyant sur un résultat de Lamarche sur la descente pour les espèces, nous utilisons ces définitions monoïdales pour prouver l’équivalence entre les points de vue <<exchangeable-output >> et << entries-only>> pour les opérades cycliques.Enfin, nous établissons une notion d’opérade cyclique catégorifiée pour les opérades cycliques avec symétries, définies dans la catégorie des ensembles en termes de générateurs et relations. Les catégorifications que nous introduisons sont obtenues en remplaçant des ensembles d’opérations de la même arité par des catégories, en relâchant certains axiomes de la structure, comme l’associativité et la commutativité, en isomorphismes, tout en laissant l’équivariance stricte, et en formulant des conditions de cohérence pour ces isomorphismes. Le théorème de cohérence que nous prouvons a la forme << tous les diagrammes d’isomorphismes canoniques commutent >>. Pour les opérades cycliques <<entries-only>> , notre preuve a un caractère syntaxique et s’appuie sur la cohérence des opérades non symétriques catégorifiées, établie par Došen et Petrić. Nous prouvons la cohérence des opérades cycliques <<exchangeable-output >>, en relevant au cadre catégorifié l’équivalence entre les définitions <<entries-only>> et <<exchangeable-output>> , mise en place précédemment dans l’approche algébrique. / In this thesis, we examine different frameworks for the general theory of cyclic operads of Getzler and Kapranov. As suggested by the title, we set up theoretical grounds of syntactic, algebraic and categorified nature for the notion of a cyclic operad.In the syntactic treatment, we propose a lambda-calculus-style formal language, called mu-syntax, as a lightweight representation of the entries-only cyclic operad structure. As opposed to the original exchangeable-output characterisation of cyclic operads, according to which the operations of a cyclic operad have inputs and an output that can be “exchanged” with one of the inputs, the entries-only cyclic operads have only entries (i.e. the output is put on the same level as the inputs). By employing the rewriting methods behind the formalism, we give a complete step-by-step proof of the equivalence between the unbiased and biased definitions of cyclic operads.Guided by the microcosm principle of Baez and Dolan and by the algebraic definitions of operads of Kelly and Fiore, in the algebraic approach we define cyclic operads internally to the category of Joyal’s species of structures. In this way, both the original exchangeable-output characterisation of Getzler and Kapranov, and the alternative entries-only characterisation of cyclic operads of Markl are epitomised as “monoid-like” objects in “monoidal-like” categories of species. Relying on a result of Lamarche on descent for species, we use these “monoid-like” definitions to prove the equivalence between the exchangeable-output and entries-only points of view on cyclic operads.Finally, we establish a notion of categorified cyclic operad for set-based cyclic operads with symmetries, defined in terms of generators and relations. The categorifications we introduce are obtained by replacing sets of operations of the same arity with categories, by relaxing certain defining axioms, like associativity and commutativity, to isomorphisms, while leaving the equivariance strict, and by formulating coherence conditions for these isomorphisms. The coherence theorem that we prove has the form “all diagrams of canonical isomorphisms commute”.For entries-only categorified cyclic operads, our proof is of syntactic nature and relies on the coherence of categorified operads established by Došen and Petrić. We prove the coherence of exchangeable-output categorified cyclic operads by “lifting to the categorified setting” theequivalence between entries-only and exchangeable-output cyclic operads, set up previously in the algebraic approach.

Les besoins en terre végétale pour l’aménagement d’espaces verts urbains induisent un prélèvement de sols agricoles ou naturels. D’autre part, des volumes considérables d’horizons profonds excavés lors de la construction de bâtiments sont mis en décharge en périphérie des villes, avec un impact sur l’environnement. Le recyclage de ces déchets inertes pour la construction de sols des espaces verts apparaît comme une solution prometteuse. Il est toutefois nécessaire de s’assurer que ces Technosols construits peuvent accueillir une diversité végétale et animale pour délivrer des services écosystémiques, comme propose de le faire ce travail de thèse. La composition des mélanges de matériaux (horizons profonds, compost de déchets verts, béton concassé) a été manipulée dans une expérimentation de 4000 m² en collaboration avec l’entreprise ECT et le CD 93. Un suivi de quatre ans a montré que le compost utilisé était responsable de la mort de certains arbres, mais qu’associé au béton, il augmentait fortement leur vitesse de croissance et de colonisation par la macrofaune. En usage prairial, l’ajout de compost a augmenté la production de biomasse et modifié l’assemblage de la communauté végétale, en favorisant les espèces compétitives, mais pas de la macrofaune. Dans une expérience en mésocosmes visant à étudier le lien entre diversité végétale et productivité, une complémentarité entre espèces a été observée pour une des trois communautés, à un niveau de fertilité intermédiaire. Il est donc possible d’améliorer la productivité primaire de nouveaux écosystèmes en manipulant la composition des mélanges de matériaux tout en évitant la dominance de certaines espèces, afin de conserver des communautés diversifiées / Topsoil requirements for the development of urban green spaces induce a harvest of agricultural or natural soils. On the other hand, huge volumes of deep horizons excavated during the construction of buildings are dumped on the outskirts of cities, with an impact on the environment. The recycling of these inert wastes for the construction of soils for green spaces appears as a promising solution. However, it is necessary to ensure that these constructed Technosols are suitable for plant and animal diversity, and can deliver ecosystem services, as proposed by this thesis. The composition of the material mixes (deep horizons, urban green waste compost, crushed concrete) was manipulated in a 4000 m² experiment in collaboration with the company ECT and CD 93. A four-year monitoring showed that the compost used was responsible for the death of some trees, but associated with concrete, it greatly increased their growth rate and macrofaunal colonization. In the meadow land use, the addition of compost increased biomass production and altered the assemblage of the plant community, favoring competitive species, but no effect on macrofauna assemblage was observed. In a mesocosm experiment aiming at studying the link between plant diversity and productivity, complementarity between species was observed for one of the three communities, at an intermediate level of fertility. It is therefore possible to improve the primary productivity of new ecosystems by manipulating the composition of the mixtures of materials while avoiding the dominance of certain species, in order to preserve diversified communities

No description available.