Walter Savitch

Walter Savitch

Walter Savitch (* 21. Februar 1943) ist emeritierter Professor für Informatik an der University of California, San Diego.

Savitch erwarb 1969 an der University of California, Berkeley den Ph.D.-Grad in Mathematik. Er ist vor allem dafür bekannt, dass er die Komplexitätsklasse NL der nichtdeterministisch logarithmischen Probleme definiert hat, und insbesondere auch für den Satz von Savitch, welcher die Beziehung der Komplexitätsklassen NSPACE und DSPACE beschreibt. Die Komplexitätsklasse NL war die erste formal definierte NLOGSPACE vollständige Sprache. Diese fundamentale Erkenntnis führte zu ausgedehnteren Forschungen der vollständigen Probleme in Bereich der Komplexitätstheorie. Er hat auch zu den Theorien der nichtdeterministischen und parallelen Berechnungsmodelle wichtige Arbeiten beigetragen.

Seine Forschungsbereiche umfassen die Komplexitätstheorie, die formalen Sprachen und die Verarbeitung Natürlicher Sprachen / berechenbarer Sprachen. Neben seinen Arbeiten in der theoretischen Informatik, hat Savitch außerdem noch einige Fachbücher zum Erlernen von C/C++, Java, Ada und anderen Programmiersprachen geschrieben.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Walter Savitch — is best known for creating the NL (nondeterministic logarithmic) class of complexity problems, and for Savitch s theorem which defines a relationship between the NSPACE and DSPACE complexity classes. His work in establishing complexity classes… …   Wikipedia

  • Savitch — Walter Savitch ist emeritierter Professor für Informatik an der University of California, San Diego. Savitch ist vor allem dafür bekannt, dass er die Komplexitätsklasse NL der nichtdeterministisch logarithmischen Probleme definiert hat, und… …   Deutsch Wikipedia

  • Savitch's theorem — In computational complexity theory, Savitch s theorem, proved by Walter Savitch in 1970, states that for any function f ( n ) ≥ log( n ):NSPACE(f(n)) ⊆ DSPACE(f²(n)). In other words, if a nondeterministic Turing machine can solve a problem using… …   Wikipedia

  • Savitch — may mean:People*Jessica Savitch (1947 1983), American journalist *Walter J. Savitch, computer scientist …   Wikipedia

  • Theorem von Savitch — Der Satz von Savitch oder Theorem von Savitch ist ein Satz aus der Komplexitätstheorie, der 1970 von Walter Savitch bewiesen wurde. Er besagt, dass ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares …   Deutsch Wikipedia

  • Satz von Savitch — Der Satz von Savitch oder Theorem von Savitch ist ein Satz aus der Komplexitätstheorie, der 1970 von Walter Savitch bewiesen wurde. Er besagt, dass ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares …   Deutsch Wikipedia

  • Teorema de Savitch — En teoría de la complejidad computacional, el Teorema de Savitch establece que: NSPACE(f(n)) DSPACE(f²(n)) Walter Savitch (1970) Como corolario, se tiene que PSPACE = NPSPACE …   Wikipedia Español

  • Teorema de Savitch — En teoría de la complejidad computacional, el Teorema de Savitch, demostrado por Walter Savitch in 1970, establece que: NSPACE(f(n)) ⊆ DSPACE(f²(n)). Como corolario, se tiene que PSPACE = NPSPACE …   Enciclopedia Universal

  • UCSD — Vorlage:Infobox Hochschule/Professoren fehlt University of California, San Diego Motto Fiat lux (dt. „Es werde Licht“) Gründung 1960 …   Deutsch Wikipedia

  • UC San Diego — Vorlage:Infobox Hochschule/Professoren fehlt University of California, San Diego Motto Fiat lux (dt. „Es werde Licht“) Gründung 1960 …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”