Classes de complexité: introduction et exemples

Cette séance de cours introduit le concept de classes de complexité en abordant la solvabilité des problèmes par des algorithmes et la classification des problèmes en fonction de leur difficulté. L'instructeur explique la notation pour comparer les fonctions et définit les classes P et NP, illustrant avec des exemples de problèmes appartenant à chaque classe. La séance de cours explore comment certains problèmes, tels que les problèmes de somme de sous-ensemble, peuvent être classés dans ces classes de complexité, conduisant au fameux problème P vs NP. L'instructeur présente également des exemples de problèmes faciles à résoudre dans la classe P et démontre la complexité de la vérification des solutions aux problèmes dans la classe NP.