Passer au contenu

/ Département d'informatique et de recherche opérationnelle

Je donne

Rechercher

Pierre McKenzie

Vcard

Professeur titulaire

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

André-Aisenstadt local 3143

pierre.mckenzie@umontreal.ca

514 343-6176

Courriels

mckenzie@iro.umontreal.ca (Travail)

Télécopieur : 514 343-5834

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.

Lire plus…

Programmes d’enseignement

  • Baccalauréat en informatique – Sciences pures et sciences appliquées Technologies de l'information (TIC)
  • Majeure en informatique – Sciences pures et sciences appliquées Technologies de l'information (TIC)
  • Baccalauréat en mathématiques et informatique – Sciences pures et sciences appliquées
  • Baccalauréat en mathématiques et informatique – Sciences pures et sciences appliquées
  • Baccalauréat en physique et informatique – Sciences pures et sciences appliquées
  • Baccalauréat en physique et informatique – Sciences pures et sciences appliquées
  • Baccalauréat en bio-informatique – Sciences de la vie Sciences pures et sciences appliquées Sciences de la santé
  • Baccalauréat en bio-informatique – Sciences pures et sciences appliquées Sciences de la santé Sciences de la vie
  • Baccalauréat en bio-informatique – Sciences pures et sciences appliquées Sciences de la santé Sciences de la vie
  • Maîtrise en informatique – Sciences pures et sciences appliquées Technologies de l'information (TIC)

Cours donnés

  • IFT3375 Informatique théorique
  • IFT6370 Informatique théorique

Expertises

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.

Encadrement Tout déplier Tout replier

Programmes de branchement catalytiques : algorithmes et applications Thèses et mémoires dirigés / 2019 - 2019
Diplômé(e) : Côté, Hugo
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
The limits of Nečiporuk’s method and the power of programs over monoids taken from small varieties of finite monoids Thèses et mémoires dirigés / 2019 - 2019
Diplômé(e) : Grosshans, Nathan
Cycle : Doctorat
Diplôme obtenu : Ph. D.
Le produit direct de fonctions et les programmes de branchement avec oracle Thèses et mémoires dirigés / 2018 - 2018
Diplômé(e) : Lavoie, Martin
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
Algorithmique et complexité des systèmes à compteurs Thèses et mémoires dirigés / 2016 - 2016
Diplômé(e) : Blondin, Michael
Cycle : Doctorat
Diplôme obtenu : Ph. D.
Automates à contraintes semilinéaires = Automata with a semilinear constraint Thèses et mémoires dirigés / 2013 - 2013
Diplômé(e) : Cadilhac, Michaël
Cycle : Doctorat
Diplôme obtenu : Ph. D.
Complexité raffinée du problème d'intersection d'automates Thèses et mémoires dirigés / 2012 - 2012
Diplômé(e) : Blondin, Michael
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
Représentation d'un polynôme par un circuit arithmétique et chaînes additives Thèses et mémoires dirigés / 2011 - 2011
Diplômé(e) : Elias, Yara
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
Analyse de la propriété d'incrémentalité dans le modèle de calcul du programme de branchement Thèses et mémoires dirigés / 2009 - 2009
Diplômé(e) : Pouliot, David
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
Programmes de génération et machines de Turing algébriques Thèses et mémoires dirigés / 2006 - 2006
Diplômé(e) : Pilette, Simon
Cycle : Maîtrise
Diplôme obtenu : M. Sc.

Projets de recherche Tout déplier Tout replier

Lower bounds and derandomizations for branching programs Projet de recherche au Canada / 2018 - 2026

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

THE COMPUTATIONAL COMPLEXITY OF POLYNOMIAL TIME PROBLEMS Projet de recherche au Canada / 2012 - 2019

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

Informations supplémentaires

Consultez cette fiche sur :