Séance de cours
Théorie de calcul: Complexité NP
Séances de cours associées (32)
É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.
Éléments de complexité informatique
Couvre les concepts et les implications de complexité informatique classique et quantique.
Délégation quantique de calcul
Couvre le concept de délégation quantique du calcul et la relation entre MIP et RE, en abordant les questions fréquentes et en discutant des matériaux utiles et des interactions avec les appareils quantiques.
Complexité et induction: Algorithmes et preuves
Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.
Complexité computationnelle: Théorie et applications
Explore la complexité computationnelle, l'exhaustivité du NP et les réductions polynômes de l'informatique théorique.
Classes de complexité: P et NPMOOC: Information, Calcul, Communication: Introduction à la pensée informatique
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.
Complexité et induction: Algorithmes et preuves
Explore la complexité du pire cas, l'induction mathématique, et des algorithmes comme la recherche binaire et le tri d'insertion.
Éléments de complexité computationnelle
Couvre les algorithmes quantiques, les classes de complexité, l'algorithme de Grover et l'information quantique dans la complexité computationnelle.
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.
Modular Arithmetic : Optimisation de l'exponentiation
Explore l'optimisation de l'exponentiation en arithmétique modulaire pour des calculs efficaces et la détermination des nombres premiers.