Théorie de calcul: Complexité des problèmes

Cette séance de cours couvre la théorie du calcul, le concept de l'infini, les problèmes indécis, et la théorie de la complexité. Il explique comment mesurer la complexité des problèmes en termes de temps et d'espace, et la hiérarchie des classes de complexité. L'instructeur discute des algorithmes pratiques pour la recherche, le tri et le trajet le plus court, soulignant l'importance d'algorithmes efficaces pour diverses tâches de calcul. La séance de cours présente la classe de complexité P, qui représente des problèmes solubles dans le temps polynôme, et fournit des exemples de problèmes entrant dans cette classe. Il se termine par un résumé de la classification des problèmes, qui fait la distinction entre les problèmes indécis et les problèmes décidables.