Walter Savitch

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Walter Savitch
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Voir et modifier les données sur Wikidata (74 ans)
Nationalité
Formation
Activités
Autres informations
A travaillé pour
image illustrant l’informatique théorique
Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Walter John Savitch est né le 21 février 1943. Il est professeur et chercheur en informatique et informatique théorique. Il surtout connu pour le théorème de Savitch (Savitch 1970), en théorie de la complexité qui précise les relations entre les classes en espace utilisant des machines de Turing déterministes et celles utilisant du non-déterminisme. En particulier ce théorème donne l'égalité PSPACE=NPSPACE.

Savitch a obtenu son doctorat (PhD) de mathématiques à l'université de Berkeley en 1969, sous la direction de Stephen Cook[1]. Il est professeur émérite à l'UCSD[2].

Bibliographie[modifier | modifier le code]

(en) Walter John Savitch, « Relationships between nondeterministic and deterministic tape complexities », Journal of Computer and System Sciences, vol. 4, no 2,‎ , p. 177-192

Notes et références[modifier | modifier le code]

Liens externes[modifier | modifier le code]