| dbo:abstract
|
- Nedeterministický algoritmus (= stochastický) je takový algoritmus, který v některých krocích může volit z několika možností dalších kroků, což je rozdíl oproti deterministickému algoritmu, kde je následující krok vždy definován jednoznačně. Nedeterministický algoritmus při stejném vstupu může dávat rozdílné výsledky. Lze zkoumat množinu všech výsledků nedeterministického algoritmu a určovat
* zda existuje alespoň jeden výsledek vyhovující zadání. Příkladem tohoto využití je nedeterministický konečný automat.
* Pravděpodobnost provedení některých kroků algoritmu, pokud jsou známy pravděpodobnosti výběru dalších kroků algoritmu. Problémy tohoto typu zkoumá například teorie hromadné obsluhy. (cs)
- Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem Algorithmen oder Maschinen (meist Turingmaschinen oder endliche Automaten) nicht nur genau eine Berechnung zu einer bestimmten Eingabe durchlaufen können (deterministisch), sondern es bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand gibt. Dabei wird durch das Programm der jeweiligen Maschine in keiner Weise vorgegeben, welche der Möglichkeiten gewählt werden muss. In der Analyse solcher Algorithmen wird dann aber stets davon ausgegangen, dass ein im jeweiligen Zusammenhang bestmöglicher Übergang gewählt wurde. 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. (de)
- En ciencias de la computación, un algoritmo no determinista es un algoritmo que con la misma entrada ofrece muchos posibles resultados, y por tanto no ofrece una solución única. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinista. (es)
- In computer programming, 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 in 1967. (en)
- 비결정론적 알고리즘(영어: Nondeterministic algorithm)은 결정론적 알고리즘과는 달리, 동일한 입력이 주어지더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 의미한다. (ko)
- 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 pode executar de forma diferente em diferentes execuções devido a uma condição de concorrência. O comportamento de um depende de um gerador de números aleatórios. Um algoritmo que resolve um problema de pode ser executado em tempo polinomial ou tempo exponencial em função das escolhas que faz durante a execução. (pt)
- В інформатиці, недетермінований алгоритм це алгоритм, який передбачає декілька шляхів обробки одних і тих самих вхідних даних, без будь-якого уточнення який саме варіант буде обраний. (uk)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4849 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:date
| |
| dbp:reason
|
- the word "nondeterministic" is used with two different meanings (en)
|
| dbp:talk
|
- Talk:Nondeterministic algorithm#Misleading Article (en)
|
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En ciencias de la computación, un algoritmo no determinista es un algoritmo que con la misma entrada ofrece muchos posibles resultados, y por tanto no ofrece una solución única. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinista. (es)
- 비결정론적 알고리즘(영어: Nondeterministic algorithm)은 결정론적 알고리즘과는 달리, 동일한 입력이 주어지더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 의미한다. (ko)
- 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 pode executar de forma diferente em diferentes execuções devido a uma condição de concorrência. O comportamento de um depende de um gerador de números aleatórios. Um algoritmo que resolve um problema de pode ser executado em tempo polinomial ou tempo exponencial em função das escolhas que faz durante a execução. (pt)
- В інформатиці, недетермінований алгоритм це алгоритм, який передбачає декілька шляхів обробки одних і тих самих вхідних даних, без будь-якого уточнення який саме варіант буде обраний. (uk)
- Nedeterministický algoritmus (= stochastický) je takový algoritmus, který v některých krocích může volit z několika možností dalších kroků, což je rozdíl oproti deterministickému algoritmu, kde je následující krok vždy definován jednoznačně. Nedeterministický algoritmus při stejném vstupu může dávat rozdílné výsledky. Lze zkoumat množinu všech výsledků nedeterministického algoritmu a určovat (cs)
- Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem Algorithmen oder Maschinen (meist Turingmaschinen oder endliche Automaten) nicht nur genau eine Berechnung zu einer bestimmten Eingabe durchlaufen können (deterministisch), sondern es bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand gibt. Dabei wird durch das Programm der jeweiligen Maschine in keiner Weise vorgegeben, welche der Möglichkeiten gewählt werden muss. In der Analyse solcher Algorithmen wird dann aber stets davon ausgegangen, dass ein im jeweiligen Zusammenhang bestmöglicher Übergang gewählt wurde. (de)
- In computer programming, 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. (en)
|
| rdfs:label
|
- Nedeterministický algoritmus (cs)
- Nichtdeterminismus (de)
- Algoritmo no determinista (es)
- 비결정론적 알고리즘 (ko)
- Nondeterministic algorithm (en)
- Algoritmo não determinístico (pt)
- Недетермінований алгоритм (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |