Concept
Réduction polynomiale
Séances de cours associées (33)
Max-Flow Min-Cut
Explore l'algorithme Ford Fulkerson, le théorème Max-Flow Min-Cut, la matrice d'incidence et la complexité de l'optimisation du réseau.
Filtres à réponse impulsionnelle finie: Partie 2
Explore la conception des filtres Finite Impulse Response et les méthodes d'optimisation pour le contrôle dans le traitement du signal.
É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.
Transformée de Fourier rapide
Explique la transformée de Fourier rapide, un algorithme rapide pour calculer la transformée de Fourier discrète.
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.
Bases de programmation entières
Introduit les bases de la programmation entière, y compris les programmes binaires entiers et les stratégies de contrainte.
Circuits électriques : Diagrammes équivalents et réductions
Explore les circuits électriques, en mettant l'accent sur les réductions pour simplifier les circuits complexes dans des formes plus gérables.
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.
Algorithme de Lenstra : factorisation entière
Couvre l'algorithme de Lenstra pour la factorisation des entiers, qui calcule efficacement les facteurs premiers d'un entier.
Cryptanalyse: Clé publique et le pouvoir de l'interaction
Explore la cryptanalyse dans les systèmes à clé publique et la puissance de l'interaction dans les preuves interactives, couvrant le CO-NP, les classes NP, P vs. NP, et plus encore.