Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Concept

Diagramme de décision binaire

En informatique, un graphe de décision binaire ou diagramme de décision binaire (ou BDD pour Binary Decision Diagram en anglais) est une structure de données utilisée pour représenter des fonctions booléennes, ou des questionnaires binaires. On utilise les BDD pour représenter des ensembles ou des relations de manière compacte / compressée. Les diagrammes de décision binaires sont utilisés par les programmes de conception assistée par ordinateur (CAO / CAD) pour générer des circuits (synthèse logique), et dans la vérification formelle. C'est une structure de donnée considérée comme compacte, en comparaison par exemple aux arbres de décision. Les diagrammes de décision binaire sont utilisés dans le model checking symbolique de CTL. Définition thumb|Exemple de diagramme de décision binaire. Un diagramme de décision binaire (BDD) est un graphe acyclique, comme montré dans la figure ci-contre. Il est composé de nœuds non terminaux porteurs de questions, aus

À 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 (17)

Chargement

Afficher plus

Publications associées

Chargement

Personnes associées (3)

, ,

Personnes associées

Chargement

Unités associées (3)

Unités associées

Chargement

Concepts associés (12)

Concepts associés

Chargement

Cours associés (6)

Cours associés

Chargement

Séances de cours associées (7)

Afficher plus

Séances de cours associées

Chargement

Fonction booléenne

vignette|Arbre de décision binaire Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit. Les fonctions booléennes sont très utilisées en inf

Problème SAT

vignette|Une instance du Sudoku peut être transformée en une formule de logique propositionnelle à satisfaire. Une assignation des variables propositionnelles donne une grille complétée. En informatiq

Logic optimization

Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in d

Efficient Data Structures For Decision Diagrams

Stéphane Rabie

Dynamic Programming Optimization (DPOP) is an algorithm proposed to solve distributed constraint optimization problems. In order to represent the multi-values functions manipulated in this algorithm, a data structure called Hypercube was implemented. A more efficient data structure, the Utility Diagram, was then proposed as an alternative to the Hypercube. DPOP also required the implementation of several operations (such as join, project, slice, split and reorder) on these two data structures. This project is a follow-up of Nacereddine Ouaret’s master thesis, which consisted in implementing all of these data structures and theirs associated operations. As DPOP may have to work on very large decision diagrams, and perform a lot of successive operations on them, having implementations which are efficient in term of speed and memory is critical. The aim of this project was therefore to seek for new ways to improve the already implemented functions for hypercubes and utility diagrams, both in term of execution time and memory consumption. This report will thus first present a quick overview of hypercubes, utility diagrams, and their associated operations (a more complete description of these objects, as well as the details about their original implementation, can be found in Nacereddine Ouaret’s report on Efficient Data Structures for Decision Diagrams). The second part will then cover various improvements made to their implementation during the course of this project. Finally, a variant for the methods used by hypercube, more economical in term of memory as it reuses existing hypercubes rather than creating new ones, will be presented.

2009

Chargement

Efficient Data Structures for Decision Diagrams

Nacereddine Ouaret

Dynamic Programming OPtimization (DPOP) is an algorithm proposed for solving distributed constraint optimization problems. In this algorithm, Hypercubes are used as the format of the messages exchanged between the agents. Then, Hybrid-DPOP (H-DPOP), a hybrid algorithm based on DPOP was proposed as an improved solution. Its main advantage over DPOP lies under the use of Multi-valued Decision Diagrams (MDDs) instead of Hypercubes. Furthermore, MDDs give a more compact representation of the messages. The MDDs were implemented and presented in by Kumar even though it was presented as Constrained Decision Diagrams (CDD) which is a generalization of MDDs. The first part of this project aims at implementing Hypercubes. An Implementation already exists. Therefore, the goal is to propose an implementation which is more efficient in term of speed and memory usage for the already implemented functions (join, project and slice). The solution implemented during this project should also provide new functions (split and re-order) and the possibility of saving Hypercubes in the XML format. The second part of the project consists in proposing and implementing a data structure that is more efficient than the MDDs implemented in H-DPOP. This data structure should also provide more functions, and also provide the possibility of saving data in the XML format.

2008

Chargement

Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

Aditya Vardhan Varre

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2018). We consider three different variants of graph homomorphisms, namely injective homomorphisms, directed homomorphisms, and injective directed homomorphisms, and obtain polynomial families complete for VF, VBP, VP, and VNP under each one of these. The polynomial families have the following properties: The polynomial families complete for VF, VBP, and VP are model independent, i.e., they do not use a particular instance of a formula, algebraic branching programs, or circuit for characterising VF, VBP, or VP, respectively. All the polynomial families are hard under p-projections.

ASSOC COMPUTING MACHINERY2021

Chargement

Afficher plus

EE-110: Logic systems (for MT)

Ce cours couvre les fondements des systèmes numériques. Sur la base d'algèbre Booléenne et de circuitscombinatoires et séquentiels incluant les machines d'états finis, les methodes d'analyse et de synthèse de systèmelogiques sont étudiées et appliquée

CS-472: Design technologies for integrated systems

Hardware compilation is the process of transforming specialized hardware description languages into circuit descriptions, which are iteratively refined, detailed and optimized. The course presents algorithms, tools and methods for hardware compilation and logic synthesis.

CS-550: Formal verification

We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to use formal verification tools and explain the theory and the practice behind them.