Séance de cours
Théorie de calcul: Décidabilité et complexité
Séances de cours associées (42)
Résoudre les jeux de parité dans la pratique
Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.
Théorie de calcul: Comparabilité et problèmes indécis
Explore la comptabilité et les problèmes indécis dans la théorie du calcul.
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.
É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.
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.
Éléments de complexité informatique
Couvre les concepts et les implications de complexité informatique classique et quantique.
Théorie de la computabilité: Solvabilité et Complexité
Il explore la théorie de la computabilité, les problèmes de décision, les classes de complexité et l'énigme « P vs NP ».
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.
É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.
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.