Conseil de recherches en sciences naturelles et en génie du Canada
Symbol of the Government of Canada

Liens de la barre de menu commune

Le CRSNG présente 2 minutes avec
Stephen Cook
Département d'informatique
University of Toronto


Résumé

Titre de la vidéo

2 minutes avec Stephen Cook

Auteur

Division des communications du CRSNG

Durée

2:58

Date de diffusion

le 27 février 2013

Description

Stephen Cook est l'un des rares chercheurs en mathématiques dont les idées ont engendré de nouveaux domaines de recherche pour les générations actuelles et futures. Ce professeur d'informatique et de mathématiques à la University of Toronto est le lauréat de la Médaille d'or Gerhard Herzberg en sciences et en génie du Canada de 2012, qui est décernée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG).

En plus d'avoir fait des contributions reconnues à la théorie de la complexité, M. Cook a fait des contributions fondamentales à la théorie informatique, à la conception d'algorithmes, aux langages de programmation et à la logique mathématique. Son œuvre toujours grandissante sera probablement citée pendant de nombreuses décennies. Ses travaux ont eu des retombées sur divers domaines des mathématiques et de l'informatique et ont contribué à de nombreux autres domaines de recherche.


Transcription
Stephen Cook

Eh bien, je m'intéressais aux ordinateurs. Mais il n'y avait pas vraiment de départements d'informatique, alors j'ai fait mes études supérieures à Harvard, au Département de mathématiques. Ma thèse portait sur un tout nouveau domaine appelé « complexité des calculs informatiques », c'est-à-dire l'étude des nombres – de la quantité de ressources, de temps et de mémoire pour résoudre des problèmes. C'était donc une idée nouvelle; alors, je suis venu ici, à la University of Toronto, où un tout nouveau Département d'informatique recrutait des spécialistes de haut niveau. Et c'est là que je suis depuis ce temps. C'est là que j'ai eu l'idée ingénieuse d'introduire les concepts que nous appelons maintenant « les problèmes NP-complets ». Cette idée, cet article, c'est ce qui m'a rendu célèbre.

Maintenant, bien entendu, on connaît des milliers de problèmes NP-complets et ils sont assez importants pour influencer les nombreux domaines de l'informatique. Mais l'un des problèmes NP-complets types est celui que l'on appelle communément « le problème du vendeur itinérant ».

On vous donne N villes – N est un grand nombre, une centaine environ, et leur emplacement sur une carte. Dans quel ordre le vendeur devrait-il se rendre dans ces villes pour que son trajet soit le plus court possible? Maintenant, si N représente 100, une factorielle de 100 représente un nombre si grand qu'aucun ordinateur imaginable ne pourrait examiner les 100 séquences factorielles avant que le Soleil ne devienne une étoile rouge. Alors, la question mathématique qui se pose ici, c'est de savoir si l'on peut résoudre chaque problème NP, le problème de recherche, et s'il existe en réalité une solution calculée en temps polynômial.

Quand à la question P ou NP, c'est une question sans réponse. En fait, c'est maintenant l'un des sept problèmes du Prix du millénaire affichés par l'Institut de mathématiques Clay, qui offre un million de dollars à celui qui pourra résoudre n'importe lequel de ces problèmes. Il semble donc que c'est l'un des sept grands problèmes mathématiques non résolus à l'heure actuelle.

Cette vidéo vous a-t-elle été utile?

Très utile

Peu utile

Inutile

Sans opinion

Commentaires :

Les gens. La découverte. L'innovation.