Séance de cours

Problème de vecteur le plus proche: cellules de Voronoi

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

Cette séance de cours couvre le problème de vecteur le plus proche dans les réseaux, en se concentrant sur la recherche du vecteur de réseau le plus proche d'une cible donnée. L'instructeur explique le concept de cellules Voronoi, qui partitionnent l'espace et aident à déterminer le vecteur le plus proche. En définissant les cellules de Voronoï comme un polytope et en explorant l’ensemble minimal d’inégalités nécessaires pour les décrire, la séance de cours explore les aspects géométriques et linéaires du problème. La discussion comprend des idées sur les inégalités définissant les facettes, l'unicité des ensembles d'inégalités minimales et le nombre fini de vecteurs pertinents dans les cellules de Voronoi.

Source officielle

Concepts associés (15)

Polytope

Un polytope est un objet mathématique géométrique. Le terme de polytope a été inventé par Alicia Boole Stott, la fille du logicien George Boole. Le terme polytope admet plusieurs définitions au sein des mathématiques. Principalement car les usages diffèrent en quelques points selon les pays, mais l'usage américain ayant tendance à s'imposer, on se retrouve confronté avec des usages contradictoires au sein d'un même pays.

Polytope abstrait

En mathématiques, et plus particulièrement en géométrie discrète, un polytope abstrait est un ensemble partiellement ordonné dont l'ordre reflète les propriétés combinatoires d'un polytope (au sens traditionnel, généralisant les polygones et les polyèdres à un nombre de dimensions quelconque), mais pas les aspects géométriques usuels, tels que les angles ou les distances. On dit qu'un polytope (géométrique) est une réalisation dans un espace à n dimensions (le plus souvent euclidien) du polytope abstrait correspondant.

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.

6-polytope

In six-dimensional geometry, a six-dimensional polytope or 6-polytope is a polytope, bounded by 5-polytope facets. A 6-polytope is a closed six-dimensional figure with vertices, edges, faces, cells (3-faces), 4-faces, and 5-faces. A vertex is a point where six or more edges meet. An edge is a line segment where four or more faces meet, and a face is a polygon where three or more cells meet. A cell is a polyhedron. A 4-face is a polychoron, and a 5-face is a 5-polytope.

Polytope régulier

droite|vignette|Le dodécaèdre régulier, un des cinq solides platoniciens. En mathématiques, plus précisément en géométrie ou encore en géométrie euclidienne, un polytope régulier est une figure de géométrie présentant un grand nombre de symétries. En dimension deux, on trouve par exemple le triangle équilatéral, le carré, les pentagone et hexagone réguliers, etc. En dimension trois se rangent parmi les polytopes réguliers le cube, le dodécaèdre régulier (ci-contre), tous les solides platoniciens.

Afficher plus

Séances de cours associées (60)

Problème de vecteur le plus proche: cellules de Voronoi

Explore le problème vectoriel le plus proche et les cellules Voronoi dans les algorithmes de réduction de réseau.

Inégalités linéaires et équivalent LP

Couvre les inégalités linéaires, les contraintes actives et les programmes linéaires équivalents.

Convex Polyhedra et programmes linéaires

Explore polyèdre convexe, programmes linéaires, et leur importance d'optimisation.

Géométrie du Lasso

Explore l'explication géométrique des raisons pour lesquelles les solutions Lasso sont rares et comment les coefficients changent avec le paramètre de régularisation.

Dynamique hamiltonienne sur les polytopes convexes

Explore la dynamique hamiltonienne sur les polytopes convexes, couvrant les capacités symlectiques, la capacité EHZ et les maximisateurs de ratio systolique.

Afficher plus

Concepts associés (15)

Polytope

Polytope abstrait

Optimisation linéaire

6-polytope

Polytope régulier

Afficher plus