| dbo:abstract
|
- In der Komplexitätstheorie dienen verschiedene Speedup-Theoreme oder Beschleunigungssätze für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer Algorithmus bekannt ist. Die ursprüngliche Version des Speedup-Theorems stammt von Manuel Blum (1967), ist jedoch heute aufgrund der Verwendung beliebiger Komplexitätsfunktionen nicht mehr von großer Bedeutung. Man setzt heute in der Komplexitätstheorie im Allgemeinen echte Komplexitätsfunktionen voraus, die gewisse Eigenschaften erfüllen müssen (siehe auch Anforderungen an Schrankenfunktionen). (de)
- En la teoría de la complejidad computacional, un teorema del aumento de velocidad es un teorema que considera un algoritmo que resuelva un problema y demuestra que existe otro algoritmo más rápido que resuelve el mismo problema (o, más generalmente, un algoritmo que utiliza una menor cantidad de cualquier recurso, no solo tiempo). El teorema del aumento de velocidad lineal para máquinas de Turing prueba que dado cualquier máquina que resuelva un problema usando f(n) de un recurso, existe otra máquina que lo resuelve utilizando cf(n) de ese mismo recurso, donde c > 0. El teorema del aumento de velocidad de Blum prueba la existencia de un problema tal que si existe un algoritmo que puede resolverlo en tiempo O(f(n)), entonces existe otro algoritmo que lo resuelve en tiempo O(log f(n)). El para una computadora cuántica prueba que si una computadora determinista puede efectuar una búsqueda en tiempo O(f(n)), entonces una computadora cuántica puede efectuar la misma búsqueda en tiempo O(√f(n)).
* Datos: Q774599 (es)
- In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a more efficient algorithm solving the same problem. Examples:
* Linear speedup theorem, that the space and time requirements of a Turing machine solving a decision problem can be reduced by a multiplicative constant factor.
* Blum's speedup theorem, which provides speedup by any computable function (not just linear, as in the previous theorem). (en)
- Nella teoria della complessità computazionale un teorema dello speedup (in inglese speed-up significa velocizzare) è un teorema che considera alcuni algoritmi che risolvono determinati problemi e dimostra l'esistenza di algoritmi più efficienti per risolvere gli stessi problemi. Il per le macchine di Turing dimostra che lo spazio e il tempo richiesti da una macchina di Turing per risolvere un problema decidibile possono essere ridotti, in parole povere, di un qualunque fattore costante moltiplicativo. Come conseguenza si ha che è sempre possibile migliorare la velocità di esecuzione di un algoritmo (a patto di utilizzare più memoria) oppure che è sempre possibile diminuire lo spazio occupato in memoria (a patto di aumentare il tempo di esecuzione), tuttavia i miglioramenti sono al più lineari. Il teorema dello speedup di Blum dimostra la velocizzazione di qualunque funzione calcolabile (non solo lineare, come nel precedente teorema). Data la desiderata funzione di speedup, deduce l'esistenza di un problema decidibile tale che qualunque algoritmo in grado di risolverlo può essere velocizzato. (it)
- 計算複雑性理論における加速定理（かそくていり、英: speedup theorem）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、使用する資源がより少ない算法）の存在を示す定理である。 (ja)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1022 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a more efficient algorithm solving the same problem. Examples:
* Linear speedup theorem, that the space and time requirements of a Turing machine solving a decision problem can be reduced by a multiplicative constant factor.
* Blum's speedup theorem, which provides speedup by any computable function (not just linear, as in the previous theorem). (en)
- 計算複雑性理論における加速定理（かそくていり、英: speedup theorem）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、使用する資源がより少ない算法）の存在を示す定理である。 (ja)
- In der Komplexitätstheorie dienen verschiedene Speedup-Theoreme oder Beschleunigungssätze für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer Algorithmus bekannt ist. (de)
- En la teoría de la complejidad computacional, un teorema del aumento de velocidad es un teorema que considera un algoritmo que resuelva un problema y demuestra que existe otro algoritmo más rápido que resuelve el mismo problema (o, más generalmente, un algoritmo que utiliza una menor cantidad de cualquier recurso, no solo tiempo). El teorema del aumento de velocidad lineal para máquinas de Turing prueba que dado cualquier máquina que resuelva un problema usando f(n) de un recurso, existe otra máquina que lo resuelve utilizando cf(n) de ese mismo recurso, donde c > 0.
* Datos: Q774599 (es)
- Nella teoria della complessità computazionale un teorema dello speedup (in inglese speed-up significa velocizzare) è un teorema che considera alcuni algoritmi che risolvono determinati problemi e dimostra l'esistenza di algoritmi più efficienti per risolvere gli stessi problemi. Il teorema dello speedup di Blum dimostra la velocizzazione di qualunque funzione calcolabile (non solo lineare, come nel precedente teorema). Data la desiderata funzione di speedup, deduce l'esistenza di un problema decidibile tale che qualunque algoritmo in grado di risolverlo può essere velocizzato. (it)
|
| rdfs:label
|
- Speedup-Theorem (de)
- Teorema del aumento de velocidad (es)
- Teorema dello speedup (it)
- 加速定理 (ja)
- Speedup theorem (en)
- Teorema da aceleração (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
