Описание тега non-deterministic
Недетерминизм относится либо к вычислительной системе, где результатом может быть один из многих заданных результатов, либо к теоретической конструкции, в которой вычислительной системе разрешено опробовать множество опций параллельно для поиска результата.
1
ответ
Кластеризация DBSCAN - что происходит, когда пограничная точка одного кластера считается базовой точкой другого кластера
Я хотел бы узнать ваше мнение о кластеризации dbscan, я пытаюсь реализовать алгоритм, как опубликовано здесь. На мой взгляд, существует возможность того, что одна точка от границы одного кластера будет центральной точкой другой, как показано на рису…
21 дек '15 в 11:30
1
ответ
Построение недетерминированной машины Тьюринга
Нарисуйте схему двухдетерминированной недетерминированной машины Тьюринга M, которая решает язык L = {w∈Σ * | w = uu u ∈Σ *} Если бы я мог получить помощь в объяснении шагов, как построить NDTM (лингвистически), я бы мог нарисовать диаграмму, но я н…
09 янв '17 в 16:40
1
ответ
Почему порядок словаря недетерминирован?
Недавно я перешел с Python 2.7 на Python 3.3, и кажется, что, хотя в Python 2 порядок словарных ключей был произвольным, но согласованным, в Python 3 порядок ключей словаря был получен с помощью, например, vars() кажется недетерминированным. Если я …
19 фев '13 в 11:25
1
ответ
Недетерминизм в сравнении с проверяемостью за полиномиальное время
Я читал, что проблема NP может быть проверена за полиномиальное время или, что то же самое, разрешима за полиномиальное время с помощью недетерминированной машины Тьюринга. Почему эти определения эквивалентны?
03 апр '14 в 04:52
3
ответа
Создание недетерминированных функций в SQL Server с помощью RAND()
После небольшого поиска и прочтения документации становится ясно, что вы можете написать пользовательские функции в SQL Server, которые помечены как детерминированные или недетерминированные в зависимости от того, какие встроенные функции используют…
20 авг '10 в 13:49
1
ответ
Структуры данных с недетерминированными компонентами в Coq
Я попытался смоделировать менее наивное монадическое кодирование недетерминизма (менее наивное, чем MonadPlus и общие списки) в Coq, которое часто используется в Haskell; например кодировка для списков выглядит так data List m a = Nil | Cons (m a) (…
05 апр '16 в 09:24
1
ответ
Python с плавающей точкой детерминизм
Приведенный ниже код (для вычисления косинусного сходства) при многократном запуске на моем компьютере выдаст 1.0, 0.9999999999999998 или 1.0000000000000002. Когда я уберу функцию нормализации, она вернет только 1.0. Я думал, что операции с плавающе…
08 фев '14 в 06:25
1
ответ
Как проверять предоставленные пользователем файлы классов в черные списки пакетов, классов и методов
Я работаю над приложением, в котором размещены определенные пользователем хранимые процедуры, которые предоставляются в виде файлов классов Java. Процедуры должны быть детерминированными, и я хочу занести в черный список различные пакеты и методы, к…
23 июл '11 в 14:21
12
ответов
Источники недетерминизма
Моя якобы детерминированная программа выдает один из нескольких слегка отличных результатов на разных прогонах. Вход, компилятор и компьютер неизменны. Я не уверен, какой вывод правильный, потому что он всегда выглядит разумным. Помимо случайного вы…
31 авг '10 в 13:29
1
ответ
Почему недетерминированная функция выбора в std lib Карри определяется не просто, а с помощью вспомогательной функции с двумя аргументами?
Рассмотрим функцию choose на языке программирования карри с указанием, что "(choose xs) недетерминированно выбирает один элемент из списка xs". Я реализовал бы это прямо через два альтернативных недетерминированных правила: choose :: [a] -> a cho…
01 мар '11 в 12:12
1
ответ
Какие проблемы решает выбор карри?
Я знаком с тем, какой выбор оператора ((?)), принимает два аргумента и соответствует им обоим. Мы могли бы определить это следующим образом: a?_=a _?b=b Это может быть использовано для введения недетерминизма между двумя значениями. Однако, что я не…
24 апр '18 в 06:29
1
ответ
Недетерминированные поля пересчитываются между показом, подсчетом и сохранением кадра данных
У нас есть uuid udf: import java.util.UUID val idUdf = udf(() => idgen.incrementAndGet.toString + "_" + UUID.randomUUID) spark.udf.register("idgen", idUdf) Проблема заключается в том, что при запуске count, или же show или же write каждый из них …
16 дек '18 в 02:36
1
ответ
Недетерминированное состояние машины понимания
Я пытаюсь создать DSL для своего проекта iOS. Для этого я планирую построить Semantic Model в форме State Machine, (Терминология взята из книги Фаулера о DSL). Главная идея: State Machine закодирован как набор states а также transitions между ними, …
22 фев '19 в 21:48
5
ответов
Ошибка сегментации при использовании pthreads недетерминированным образом
Проблема в том, что когда я запускаю приведенный ниже код на одном ядре, иногда он работает правильно, а иногда я получаю ошибку сегментации. Вероятно, эта проблема будет возникать чаще на многоядерной машине. Мне нужно знать, где этот недетерминизм…
22 дек '09 в 06:56
1
ответ
Как преобразовать монадическую функцию списка в поиск в ширину?
Я только что понял, как выяснить, как использовать монаду List для недетерминированных вычислений. Однако я полагаю, что мой алгоритм выиграл бы от поиска в ширину вместо поиска в глубину, получаемого из монады List. Вот выдержка, показывающая интер…
11 мар '14 в 18:33
9
ответов
Почему обратный анализ делает алгоритм недетерминированным?
Так что, по крайней мере, два профессора упомянули, что откат назад делает алгоритм недетерминированным, не давая слишком много объяснений, почему это так. Я думаю, что понимаю, как это происходит, но мне трудно выразить это словами. Может ли кто-ни…
01 фев '09 в 05:28
0
ответов
Как детерминистически обработать ситуацию в NodeJS, где асинхронные функции используют память быстрее, чем сборщик мусора восстанавливает ее?
Я столкнулся с проблемой, когда у меня не хватает памяти, потому что сборка мусора не освобождает ресурсы достаточно эффективно, чтобы помешать многим асинхронным функциям использовать их все. Я не храню ссылки на какие-либо объекты, созданные во вр…
14 мар '16 в 08:26
2
ответа
Контекстно-зависимый язык с недетерминированной машиной Тьюринга
Как я могу показать, что язык чувствителен к контексту с недетерминированной машиной Тьюринга? я знаю, что язык, который принимается линейно-связанным автоматом (LBA), является контекстно-зависимым языком. А LBA - это недетерминированная машина Тьюр…
30 ноя '11 в 03:24
2
ответа
Пролог: избегайте лишних точек выбора (недетерминизм) с оператором вырезания и без него
Во-первых, я прочитал все другие посты на SO, касающиеся использования разрезов в Прологе, и определенно вижу проблемы, связанные с их использованием. Однако для меня все еще есть некоторая неясность, и я хотел бы решить это раз и навсегда. В привед…
12 июн '16 в 15:16
1
ответ
Недетерминированные градиентные вычисления
Я понял, что мои модели оказываются разными каждый раз, когда я их тренирую, хотя я сохраняю случайное начальное число TensorFlow одинаковым. Я подтвердил, что: Инициализация является детерминированной; веса идентичны до первого обновления. Входные …
23 фев '17 в 10:10