About: Nondeterministic algorithm     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatAlgorithms, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FNondeterministic_algorithm

In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one.

AttributesValues
rdf:type
rdfs:label
  • Nondeterministic algorithm
  • Nichtdeterminismus
  • Algoritmo no determinista
  • Algoritmo não determinístico
rdfs:comment
  • Nichtdeterministische Maschinen sind theoretische Modelle und im Allgemeinen nicht praktisch realisierbar. Ihr Zweck in der theoretischen Informatik ist, die Komplexität von Problemen nach oben zu beschränken, das soll heißen, dass ein Problem, für das man einen nichtdeterministischen Algorithmus angeben kann, „leichter“ ist als ein Problem, für das man dies nicht kann. In vielen Fällen ist es leichter, für ein Problem einen nichtdeterministischen Algorithmus zu finden als einen deterministischen (und damit praktisch realisierbaren) Algorithmus. Daher ist es eine wichtige Frage in der theoretischen Informatik, unter welchen Umständen man nichtdeterministische Algorithmen bzw. Maschinen durch deterministische Algorithmen bzw. Maschinen effizient simulieren kann.
  • En ciencias de la computación, un algoritmo no determinista es un algoritmo que con la misma entrada ofrece muchos posibles resultados. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinista.
  • Em ciência da computação, um algoritmo não determinístico é um algoritmo em que, dada uma certa entrada, pode apresentar comportamentos diferentes em diferentes execuções, ao contrário de um algoritmo determinístico. Um algoritmo concorrente pode executar de forma diferente em diferentes execuções devido a uma condição de concorrência. O comportamento de um algoritmo probabalistico depende de um gerador de números aleatórios. Um algoritmo que resolve um problema de tempo polinomial não determinístico pode ser executado em tempo polinomial ou tempo exponencial em função das escolhas que faz durante a execução.
  • In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one.
sameAs
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
foaf:depiction
  • External Image
foaf:isPrimaryTopicOf
thumbnail
prov:wasDerivedFrom
has abstract
  • In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one. The notion was introduced by Robert W. Floyd.
  • Nichtdeterministische Maschinen sind theoretische Modelle und im Allgemeinen nicht praktisch realisierbar. Ihr Zweck in der theoretischen Informatik ist, die Komplexität von Problemen nach oben zu beschränken, das soll heißen, dass ein Problem, für das man einen nichtdeterministischen Algorithmus angeben kann, „leichter“ ist als ein Problem, für das man dies nicht kann. In vielen Fällen ist es leichter, für ein Problem einen nichtdeterministischen Algorithmus zu finden als einen deterministischen (und damit praktisch realisierbaren) Algorithmus. Daher ist es eine wichtige Frage in der theoretischen Informatik, unter welchen Umständen man nichtdeterministische Algorithmen bzw. Maschinen durch deterministische Algorithmen bzw. Maschinen effizient simulieren kann.
  • En ciencias de la computación, un algoritmo no determinista es un algoritmo que con la misma entrada ofrece muchos posibles resultados. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinista.
  • Em ciência da computação, um algoritmo não determinístico é um algoritmo em que, dada uma certa entrada, pode apresentar comportamentos diferentes em diferentes execuções, ao contrário de um algoritmo determinístico. Um algoritmo concorrente pode executar de forma diferente em diferentes execuções devido a uma condição de concorrência. O comportamento de um algoritmo probabalistico depende de um gerador de números aleatórios. Um algoritmo que resolve um problema de tempo polinomial não determinístico pode ser executado em tempo polinomial ou tempo exponencial em função das escolhas que faz durante a execução.
http://purl.org/voc/vrank#hasRank
http://purl.org/li...ics/gold/hypernym
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git39 as of Aug 09 2019


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3232 as of Aug 9 2019, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2019 OpenLink Software