Недетерминированность теории означает что
Детерминированность
Детерминированность (от лат. determinans — определяющий) — определяемость. Детерминированность может подразумевать определяемость на общегносеологическом уровне или для конкретного алгоритма. Под детерминированностью процессов в мире понимается однозначная предопределённость. Является антонимом стохастичности.
Детерминированность в решении какой-либо практической задачи или в алгоритме означает, что способ решения задачи определён однозначно в виде последовательности шагов. На любом шаге не допускаются никакие двусмысленности или неопределённости и независимо от единичных вещей. [источник не указан 261 день]
См. также
Полезное
Смотреть что такое «Детерминированность» в других словарях:
ДЕТЕРМИНИРОВАННОСТЬ — (от лат. determinans – определяющий) определяемость. Общая детерминированность всех совершающихся в мире процессов, включая человеческое мышление, чувствование и волеизъявление, означает не одно и то же, что каузальная детерминированность (см.… … Философская энциклопедия
детерминированность — определённость, ясность, конкретность, чёткость, точность; определенность, обусловленность. Ant. неопределённость Словарь русских синонимов. детерминированность сущ., кол во синонимов: 3 • обусловленность … Словарь синонимов
Детерминированность — ж. Обусловленность, предопределённость. Толковый словарь Ефремовой. Т. Ф. Ефремова. 2000 … Современный толковый словарь русского языка Ефремовой
детерминированность — недетерминированность … Словарь антонимов
Детерминированность — (от лат. determinans определяющий) определяемость … Начала современного естествознания
детерминированность — детермин ированность, и … Русский орфографический словарь
детерминированность — Syn: определенность, ясность, конкретность, четкость, точность Ant: неопределенность … Тезаурус русской деловой лексики
Детерминированность (теория игр) — В теории игр детерминированность существование выигрышной стратегии для одного из игроков. То есть алгоритм, следуя которому один (и только один) из игроков неизбежно выигрывает. Литература Йех, Т. (англ.) Теория множеств (издание третьего… … Википедия
детерминированность тканей — см. Детерминация тканевая … Большой медицинский словарь
недетерминированность — детерминированность конкретность … Словарь антонимов
Детерминированность против недетерминированности
Во многих случаях лишь тонкая грань отделяет детерминированные алгоритмы от недетерминированных. Но различие между ними достаточно очевидно и существенно. Детерминированный алгоритм не надеется на творческие способности механизма, выполняющего алгоритм, тогда как для недетерминированного «алгоритма» они могут быть достаточно важны. Например, сравните команды
Дойдите до следующего перекрестка и поверните направо или налево. и
Дойдите до следующего перекрестка и поверните направо или налево в зависимости от того, что скажет вам человек, стоящий на углу.
В обоих случаях действие, которое выполнит инструктируемый, не определено до начала выполнения команды. Однако первая команда требует от человека последовать направлению, выбранному им самостоятельно, то есть это недетерминированная инструкция. Вторая команда не предъявляет подобных требований к человеку — он получает инструкции на каждом шаге. Если первую команду выполнят несколько человек, то некоторые из них повернут направо, а другие — налево. Если несколько человек выполнят вторую команду и получат одинаковую информацию, то все повернут в одном направлении. В этом и заключается важное различие между детерминированными и недетерминированными «алгоритмами». Если детерминированный алгоритм выполнять несколько раз с одинаковыми входными данными, то выполненные действия всегда будут одинаковыми. В то же время недетерминированный алгоритм в одних и тех же условиях может привести к получению различных результатов.
Задача, которая может быть решена за полиномиальное время при помощи недетерминированного алгоритма, называется недетерминированной полиномиальной задачей (nondeterministic polynomial problem), или NP-задачей. Класс NP-задач обозначается NP. Обратите внимание, что все задачи из Р также принадлежат NP, так как к любому (детерминированному) алгоритму можно добавить недетерминированную комайду, не влияющую на работу алгоритма.
Ответа на вопрос, все ли NP-задачи находятся в Р, пока что нет, что демонстрирует нам задача коммивояжера. Возможно, это самая известная нерешенная задача вычислительной техники на сегодняшний день. Ее решение могло бы иметь значительные последствия. Например, в следующем разделе мы узнаем, что существуют системы шифрования, целостность которых зависит от огромного количества времени, необходимого для решения задач, схожих с задачей коммивояжера. Если окажется, что эффективные решения подобных задач существуют, такие системы шифрования будут подвергнуты риску.
Усилия по поиску ответа на вопрос, совпадает ли класс NP с классом Р, привели к обнаружению в классе NP нового класса задач, известного как NP-полные задачи (NP-complete problem). У этих проблем есть общее свойство, которое заключается в том, что решение с полиномиальным временем любой из них обеспечило бы решение с полиномиальным временем для всех остальных NP-задач. То есть, если найдется (детерминированный) алгоритм для решения одной из NP-полных задач в полиномиальное время, то этот алгоритм можно было бы расширить для решения всех остальных задач из NP в полиномиальное время. Следовательно, было бы доказано, что класс NP совпадает с классом Р. Задача коммивояжера является одной из NP-полных задач.
Подведем итог. Мы обнаружили, что задачи могут быть разрешимыми (имеющими алгоритмическое решение) и неразрешимыми (для которых нет алгоритмического решения), что показано на рис. 11.7. Более того, в классе разрешимых задач есть два подкласса. Первый — это набор полиномиальных задач, то есть задач, имеющих практическое решение. Второй представляет собой не полиномиальные задачи, практическое решение для которых может быть найдено только для относительно небольших и тщательно отобранных входов. И в заключение, существуют загадочные NP-задачи, не поддающиеся точной классификации.
ДЕТЕРМИНИРОВАННОСТЬ
Смотреть что такое «ДЕТЕРМИНИРОВАННОСТЬ» в других словарях:
детерминированность — определённость, ясность, конкретность, чёткость, точность; определенность, обусловленность. Ant. неопределённость Словарь русских синонимов. детерминированность сущ., кол во синонимов: 3 • обусловленность … Словарь синонимов
Детерминированность — Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии. Детерминированность (от лат. determinans опре … Википедия
Детерминированность — ж. Обусловленность, предопределённость. Толковый словарь Ефремовой. Т. Ф. Ефремова. 2000 … Современный толковый словарь русского языка Ефремовой
детерминированность — недетерминированность … Словарь антонимов
Детерминированность — (от лат. determinans определяющий) определяемость … Начала современного естествознания
детерминированность — детермин ированность, и … Русский орфографический словарь
детерминированность — Syn: определенность, ясность, конкретность, четкость, точность Ant: неопределенность … Тезаурус русской деловой лексики
Детерминированность (теория игр) — В теории игр детерминированность существование выигрышной стратегии для одного из игроков. То есть алгоритм, следуя которому один (и только один) из игроков неизбежно выигрывает. Литература Йех, Т. (англ.) Теория множеств (издание третьего… … Википедия
детерминированность тканей — см. Детерминация тканевая … Большой медицинский словарь
недетерминированность — детерминированность конкретность … Словарь антонимов
Теория вычислений. Введение в конечные автоматы
Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рассуждения и легкость программной или аппаратной реализации.
С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.
У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.
Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.
Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.
Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.
Стартовое состояние — состояние откуда КА начинает свою работу.
Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
Детерминированные конечные автоматы (deterministic finite automaton)
Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.
Детерминированность — для всех состояний имеется максимум и минимум одно правило для любого возможного входного символа, то есть например, для состояния 1 не может быть два перехода с одним и тем же входным символом.
Недетерминированные конечные автоматы (nondeterministic finite automaton)
НКА не является каким-то существенным улучшением ДКА, просто в нем добавлен так сказать синтаксический сахар, в виде свободных переходов, недетерминированности и множеств состояний. Реализовать можно как массив состоящий из структур в которой хранится состояние, входной символ и следующее состояние.
Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.
Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.
Множества состояний — в один момент времени НКА может находится в нескольких состояниях.
Заключительное состояние обозначается двойным кругом.
В стартовом состоянии у нас текущим состоянием является <1>, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество <1, 2>.
Свободным переходом обозначается пунктирной линией.
Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии <2, 4>.
Для преобразования НКА в ДКА используется алгоритм Томпсона.
При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.
Конечные автоматы с магазинной памятью (pushdown automaton)
Это тот же КА, но с дополнительной памятью в виде стека. Теперь для совершения перехода нужно учитывать еще несколько факторов, символ который нужно удалить из стека и символы которые нужно добавить в стек.
КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стека (я понимаю, что память тоже конечна).
Удаление символа из стека — при любом переходе решается какой символ вытолкнуть, если на вершине стека не оказалось такого символа, то он и не выталкивается. Так же если символ нужно оставить в стеке, то он добавляется вместе с добавляемыми символами.
Добавление символов в стек — при любом переходе решает какие символы добавить в стек.
Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.
ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.
Машина Тьюринга (Turing machine)
Самая мощная машина из существующих, его преимущество перед другими в ленте с которой он может работать как хочет. В нем нет свободных переходов. Умеет интерпретировать другие автоматы такие как КА, КАМП.
Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.
Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.
Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.
ДМТ эквивалентен НМТ, так, что они тоже не различаются.
Универсальная машина Тьюринга (universal Turing machine)
Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.
ДЕТЕРМИНИРОВАННОСТЬ
Смотреть что такое ДЕТЕРМИНИРОВАННОСТЬ в других словарях:
ДЕТЕРМИНИРОВАННОСТЬ
детерминированность ж. Обусловленность, предопределенность.
ДЕТЕРМИНИРОВАННОСТЬ
ДЕТЕРМИНИРОВАННОСТЬ
Вертер Верстание Верста Верона Верньер Верность Верно Вернер Верна Вермонт Верист Верес Верентин Веред Верди Верден Верд Вера Вентерь Вента Вено Вениамин Венет Венерн Венерин Венера Венед Вендит Вендетта Венд Вена Веер Ведьмин Ведьма Ведро Ведренность Ведомость Ведомо Ведин Веди Веденность Ведание Веда Вдеть Вдетость Ватт Ватин Ватер Варьете Вариометр Варин Варимость Вариетет Варение Вард Вар Вано Вандемьер Ваер Вадим Вади Вад Атто Атомность Атом Атм Атень Атеист Асьенто Асьенд Астроним Астрон Астро Астр Астерометр Астероид Асиндетон Асидерит Асеев Артрон Артрит Артос Артист Артериит Артемьев Артемон Артем Арт Арсин Арсеньев Арсенит Арсенид Арсен Арон Арно Арменист Аристон Аристид Арион Арин Арест Ареометр Арен Аредов Ардометр Арден Аортит Аорист Аоот Аон Антонов Антоно Антонио Антонин Антоним Антонид Антон Антисемит Антимонит Антимонид Антимир Антиминс Антидот Антидор Анти Ант Анри Анортит Анонс Анонимность Анонимно Аноним Анон Анод Аннот Анисимов Анисим Анис Анионит Анион Анин Анимист Аним Анид Анероид Анемон Аневрин Андростерон Андрон Андрис Андреев Андре Андерсен Амьен Амт Амосов Амон Амниот Амнион Аминодонт Амин Амид Аметист Амер Амвон Аист Аир Адрон Адрес Адонис Админ Адить Адермин Аденит Аденин Аден Адвентист Автостроение Автор Вертеть Вертодром Вес Автоним Автомедон Автодром Весна Весомо Авто Авт Вест Аврор Авост Вестерн Авист Авиньон Авест Аверс Вести Авенир Авенид Весть Весь Весьма Авдитор Авометр Аврорин Автодин Автодоение Автономист. смотреть
ДЕТЕРМИНИРОВАННОСТЬ
1) Орфографическая запись слова: детерминированность2) Ударение в слове: детермин`ированность3) Деление слова на слоги (перенос слова): детерминированн. смотреть
ДЕТЕРМИНИРОВАННОСТЬ
ДЕТЕРМИНИРОВАННОСТЬ (от лат. determinans – определяющий)определяемость. Общая детерминированность всех совершающихся в мире процессов, включая чело. смотреть
ДЕТЕРМИНИРОВАННОСТЬ
Ударение в слове: детермин`ированностьУдарение падает на букву: иБезударные гласные в слове: детермин`ированность
ДЕТЕРМИНИРОВАННОСТЬ
детермини́рованность ж.determinancy* * *determinancyСинонимы: обусловленность, определенность, предопределенность Антонимы: недетерминированность
ДЕТЕРМИНИРОВАННОСТЬ
(от лат. determinans — определяющий) — определяемость. Начала современного естествознания. Тезаурус. — Ростов-на-Дону.В.Н. Савченко, В.П. Смагин.2006. Синонимы: обусловленность, определенность, предопределенность Антонимы: недетерминированность. смотреть
ДЕТЕРМИНИРОВАННОСТЬ
ДЕТЕРМИНИРОВАННОСТЬ
determinancyСинонимы: обусловленность, определенность, предопределенностьАнтонимы: недетерминированность
ДЕТЕРМИНИРОВАННОСТЬ
недетерминированностьСинонимы: обусловленность, определенность, предопределенность Антонимы: недетерминированность
ДЕТЕРМИНИРОВАННОСТЬ
确定性决定性Синонимы: обусловленность, определенность, предопределенность Антонимы: недетерминированность
ДЕТЕРМИНИРОВАННОСТЬ
ДЕТЕРМИНИРОВАННОСТЬ
ДЕТЕРМИНИРОВАННОСТЬ
детерминированность определённость, ясность, конкретность, чёткость, точность, определенность, обусловленность. Ant. неопределённость