Недетермінізм - Велика Енциклопедія Нафти та Газа, стаття, сторінка 1
Недетермінізм
Недетермінізм природним шляхом проявляється при дослідженні та аналізі алгоритмів, а також при завданні класів алгоритмів. [1]
Недетермінізм можна усунути з допомогою накладання порядку вибору цілей. У будь-якому випадку, всі результати, знайдені недетерміновано, можуть бути виявлені за допомогою вичерпного впорядкованого пошуку. [2]
Поняття недетермінізму відіграє важливу роль у визначенні обчислювальної складності алгоритмів (С. Тьюринга здатна завершити за прийнятний час такі розрахунки, які не можуть бути реалізовані так само швидко ніякою детермінованою машиною Тьюринга. [3]
Отже, недетермінізм обчислювального процесу означає, що будь-якій парі, що складається з вхідного та вихідного повідомлень, може відповідати більше однієї історії виконання програми. Недетермінізм процесів зумовлює різноманітні послідовності формування компонентів повідомлення. Тим самим забезпечується динамічний механізм породження процесів готовності вхідних даних, а кількість процесів, пов'язане з виконанням конкретної програми, у випадку не обмежується. Основні питання, що при цьому виникають, полягають у наступному. [4]
Отже, внутрішній недетермінізм однозначних процесів (див. визначення 2.2 і 2.3) може порушувати властивості безперервності процесів, на відміну зовнішнього недетермінізму. Зовнішній недетермінізм проявляється у тому, що послідовність вихідних повідомлень однозначно не визначається послідовністю вхідних повідомлень. Інакше кажучи, процеси обчислень є однозначними. Стосовно мереж процесів Кана [113, 123], наприклад, зовнішній недетермінізм означає, що історії внутрішніх та вихідних каналів мережі не повністю визначаютьсяісторіями вхідних каналів [5]
Завдяки силі недетермінізму приналежність даної задачі класу (№ 3 зазвичай доводиться легко. Приклади 10.3 і 10.4 є типовими ілюстраціями цього кроку. Труднощі викликає доказ того, що будь-яке завдання з fS поліноміально трансформується в дане завдання. [6]
У Пролозі цей недетермінізм реалізовано з допомогою механізму повернень. [8]
Розглянемо позитивні сторони недетермінізму. [9]
Пояснимо зв'язок проблем недетермінізму та блокування обчислень на таких прикладах. Дуги а, 6, с, d відповідають передачі токенів. [11]
Це демонструє силу недетермінізму, бо всі підмножини з вузлів перевіряються паралельно незалежними екземплярами розпізнаючого пристрою. [12]
З одного боку, підтримка недетермінізму є цінною властивістю моделей обчислень та систем програмування. [13]
Мережі Петрі дозволяють моделювати асинхронність і недетермінізм паралельних незалежних подій, паралелізм конвеєрного типу, конфліктні взаємодії між процесами. [14]
Розглянемо питання про співвідношення між детермінізмом та недетермінізмом у класі кінцевих автоматів. [15]