Rechenressource
Im Computerkomplexitätstheorie, a Rechenressource ist eine Ressource, die von einigen verwendet wird Computermodelle in der Lösung von Rechenprobleme.
Die einfachsten Rechenressourcen sind Berechnungszeit, die Anzahl der Schritte, die erforderlich sind, um ein Problem zu lösen, und SpeicherraumDie Menge an Speicher, die bei der Lösung des Problems erforderlich ist, aber es wurden viele kompliziertere Ressourcen definiert.
Ein Rechenproblem wird im Allgemeinen in Bezug auf seine Aktion auf eine gültige Eingabe definiert. Beispiele für Probleme könnten "eine Ganzzahl gegeben sein n, herausfinden, ob n ist Prime "oder" angegeben zwei Zahlen x und yBerechnen Sie das Produkt x*y". Wenn die Eingaben größer werden, wird die Menge an Rechenressourcen, die zur Lösung eines Problems erforderlich sind Asymptotische Analysedurch Identifizierung der Ressourcen als Funktion der Länge oder Größe der Eingabe. Die Verwendung von Ressourcen wird häufig teilweise mit Verwendung quantifiziert Big O Notation.
Computerressourcen sind nützlich, da wir untersuchen können, welche Probleme in einer bestimmten Menge jeder Rechenressource berechnet werden können. Auf diese Weise können wir bestimmen, ob Algorithmen Für die Lösung des Problems sind optimal und wir können Aussagen über eine machen Effizienz des Algorithmus. Der Satz aller Rechenprobleme, die unter Verwendung einer bestimmten Menge einer bestimmten Rechenressource gelöst werden können, ist a Komplexitätsklasseund Beziehungen zwischen verschiedenen Komplexitätsklassen sind eines der wichtigsten Themen in der Komplexitätstheorie.
Beschreibung allgemein zugänglicher Computergeräte
Der Begriff "Rechenressource" wird üblicherweise verwendet, um zugängliche Computergeräte und -software zu beschreiben. Sehen Utility Computing.
Formale Quantifizierung der Computerfähigkeit
Es wurden einige Anstrengungen unternommen, um die Computerfunktion offiziell zu quantifizieren. Ein begrenztes Turing Maschine wurde verwendet, um spezifische Berechnungen unter Verwendung der Anzahl der Zustandsübergänge und der Alphabetgröße zu modellieren, um den Rechenaufwand zu quantifizieren, der zur Lösung eines bestimmten Problems erforderlich ist.[1][2]
Verweise
- ^ Gregory J., Chaitin (1966). "Über die Länge der Programme zur Berechnung endlicher binärer Sequenzen" (PDF). Journal of the ACM. 13 (4): 547–569. doi:10.1145/321356.321363. S2CID 207698337. Archiviert von das Original (PDF) am 2007-02-05. Abgerufen 2007-09-25.
- ^ Sau, Daby; Eleftheriadis, Alexandros (1998). "Darstellung von Informationen mit Rechenressourcengrenzen" (PDF). Signale, Systeme und Computer. Konferenzaufzeichnung der zweiunddreißigsten Asilomar-Konferenz auf. Vol. 1. S. 452–456. ISBN 0-7803-5148-7. 10.1109/ACSSC.1998.750904. Abgerufen 2007-09-25.