[hal-01108627] From complexity to algebra and back: digraph classes, collapsibility and the PGP

Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idempotent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idempotent polymorphisms whose associated clone algebra has: either the polynomially generated powers property (PGP); or the exponentially generated powers property (EGP). Similarly, we build on [DaMM ICALP'14] to prove that semicomplete digraphs have the same property. These gap theorems are further motivated by new evidence that PGP could be the algebraic explanation that a QCSP is in NP even for unbounded alternation. Along the way we also effect a study of a concrete form of PGP known as collapsibility, tying together the algebraic and structural threads from [Chen Sicomp'08], and show that collapsibility is equivalent to its Π2-restriction. We also give a decision procedure for k-collapsibility from a singleton source of a finite structure (a form of collapsibility which covers all known examples of PGP for finite structures). Finally, we present a new QCSP trichotomy result, for partially reflexive paths with constants. Without constants it is known these QCSPs are either in NL or Pspace-complete [Martin CP'11], but we prove that with constants they attain the three complexities NL, NP-complete and Pspace-complete. [Martin CP'11] Barnaby Martin: QCSP on Partially Reflexive Forests. CP 2011: 546-560 [DaMM ICALP'14] Petar Dapic, Petar Markovic, Barnaby Martin: QCSP on Semicomplete Digraphs. ICALP (1) 2014. [Chen Sicomp'08] Hubie Chen: The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case. SIAM J. Comput. 37(5): 1674-1701 (2008).

from HAL : Dernières publications http://ift.tt/1JrFVGG

[hal-01134194] Optimal Transport using Helmholtz-Hodge Decomposition and First-Order Primal-Dual Algorithms

This work deals with the resolution of the optimal transport problem between 2D images in the fluid mechanics framework of Benamou and Brenier formulation [1], which numerical resolution is still challenging even for medium-sized images. We develop a method using the Helmholtz-Hodge decomposition [2] in order to enforce the divergence-free constraint throughout the iterations. We then show how to use a first order primal-dual algorithm for convex problems of Chambolle and Pock [3] to solve the obtained problem, leading to a new algorithm easy to implement. Besides, numerical experiments demonstrate that this algorithm is faster than state of the art methods and efficient with real-sized images.

from HAL : Dernières publications http://ift.tt/1B7XFTz

[hal-01133948] Modélisations de textures par champ gaussien à orientation locale prescrite

Nous présentons dans ce papier deux nouveaux modèles de texture orientée, basés sur une nouvelle classe de champs gaussiens, appelés champs browniens fractionnaires localement anisotropes, à orientation locale prescrite en chaque point. Ces champs aléatoires sont une version locale d'une classe spécifique de champs anisotropes autosimilaires à incréments stationnaires. La simulation de telles textures s'appuie sur un nouvel algorithme couplant l'utilisation de la notion de champs tangents à la méthode de Cholesky ou plus récemment la méthode des bandes tournantes, cette dernière ayant prouvé son efficacité à générer des textures stationnaires anisotropes. Des applications numériques illustrent la faculté de la méthode à synthétiser des textures à orientation locale prescrite.

from HAL : Dernières publications http://ift.tt/1OJ2FIk

[hal-01170063] A Day-ahead Centralized Unit Commitment Algorithm for A Multi-agent Smart Grid

Renewable energy resources like wind and solar have become an effective factor in the energy production on the planet as they are inexhaustible renewable resources. However, they are very intermittent and their output cannot be predicted certainly. In this paper an algorithm of unit commitment within a power grid integrating wind and photovoltaic production units is proposed in a centralized approach that takes into account provisional data about the renewable energy production. Here the unit commitment problem is stated as a power demand coverage problem with some prespecified merit order list. A multi-agent architecture is proposed to facilitate the message exchange and easy addition and deletion of agents in the grid. This architecture is flexible and easy reconfigurable as it can provide solutions under assumptions of a decentralized approach. An implementation using JADE platform is presented in this work. The system is tested using real-data sets from an existent energy transport network in France (RTE). The results based on different operating conditions show the economic sense of the proposed strategy.

from HAL : Dernières publications http://ift.tt/1OJ4sNs

[hal-01202398] L’Internet des objets : un nouveau champ d’action pour la cybercriminalité

