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. Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité. vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). Considérons l'exemple du problème du voyageur de commerce. La donnée du problème est un ensemble de villes et de distances séparant ces villes. L'objectif du problème est de trouver un plus court circuit qui passe une et une seule fois par toutes les villes. Il existe un problème de décision associé : étant donné un ensemble de villes, les distances entre villes et un entier k, déterminer s'il existe un circuit qui passe une et une seule fois par toutes les villes de longueur inférieure à k. Ainsi, on distingue deux types de problèmes. Les problèmes de décision posent une question dont la réponse est oui ou non ; dans le cas du problème du voyageur de commerce : existe-il oui ou non un circuit de longueur inférieure à k ? Les problèmes de recherche d'une solution comportent une question ou plutôt une injonction de la forme « renvoyer un élément tel que... » dont la réponse consiste à fournir un tel élément; dans le cas du problème du voyageur de commerce, exhiber un circuit de longueur minimale. Il s'agit donc d'un problème fonctionnel, et il sera donc catégorisé dans une classe fonctionnelle, par exemple FP si la solution est calculée en temps polynomial.

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

Publications associées (65)

Personnes associées (75)

Unités associées (3)

Concepts associés (167)

Cours associés (98)

Séances de cours associées (729)

MOOCs associés (17)

IoT Systems and Industrial Applications with Design Thinking

The first MOOC to provide a comprehensive introduction to Internet of Things (IoT) including the fundamental business aspects needed to define IoT related products.

Logic Circuits for Embedded Systems part B

Digital Design in Embedded Systems part A

CS-455: Topics in theoretical computer science

The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f

CS-524: Computational complexity

In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation. This course advances the students knowle

CS-459: Foundations of probabilistic proofs

Probabilistic proof systems (eg PCPs and IPs) have had a tremendous impact on theoretical computer science, as well as on real-world secure systems. They underlie delegation of computation protocols a

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks

IEEE COMPUTER SOC2022

In this dissertation, I develop theory and evidence to argue that new technologies are central to how firms organize to create and capture value. I use computational methods such as reinforcement lear

EPFL2022

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in m

EPFL2022

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

Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.

Problème SAT

vignette|Une instance du Sudoku peut être transformée en une formule de logique propositionnelle à satisfaire. Une assignation des variables propositionnelles donne une grille complétée. En informatique théorique, le problème SAT ou problème de satisfaisabilité booléenne est le problème de décision, qui, étant donné une formule de logique propositionnelle, détermine s'il existe une assignation des variables propositionnelles qui rend la formule vraie. Ce problème est important en théorie de la complexité.

MHD Stabilité de l'équilibre

Explore l'équilibre et la stabilité Magnetohydrodynamique, les solutions MHD idéales, le théorème « boule poilue » et les conditions limites.

Théorie du calcul : conclusions et théorie de la complexité

Explore les problèmes de prise de décision, la théorie de la complexité et les classes NP vs P.

Simplification de la propagation des croyances

Explore la simplification des équations de propagation des croyances pour les modèles par paires, réduisant la complexité de calcul de l'ordre n cube à l'ordre n.