Algorithme de parcours en profondeur

L'algorithme de parcours en profondeur (ou parcours en profondeur, ou DFS, pour Depth-First Search) est un algorithme de parcours d'arbre, et plus généralement de parcours de graphe. Il se décrit naturellement de manière récursive. Son application la plus simple consiste à déterminer s'il existe un chemin d'un sommet à un autre. Histoire Pour les graphes non orientés, le parcours en profondeur correspond à la méthode intuitive qu'on utilise pour trouver la sortie d'un labyrinthe sans tourner en rond. Des algorithmes de parcours en profondeur sont formulés dès le . Édouard Lucas (1891) dans ses Récréations mathématiques en propose une solution rigoureuse dont il attribue l'idée à Charles Pierre Trémaux. Gaston Tarry en donne une autre solution. Principe vignette|Exploration d'un labyrinthe à la manière du parcours en profondeur. L'exploration d'un parcours en profondeur depuis un sommet S fonctionne comme suit. Il poursuit alors un chemin dans le graphe jusqu'à

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

Publications associées

Chargement

Personnes associées (3)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (24)

Concepts associés

Chargement

Cours associés (6)

Cours associés

Chargement

Séances de cours associées (7)

Séances de cours associées

Chargement

Horizontal side-channel full key recovery on ephemeral SIKE

Aymeric Genet, Novak Kaluderovic, Natacha Yolande Emmanuel Marie Linard de Guertechin

This paper describes the first practical single-trace side-channel power analysis of SIKE. The attack exploits the nature of elliptic curve point addition formulas which require the same function to be executed multiple times. We target the three point ladder which involves a loop of a double-and-add procedure, of which each iteration depends on a single bit of the private key. We show how a single trace of a loop iteration can be segmented into different power traces on which several 32-bit words can be hypothesised based on the current value of the private key bit. This segmentation enables a classical correlation power analysis in an extend-and-prune approach. Further error-correction techniques based on depth-search are suggested. The attack was experimentally verified on an STM32F3 featuring a Cortex-M4 microcontroller which runs the SIKEp434 implementation adapted to 32-bit ARM. We obtained a resounding 100% success rate recovering the full private key in each experiment. Finally, we provide a simple countermeasure with a negligible overhead which mitigates our attack successfully.

2021

Chargement

Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

Shaul Nadav Hallak

This paper introduces a method for computing points satisfying the second-order necessary optimality conditions for nonconvex minimization problems subject to a closed and convex constraint set. The method comprises two independent steps corresponding to the first- and second-order conditions. The first-order step is a generic closed map algorithm, which can be chosen from a variety of first-order algorithms, making it adjustable to the given problem. The second-order step can be viewed as a second-order feasible direction step for nonconvex minimization subject to a convex set. We prove that any limit point of the resulting scheme satisfies the second-order necessary optimality condition, and establish the scheme's convergence rate and complexity, under standard and mild assumptions. Numerical tests illustrate the proposed scheme.

SPRINGER/PLENUM PUBLISHERS2020

Chargement

LF-Net: Learning Local Features from Images

Pascal Fua, Yuki Ono, Eduard Trulls Fortuny, Kwang Moo Yi

We present a novel deep architecture and a training strategy to learn a local feature pipeline from scratch, using collections of images without the need for human supervision. To do so we exploit depth and relative camera pose cues to create a virtual target that the network should achieve on one image, provided the outputs of the network for the other image. While this process is inherently non-differentiable, we show that we can optimize the network in a two-branch setup by confining it to one branch, while preserving differentiability in the other. We train our method on both indoor and outdoor datasets, with depth data from 3D sensors for the former, and depth estimates from an off-the-shelf Structure-from-Motion solution for the latter. Our models outperform the state of the art on sparse feature matching on both datasets, while running at 60+ fps for QVGA images.

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)

Chargement

Lexique de la théorie des graphes

NOTOC A ; Acyclique : graphe ne contenant pas de cycle. ; Adjacence : une liste d'adjacence est une structure de données constituée d'un tableau dont le i-ème élément co

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets

Arbre enraciné

En théorie des graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent. En informat

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

CS-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

COM-308: Internet analytics

Internet analytics is the collection, modeling, and analysis of user data in large-scale online services, such as social networking, e-commerce, search, and advertisement. This class explores a number of the key functions of such online services that have become ubiquitous over the past decade.