L’observation de la cybercriminalité et des différentes formes d’abus dans l’utilisation des technologies numériques a montré au cours des dix dernières années que les activités illégales ne se contentaient plus d’un rôle marginal dans l’univers numérique, mues par des mobiles touchant à l’appropriation financière ou à l’appropriation informationnelle. L’émergence d’un Internet des objets en tant que support des activités humaines doit évidemment nous amener à prendre en compte ce type de risque, d’autant plus que les conséquences en sont encore difficiles à évaluer, ne serait-ce que par l’ampleur d’une telle évolution (le nombre des objets, des réseaux qui interagissent, des nouveaux usages étant considérable). C’est donc une multitude d’axes de recherche en matière de sécurité qui doivent être ouverts ou soutenus, y compris ceux qui permettront de tirer profit de ces nouvelles technologies pour améliorer la sécurité.

from HAL : Dernières publications http://ift.tt/1NMrGDb

[hal-01185255] About Interface Conditions for Coupling Hydrostatic and Nonhydrostatic Navier-Stokes Flows

In this work we are interested in the search of interface conditions to couple hydrostatic and nonhydrostatic ocean models. To this aim, we consider simplified systems and use a time discretization to handle linear equations. We recall the links between the two models (with the particular role of the aspect ratio δ = H/L 1) and introduce an iterative method based on the Schwarz algorithm (widely used in domain decomposition methods). The convergence of this method depends strongly on the choice of interface conditions: this is why we look for exact absorbing conditions and their approximations in order to provide tractable and efficient coupling algorithms.

from HAL : Dernières publications http://ift.tt/1FVLIDn

[hal-00982087] Towards optimized Schwarz methods for the Navier-Stokes equations

This paper presents a study of optimized Schwarz domain decomposition methods for Navier-Stokes equations. Once discretized in time, optimal transparent boundary conditions are derived for the resulting Stokes equations, and a series of local approximations for these nonlocal conditions are proposed. Their convergence properties are studied, and numerical simulations are conducted on the test case of the driven cavity. It is shown that conditions involving one or two degrees of freedom can improve the convergence properties of the original algorithm.

from HAL : Dernières publications http://ift.tt/1C6K3uB

[hal-01200624] Colloquium: Mechanical formalisms for tissue dynamics

The understanding of morphogenesis in living organisms has been renewed by tremendous progress in experimental techniques that provide access to cell scale, quantitative information both on the shapes of cells within tissues and on the genes being expressed. This information suggests that our understanding of the respective contributions of gene expression and mechanics, and of their crucial entanglement, will soon leap forward. Biomechanics increasingly benefits from models, which assist the design and interpretation of experiments, point out the main ingredients and assumptions, and ultimately lead to predictions. The newly accessible local information thus calls for a reflection on how to select suitable classes of mechanical models. We review both mechanical ingredients suggested by the current knowledge of tissue behaviour, and modelling methods that can help generate a rheological diagram or a constitutive equation. We distinguish cell scale (“intra-cell”) and tissue scale (“inter-cell”) contributions. We recall the mathematical framework developed for continuum materials and explain how to transform a constitutive equation into a set of partial differential equations amenable to numerical resolution. We show that when plastic behaviour is relevant, the dissipation function formalism appears appropriate to generate constitutive equations; its variational nature facilitates numerical implementation, and we discuss adaptations needed in the case of large deformations. The present article gathers theoretical methods that can readily enhance the significance of the data to be extracted from recent or future high throughput biomechanical experiments.

from HAL : Dernières publications http://ift.tt/1QrBuQB

[hal-01122681] Embedded Real-Time Localization of UAV based on an Hybrid Device

This paper presents a method for localizing an Unmanned Aerial Vehicle (UAV) in indoor or outdoor environments. The approach has the ability to estimate the 3D pose of the on-board camera by using a Harris corner detector and the Levenberg-Marquardt (LM) with the Random Sample Consensus (RANSAC) algorithm to perform detection. The implementation of such computational intensive tasks in embedded system is necessary for the autonomy of UAV. Accelerators implemented on FPGA provide a solution to reach required performances. In addition to the algorithm development, we present the embedding of a real time camera pose estimation algorithm on a Xilinx System on Programmable Chip (SoPC) platform. Partition- ing of our embedded application into hardware and software parts on a Zynq Board has significantly reduced the execution time when compared with software implementation, while offering necessary reconfiguration capabilities.

from HAL : Dernières publications http://ift.tt/1GjBSPy

