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
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
Enseignement
Cours siglés (session en cours uniquement)
Programmes
- 117510 – Baccalauréat en informatique
- 117520 – Majeure en informatique
- 119110 – Baccalauréat en mathématiques et informatique
- 119110 – Baccalauréat en mathématiques et informatique
- 120510 – Baccalauréat en physique et informatique
- 120510 – Baccalauréat en physique et informatique
- 146811 – Baccalauréat en bio-informatique
- 146811 – Baccalauréat en bio-informatique
- 217510 – Maîtrise en informatique
- 246810 – Maîtrise en bio-informatique
Encadrement
Thèses et mémoires dirigés (dépôt institutionnel Papyrus)
Programmes de branchement catalytiques : algorithmes et applications
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
Cycle : Doctorat
Diplôme obtenu : Ph. D.
Le produit direct de fonctions et les programmes de branchement avec oracle
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
Algorithmique et complexité des systèmes à compteurs
Cycle : Doctorat
Diplôme obtenu : Ph. D.
Automates à contraintes semilinéaires = Automata with a semilinear constraint
Cycle : Doctorat
Diplôme obtenu : Ph. D.
Complexité raffinée du problème d'intersection d'automates
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
Représentation d'un polynôme par un circuit arithmétique et chaînes additives
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
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
Programmes de génération et machines de Turing algébriques
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
Projets
Projets de recherche
Lower bounds and derandomizations for branching programs
THE COMPUTATIONAL COMPLEXITY OF POLYNOMIAL TIME PROBLEMS
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.