Présentation du concept
Le calcul est-il un concept universel et fondamental ? Pour répondre à cette question, Tim Roughgarden nous emmène en 1936, lorsque Alan Turing a posé les fondements de l'informatique en résolvant un problème mathématique obscur. Le papier de Turing a introduit la machine théorique qui porte son nom et a prouvé que certains problèmes ne peuvent être résolus par aucun algorithme, quelle que soit la quantité de temps ou de puissance de calcul utilisée.
Problèmes résolubles et algorithmes rapides
Une fois les problèmes irresolubles identifiés, Roughgarden se tourne vers une question plus subtile : quels problèmes les ordinateurs peuvent-ils résoudre rapidement ? Il nous présente des raccourcis algorithmiques, des astuces ingénieuses qui permettent aux programmes d'éviter d'examiner toutes les solutions possibles. Par exemple, l'application de cartographie de votre téléphone utilise l'algorithme de Dijkstra pour trouver le chemin le plus court sans vérifier tous les chemins concevables.
Problème du voyageur de commerce et NP-complétude
Cependant, le Problème du voyageur de commerce (TSP) résiste à toutes les tentatives de trouver un algorithme rapide, malgré sa ressemblance avec le problème du chemin le plus court. Roughgarden explique comment ce puzzle a conduit à la théorie de la NP-complétude, l'une des découvertes les plus surprenantes de l'informatique. Des milliers de problèmes apparemment sans rapport (ordonnancement, résolution de puzzles, optimisation de réseaux) s'avèrent être des versions déguisées du même défi sous-jacent.
P versus NP et implications
Cela nous amène à la question P versus NP, la question ouverte la plus importante en informatique et l'un des grands problèmes non résolus des mathématiques. Roughgarden retrace son histoire à travers des figures comme Hilbert, Gödel et von Neumann, montrant comment deux traditions de recherche distinctes, l'une axée sur ce que les algorithmes peuvent accomplir, l'autre sur leurs limites, ont convergé vers cette seule question. Le cours se termine par une examination de ce que la réponse pourrait signifier pour la cryptographie, l'intelligence artificielle, l'informatique quantique et notre compréhension du calcul lui-même.