[hal-01023862] Stochastic Reliability Evaluation of Sea-of-Tiles Based on Double Gate Controllable-Polarity FETs

Promising devices like Double Gate Field Effect transistors [1] (DGFET) are proposed as basic elements to form tiles for a new kind of nanofabric [2]. For this fabric, regular arrays of tiles are expected in order to build a Sea-of-Tiles. DGGET transistors enable a concise expression of computational function. In order to facilitate this building, a specific logic synthesis methodology based on BBDD was proposed in [3]. We propose in this paper to evaluate the reliability of an application mapped onto this kind of fabric. Based on the BBDD representation of the application, we propose a more accurate stochastic method that takes care of the mapping of the application onto the regular fabric. Stochastic methods for reliability evaluation such as [4] [5] rely on bit streams or probabilistic transfer matrices. Unlike these methods, we propose to model the reliability problem of the nanofabric by means of Bayesian network. The usage of Bayesian methods is not completely new [6] [7] in the context of nanotechnology. Nevertheless, in this paper, we explore Bayesian methodologies for DGFET Sea-of-tiles nanofabric, by integrating them at the application level. This enables us to consider offline reliability strategies as well as online ones based on diagnosis capabilities of Bayesian networks, showing a real new opportunity for EDA tools

from HAL : Dernières publications http://ift.tt/1V4y797

[hal-01146318] FPGA Implementation of Bayesian Network Inference for an Embedded Diagnosis

[...]

from HAL : Dernières publications http://ift.tt/1V4y50U

[hal-01146309] Bayesian Network-Based Framework for the Design of Reconfigurable Health Management Monitors

[...]

from HAL : Dernières publications http://ift.tt/1V4y50O

[hal-01147706] Étude de l'activité d'un stagiaire d'EPS au travail et en vidéo-formation : Une « traçabilité » de l'évolution de l'intervention professionnelle

Cet article présente une étude de cas constitutive d'une recherche en ergonomie cognitive visant à décrire et interpréter l'activité déployée par des enseignants novices, alternativement au travail et en vidéo-formation autonome. L'analyse porte ici sur les significations produites pendant les navigations d'un enseignant sur une plateforme de vidéo-formation, ainsi que sur les effets géné-rés sur son activité de travail, lors de son entrée dans le métier. Les résultats montrent que ses connaissances professionnelles se créent et se transforment en réponse aux insatisfactions qui émergent pour lui envers son activité de travail, que ce soit au travail ou en en vidéo-formation, et se stabilisent si elles s'accordent à l'épreuve de cette même activité avec ses normes de viabilité per-sonnelles. Mots-clés: enseignants débutants, vidéo-formation, développement profession-nel, situations typiques d'enseignement, conception de formation. Abstract: This article presents a case study that is part of a larger research in a cognitive ergonomics approach, aiming at describing and interpreting the activity deployed by novice teachers alternatively while working and while video-training autonomously. The analysis deals here with the significations produced for a teacher while surfing on a video-training platform, and also with the effects generated on his work activity, during his entry into the profession. The findings show that his professional knowledge is created and transformed in response to dissatisfactions emerging for him toward his work activity, at work or during video-training sessions, and is stabilized if it accords, proof against this activity, with his personal norms of viability. Des outils numériques pour former les enseignants Durant ces vingt dernières années, la conception d'environnements numériques de formation a connu un développement conséquent. Elle s'accompagne d'un développement des pratiques et dispositifs d'e-learning et de formation hybride, en particulier pour les étudiants et professionnels novices, qui constitue un phénomène plus Recherches & Educations 2 récent mais grandissant (Albero, 2004). Le cas de la formation des futurs enseignants et des enseignants novices (EN par la suite) en est un bon exemple. Sa dimension professionnelle, voire professionnalisante, est fortement portée par l'institution qui mise objectivement sur ces nou-veaux espaces (Escalié & Chaliès, 2011). Selon Albero, bien que la re-cherche se soit largement emparée du champ des environnements numériques de formation, ses résultats ne se départissent pas pour autant d'un caractère émietté et non cumulatif ; ce constat est particulièrement vrai pour le cas des dispositifs de vidéo-formation des enseignants dont relève notre étude (Gaudin & Chaliès, 2012). En effet, bien que la formation des enseignants ait une longue tradition d'usage de la vidéo (Brouwer, 2007 ; Flandin, sous presse ; Leblanc & Veyrunes, 2012), la recherche peine à produire les études systématiques nécessaires à une véritable capitalisation des résultats. Dans ces conditions , étayer scientifiquement la conception de situations de formation reste difficile (Sherin, 2003). De plus, la plupart des études menées ne s'intéressent pas à l'impact des situations de vidéo-formation sur l'évolution réelle de l'activité professionnelle des enseignants, mais uni-quement à ce que ces derniers en disent (e.g. Moreno, Abercrombie & Hushman, 2009) ou à leurs intentions de changement (e.g. Meyer, David & Aubé, 2012). Elles présentent donc très peu souvent les données empi-riques nécessaires à cet objectif (Gaudin & Chaliès, 2012). Enfin, rares sont celles qui prennent en compte les significations que les enseignants attribuent à leur activité en formation ou au travail, et la singularité des situations analysées qui peut pourtant conditionner largement les effets produits par un même dispositif (Flandin & Ria, 2012b). C'est pourquoi notre recherche s'attache à composer avec ces différentes dimensions pour décrire la trajectoire de formation d'un EN et déterminer le rôle que peut y jouer l'utilisation d'un dispositif basé sur la vidéo.

