Programmation structurée | EPFL Graph Search

La programmation structurée constitue un sous-ensemble de la programmation impérative. C'est un paradigme important de la programmation, apparu vers 1970. Elle dérive de travaux de Nicklaus Wirth pour son Algol W et reçut son coup d'envoi avec l'article fondateur de Dijkstra dans Communications of the ACM nommé GO TO statement considered harmful (L'instruction GOTO est considérée nocive). Elle est en effet célèbre pour avoir tenté d’éliminer l'instruction goto, ou, du moins, de limiter son usage à des cas inhabituels et graves . Usage La programmation structurée est possible dans n'importe quel langage de programmation procédural, mais certains, comme le FORTRAN IV, s'y prêtaient très mal. Vers 1970, la programmation structurée devint une technique populaire, et les langages de programmation procéduraux intégrèrent à l'image d'Algol et en le dépassant des mécanismes rendant aisée la programmation structurée (faisant tomber en désuétude des langages parfois novateurs, mais

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In this paper we focus on the maximum item size s and the maximum item value v. We give algorithms that run in time O(n + s³) and O(n + v³) for the Knapsack problem, and in time Õ(n + s^{5/3}) for the Subset Sum problem. Our algorithms work for the more general problem variants with multiplicities, where each input item comes with a (binary encoded) multiplicity, which succinctly describes how many times the item appears in the instance. In these variants n denotes the (possibly much smaller) number of distinct items. Our results follow from combining and optimizing several diverse lines of research, notably proximity arguments for integer programming due to Eisenbrand and Weismantel (TALG 2019), fast structured (min,+)-convolution by Kellerer and Pferschy (J. Comb. Optim. 2004), and additive combinatorics methods originating from Galil and Margalit (SICOMP 1991).

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Covariance Estimation for Random Surfaces beyond Separability

Tomas Masák

This thesis focuses on non-parametric covariance estimation for random surfaces, i.e.~functional data on a two-dimensional domain. Non-parametric covariance estimation lies at the heart of functional data analysis, andconsiderations of statistical and computational efficiency often compel the use of separability of the covariance, when working with random surfaces. We seek to provide efficient alternatives to this ambivalent assumption.In Chapter 2, we study a setting where the covariance structure may fail to be separable locally -- either due to noise contamination or due to the presence of a non-separable short-range dependent signal component. That is, the covariance is an additive perturbation of a separable component by a non-separable but banded component. We introduce non-parametric estimators hinging on shifted partial tracing -- a novel concept enjoying strong denoising properties. We illustrate the usefulness of the proposed methodology on a data set of mortality surfaces.In Chapter 3, we propose a distinctive decomposition of the covariance, which allows us to understand separability as an unconventional form of low-rankness. From this perspective, a separable covariance has rank one. Allowing for a higher rank suggests a structured class in which any covariance can be approximated up to an arbitrary precision. The key notion of the partial inner product allows us to generalize the power iteration method to general Hilbert spaces and estimate the aforementioned decomposition from data. Truncation and retention of the leading terms automatically induces a non-parametric estimator of the covariance, whose parsimony is dictated by the truncation level. Advantages of this approach, allowing for estimation beyond separability, are demonstrated on the task of classification of EEG signals.While Chapters 2 and 3 propose several generalizations of separability in the densely sampled regime, Chapter 4 deals with the sparse regime, where the latent surfaces are observed only at few irregular locations. Here, a separable covariance estimator based on local linear smoothers is proposed, which is the first non-parametric utilization of separability in the sparse regime. The assumption of separability reduces the intrinsically four-dimensional smoothing problem into several two-dimensional smoothers and allows the proposed estimator to retain the classical minimax-optimal convergence rate for two-dimensional smoothers. The proposed methodology is used for a qualitative analysis of implied volatility surfaces corresponding to call options, and for prediction of the latent surfaces based on information from the entire data set, allowing for uncertainty quantification. Our quantitative results show that the proposed methodology outperforms the common approach of pre-smoothing every implied volatility surface separately.Throughout the thesis, we put emphasis on computational aspects, since those are the main reason behind the immense popularity of separability. We show that the covariance structures of Chapters 2 and 3 come with no (asymptotic) computational overhead relative to assuming separability. In fact, the proposed covariance structures can be estimated and manipulated with the same asymptotic costs as the separable model. In particular, we develop numerical algorithms that can be used for efficient inversion, as required e.g.~for prediction. All the methods are implemented in R and available on~GitHub.

EPFL2022

Resistive random access memory based multiplexers and field programmable gate arrays

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Edouard Giacomin, Gain Kim, Xifan Tang

Resistive random access memory (RRAM) based multiplexers and field programmable gate arrays (FPGAs) are provided. The RRAM-based multiplexers and FPGAs include a 4T1R programming structure to program the RRAMs. The programming structure includes two programming transistors connected between the power supply and the top electrode of the RRAM and two programming transistors connected between the power supply and the bottom electrode of the RRAM. The programming transistors are used to set and rest the RRAMs. In the RRAM-based multiplexer programming transistors connected to the bottom electrodes are shared between a plurality of RRAMs. The shared programming transistors and an output inverter of the RRAM are provided in a deep N-well of the RRAM-based multiplexer. The programming transistors connected to the top electrodes of the RRAMs and a plurality of input inverters are provided in a regular well of the RRAM-based multiplexer.

2018

Covariance Estimation for Random Surfaces beyond Separability

Tomas Masák

EPFL2022