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, room 3143
Profile
Research expertise
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.
Biography
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.
For more information…
Affiliations and responsabilities
Teaching and supervision
Teaching
Courses taught (current session only)
Programs
- 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
Student supervision
Theses and dissertation supervision (Papyrus Institutional Repository)
Programmes de branchement catalytiques : algorithmes et applications
Cycle : Master's
Grade : M. Sc.
The limits of Nečiporuk’s method and the power of programs over monoids taken from small varieties of finite monoids
Cycle : Doctoral
Grade : Ph. D.
Le produit direct de fonctions et les programmes de branchement avec oracle
Cycle : Master's
Grade : M. Sc.
Algorithmique et complexité des systèmes à compteurs
Cycle : Doctoral
Grade : Ph. D.
Automates à contraintes semilinéaires = Automata with a semilinear constraint
Cycle : Doctoral
Grade : Ph. D.
Complexité raffinée du problème d'intersection d'automates
Cycle : Master's
Grade : M. Sc.
Représentation d'un polynôme par un circuit arithmétique et chaînes additives
Cycle : Master's
Grade : M. Sc.
Analyse de la propriété d'incrémentalité dans le modèle de calcul du programme de branchement
Cycle : Master's
Grade : M. Sc.
Programmes de génération et machines de Turing algébriques
Cycle : Master's
Grade : M. Sc.
Projects
Research projects
Lower bounds and derandomizations for branching programs
THE COMPUTATIONAL COMPLEXITY OF POLYNOMIAL TIME PROBLEMS
Outreach
Publications and presentations
Disciplines
- Computer Science
- Pure Mathematics
Areas of expertise
- Finite automata
- Boolean circuit
- Formal language
- Logic
- Computational complexity theory