Fonction OU exclusif | EPFL Graph Search

La fonction OU exclusif, souvent appelée XOR (eXclusive OR) ou disjonction exclusive, ou somme binaire en cryptographie où il est noté +, ou encore ⊻ en algèbre relationnelle, est un opérateur logique de l'algèbre de Boole. À deux opérandes, qui peuvent avoir chacun la valeur VRAI ou FAUX, il associe un résultat qui a lui-même la valeur VRAI seulement si les deux opérandes ont des valeurs distinctes. Cet opérateur est très utilisé en électronique, en informatique, et aussi en cryptographie du fait de ses propriétés intéressantes. Son symbole est traditionnellement un signe plus dans un cercle : « ⊕ ». Définition Appelons A et B les deux opérandes considérés. Convenons de représenter leur valeur ainsi : :1 = VRAI :0 = FAUX L'opérateur XOR est défini par sa table de vérité, qui indique pour toutes les valeurs possibles de A et B la valeur du résultat R : Comme on peut le voir, l'opérateur logique XOR, ou OU exclusif, peut se définir par la ph

Secondary Structure Assignment of Amyloid-β Peptide Using Chemical Shifts

Ursula Röthlisberger, Geoffrey Wood

The distinct conformational dependence of chemical shifts caused by R-helices and β-sheets renders NMR chemical shift analysis a powerful tool for the structural determination of proteins. However, the time scale of NMR experiments can make a secondary structure assignment of highly flexible peptides or proteins, which may be converting between conformational substates, problematic. For instance the amyloid-β monomer, according to NMR chemical shifts, adopts a predominately random coil struc- ture in aqueous solution (with

2011

The Learnability of the Grammar of Jazz: Bayesian Inference of Hierarchical Structures in Harmony

Daniel Harasim

Musical grammar describes a set of principles that are used to understand and interpret the structure of a piece according to a musical style. The main topic of this study is grammar induction for harmony --- the process of learning structural principles from the observation of chord sequences. The question how grammars are learnable by induction from sequential data is an instance of the more general question how abstract knowledge is inducible from the observation of data --- a central question of cognitive science. Under the assumption that human learning approximately follows the principles of rational reasoning, Bayesian models of cognition can be used to simulate learning processes. This study investigates what prior knowledge makes it possible to learn musical grammar inductively from Jazz chord sequences using Bayesian models and computational simulations. The theoretical part of the thesis presents how questions about learnability can be studied in a unified framework involving music analysis, cognitive modeling, Bayesian statistics, and computational simulations. A new grammar formalism, called Probabilistic Abstract Context-Free Grammar (PACFG), is proposed that allows for flexible probability models which facilitate the grammar-induction experiments of this study. PACFG can jointly model multiple musical dimensions such as harmony and rhythm, and can use coordinate ascent variational inference for grammar learning. The empirical part of the thesis reports supervised and unsupervised grammar-learning experiments. To train and evaluate grammar models, a ground-truth dataset of hierarchical analyses of complete Jazz standards, called the Jazz Harmony Treebank (JHT), was created. The supervised grammar-learning experiments, in which grammars for Jazz harmony are learned from the JHT analyses, show that jointly modeling harmony and rhythm significantly improves the grammar models' prediction of the ground truth. The performance and robustness of the grammars are further improved by a transpositionally invariant parameterization of rule probabilities. Following the supervised grammar learning, unsupervised grammar learning was performed by inducing harmony grammars merely from Jazz chord sequences, without the observation of the JHT trees. The results show that the best induced grammar performs similarly well as the best supervised grammar. In particular, the goal-directedness of functional harmony does not need to be assumed a priori, but can be learned without usage of music-specific prior knowledge. The findings of this thesis show that general prior knowledge enables an ideal learner to acquire abstract musical principles by statistical learning. In conclusion, it is plausible that much aspects of musical grammar have been learned by Jazz musicians and listeners, instead of being innate predispositions or explicitly taught concepts. This thesis is moreover embedded into the context of empirical music research and digital humanities. Current studies either describe complex musical structures qualitatively or investigate simpler aspects quantitatively. The computational models developed in this thesis demonstrate that deep insights into music and statistical analyses are not mutually exclusive. They enable a new kind of data-driven music theory and musicology, for instance through comparative analyses of musical grammar for different styles such as Jazz, Rock, and Western classical music.

EPFL2020

Exact Synthesis of ESOP Forms

Giovanni De Micheli, Heinz Riener, Bruno Schmitt Antunes

We present an exact synthesis approach for computing Exclusive-or Sum-of-Products (ESOP) forms with a minimum number of product terms using Boolean satisfiability. Our approach finds one or more ESOP forms for a given Boolean function. The approach can deal with incompletely specified Boolean functions defined over many Boolean variables and is particularly fast if the Boolean function can be expressed with only a few product terms. We describe the formalization of the ESOP synthesis problem with a fixed number of terms as a decision problem and present search procedures for determining ESOP forms of minimum size. We further discuss how the search procedures can be relaxed to find ESOP forms of small sizes in reasonable time. We experimentally evaluate the performance of the SAT-based synthesis procedures on completely and incompletely specified Boolean functions.

Springer2019

The Learnability of the Grammar of Jazz: Bayesian Inference of Hierarchical Structures in Harmony

Daniel Harasim

EPFL2020