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

Complexité computationnelle: Théorie et applications

Description

Cette séance de cours s'inscrit dans les subtilités de la complexité computationnelle, explorant des sujets tels que l'exhaustivité du NP, les réductions polynômes et la forme normale conjuguée. L'instructeur explique la signification de ces concepts dans le contexte de l'informatique théorique.

Source officielle

Proximité ontologique

Informatique théorique

Theory of computation: Théorie de la complexité (informatique théorique)

Concepts associés (31)

Problème NP-complet

En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l

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 .

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

NP-difficile

vignette|300px|Mise en évidence d'un problème NP-difficile si Problème P ≟ NP. Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP. Ainsi, un problème H est NP-difficile, si tout problème L de la classe NP peut être réduit en temps polynomial à H. Si un problème NP-difficile est dans NP, alors c'est un problème NP-complet.

Afficher plus

Séances de cours associées (54)

Complexité computationnelle

Couvre les bases de la complexité computationnelle, y compris les grandes classes de notation O et de complexité.

Systèmes complexes : phénomènes critiques

Explore les phénomènes critiques dans les systèmes complexes, y compris les objets stochastiques, la percolation et l'optimisation combinatoire.

P vs NP: Théorie de la complexité

S'insère dans la théorie de la complexité, en se concentrant sur le problème P vs NP et la classification des problèmes informatiques en fonction de l'efficacité.

Classes de complexité: P et NP

Explore les classes de complexité P et NP, en mettant en évidence les problèmes solvables et vérifiables, y compris les défis complets du NP.

Éléments de complexité computationnelle

Introduit la complexité computationnelle, les problèmes de décision, la complexité quantique et les algorithmes probabilistes, y compris les problèmes dures au NP et les problèmes complets au NP.

Afficher plus

Concepts associés (31)

Problème NP-complet

Réduction polynomiale

Théorie de la complexité (informatique théorique)

Computational complexity

NP-difficile

Afficher plus