Passer au contenu

/ La recherche

Je donne

Rechercher

Sciences naturelles et génie

Pierre McKenzie

La théorie de la complexité du calcul

Professeur titulaire

Faculté des arts et des sciences - Département d'informatique et de recherche opérationnelle

André-Aisenstadt, local 3143

514 343-6176

pierre.mckenzie@umontreal.ca

Autre numéro : 514 343-5834 (Télécopieur)
Autre courriel : mckenzie@iro.umontreal.ca (Travail)

Portrait

Expertise de recherche

Mon intéret de recherche à long terme est la théorie de la complexité du calcul. Cette théorie vise à ordonner partiellement les problèmes calculatoires selon la quantité de ressources nécessaire et suffisante pour les résoudre. Le temps et la mémoire sont des exemples de ressources. La multiplication de deux entiers et le calcul d'un chemin dans un graphe sont des exemples de problèmes. Est-il plus difficile de calculer un chemin que de multiplier? Une telle question se formule mathématiquement et sa réponse n'est pas connue: elle requiert une preuve que tout algorithme imaginable effectuant le calcul de chemins prendra nécessairement plus de ressources sur de grands graphes que les ressources requises pour multiplier de grands entiers. En complexité, les conjectures abondent mais les progrès sont lents.

Biographie

Après des études de premier cycle en physique et une maîtrise dans le domaine des systèmes d’exploitation à l’Université McGill, Pierre McKenzie a consacré une année à faire le tour du monde. Programmeur en Australie en 1978, il se souvient d’une conférence en informatique prononcée à Melbourne par un ancien étudiant d’un certain Steve Cook. 

De retour au pays, il s’inscrit au doctorat à l’Université de Toronto dans le but de pousser plus loin l’étude des systèmes d’exploitation. L’incident de parcours était inévitable : cinq ans plus tard, il détenait un doctorat, en théorie de la complexité, obtenu sous la direction d’Allan Borodin et de Steve Cook, inventeur de la NP-complétude.

Pierre McKenzie est entré en fonction au DIRO en 1984 et il y fait carrière depuis, si l’on exclut une année à l’Université de la Colombie britannique (où ses enfants ont appris l’anglais) et une année à l’Université de Tübingen (où ses enfants, mais pas lui, ont appris l’allemand).

En 2001, il se voyait en confier l’important mandat de diriger le DIRO, qu'il a dirigé jusqu'en 2005.

Pour en savoir plus…

Affiliations et responsabilités

Enseignement et encadrement

Encadrement

Thèses et mémoires dirigés (dépôt institutionnel Papyrus)

2019

Programmes de branchement catalytiques : algorithmes et applications

Diplômé(e) : Côté, Hugo
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2019

The limits of Nečiporuk’s method and the power of programs over monoids taken from small varieties of finite monoids

Diplômé(e) : Grosshans, Nathan
Cycle : Doctorat
Diplôme obtenu : Ph. D.
2018

Le produit direct de fonctions et les programmes de branchement avec oracle

Diplômé(e) : Lavoie, Martin
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2016

Algorithmique et complexité des systèmes à compteurs

Diplômé(e) : Blondin, Michael
Cycle : Doctorat
Diplôme obtenu : Ph. D.
2013

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Diplômé(e) : Cadilhac, Michaël
Cycle : Doctorat
Diplôme obtenu : Ph. D.
2012

Complexité raffinée du problème d'intersection d'automates

Diplômé(e) : Blondin, Michael
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2011

Représentation d'un polynôme par un circuit arithmétique et chaînes additives

Diplômé(e) : Elias, Yara
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2009

Analyse de la propriété d'incrémentalité dans le modèle de calcul du programme de branchement

Diplômé(e) : Pouliot, David
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2006

Programmes de génération et machines de Turing algébriques

Diplômé(e) : Pilette, Simon
Cycle : Maîtrise
Diplôme obtenu : M. Sc.

Projets

Projets de recherche

2018 - 2026

Lower bounds and derandomizations for branching programs

Chercheur principal : Pierre McKenzie
Sources de financement : CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Programmes de subvention : PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe
2012 - 2019

THE COMPUTATIONAL COMPLEXITY OF POLYNOMIAL TIME PROBLEMS

Chercheur principal : Pierre McKenzie
Sources de financement : CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Programmes de subvention : PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe

Rayonnement

Publications et communications

Disciplines

  • Informatique
  • Mathématiques fondamentales

Champ d’expertise

  • Automates finis
  • Circuits booléens
  • Langage formel
  • Logique
  • Théorie de la complexité (informatique théorique)

Aide en ligne pour votre profil | Nous joindre

Le Répertoire des professeurs est propulsé par les données du SADVR et est un projet du CENR.

Personnes-ressource dans nos équipes
Qui fait quoi?
Formulaires, procédures et systèmes
Formulaires et procédures
Occasions de financement avec PIVOT
PIVOT