Programmation dynamique : sous-séquence commune la plus longue

Cette séance de cours couvre le concept de programmation dynamique, en se concentrant sur le problème de la sous-séquence commune la plus longue. Il explique comment identifier les choix et la sous-structure optimale, utiliser efficacement les approches descendantes ou ascendantes, et fournit une explication détaillée de l'algorithme de programmation dynamique. La séance de cours explore également la multiplication en chaîne matricielle et les formulations récursives pour trouver la sous-séquence commune la plus longue. Il se termine par une discussion sur l'approche ascendante pour résoudre le problème de sous-séquence commune la plus longue et enregistrer la solution optimale à l'aide de tableaux supplémentaires.

À 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.

Séances de cours associées (11)

Concepts associés (44)

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, ma

Produit matriciel

Le produit matriciel désigne la multiplication de matrices, initialement appelé la « composition des tableaux ». Il s'agit de la façon la plus fréquente de multiplier des matrices entre elles. En algèbre linéaire, une matrice A de dimensions m lignes et n colonnes (matrice m×n) représente une application linéaire ƒ d'un espace de dimension n vers un espace de dimension m. Une matrice colonne V de n lignes est une matrice n×1, et représente un vecteur v d'un espace vectoriel de dimension n. Le produit A×V représente ƒ(v).

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).

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 .

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.

Generalized eigenvector

In linear algebra, a generalized eigenvector of an matrix is a vector which satisfies certain criteria which are more relaxed than those for an (ordinary) eigenvector. Let be an -dimensional vector space and let be the matrix representation of a linear map from to with respect to some ordered basis. There may not always exist a full set of linearly independent eigenvectors of that form a complete basis for . That is, the matrix may not be diagonalizable.

Multiplication de la chaîne matricielle CS-250: Algorithms I

Se plonge dans la programmation dynamique en mettant l'accent sur la multiplication de chaînes matricielles et le plus long problème de sous-séquence commune.

Programmation dynamique : multiplication de chaînes matricielles CS-250: Algorithms I

Explore la programmation dynamique en mettant l'accent sur la multiplication matricielle et l'importance d'une sous-structure optimale.

Programmation dynamique : multiplication de chaînes matricielles CS-250: Algorithms I

Explore la programmation dynamique en mettant l'accent sur l'optimisation de la multiplication de chaînes matricielles.

Principes du parallélisme CS-214: Software construction

Couvre les bases du parallélisme, y compris des exemples physiques, le contexte historique, l'ère multicore, et des collections parallèles dans Scala.

Composite d'applications MATH-113: Algebraic structures

Couvre le concept de composite d'applications et l'importance de certaines hypothèses dans la multiplication matricielle.