Activité "Pourquoi réfléchir ?"

Pas besoin de réfléchir les algorithmes calculent tellement vite ? Les réseaux de télécommunication mais aussi les réseaux routiers, sociaux ou biologiques se modélisent bien avec des graphes. Les sommets représentent les routeurs, les abonnés, les villes, les individus ou les protéines. Les arêtes représentent des liaisons ou des relations. Au cours de cette conférence, nous présentons divers problèmes qui se posent dans ces réseaux. Pour certains d’entre eux, nous ne savons pas calculer une solution autrement que « tester toutes les solutions potentielles ». Cette question est d’une importance majeure car un grand nombre de problèmes ne peuvent pas être résolus (en un temps raisonnable) même si les ordinateurs effectuent un très très grand nombre d’opérations par seconde. De nombreux chercheurs réfléchissent à améliorer ces temps de calcul prohibitifs. Nous présentons certains de ces problèmes difficiles à résoudre (par exemple le problème du voyageur de commerce) et montrons également des problèmes pour lesquels des solutions efficaces existent.