/ en / Traditional / mobile

Beats Biblionetz - Personen

Definitionen von David Harel

Auf dieser Seite sind alle im Biblionetz vorhandenen Definitionen von David Harel aufgelistet.

Church-Turing-These
  • Jedes algorithmische Problem, das in irgendeiner Programmiersprache programmiert und auf irgendeinem dafür geeigneten Computer ausgeführt werden werden (sogar auf Computern, die noch nicht gebaut sind, aber prinzipiell gebaut werden könnten), und selbst wenn es unbeschränkt viel Zeit und Speicherplatz für immer grössere Eingaben benötigt - jedes solche Programm ist auch durch eine Turing-Maschine lösbar.
    von David Harelim Buch Das Affenpuzzle (2000) im Text Manchmal können wir es nicht auf Seite 39
Halteproblem
  • Als Eingabe wird das Halteproblem "gefüttert" mit dem Text eines zulässigen Programms A in unserer ausgewählten Programmiersprache Spr und einer möglichen Eingabe X (die nichts anderes als eine Folge von Symbolen ist). Das Problem fragt danach, ob A anhalten würde, wenn wir es mit der Eingabe X laufen liessen.
    von David Harelim Buch Das Affenpuzzle (2000) im Text Manchmal können wir es nicht auf Seite 50
NP
  • NP (ohne "-vollständig") steht für die Klasse der Probleme, für die es magische, nicht-deterministische Polynomialzeit-Algorithmen gibt.
    von David Harelim Buch Das Affenpuzzle (2000) im Text Manchmal wissen wir es nicht auf Seite 106
NP-complete
  • Die NP-vollständigen Probleme sind die "härtesten" in NP, und zwar in dem "alle-mit-einem"-Sinn: Falls eines von ihnen in P liegen sollte, dann sind alle anderen Probleme aus NP auch in P.
    von David Harelim Buch Das Affenpuzzle (2000) im Text Manchmal wissen wir es nicht auf Seite 106
P (PTIME)
  • PTIME oder manchmal kurz P steht für die Klasse der Probleme mit Polynomialzeit-Algorithmen, also derjenigen Probleme, die wir bislang gut oder durchführbar genannt haben.
    von David Harelim Buch Das Affenpuzzle (2000) im Text Manchmal wissen wir es nicht auf Seite 106