Cтраница 2
С другой стороны, помимо проблемы однозначности результата недетерминизм влечет за собой ряд других побочных проявлений, влияющих на эффективность вычислений. Так, например, при программировании с помощью системы MPI некоторые процессы могут сколь угодно долго находиться в ожидании приема сообщения от передающего процесса, если существует какой-либо другой процесс, постоянно посылающий вызовы MPI Recv тому же процессу-отправителю. [16]
Таким образом, если реализация языка программирования допускает внутренний недетерминизм процессов, обеспечивая их однозначность и непрерывность, то денотационная семантика, являющаяся частью определения языка, точно специфицирует, что является результатом вычисления. [17]
Наконец, существует еще один довод в пользу недетерминизма. Недетерминизм обобщает детерминизм и поэтому представляет интерес как более широкая модель алгоритмов. Это позиция чистого доа-тематика и поэтому многие прагматически настроенные программисты могут этот вывод не принимать. [18]
Так, CSP описывает поведение последовательных недетерминированных процессов, причем недетерминизм означает произвольное независимое чередование процессов. [19]
При описании функционирования сетей Петри ( глава 1) отмечался недетерминизм следующего рода: если i есколько переходов могут сработать, то срабатывает любой из них. В реальных дискретных системах имеют место ситуации, когда из двух готовых работать устройств требуется запустить сначала одно, например, первое, а затем второе. Другими словами, одно из устройств имеет приоритет на запуск перед другим в том случае, если оба готовы работать. [20]
Итак, полагаем, что приведено достаточно доводов в пользу недетерминизма как методологического средства прикладной теории алгоритмов. [21]
Однако здесь рассматривается проблема внешнего по отношению к сети процессов недетерминизма и нет строгого определения операционной семантики. В [71] показано, что недетерминизм процессов может приводить к потере свойства непрерывности вычислений, когда уже неприменима теорема о наименьшей неподвижной точке или аналогичная ей теорема Кнастера-Тарского. Сохранение при этом свойства монотонности процессов не дает конструктивного приема для отыскания наименьшей неподвижной точки вычислений. [22]
Как видно из предыдущего материала, соотношение между детерминизмом и недетерминизмом является весьма сложным. Недетерминизм выступает как удобное выразительное средство, но требует тщательного рассмотрения в вопросах реализации. Дейкстры позволяют управлять недетерминированным выбором. [23]
В значительной мере гибкость и мощь процедуры вывода является следствием ее недетерминизма, так как на каждом шаге алгоритма может быть выбрана любая связь для резольвирования. [24]
При практическом осуществлении систем управления недетерминированными объектами функции устранения влияния их недетерминизма на процесс управления обычно выполняют специальные технические устройст - ва - автоматические регуляторы, которые совместно с объектом, режим работы которого они регулируют, образуют, автоматическую систему регулирования. [25]
В теории вероятностей рассматриваются события или объекты, неопределенность характеристик которых связана с их недетерминизмом, с их случайным изменением. Очевидно, что здесь понятия детерминированного и недетерминированного объектов требуют уточнения, и насколько можно судить, существующие формальные построения в теории нечетных множеств и теории вероятностей не позволяют этого сделать сколько-нибудь точно. Требует уточнения понятие неопределенной части детерминированного объекта - почему объект с неопределенной частью может вообще называться детерминированным. [26]
Итак, мы рассмотрели модель распределенных вычислений, существенным отличием которой от известных моделей является сочетание недетерминизма процессов и асинхронного обмена разнородными сообщениями. Теорема 2.1 обосновывает достаточное условие однозначности вычислений. Операционная и детонационная семантика модели согласованы. [27]
Следует отметить, что при реализации протокола по формальному описанию стандарта разработчик должен тщательно проанализировать все случаи недетерминизма и в зависимости от конкретных условий оставить его или устранить. Естественно, что в тех случаях, когда недетерминизм нежелателен, рассмотренная модель позволяет спе-цифировать строго детерминированные протокольные автоматы. [28]
Множество, задаваемое порождающим процессом, считается эффективно заданным множеством, так как возможность осуществить любой выбор в точках недетерминизма по соглашению при-внается бесспорной. [29]
Итак, внутренний недетерминизм однозначных процессов ( см. определения 2.2 и 2.3) может не нарушать свойства непрерывности процессов, в отличие от недетерминизма внешнего. Внешний недетерминизм проявляется в том, что последовательность выходных сообщений не определяется однозначно последовательностью входных сообщений. Иными словами, процессы вычислений не являются однозначными. Применительно к сетям процессов Кана [113, 123], например, внешний недетерминизм означает, что истории внутренних и выходных каналов сети не полностью определяются историями входных каналов. [30]