# Vaughan Pratt

Vaughan Pratt (né le 12 avril 1944) est un professeur émérite de l'Université Stanford, qui est l'un des premiers pionniers dans le domaine de l'informatique. Depuis 1969, Pratt a apporté plusieurs contributions à des domaines fondamentaux tels que les algorithmes de recherche, les algorithmes de tri et les tests de primalité. Plus récemment, ses recherches portent sur la modélisation formelle des systèmes concurrents et des espaces de Chu.

## Carrière

Il grandit en Australie et fait ses études à la Knox Grammar School, où il obtient son diplôme en 1961, Pratt fréquente l'Université de Sydney, où il termine sa thèse de maîtrise en 1970, liée à ce que l'on appelle aujourd'hui le traitement du langage naturel. Il se rend ensuite aux États-Unis, où il réalise une thèse de doctorat à l'Université de Stanford en seulement 20 mois sous la supervision du directeur de thèse Donald Knuth. Sa thèse porte sur l'analyse de l'algorithme de tri Shellsort et des réseaux de tri.
Pratt est professeur adjoint au MIT (de 1972 à 1976) puis professeur associé (de 1976 à 1982). En 1974, en collaboration avec Knuth et James H. Morris, Pratt termine et formalise le travail qu'il a commencé en 1970 en tant qu'étudiant diplômé à Berkeley ; le résultat co-écrit est l'algorithme de recherche de motifs Knuth-Morris-Pratt. En 1976, il développe le système de logique dynamique, une logique modale du comportement structuré.
Il prend un congé sabbatique du MIT à Stanford (1980 à 1981) et est nommé professeur titulaire à Stanford en 1981.
Pratt dirige le projet de station de travail SUN à Stanford de 1980 à 1982. Il contribue de diverses manières à la fondation et au début du fonctionnement de Sun Microsystems, comme consultant pendant sa première année, puis en prenant un congé de Stanford pour les deux années suivantes, en devenant directeur de recherche, et enfin en reprenant son rôle de consultant auprès de Sun et en revenant à Stanford en 1985.
Il conçoit également le logo de Sun Microsystems qui comporte quatre copies entrelacées du mot « soleil » ; il s'agit d'un ambigramme.
Pratt devient professeur émérite à Stanford en 2000.

## Contributions

Un certain nombre d’algorithmes bien connus portent le nom de Pratt. Les certificats de Pratt, de courtes preuves de la primalité d'un nombre, ont démontré de manière pratique que la primalité peut être efficacement vérifiée, en plaçant le problème du test de primalité dans la classe de complexité NP et en fournissant la première preuve solide que le problème n'est pas co-NP-complet. L'algorithme de Knuth-Morris-Pratt, que Pratt a conçu au début des années 1970 avec son collègue professeur de Stanford Donald Knuth et indépendamment de Morris, est toujours l'algorithme de recherche de chaînes générales le plus efficace connu aujourd'hui. Avec Blum, Floyd, Rivest et Tarjan, il décrit la médiane des médianes, le premier algorithme de sélection optimale du pire des cas.
Pratt crée des outils utiles. En 1976, il écrit un document de travail au MIT AI Lab sur CGOL, une syntaxe alternative pour MACLISP qu'il a conçue et implémentée sur la base de son paradigme d'analyse de priorité d'opérateur descendante. Son analyseur est parfois appelé « analyseur Pratt » et est utilisé dans des systèmes ultérieurs, tels que MACSYMA. Douglas Crockford l'a également utilisé comme analyseur sous-jacent pour JSLint. Pratt a également mis en œuvre un éditeur de texte basé sur TECO appelé « DOC », qui est ensuite renommé « ZED ».
En 1999, Pratt construit le plus petit serveur Web du monde (à l'époque) : il a la taille d'une boîte d'allumettes$^,$.
Il est membre d’au moins sept organisations professionnelles, dont l'Association for Computing Machinery et fait partie du comité de rédaction de trois grandes revues de mathématiques. Il est également le fondateur, président et directeur technique de TIQIT Computers, Inc. pendant les dix années précédant sa fermeture en 2010.