from HAL : Dernières publications http://ift.tt/1FVwrCx

[hal-01202379] Sécurité informatique, cours et exercices corrigés

[...]

from HAL : Dernières publications http://ift.tt/1iGSUyu

[hal-01202378] Analysis of Rainbow Tables with Fingerprints

[...]

from HAL : Dernières publications http://ift.tt/1V3gcdB

[hal-01202377] Comparing distance bounding protocols: A critical mission supported by decision theory

[...]

from HAL : Dernières publications http://ift.tt/1V4y4Ke

[hal-01202376] Distance Geometry and Applications

[...]

from HAL : Dernières publications http://ift.tt/1V4y4tS

[hal-01196694] Ant Colony Optimization with Environment Changes: an Application to GPS Surveying

We propose a variant on the well-known Ant Colony Optimization (ACO) general framework where we introduce the environment to play an important role during the optimization process. Together with diversification and intensification, the environment is introduced with the aim of avoiding the search to get stuck at local optima. In this work, the environment is simulated by means of the Logistic map, that is used in ACO for perturbing the update of the pheromone trails. Our preliminary experiments show that our environmental ACO (eACO), with variable environment, outperforms the standard ACO on a set of instances of the GPS Surveying Problem (GSP).

from HAL : Dernières publications http://ift.tt/1JiNuyD

[hal-01083405] Digital Trees and Memoryless Sources: from Arithmetics to Analysis

Digital trees, also known as "tries", are fundamental to a number of algorithmic schemes, including radix-based searching and sorting, lossless text compression, dynamic hashing algorithms, communication protocols of the tree or stack type, distributed leader election, and so on. This extended abstract develops the asymptotic form of expectations of the main parameters of interest, such as tree size and path length. The analysis is conducted under the simplest of all probabilistic models; namely, the memoryless source, under which letters that data items are comprised of are drawn independently from a fixed (finite) probability distribution. The precise asymptotic structure of the parameters' expectations is shown to depend on fine singular properties in the complex plane of a ubiquitous Dirichlet series. Consequences include the characterization of a broad range of asymptotic regimes for error terms associated with trie parameters, as well as a classification that depends on specific arithmetic properties, especially irrationality measures, of the sources under consideration.

from HAL : Dernières publications http://ift.tt/1FnxVue

[hal-01083405] Digital Trees and Memoryless Sources: from Arithmetics to Analysis

Digital trees, also known as \emph``tries'', are fundamental to a number of algorithmic schemes, including radix-based searching and sorting, lossless text compression, dynamic hashing algorithms, communication protocols of the tree or stack type, distributed leader election, and so on. This extended abstract develops the asymptotic form of expectations of the main parameters of interest, such as tree size and path length. The analysis is conducted under the simplest of all probabilistic models; namely, the \emphmemoryless source, under which letters that data items are comprised of are drawn independently from a fixed (finite) probability distribution. The precise asymptotic structure of the parameters' expectations is shown to depend on fine singular properties in the complex plane of a ubiquitous \emphDirichlet series. Consequences include the characterization of a broad range of asymptotic regimes for error terms associated with trie parameters, as well as a classification that depends on specific \empharithmetic properties, especially irrationality measures, of the sources under consideration.

from HAL : Dernières publications http://ift.tt/1JiNsGX