Séance de cours

Multiplication de la chaîne matricielle

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

CS-250: Algorithms I

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, s ...

Description

Cette séance de cours couvre l'algorithme de programmation dynamique pour la multiplication de la chaîne matricielle, expliquant l'approche ascendante pour trouver la solution optimale. Il traite de l'algorithme de récupération d'une solution optimale et fournit des exemples de dimensions et d'instances matricielles. L'instructeur explique également le choix de l'endroit où faire la parenthèse extérieure et les sous-problèmes qui se chevauchent. En outre, la séance de cours introduit le concept de la sous-séquence commune la plus longue, la définissant comme une sous-séquence non consécutive commune à deux séquences.

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

Enseignant·e·s (3)

Mikhail Kapralov

Enseignement et PhD Doctorant·es actuel·les Weronika Wrzos-Kaminska, Guy Weissenberg, Davide Mazzali, Ekaterina Kochetkova, Kshiteej Jitesh Sheth A dirigé les thèses EPFL de Amir Zandieh, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos, Grzegorz Adam Gluch, Makarov Mikhail A co-dirigé les thèses EPFL de Paritosh Garg Cours Algorithms II CS-450 Un premier cours de 2eme cycle sur les algorithmes, ce cours a peu de prerequis, mais va vite. Il couvre les techniques principales d'analyse et de

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Source officielle

Proximité ontologique

Mathématiques

Algèbre: Algèbre linéaire

Concepts associés (32)

Matrice (mathématiques)

thumb|upright=1.5 En mathématiques, les matrices sont des tableaux d'éléments (nombres, caractères) qui servent à interpréter en termes calculatoires, et donc opérationnels, les résultats théoriques de l'algèbre linéaire et même de l'algèbre bilinéaire. Toutes les disciplines étudiant des phénomènes linéaires utilisent les matrices. Quant aux phénomènes non linéaires, on en donne souvent des approximations linéaires, comme en optique géométrique avec les approximations de Gauss.

Matrix multiplication algorithm

Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).

Addition matricielle

vignette|Illustration d'une addition matricielle L'addition matricielle est une opération mathématique qui consiste à produire une matrice qui est le résultat de l'addition de deux matrices de même type. L'addition des matrices est définie pour deux matrices de même type. La somme de deux matrices de type (m, n), et , notée A + B, est à nouveau une matrice de type (m, n) obtenue en additionnant les éléments correspondants, i.e., pour tous i, j, Par exemple: L'ensemble des matrices de type (m, n) avec la loi d'addition forment un groupe abélien.

Matrice de rotation

En mathématiques, et plus précisément en algèbre linéaire, une matrice de rotation Q est une matrice orthogonale de déterminant 1, ce qui peut s'exprimer par les équations suivantes : QtQ = I = QQt et det Q = 1, où Qt est la matrice transposée de Q, et I est la matrice identité. Ces matrices sont exactement celles qui, dans un espace euclidien, représentent les isométries (vectorielles) directes.

Complexité de la multiplication de matrices

En informatique théorique, la complexité de la multiplication de matrices est le nombre d'opérations requises pour l'opération de produit matriciel. Les algorithmes de multiplication de matrices constituent un sujet central dans les algorithmes théoriques et numériques en algèbre linéaire numérique et en optimisation, donc déterminer la complexité en temps du produit est d'une importance pratique. L'application directe de la définition mathématique de la multiplication de matrices donne un algorithme qui nécessite opérations sur le corps de base pour multiplier deux matrices d'ordre .

Afficher plus

Séances de cours associées (32)

Algèbre linéaire : matrices et opérations

Introduit des concepts clés en algèbre linéaire, y compris les matrices, les opérations et les invariants numériques.

Décomposition de la valeur singulière : applications et interprétation

Explique la construction de U, la vérification des résultats et l'interprétation de SVD dans la décomposition matricielle.

Opérations de la matrice : Définitions et propriétés

Couvre les définitions et les propriétés des matrices, y compris les opérations matricielles et les déterminants.

Calcul de la matrice

Couvre la définition et les opérations de base des matrices, y compris l'addition, la multiplication scalaire et la multiplication matricielle.

Polynômes caractéristiques et matrices similaires

Explore les polynômes caractéristiques, la similarité des matrices et les valeurs propres dans les transformations linéaires.

Afficher plus

Concepts associés (32)

Matrice (mathématiques)

Matrix multiplication algorithm

Addition matricielle

Matrice de rotation

Complexité de la multiplication de matrices

Afficher plus