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

Pseudorandomité : théorie et applications

Dans cours

MATH-467: Probabilistic methods in combinatorics

The 'probabilistic method' is a fundamental tool in combinatorics. The basic idea is as follows: to prove that an object (for example, graph) with certain properties exists, it suffices to prove that if the object is chosen at random, then it has the desir ...

Description

Cette séance de cours couvre le concept de pseudo-aléatoire, en se concentrant sur la théorie et les applications. Il discute de l’importance de la pseudoaléatoire dans l’IA, des défis de tester des propriétés avec des probabilités exponentiellement petites et de l’idée de graphiques pseudo-aléatoires. La séance de cours se penche également sur la théorie des systèmes dynamiques, en regardant des variétés et des promenades aléatoires sur les surfaces. Il explore la matrice de transition dans des marches aléatoires, des matrices laplaciennes et les propriétés des matrices d'adjacence. En outre, il explique la relation entre les valeurs propres et les vecteurs propres dans les matrices d'adjacence et de Laplacien, en soulignant l'importance de la pseudoaléatoire dans diverses applications.

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

Algèbre: Algèbre linéaire

Concepts associés (32)

Matrice laplacienne

En théorie des graphes, une matrice laplacienne, ou matrice de Laplace, est une matrice représentant un graphe. La matrice laplacienne d'un graphe G non orienté et non réflexif est définie par : où est la matrice des degrés de G et la matrice d'adjacence de G. Formellement : A la différence de la matrice d'adjacence d'un graphe, la matrice laplacienne a une interprétation algébrique ce qui rend son analyse spectrale fructueuse. Plus précisément la matrice correspond à l'opérateur de diffusion sur le graphe.

Line graph

En théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.

Graphe planaire

Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.

List of graphs

This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.

Couleur

vignette|Peinture de Claude Monet. La couleur est la perception visuelle de l'aspect d'une surface ou d'une lumière, basée, sans lui être rigoureusement liée, sur la répartition spectrale de la lumière, qui stimule des cellules nerveuses spécialisées situées sur la rétine nommées cônes. Le système nerveux transmet et traite l'influx jusqu'au cortex visuel.

Afficher plus

Séances de cours associées (46)

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.

Graphiques : Propriétés et représentations

Couvre les propriétés du graphique, les représentations et les algorithmes de traversée à l'aide de BFS et de DFS.

Groupes d'automorphisme : Arbres et graphiques III

Explore des groupes d'arbres et de graphiques d'automorphisme, y compris des actions sur les arbres et des homomorphismes de groupe.

Algèbre linéaire : Diagonalisation

Explore la diagonalisation des matrices et les conditions de diagonalisation exacte, avec des exemples démontrant le processus.

Graphiques et matrices

Explore les graphiques et les matrices, y compris les matrices d'adjacence, de degré et de Laplace, le théorème des arbres matriciels et les arbres qui s'étendent.

Afficher plus

Concepts associés (32)