Editer votre profil

McKenzie, Pierre

Professeur titulaire

Contact :

  • Téléphone 514-343-6176 Pav. PAVILLON ANDRE-AISENSTADT \ bur. 3143

Site Web

McKenzie, Pierre

Expertises de recherche

Mon intérêt de recherche est la théorie de la complexité du calcul. Cette théorie a pour but de classifier les problèmes calculatoires soumis à l'ordinateur en fonction des ressources nécessaires à leur résolution.

Le temps de calcul et la quantité de mémoire utilisés sont des exemples de ressources. Multiplier deux nombres et calculer un chemin dans un labyrinthe sont des exemples de problèmes calculatoires.

Par exemple, est-il strictement plus coûteux, en quantité de mémoire, de déterminer un chemin dans un labyrinthe que de multiplier deux nombres? Une telle question se formule mathématiquement à l'aide de modèles de calcul abstraits, tels le circuit booléen, l'automate formel et la logique descriptive.  Y répondre par l'affirmative, ce que nous ne savons toujours pas faire aujourd'hui, requiert une preuve mathématique que toute procédure imaginable capable de déterminer un chemin dans un labyrinthe d'une certaine taille demandera plus de mémoire que la multiplication de deux entiers de taille comparable.

Champs d'expertise

Cours donnés au département ce trimestre

Thèses et mémoires dirigés au département et disponibles dans Papyrus

Nouvelles