Composition de fonctions

Résumé

La composition de fonctions (ou composition d’applications) est, en mathématiques, un procédé qui consiste, à partir de deux fonctions, à en construire une nouvelle. Pour cela, on utilise les images de la première fonction comme arguments pour la seconde (à condition que cela ait un sens). On parle alors de fonction composée (ou d'application composée). Définition formelle Soient X, Y et Z trois ensembles quelconques. Soient deux fonctions f:X\to Y et g:Y \to Z. On définit la composée de f par g, notée g \circ f, par :\forall x \in X,\ (g\circ f)(x)=g(f(x)). On applique ici f à l'argument x, puis on applique g au résultat. On obtient ainsi une nouvelle fonction g \circ f: X \to Z. La notation g \circ f se lit « g rond f », « f suivie de g » ou encore « g après f ». On note parfois g\circ f(x) pour (g \circ f)(x). Cette définition peut être visualisée par un diagramme

Source officielle

https://fr.wikipedia.org/wiki/Composition_de_fonctions

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (30)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées (2)

Unités associées

Chargement

Concepts associés (108)

Concepts associés

Chargement

Cours associés (42)

Cours associés

Chargement

Séances de cours associées (86)

Séances de cours associées

Chargement

Accelerating parser combinators with macros

Eric Beguet, Manohar Jonnalagedda

Parser combinators provide an elegant way of writing parsers: parser implementations closely follow the structure of the underlying grammar, while accommodating interleaved host language code for data processing. However, the host language features used for composition introduce substantial overhead, which leads to poor performance. In this paper, we present a technique to systematically eliminate this overhead. We use Scala macros to analyse the grammar specification at compile-time and remove composition, leaving behind an efficient top-down, recursive-descent parser. We compare our macro-based approach to a staging-based approach using the LMS framework, and provide an experience report in which we discuss the advantages and drawbacks of both methods. Our library outperforms Scala's standard parser combinators on a set of benchmarks by an order of magnitude, and is 2x faster than code generated by LMS.

ACM Press2014

Chargement

Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the original message m, or a completely unrelated one. In the common split-state model, the codeword consists of multiple blocks (or states) and each block is tampered with independently. The central goal in the split-state model is to construct high rate non-malleable codes against all functions with only two states (which are necessary). Following a series of long and impressive line of work, constant rate, two-state, non-malleable codes against all functions were recently achieved by Aggarwal et al. [2]. Though constant, the rate of all known constructions in the split state model is very far from optimal (even with more than two states). In this work, we consider the question of improving the rate of splitstate non-malleable codes. In the "information theoretic" setting, it is not possible to go beyond rate 1/2. We therefore focus on the standard computational setting. In this setting, each tampering function is required to be efficiently computable, and the message in the tampered codeword is required to be either the original message m or a "computationally" independent one. In this setting, assuming only the existence of one-way functions, we present a compiler which converts any poor rate, two-state, (sufficiently strong) non-malleable code into a rate-1, two-state, computational non-malleable code. These parameters are asymptotically optimal. Furthermore, for the qualitative optimality of our result, we generalize the result of Cheraghchi and Guruswami [10] to show that the existence of one-way functions is necessary to achieve rate > 1/2 for such codes. Our compiler requires a stronger form of non-malleability, called augmented non-malleability. This notion requires a stronger simulation guarantee for non-malleable codes and simplifies their modular usage in cryptographic settings where composition occurs. Unfortunately, this form of non-malleability is neither straightforward nor generally guaranteed by known results. Nevertheless, we prove this stronger form of non-malleability for the two-state construction of Aggarwal et al. [3]. This result is of independent interest.

Springer Int Publishing Ag2016

Chargement

Twisting structures and morphisms up to strong homotopy

Kathryn Hess Bellwald

We define twisted composition products of symmetric sequences via classifying morphisms rather than twisting cochains. Our approach allows us to establish an adjunction that simultaneously generalizes a classic one for algebras and coalgebras, and the bar-cobar adjunction for quadratic operads. The comonad associated to this adjunction turns out to be, in several cases, a standard Koszul construction. The associated Kleisli categories are the "strong homotopy" morphism categories. In an appendix, we study the co-ring associated to the canonical morphism of cooperads , which is exactly the two-sided Koszul resolution of the associative operad , also known as the Alexander-Whitney co-ring.

2019

Chargement

Springer Int Publishing Ag2016