Academic literature on the topic 'Permutations (Mathématiques) – Informatique'

Depuis plusieurs decennies les decompositions de graphes ont ete largement etudiees, en particulier comme des outils destines a mettre en uvre le paradigme diviser pour resoudre. Ici, nous nous interessons a des decompositions dont le point commun est le suivant: identifier des ensembles d'elements d'un graphe qui ont un comportement similaire vis a vis du reste du graphe. Ces ensembles sont appeles ensembles de decomposition. Nous formalisons et etudions un concept central en theorie de la decomposition: la notion de permutation factorisante. Il s'agit d'une permutation sur les sommets ou les arcs du graphe qui respecte la decomposition de ce dernier en ensembles de decomposition. Nous illustrons son interet dans le cadre de plusieurs decompositions: nous montrons que calculer la decomposition par substitution est equivalent a calculer une permutation factorisante. En utilisant la theorie de la decomposition par substitution, nous proposons une nouvelle decomposition: la decomposition en blocs des graphes d'heritage. Les graphes d'heritage (appeles aussi hierarchies d'heritage) sont les graphes orientes sans circuits possedant un plus grand et un plus petit element. Ils modelisent des relations souvent presentes dans les langages a objets ou en representation de connaissances. Nous proposons des algorithmes de calcul de cette decomposition, la aussi bases sur le calcul d'une permutation factorisante

Les substitutions sont des applications qui remplacent chaque lettre d'un alphabet par un mot sur le même alphabet. Elle agissent naturellement sur des suites infinies de symboles, et produisent des systèmes très structurés ayant beaucoup de propretés. Cette thèse porte sur l'étude d'une classe particulière vérifiant des restriction algébriques, les substitutions de type Pisot, et leurs objets associés, de nature dynamique, fractale ou combinatoire. Nous commençons par l'étude combinatoire de certaines propriétés qualitatives des motifs bi-dimensionnels engendrés par une version "duale" des substitutions de type Pisot. On applique ces résultats à l'étude des familles infinies de substitutions définies comme l'ensemble des produits finis sur un ensemble fini de susbtitutions. On obtient des propriétés dynamiques des systèmes symboliques associés, des caractérisations de certaines propriétés topologiques des fractals de Rauzy associés, des propriétés des valeurs propres Pisot associées, et des applications en géométrie discrète. Une attention particulière est portée sur les substitutions associées aux algorithmes de fraction continues multidimensionnels d'Arnoux-Rauzy, Brun et Jacobi-Perron. Ensuite nous donnons des constructions explicites pour donner une description complète des groupes fondamentaux de fractals de Rauzy planaires, dans le cas où le groupe est dénombrable. Dans les deux derniers chapitres, on s'affranchit de la condition algébrique Pisot, pour étudidier des objets plus généraux provenant des outils combinatoires utilisés dans les précédents chapitres, en insistant sur des questions d'(in)décidabilité calculatoire
Substitutions are mappings which replace each symbol of a given alphabet by a word over the same alphabet. They naturally act over infinite sequences of symbols, and produce highly ordered Systems with many properties. This thesis concerns a particular class with algebraic restrictions, Pisot substitutions, and their related objects of dynamical, fractal o combinatorial nature. We begin with the combinatorial study of some qualitative properties of the two-dimensional patterns generated by iterating a two-dimensional "dual" version of Pisot substitutions. We apply these results to study the infinite families of substitutions obtained by taking arbitrary products over a finite set of Pisot substitutions. Applications include dynamica properties of the associated symbolic Systems, some language theoretical characterization of some topological properties of their associated Rauzy fractals, some number-theoretical properties of their associated Pisot numbers, and some results in discrete geometry. Particular focus is set on the substitutions associated with the Arnoux-Rauzy, Brun and Jacobi-Perron multidimensional continued fraction algorithms Next we give explicit construction to give a complete description of the possible fondamental groups of planar Rauzy fractals in the case where the group is countable. In the last two chapters, we "step back" from the Pisot algebraic assumption to study some more general objects arising from the combinatorial tools used in the previous chapters, focusing on some computational (un)decidability questions

La thèse se compose de deux parties. La première partie relate de l'étude de schémas de chiffrement par blocs, notamment les schémas de Feistel avec permutations internes et les schémas du type Misty. Le cadre de l'étude est générique, i. E. Les permutations internes sont supposées aléatoires. Ceci permet d'obtenir des propriétés de la structure même des schémas, sans prendre en compte leur contexte d'utilisation. Cette partie focalise sur les attaques génériques sur ces deux schémas. La deuxième partie concerne l'étude de cryptosystèmes multivariés. Une propriété de la différentielle de la clé publique du schéma HM est exhibée, fournissant un distingueur. Par ailleurs, une attaque par bases de Gröbner permet d'inverser le système efficacement. Nous exposons également une attaque sur le schéma HFE, permettant le recouvrement de la clé privée pour une famille d'instances particulières, classées à présent comme "clés faibles"
The thesis is made up of two parts. The first one deals with the study of bloc ciphers, Feistel networks with internal permutations and Misty-like schemes. The context is generic, in the sense that the internal permutations are supposed random. His allows to obtain properties that only concern the structure of the scheme and do not depend on any particular application. This part focuses on generic attacks on these two schemes. The second part is about multivariate cryptosystems. A differential property of the public key of HM is shown, allowing to get an efficient distinguisher. Moreover, we can invert the system by using Gröbner bases. We also describe a key-recovery attack on HFE, which works for a family of key instances, now called "weak keys"

Les langages de programmation fonctionnels font partie des langages de très haut niveau. Ils peuvent être vus comme des extensions ou des variantes du lambda-calcul, un formalisme mathématique puissant qui a donné lieu à d'innombrables travaux durant les vingt dernières années. Ils bénéficient de ce fait assez directement, pour la définition de leur sémantique, du riche corps de doctrine qui a été constitué autour de celui-ci. Si ce formalisme, au départ simple, donne lieu à tant de variations, c'est en particulier à des fins d'implantation. Notamment, au travers de la béta-réduction (une opération fondamentale du lambda-calcul) différentes stratégies d'évaluation peuvent être définies : elles constituent autant de spécifications possibles pour les implantations de ces langages. La béta-réduction est une opération complexe comparée aux instructions machines utilisées pour la mettre en oeuvre et, de ce fait, il existe un fossé assez important entre la spécification d'une stratégie d'évaluation et sa réalisation. En conséquence, les preuves de corrections des implantations de langages fonctionnels restent limitées, rendant difficile les comparaisons formelles entre les différentes implantations. Les calculs de substitutions explicites, introduits par Curien, remplacent l'opération de substitution intervenant dans la béta-réduction par des opérations plus élémentaires. Ces calculs décomposent la béta-réduction en une règle de déclenchement de la substitution et un ensemble de règles de propagation de cette substitution. Ces règles de propagation ont un grain fin qui rapprochent la béta-réduction des instructions qui l'implantent. L'introduction de ces calculs a ouvert une voie nouvelle de recherche d'un formalisme mieux adapté à la description unifiée de sémantique, de stratégie d'évaluation et d'implantations associées. [. . . ]

Après une partie introductive, où les définitions de base sont fournies et des motivations pour le travail sont présentées, la thèse se divise en deux chapitres. Le premier chapitre traite de certaines classes de polyominos, les polyominoes convexes dirigés et les polyominoes k-convexes. Dans la première partie du chapitre nous présentons une approche unifiée pour obtenir les séries génératrices des polyominoes convexes dirigés selon différentes statistiques. Dans la deuxième partie du chapitre nous traitons le problème de l'énumeration des polyominos k-convexes selon leur demi-périmètre. Ce problème est consideré difficile et il n'a été résolu que pour k= 1,2. Nous donnons une énumération complète, pour tout k, des sous classes des k-parallélogrammes et des polyominoes k-convexes dirigées. Le deuxième chapitre traite de polyominoes définis par des paires de permutations, appelles permutominoes. Nous introduisons une généralisation naturelle de la classe des permutominoes à toute dimension et nous presentons une approche d'énumération unifiée qui nous permets d'obtenir de nouveaux résultats et de retrouver des resultats déjà connus. Enfin, pour le cas de dimension deux, nous résolvons le problème ouvert de la caractérisation des paires de permutations associées à un permutomino convexe par colonne et nous donnons une preuve bijective de leur énumération
After an introductory part, where some basic definitions are provided and some motivations for the investigation are presented, the thesis is divided into two chapters. The first chapter concerns particular classes of polyominoes. After a presentation of the background and the introduction of notations, we introduce a unified approach to obtain generating functions for different statistics on directed convex polyominoes. The problem of counting k-convex polyominoes according to their semi-perimeter is a difficult problem: it is solved for k=1,2. In the last part of the first chapter we introduce two particular classes of k-convex polyominoes, namely k-parallelogram and directed k-convex polyominoes, and we solve completely the corresponding enumeration problem. The second chapter deals with permutominoes (polyominoes defined by pairs of permutations). It begins with a background and some classical enumerative results for particular permutominoes. We introduce a naturel generalization of permutominoes to any dimension and we obtain new enumerative results and other already known are recovered by a unified approach. Concerning the two dimensional case, we solve the open problem of the characterization of the pairs of permutations defining the column-convex permutominoes and we find a bijective proof for the number of directed column-convex permutominoes, that we know to be counted by factoriel numbers

La combinatoire algébrique est le champ de recherche qui utilise des méthodes combinatoires et des algorithmes pour étudier les problèmes algébriques, et applique ensuite des outils algébriques à ces problèmes combinatoires. L’un des thèmes centraux de la combinatoire algébrique est l’étude des permutations car elles peuvent être interprétées de bien des manières (en tant que bijections, matrices de permutations, mais aussi mots sur des entiers, ordre totaux sur des entiers, sommets du permutaèdre…). Cette riche diversité de perspectives conduit alors aux généralisations suivantes du groupe symétrique. Sur le plan géométrique, le groupe symétrique engendré par les transpositions élémentaires est l’exemple canonique des groupes de réflexions finis, également appelés groupes de Coxeter. Sur le plan monoïdal, ces même transpositions élémentaires deviennent les opérateurs du tri par bulles et engendrent le monoïde de 0-Hecke, dont l’algèbre est la spécialisation à q=0 de la q-déformation du groupe symétrique introduite par Iwahori. Cette thèse se consacre à deux autres généralisations des permutations. Dans la première partie de cette thèse, nous nous concentrons sur les matrices de permutations partielles, en d’autres termes les placements de tours ne s’attaquant pas deux à deux sur un échiquier carré. Ces placements de tours engendrent le monoïde de placements de tours, une généralisation du groupe symétrique. Dans cette thèse nous introduisons et étudions le 0-monoïde de placements de tours comme une généralisation du monoïde de 0-Hecke. Son algèbre est la dégénérescence à q=0 de la q-déformation du monoïde de placements de tours introduite par Solomon. On étudie par la suite les propriétés monoïdales fondamentales du 0-monoïde de placements de tours (ordres de Green, propriété de treillis du R-ordre, J-trivialité) ce qui nous permet de décrire sa théorie des représentations (modules simples et projectifs, projectivité sur le monoïde de 0-Hecke, restriction et induction le long d’une fonction d’inclusion).Les monoïdes de placements de tours sont en fait l’instance en type A de la famille des monoïdes de Renner, définis comme les complétés des groupes de Weyl (c’est-à-dire les groupes de Coxeter cristallographiques) pour la topologie de Zariski. Dès lors, dans la seconde partie de la thèse nous étendons nos résultats du type A afin de définir les monoïdes de 0-Renner en type B et D et d’en donner une présentation. Ceci nous conduit également à une présentation des monoïdes de Renner en type B et D, corrigeant ainsi une présentation erronée se trouvant dans la littérature depuis une dizaine d’années. Par la suite, nous étudions comme en type A les propriétés monoïdales de ces nouveaux monoïdes de 0-Renner de type B et D : ils restent J-triviaux, mais leur R-ordre n’est plus un treillis. Cela ne nous empêche pas d’étudier leur théorie des représentations, ainsi que la restriction des modules projectifs sur le monoïde de 0-Hecke qui leur est associé. Enfin, la dernière partie de la thèse traite de différentes généralisations des permutations. Dans une récente séries d’articles, Châtel, Pilaud et Pons revisitent la combinatoire algébrique des permutations (ordre faible, algèbre de Hopf de Malvenuto-Reutenauer) en terme de combinatoire sur les ordres partiels sur les entiers. Cette perspective englobe également la combinatoire des quotients de l’ordre faible tels les arbres binaires, les séquences binaires, et de façon plus générale les récents permutarbres de Pilaud et Pons. Nous généralisons alors l’ordre faibles aux éléments des groupes de Weyl. Ceci nous conduit à décrire un ordre sur les sommets des permutaèdres, associaèdres généralisés et cubes dans le même cadre unifié. Ces résultats se basent sur de subtiles propriétés des sommes de racines dans les groupes de Weyl qui s’avèrent ne pas fonctionner pour les groupes de Coxeter qui ne sont pas cristallographiques
Algebraic combinatorics is the research field that uses combinatorial methods and algorithms to study algebraic computation, and applies algebraic tools to combinatorial problems. One of the central topics of algebraic combinatorics is the study of permutations, interpreted in many different ways (as bijections, permutation matrices, words over integers, total orders on integers, vertices of the permutahedron…). This rich diversity of perspectives leads to the following generalizations of the symmetric group. On the geometric side, the symmetric group generated by simple transpositions is the canonical example of finite reflection groups, also called Coxeter groups. On the monoidal side, the simple transpositions become bubble sort operators that generate the 0-Hecke monoid, whose algebra is the specialization at q=0 of Iwahori’s q-deformation of the symmetric group. This thesis deals with two further generalizations of permutations. In the first part of this thesis, we first focus on partial permutations matrices, that is placements of pairwise non attacking rooks on a n by n chessboard, simply called rooks. Rooks generate the rook monoid, a generalization of the symmetric group. In this thesis we introduce and study the 0-Rook monoid, a generalization of the 0-Hecke monoid. Its algebra is a proper degeneracy at q = 0 of the q-deformed rook monoid of Solomon. We study fundamental monoidal properties of the 0-rook monoid (Green orders, lattice property of the R-order, J-triviality) which allow us to describe its representation theory (simple and projective modules, projectivity on the 0-Hecke monoid, restriction and induction along an inclusion map).Rook monoids are actually type A instances of the family of Renner monoids, which are completions of the Weyl groups (crystallographic Coxeter groups) for Zariski’s topology. In the second part of this thesis we extend our type A results to define and give a presentation of 0-Renner monoids in type B and D. This also leads to a presentation of the Renner monoids of type B and D, correcting a misleading presentation that appeared earlier in the litterature. As in type A we study the monoidal properties of the 0-Renner monoids of type B and D : they are still J-trivial but their R-order are not lattices anymore. We study nonetheless their representation theory and the restriction of projective modules over the corresponding 0-Hecke monoids. The third part of this thesis deals with different generalizations of permutations. In a recent series of papers, Châtel, Pilaud and Pons revisit the algebraic combinatorics of permutations (weak order, Malvenuto-Reutenauer Hopf algebra) in terms of the combinatorics of integer posets. This perspective encompasses as well the combinatorics of quotients of the weak order such as binary trees, binary sequences, and more generally the recent permutrees of Pilaud and Pons. We generalize the weak order on the elements of the Weyl groups. This enables us to describe the order on vertices of the permutahedra, generalized associahedra and cubes in the same unified context. These results are based on subtle properties of sums of roots in Weyl groups, and actually fail for non-crystallographic Coxeter groups

L'optimisation joue un rôle essentiel dans la conception industrielle, mais ne se limite pas à la minimisation d'une simple fonction, comme le coût ou la résistance. Ces outils sont également utilisés dans les phases conceptuelles, pour mieux comprendre ce qui est possible. Pour soutenir cette exploration, nous nous concentrons sur les algorithmes de diversité de qualité (QD), qui produisent des ensembles de solutions variées et performantes. Ces techniques nécessitent souvent l'évaluation de millions de solutions, ce qui les rend peu pratiques dans les cas de conception. Dans cette thèse, nous proposons des méthodes pour améliorer radicalement l'efficacité des données de la QD avec l'apprentissage machine, permettant son application à la conception. Dans notre première contribution, nous développons une méthode de modélisation des performances des réseaux neuronaux évolués utilisés pour le contrôle et la conception. Les structures de ces réseaux se développent et changent, ce qui les rend difficiles à modéliser - mais grâce à une nouvelle méthode, nous sommes en mesure d'estimer leurs performances en fonction de leur hérédité, améliorant ainsi l'efficacité des données à plusieurs reprises. Dans notre deuxième contribution, nous combinons l'optimisation basée sur un modèle avec MAP-Elites, un algorithme QD. Un modèle de performance est créé à partir de modèles connus, et MAP-Elites crée un nouvel ensemble de modèles en utilisant cette approximation. Un sous-ensemble de ces conceptions est évalué pour améliorer le modèle, et le processus se répète. Nous montrons que cette approche améliore l'efficacité de MAP-Elites par des ordres de grandeur. Notre troisième contribution intègre des modèles générateurs dans MAP-Elites pour apprendre des codages spécifiques à un domaine. Un auto-codeur variationnel est formé sur les solutions produites par MAP-Elites, capturant la "recette" commune pour une haute performance. Ce codage appris peut ensuite être réutilisé par d'autres algorithmes pour une optimisation rapide, y compris MAP-Elites. Tout au long de cette thèse, bien que notre vision se concentre sur la conception, nous examinons les applications dans d'autres domaines, comme la robotique. Ces avancées ne sont pas exclusives à la conception, mais servent de travail de base à l'intégration de la DQ et de l'apprentissage machine
Optimization plays an essential role in industrial design, but is not limited to minimization of a simple function, such as cost or strength. These tools are also used in conceptual phases, to better understand what is possible. To support this exploration we focus on Quality Diversity (QD) algorithms, which produce sets of varied, high performing solutions. These techniques often require the evaluation of millions of solutions -- making them impractical in design cases. In this thesis we propose methods to radically improve the data-efficiency of QD with machine learning, enabling its application to design. In our first contribution, we develop a method of modeling the performance of evolved neural networks used for control and design. The structures of these networks grow and change, making them difficult to model -- but with a new method we are able to estimate their performance based on their heredity, improving data-efficiency by several times. In our second contribution we combine model-based optimization with MAP-Elites, a QD algorithm. A model of performance is created from known designs, and MAP-Elites creates a new set of designs using this approximation. A subset of these designs are the evaluated to improve the model, and the process repeats. We show that this approach improves the efficiency of MAP-Elites by orders of magnitude. Our third contribution integrates generative models into MAP-Elites to learn domain specific encodings. A variational autoencoder is trained on the solutions produced by MAP-Elites, capturing the common “recipe” for high performance. This learned encoding can then be reused by other algorithms for rapid optimization, including MAP-Elites. Throughout this thesis, though the focus of our vision is design, we examine applications in other fields, such as robotics. These advances are not exclusive to design, but serve as foundational work on the integration of QD and machine learning

À l'origine de cette thèse, nous nous sommes intéressés à l'algorithme de tri TimSort qui est apparu en 2002, alors que la littérature sur le problème du tri était déjà bien dense. Bien qu'il soit utilisé dans de nombreux langages de programmation, les performances de cet algorithme n'avaient jamais été formellement analysées avant nos travaux. L'étude fine de TimSort nous a conduits à enrichir nos modèles théoriques, en y incorporant des caractéristiques modernes de l'architecture des ordinateurs. Nous avons, en particulier, étudié le mécanisme de prédiction de branchement. Grâce à cette analyse théorique, nous avons pu proposer des modifications de certains algorithmes élémentaires (comme l'exponentiation rapide ou la dichotomie) qui utilisent ce principe à leur avantage, améliorant significativement leurs performances lorsqu'ils sont exécutés sur des machines récentes. Enfin, même s'il est courant dans le cadre de l'analyse en moyenne de considérer que les entrées sont uniformément distribuées, cela ne semble pas toujours refléter les distributions auxquelles nous sommes confrontés dans la réalité. Ainsi, une des raisons du choix d'implanter TimSort dans des bibliothèques standard de Java et Python est probablement sa capacité à s'adapter à des entrées partiellement triées. Nous proposons, pour conclure cette thèse, un modèle mathématique de distribution non-uniforme sur les permutations qui favorise l'apparition d'entrées partiellement triées, et nous en donnons une analyse probabiliste détaillée
At first, we were interested in TimSort, a sorting algorithm which was designed in 2002, at a time where it was hard to imagine new results on sorting. Although it is used in many programming languages, the efficiency of this algorithm has not been studied formally before our work. The fine-grain study of TimSort leads us to take into account, in our theoretical models, some modern features of computer architecture. In particular, we propose a study of the mechanisms of branch prediction. This theoretical analysis allows us to design variants of some elementary algorithms (like binary search or exponentiation by squaring) that rely on this feature to achieve better performance on recent computers. Even if uniform distributions are usually considered for the average case analysis of algorithms, it may not be the best framework for studying sorting algorithms. The choice of using TimSort in many programming languages as Java and Python is probably driven by its efficiency on almost-sorted input. To conclude this dissertation, we propose a mathematical model of non-uniform distribution on permutations, for which permutations that are almost sorted are more likely, and provide a detailed probabilistic analysis

La résolution efficace de problèmes d'optimisation a permutation de grande taille nécessite le développement de méthodes hybrides complexes combinant différentes classes d'algorithmes d'optimisation. L'hybridation des metaheuristiques avec les méthodes exactes arborescentes, tel que l'algorithme du branch-and-bound (B&B), engendre une nouvelle classe d'algorithmes plus efficace que ces deux classes de méthodes utilisées séparément. Le défi principal dans le développement de telles méthodes consiste a trouver des liens ou connections entre les stratégies de recherches divergentes utilisées dans les deux classes de méthodes. Les Algorithmes Genetiques (AGs) sont des metaheuristiques, a base de population, tr'es populaires bas'es sur des op'erateurs stochastiques inspirés de la théorie de l'évolution. Contrairement aux AGs et aux m'etaheuristiques généralement, les algorithmes de B&B sont basées sur l'énumération implicite de l'espace de recherche représente par le moyen d'un arbre, dit arbre de recherche. Notre approche d'hybridation consiste a définir un codage commun des solutions et de l'espace de recherche ainsi que des opérateurs de recherche ad'equats afin de permettre un couplage efficace de bas niveau entre les deux classes de méthodes AGs et B&B. La représentation de l'espace de recherche par le moyen d'arbres est traditionnellement utilis'ee dans les algorithmes de B&B. Dans cette thèse, cette représentation a été adaptée aux metaheuristiques. L'encodage des permutations au moyen de nombres naturels faisant référence a l'ordre d'énumération lexicographique des permutations dans l'arbre du B&B, est proposé comme une nouvelle manière de représenter l'espace de recherche des problèmes 'a permutations dans les metaheuristiques. Cette méthode de codage est basée sur les propriétés mathématiques des permutations, 'a savoir les codes de Lehmer et les tables d'inversions ainsi que les système d'énumération factoriels. Des fonctions de transformation permettant le passage entre les deux représentations (permutations et nombres) ainsi que des opérateurs de recherche adaptes au codage, sont définis pour les problèmes 'a permutations généralisés. Cette représentation, désormais commune aux metaheuristiques et aux algorithmes de B&B, nous a permis de concevoir des stratégies d'hybridation et de collaboration efficaces entre les AGs et le B&B. En effet, deux approches d'hybridation entre les AGs et les algorithmes de B&B (HGABB et COBBIGA) bas'es sur cette représentation commune ont été proposées dans cette thèse. Pour validation, une implémentation a été réalisée pour le problème d'affectation quadratique 'a trois dimension (Q3AP). Afin de résoudre de larges instances de ce problème, nous avons aussi propose une parallélisation pour les deux algorithme hybrides, basée sur des techniques de décomposition d'espace (décomposition par intervalle) utilisées auparavant pour la parallélisation des algorithmes de B&B. Du point de vue implémentation, afin de faciliter de futurs conceptions et implémentations de méthodes hybrides combinant metaheuristiques et méthodes exacte arborescentes, nous avons développe une plateforme d'hybridation intégrée au logiciel pour metaheuristiques, ParadisEO. La nouvelle plateforme a été utilisée pour réaliser des expérimentations intensives sur la grille de calcul Grid'5000.