Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Sparsest Cut: Théorie de l'ARV

Dans cours

CS-455: Topics in theoretical computer science

The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of fundamental questions that underlie some of the key probl ...

Description

Cette séance de cours couvre la preuve du théorème ARV de Bourgain (Arora - Rao - Vazirani), en se concentrant sur l'ensemble fini des points dans un espace semi-métrique. L'instructeur démontre l'échantillonnage uniforme et les concepts clés derrière le théorème, tels que la distance entre les points et le concept de type négatif. La séance de cours se termine par l'application de l'algorithme ARV pour trouver la coupe la plus clairsemée dans un graphique. Divers Lemmas sont introduits pour soutenir le théorème principal, soulignant l'importance des propriétés métriques et l'existence d'ensembles spécifiques dans le contexte du théorème.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Logique

Logique classique: Calcul des prédicats

Concepts associés (32)

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. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.

Graphe (mathématiques discrètes)

Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.

Théorie spectrale des graphes

En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées .

Lexique de la théorie des graphes

NOTOC 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 -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Démonstration (logique et mathématiques)

vignette| : un des plus vieux fragments des Éléments d'Euclide qui montre une démonstration mathématique. En mathématiques et en logique, une démonstration est un ensemble structuré d'étapes correctes de raisonnement. Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l'application d'une règle qui permet d'affirmer qu'une proposition, la conclusion, est une conséquence logique d'une ou plusieurs autres propositions, les prémisses de la règle.

Afficher plus

Séances de cours associées (59)

Modèles graphiques : Représentation des distributions probabilistes

Couvre les modèles graphiques pour les distributions probabilistes à l'aide de graphiques, de nœuds et de bords.

Théorie des graphes spectraux : introduction

Introduit la théorie des graphes spectraux, explorant les valeurs propres et le rôle des vecteurs propres dans les propriétés des graphes.

Fonctions de cartographie et surjections

Explore les fonctions cartographiques, les surjections, les fonctions injectives et surjectives et les fonctions bijectives.

Produit cartésien et induction

Présente le produit cartésien et l'induction pour les épreuves utilisant des entiers et des ensembles.

Test d'identité polynomiale

Couvre les tests d'identité polynomiale à l'aide d'oracles et d'évaluations ponctuelles aléatoires, avec des applications dans la théorie des graphes et les aspects algorithmiques.

Afficher plus

Concepts associés (32)

Théorie des graphes

Graphe (mathématiques discrètes)

Théorie spectrale des graphes

Lexique de la théorie des graphes

Démonstration (logique et mathématiques)

Afficher plus