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

Algèbre linéaire en 2D : applications de réduction

Description

Cette séance de cours couvre l'application de réductions dans R2, se concentrant sur le calcul de f composé n fois avec lui-même pour une fonction linéaire f: R2 → R2. Le processus consiste à écrire Aƒ = PRƒP−1, où Rƒ est la forme réduite de Aƒ. La séance de cours explore différents scénarios basés sur les caractéristiques de la matrice Aƒ, fournissant des exemples et des preuves pour divers cas.

Source officielle

Proximité ontologique

Mathématiques

Algèbre: Algèbre linéaire

Concepts associés (32)

Réduction en espace logarithmique

En théorie de la complexité, une réduction en espace logarithmique est une réduction calculable par une machine de Turing disposant d'un espace de travail logarithmique. La machine de Turing utilisée pour une réduction en espace logarithmique est constituée de trois rubans au lieu d'un : un ruban d'entrée (en lecture seule), un ruban de travail (de taille logarithmique en la taille du ruban d'entrée), et un ruban de sortie (en écriture seule et tel que la tête d'écriture ne peut écrire deux fois sur une même case).

Réduction (complexité)

En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème. S'il existe une telle réduction d'un problème A à un problème B, on dit que le problème A se réduit au problème B. Dans ce cas, le problème B est plus difficile que le problème A, puisque l'on peut résoudre le problème A en appliquant la réduction puis un algorithme pour le problème B. On écrit alors A ≤ B.

Many-one reduction

In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem (whether an instance is in ) to another decision problem (whether an instance is in ) using an effective function. The reduced instance is in the language if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving .

Turing reduction

In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine which decides problem given an oracle for (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems. If a Turing reduction from to exists, then every algorithm for can be used to produce an algorithm for , by inserting the algorithm for at each place where the oracle machine computing queries the oracle for .

Réduction polynomiale

Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP. Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage est réductible en temps polynomial à un langage (noté ) s'il existe une fonction calculable en temps polynomial telle que pour tout , si et seulement si .

Afficher plus

Séances de cours associées (40)

Algèbre linéaire: opérations matricielles et bases

Explore les opérations matricielles, la détermination des rangs, les dimensions du noyau et les concepts de base en algèbre linéaire.

Représentations matricielles: Cartes linéaires

Explore les représentations matricielles des cartes linéaires et leur invariance, en utilisant des exemples et des cas particuliers.

Algèbre linéaire: matrices et applications linéaires

Couvre les matrices, les applications linéaires, les espaces vectoriels et les fonctions bijectives.

Algèbre linéaire: réduction de l'application linéaire

Couvre la réduction d'une application linéaire et la recherche de formes et de bases réduites correspondantes.

Projections et applications

Explore les projections dans R3, les propriétés matricielles, et trace les concepts avec des exemples pratiques.

Afficher plus

Concepts associés (32)

Réduction en espace logarithmique

Réduction (complexité)

Many-one reduction

Turing reduction

Réduction polynomiale

Afficher plus