Passer au contenu principal

Switch to dark mode

Recherche

Afficher tous les résultats pour

Accueil

Séance de cours

Comprendre la complexité: algorithmes et problèmes NP

À propos
Confidentialité
Mentions légales

Copyright © 2025 EPFL, tous droits réservés

Graph Chatbot

Description

Cette séance de cours couvre les classes de complexité, l'effet de la complexité sur le temps de l'ordinateur, les problèmes traçables, la classe NP, les problèmes NP-complets, 3-SAT, et résume le concept de problèmes traçables appartenant à la classe P.

Source officielle

https://mediaspace.epfl.ch/media/0_v5uxu4ht

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

Dans cours

DEMO: mollit aliqua

Reprehenderit sit ea velit occaecat. Ut minim esse incididunt cupidatat est minim non ad nostrud cillum mollit. Excepteur culpa laborum occaecat in officia cupidatat reprehenderit consectetur et fugiat proident irure.

Enseignant

culpa commodo ex voluptate

Veniam duis et est adipisicing fugiat. Dolor pariatur sit ea cillum. Nostrud esse dolor laboris do ullamco ullamco aliquip ad cupidatat. Exercitation ipsum sint non reprehenderit cillum non occaecat dolore elit fugiat laborum non ut. Magna duis tempor exercitation esse adipisicing officia adipisicing commodo et pariatur occaecat.

Proximité ontologique

Informatique théorique

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

Séances de cours associées (28)

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

Comprendre la complexité : Tractable Problems et NP-Complete

Couvre les classes de complexité, l'effet sur le temps de l'ordinateur, les problèmes traçables, la classe NP et les problèmes NP-complets.

Complexité des algorithmes : notation Big-O

Explore la complexité de l'algorithme, la notation big-O, l'induction, la récursion et l'analyse des temps de fonctionnement, couvrant les problèmes NP et les classes de complexité.

Éléments de complexité informatique

Couvre les concepts et les implications de complexité informatique classique et quantique.

Théorie de calcul: Décidabilité et complexité

S'inscrit dans la théorie du calcul, couvrant la décidabilité, la complexité, P vs. NP, et les réductions.