Детерминированные и недетерминированные алгоритмы реферат

Обновлено: 06.07.2024

Delphi site: daily Delphi-news, documentation, articles, review, interview, computer humor.

Теперь, когда мы рассмотрели несколько достаточно сложных конечных автоматов и ближе познакомились с ними, следует ознакомиться с рядом новых терминов. Первый из них - автомат (automaton или, в просторечии, automata). Это всего лишь еще одно название машины состояний, которое используется исключительно в учебных курсах и учебниках по компьютерным наукам. Конечный автомат (он же и конечная машина состояний) - это всего лишь машина состояний, количество состояний которой не бесконечно. Оба приведенные ранее примера представляли конечные автоматы: в первом имелось три состояния, во втором -пять.

И еще один новый термин - детерминированный (deterministic). Взгляните на конечный автомат, представленный на рис. 10.2. Независимо от текущего состояния и от того, каким будет следующий символ, точно известно, в какое состояние должен быть выполнен переход. Все переходы полностью определены. Этот конечный автомат является детерминированным. В процессе его работы не требуется делать какие-либо предположения или осуществлять выбор. Например, если бы двойная кавычка была получена во время нахождения в состоянии FieldStart, потребовалось бы выполнить переход в состояние ScanQuoted.

Рисунки 10.1 и 10.2 служат примерами детерминированных конечных машин состояний (deterministic finite state machines - DFSM), или детерминированных конечных автоматов (deterministic finite automata - DFA). Противоположными им являются конечные автоматы, в ряде состояниях которых требуется осуществлять какой-либо выбор. При использовании конечного автомата этого типа приходится решать, нужно ли для данного конкретного символа выполнять переход в состояние X или в состояние Y. Как можно догадаться, реализация конечного автомата такого вида требует несколько более сложного кода. Не удивительно, что эти конечные автоматы называются недетерминированными конечными машинами состояний (non-deterministic finite state machines - NDFSM), или недетерминированными конечными автоматами (deterministic finite automata - NFA).

Теперь рассмотрим NFA-автомат. На рис. 10.3 показан NFA-автомат, который может преобразовывать строку, содержащую число в десятичном формате, в двоичное значение. При взгляде на этот рисунок у читателей может возникнуть вопрос, что представляют собой переходы, обозначенные странным символом е. Это -бесплатные, или свободные переходы, которые можно выполнить без использования текущего символа или лексемы. Так, например, от начала лексемы А к следующей лексеме В можно перейти, используя знак "+и, знак "-" или просто выполнив это переход (бесплатный переход). Эти свободные переходы - отличительная особенность недетерминированных конечных автоматов.

Рисунок 10.3. ЫРА-автомат для проверки, является ли строка числом

Воспользуемся этим рисунком для проверки таких строк, как "1", "1.23й, "+.7", "-12". Как видите, верхняя ветвь служит для обработки целочисленных значений (не содержащих десятичной точки). Средняя ветвь выполняет обработку строк, которые состоят, по меньшей мере, из одной цифры, предшествующей десятичной точке, но которые могут и не иметь цифр, следующих за точкой. Нижняя ветвь предназначена для обработки строк, которые могут не содержать ни одной цифры перед десятичной точкой, но обязательно должны содержать хотя бы одну цифру после нее. Если немного подумать, становится понятно, что этот конечный автомат не сможет воспринимать самостоятельно вводимую десятичную точку.

Однако одна проблема остается нерешенной: хотя конечный автомат воспримет строку "1.2", как он "узнает", что нужно выполнять среднюю ветвь? Более того, может возникать более принципиальный вопрос: зачем вообще связываться с NFA-автоматом? Весь алгоритм кажется слишком сложным. Поэтому, почему бы не ограничиться применением DFA-автомата?

В действительности на второй вопрос проще ответить, чем на первый. NFA -естественные конечные автоматы для вычисления регулярных выражений. Разобравшись в использовании NFA-автоматов, мы проходим более половины пути к конечной цели этой главы - к возможности сопоставления строки с регулярным выражением.

Вернемся к первому вопросу: откуда NFA-автомат знает, что для строки "1.2" необходимо выполнять среднюю ветвь алгоритма? Естественно, автомат этого не знает. Существует несколько способов обработки строки с помощью подобного конечного автомата. И простейшим для описания является алгоритм проб и ошибок. В качестве вспомогательного мы используем еще один алгоритм - алгоритм с отходом (backtracking algorithm).

Обратите внимание, что нас интересует определение только одного пути конечного автомата, воспринимающего строку. Могут существовать и другие, но перечисление их всех интереса для нас не представляет.

Посмотрим, как работает этот алгоритм, проследив, что происходит при попытке ввода строки "12.34".

Работа алгоритма начинается с состояния А. Первой лексемой является "1". Мы не можем выполнить ни переход "+" в состояние В, ни переход "-". Поэтому мы выполняем свободный переход (связь е). В результате автомат оказывается в состоянии В с той же лексемой "1". Теперь у нас имеются две возможности: выполнить переход в состояние С или в состояние D, поглощая при этом лексему. Выберем первую возможность. Прежде чем выполнить переход, отметим, что именно мы собираемся сделать, чтобы в случае неудачи не повторять ошибку. Итак, мы выполняем переход в состояние С, поглощая при этом лексему. Мы получаем вторую лексему, "2". Пока все достаточно просто. Автомат остается в том же состоянии и использует лексему.

При преобразовании этого конечного автомата в код потребуется решить несколько проблем.

Во-первых, мы больше не располагаем простым циклом For для циклической обработки символов в строке. В случае применения детерминированного автомата каждый считываемый из входной строки символ вызывал переход (даже если это переход в то же самое состояние) и отсутствовала какая-либо возможность отхода или возврата к уже посещенному символу. В случае применения недетерминированного конечного автомата мы заменяем цикл For циклом While и при необходимости обеспечиваем увеличение переменной индекса строки.

Во-вторых, в некоторых состояниях мы не можем использовать применительно к входному символу простой оператор Case или If. Нам приходится иметь дело с множеством "вариантов перехода". Некоторые из них будут немедленно отбрасываться, поскольку текущий символ не соответствует условию перехода. Другие будут приняты, причем некоторые из них будут отброшены на более позднем этапе, а какой-то вариант будет использован. А пока просто пронумеруем возможные переходы и поочередно их выполним. Для этого будем использовать целочисленную переменную.

Теперь нужно рассмотреть последний фрагмент кода: реализацию собственно алгоритма с отходом. При каждом выборе допустимого перехода (сравните его с отбрасыванием перехода из-за того, что текущий символ не соответствует условиям перехода) необходимо сохранить информацию о конкретном выполненном переходе. Тогда, при необходимости выполнить отход к тому же состоянию с тем же самым входным символом, можно легко выбрать следующий переход и проверить его. Конечно, выбор вариантов переходов может требоваться в любом состоянии. Поэтому нужно записать их все, чтобы их можно было выполнить в обратном порядке. Отход выполняется в состояние, предшествовавшее последнему сделанному выбору. Иначе говоря, следует воспользоваться структурой типа "последним вошел, первым вышел", т.е. стеком. Применим один из стеков, которые были реализованы в главе 3.

Что же нужно сохранять в стеке? Разумеется, в нем необходимо сохранять состояние, в котором был сделан выбор, номер выполненного перехода (чтобы для проверки можно было выбрать следующий переход) и, наконец, индекс символа, для которого был осуществлен выбор. Используя эти три информационных элемента, можно легко вернуть конечный автомат к предшествующему состоянию, чтобы можно было выбрать следующий, и, возможно, более удачный вариант перехода.

Код реализации NFA-автомата для анализа десятичных чисел приведен в листинге 10.3. Этот конечный автомат будет поглощать строку в момент, когда строка исчерпана, а автомат находится в конечном состоянии. Автомат не примет строку, если строка исчерпана, а состояние отличается от конечного, или если в данном состоянии текущий символ не удовлетворяет условиям перехода. Во второй ситуации должно выполняться также следующее условие: стек отхода должен быть пуст.

Листинг 10.3. Проверка того, что строка является числом, с помощью NFA-автомата

Исходный код подпрограммы 18Уа11оЯшЬег11ЕА можно найти на \¥еЬ-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.pas.

Из листинга 10.3 видно, что базовая структура кода реализации всех состояний одинакова. Предполагается, что для каждого состояния существует ряд переходов, начиная с 0 (на рис. 10.3 переходы пронумерованы по ходу часовой стрелки). Для каждого состояния поочередно выполняется проверка возможности выполнения каждого из переходов. Если переход можно выполнить, сделанный выбор заталкивается в стек, после чего переход выполняется. Если переход невозможен, предпринимается попытка выполнения следующего перехода.

Если нужно осуществить отход, мы выталкиваем верхний выбор из стека и проверяем возможность выполнения следующего перехода. Хранящаяся в стеке информация достаточна для восстановления состояния подпрограммы, существовавшего в момент выбора.

Для сравнения на рис. 10.4 показана блок-схема детерминированного автомата, который выполняет эту же проверку, а код, реализующий его, приведен в листинге 10.4.

Рисунок 10.4. DFA-автомат для проверки, является ли строка числом

Листинг 10.4: Проверка того, что строка является числом, с помощью DFA-автомата

Исходный код подпрограммы IsValidNumber можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.

Ели сравнить коды, приведенные в листингах 10.3 и 10.4, невозможно не заметить, что код NFA-автомата значительно сложнее. Он содержит целый набор вспомогательных подпрограмм, которые необходимо закодировать и поддерживать. Он также более чреват ошибками (необходимо побеспокоиться о поддержке стека, о возврате конечного автомата к предшествующему состоянию, о выборе следующего перехода и т.п.).

В общем случае, если требуется фиксированный, заранее определенный автомат, следует попытаться разработать и использовать детерминированный автомат. Следует попытаться свести реализацию недетерминированных автоматов к автоматическим алгоритмам. Реализация их вручную - чересчур трудоемкая задача.

Конечно, в рассмотренном примере NFA-автомат (и в примере его аналога DFA-автомата) мы всего лишь проверяем, является ли строка текстовым описанием целого числа или числа с плавающей точкой. Обычно желательно также вычислить интересующее число, а это усложняет код реализации переходов. Реализация этой функции при использовании DFA-автомата достаточно проста. Мы устанавливаем значение аккумуляторной (накопительной) переменной равным 0. При декодировании каждой цифры, расположенной перед десятичной точкой, мы умножаем значение аккумуляторной переменной на 10.0 и добавляем к нему значение новой цифры. Для цифр, следующих за десятичной точкой, мы поддерживаем значение счетчика текущего десятичного разряда и увеличиваем его на единицу при считывании каждой цифры. Для каждой такой цифры мы добавляем ее значение, умноженное на 0.1 в степени, соответствующей достигнутой десятичной позиции.

А как насчет NFA-автомата? Что ж, в этом случае решить задачу достаточно трудно. Вся сложность обусловлена необходимостью реализации алгоритма отхода. В любой момент времени внезапно может оказаться, что необходимо вернуться к предыдущему состоянию. В примере преобразования строки в число с плавающей точкой это не очень страшно: при заталкивании выбора в стек достаточно сохранить в нем и текущее значение аккумуляторной переменной (и значения всех необходимых дополнительных переменных). При выполнении отхода в качестве данных для восстановления состояния в момент неудачного выбора мы вытолкнем из стека и значение накопительной переменной.

Подробный и доступный доклад о детерминированных и недетерминированных автоматах. Приведены примеры и определения.

Арбиб М.А. Алгебраическая теория автоматов, языков и полугрупп

формат djvu
размер 3.6 МБ
добавлен 10 ноября 2010 г.

Издательство: Статистика, 1975, 335 c. Монография посвящена рассмотрению математического аппарата количественного и качественного анализа АСУ. Конечные автоматы благодаря их простой реализуемости на ЭВМ имеют значительные преимущества по сравнению с другими моделями. Авторы знакомят читателей с основными достижениями в этой области. Книга рассчитана на разработчиков АСУ и цифровых средств вычислительной техники, на математиков, работающих в обл.

Брауэр В. Введение в теорию конечных автоматов

формат djvu
размер 11.68 МБ
добавлен 23 сентября 2010 г.

М.: Радио и связь, 1987. 392 с. В книге профессора Гамбургского университета описаны основные классические модели теории конечных автоматов (автоматы Мили и Мура) и более сложные модели (автоматы Рабина — Скотта, многоленточные автоматы, конечные преобразователи). Рассмотрены преобразования конечных автоматов и регулярные множества. Существенную часть книги составляют упражнения.

Гинзбург Сеймур. Математическая теория контекстно-свободных языков

формат djvu
размер 3.64 МБ
добавлен 15 октября 2011 г.

Москва, "Мир", 1970-326 стр. Перевод с английского В книге достаточно полно изложены основные понятия и результаты теории контекстно-свободных грамматик и языков, прослеживаются ее связи с теорией автоматов, языками программирования, лингвистикой и машинным переводом. Имеется большое число упражнений самой различной трудности, которые в совокупности существенно дополняют основной текст книги. Книга окажется полезной математику, желающему ознакоми.

Дехтярь М.И. Конечные автоматы (Лекции по дискретной математике)

формат pdf
размер 475.64 КБ
добавлен 06 ноября 2010 г.

Содержание Переработка информации с помощью конечных автоматов Конечные автоматы распознаватели Детерминированные конечные автоматы (ДКА) и автоматные языки Произведение автоматов Недетерминированные конечные автоматы и их детерминизация Регулярные выражения и языки Регулярные языки и конечные автоматы Автоматы для регулярных языков Свойства замкнутости класса автоматных языков Теорема о разрастании автоматных языков. Неавтоматные языки

Карпов Ю.Г. Теория автоматов

формат djvu
размер 1.93 МБ
добавлен 18 марта 2010 г.

СПб.: Питер, 2003. - 208 с., ил. В книге рассматриваются: Конечные функциональные преобразователи (булевы функции, функциональная полнота); Введение в математическую логику (формальные модели, логика высказываний, логическое следствие, основы логики предикатов и логического вывода, логическое программирование); Конечные автоматы (автоматное преобразование информации, примеры КА, графы переходов, алгебраическая структурная теория КА); Автоматн.

Карпов Ю.Г. Теория автоматов

формат exe
размер 8.96 МБ
добавлен 09 августа 2008 г.

Конечные функциональные преобразователи.Булевы функции. Функциональная полнота.Формы представления булевых функций. Введение в математическую логику.Формальные высказывания. Логика высказываний.Логическое следствие.Основы логики предикатов и логического вывода.Логическое программирование Конечные автоматы.Автоматное преобразование информации.Примеры КА.Визуальный формализм представления моделей реактивных систем.Графы переходов при спецификации и.

Кокин А.Г., Кузнецов В.Н. Конечные автоматы: языки и грамматики

формат doc
размер 102.1 КБ
добавлен 05 января 2012 г.

Пентус А.Е., Пентус М.Р. Теория формальных языков

формат pdf
размер 539.73 КБ
добавлен 10 февраля 2010 г.

М.: Издательство ЦПИ при механико-математическом факультете МГУ, 2004. - 80 с. Учебное пособие посвящено классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, классификация формальных языков по Хомскому, регулярные выражения, конечные автоматы, автоматы с магазинной памятью, алгоритмические проблемы, связанные с контекстно-свободными грамматиками. Для студе.

Постников А.И., Вейсов Е.А. Теория автоматов и машинная арифметика

формат doc
размер 5.79 МБ
добавлен 23 сентября 2010 г.

Учебное пособие, ИПЦ КГТУ 2006 г. Информация и вычислительные машины. Системы счисления. Основы алгебры логики. Минимизация ФАЛ. Основные электронные узлы комбинационного типа. Основы теории автоматов. Типовые узлы ЦВМ на основе триггеров. Микропрограммные автоматы. Управляющие автоматы с программируемой логикой. Операционный автомат. Сложение двоичных чисел. Умножение двоичных чисел. Деление двоичных чисел. Ускорение выполнения арифметических о.

Салий В.Н. Универсальная алгебра и автоматы

формат pdf
размер 38.07 МБ
добавлен 25 января 2012 г.

Учебное пособие, 1988 г., 73 стр. Саратовский государственный университет. ISBN 5-292-00263-1 В пособии излагаются основные понятия и результаты теории конечных автоматов без выхода, связанные с универсально-алгебраическими конструкциями. Представление об автомате без выхода как о конечной унарной алгебре позволяет применить в теории автоматов хорошо разработанные универсально-алгебраические средства, придать установленным с их помощью фактам ес.

ГОСТ

Алгоритмы и способы их разработки

Дискретная математика – это область науки, в которой рассматриваются разнообразные задачи с дискретными (не являющимися непрерывными) данными, исследуются методы решения таких задач и изучаются наиболее оптимальные алгоритмы поиска этих решений.

В связи с современными условиями, связанными с развитием вычислительной техники, появились возможности по программированию разнообразных алгоритмов, которые используются при решении огромного количества прикладных задач.

Несмотря на то, что не существует универсального подхода к составлению алгоритмов, полезно знать некоторые общие принципы и способы, которые используются при разработке любых алгоритмов, применяемых для эффективного решения различных задач.

Наиболее распространённым методом является системный подход, основанный на принципах декомпозиции (нисходящего проектирования) и синтеза (восходящего проектирования).

При нисходящем проектировании происходит процесс пошагового разделения исходной задачи на целый ряд более мелких подзадач, для которых достаточно применять более простые технологии решения. В итоге, в результате повторения данного процесса нужное количество раз, будут получены подзадачи, решаемые с помощью элементарных команд.

При восходящем проектировании, наоборот, сначала разрабатываются элементарные конструкции, на основе которых формируются подзадачи более общего назначения, представляющие собой функционально завершённые элементы. Далее, опираясь на них, аналогичным образом создаются ещё более общие подзадачи, и данный процесс продолжается до тех пор, пока не будет получен уровень, на котором решается исходная задача. Такой принцип синтеза используется в модульном программировании, технология которого основывается на максимальном использовании различных стандартных функций, процедур и других специализированных программных продуктов.

Готовые работы на аналогичную тему

Также при проектировании алгоритмов применяются методы дедукции (переход от общего знания к частному) и индукции (переход от известных частных фактов к общему выводу).

Ещё для составления алгоритмов при решении сложных вычислительных задач и задач, связанных с обработкой данных, принято использовать такие способы организации вычислительного процесса, как итерация и рекурсия.

Особенностью итерации и рекурсии является их взаимозаменяемость. То есть для решения задач, в которых требуется применение рекурсии (например, вычисление факториала), можно составить алгоритм, использующий несколько итераций, и, наоборот, от итерационной задачи вернуться к рекурсивному алгоритму.

Основные методы построения алгоритмов

В дискретной математике существует целый ряд алгоритмов, позволяющих эффективно решать те или иные прикладные задачи, относящиеся к самым разнообразным классам. Причём даже для однотипных задач зачастую есть сразу несколько вариантов алгоритмов, применяемых для поиска их решения.

Рассмотрим наиболее важные методы, на основе которых создавались многие распространённые алгоритмы дискретной математики.

Метод декомпозиции (частных целей).

Несмотря на то, что не существует каких-либо чётких правил для определения класса задач, которые можно было бы решить с помощью этого метода, именно такой подход в алгоритмизации является наиболее распространённым, составляя основу всего программирования. Данный принцип позволяет применять уже полученные в некоторой задаче решения для дальнейшего поиска ответа в какой-то другой, схожей с ней, задаче.

Метод подъёма (от начального предположения).

Этот метод не всегда является эффективным, так как при его использовании невозможно быть уверенным, что найденное в задаче решение будет оптимальным.

Метод отрабатывания назад.

Здесь предполагается, что решение задачи уже известно, и весь метод заключается в том, что последовательно определяются условия, при которых такое решение может быть получено.

Метод динамического программирования.

С помощью этого метода можно решать достаточно сложные задачи, комбинируя решения различных вспомогательных подзадач. И в отличие от метода декомпозиции, где исходная задача разделяется на независимые подзадачи, здесь подзадачи могут перекрываться. При этом каждая подзадача решается только один раз, после чего её ответ сохраняется и может быть использован в последующем решении.

Для них характерно то, что на каждом отдельном шаге решения задачи выбирается тот вариант, который в данный момент является локально оптимальным, соответствуя всем предъявляемым к нему по условию задачи требованиям. Такие алгоритмы позволяют получать эффективные решения, но не подходят для любого класса задач.

Метод поиска с возвратом (отбрасывания назад).

Данный метод предполагает максимально возможное углубление по ветви исследуемого решения, а затем обратный возврат и попытку сделать какой-то другой выбор на ближайшем шаге алгоритма, где это допустимо. Такой подход позволяет решать задачи, в которых просматриваются все возможные варианты в поиске среди них оптимального решения.

Детерминированные и недетерминированные алгоритмы

Все алгоритмы можно разделить на две большие группы:

детерминированные (определённые) алгоритмы;
недетерминированные (неопределённые) алгоритмы.

Говорят, что задача имеет детерминированный метод решения, если она решается прямым способом. Любой детерминированный алгоритм всегда позволяет найти регулярное решение и характеризуется очень чёткой определённостью на каждом своём шаге, а также недопустимостью применения методов проб и ошибок.

Если же решение задачи не может быть получено прямым методом и его приходится выбирать из множества различных вариантов, то в этом случае говорят о недетерминированном методе решения. Такой недетерминированный алгоритм предполагает систематический подход в поиске нужного решения среди всех возможных и основывается на методе проб и ошибок, допуская в своей реализации многократные повторы и случайный выбор. И, несмотря на то, что обычно поиск решения задачи таким способом оказывается достаточно сложным, проверку полученного в ходе выполнения алгоритма решения будет легко выполнить.

Теперь приведём примеры различных задач, для которых применяется тот или иной метод решения. Так, детерминированные алгоритмы применяются при решении математических уравнений, в задачах о проверке данных и во многих других задачах. Недетерминированные алгоритмы позволяют, например, определить все делители заданного числа, найти нужное слово (или строку) в некотором тексте, а также используются при решении известной задачи коммивояжера.

При поиске алгоритма для решения какой-либо задачи обычно рекомендуется выбирать детерминированные алгоритмы (если они вообще возможны и применимы в данной ситуации), так как именно они являются наиболее эффективными.

Столкнулся с тем, что качество определений википедии оставляет желать лучшего. Да, текста там много, но при этом формализация не является полной и точной. Остальная часть рунета пуста, в буквальном смысле. Все что есть, сотни сайтов копи-пасты с той же википедии. Поиск по книгам, посвященным программированию и алгоритмам (в частности) тоже не дал результатов. Определений либо вообще нет, либо приводятся отрывочно, либо качество перевода и работа редактора настолько запредельная, что сложно уловить смысл.

Если можете сформулировать лучше, дайте свои определения для детерминированного и недетерминированного алгоритма (стохастический, уже имеет максимально полное и при этом не большое, но понятное определение).

К разветвляющимся алгоритмам можно отнести:

Алгоритм, поведение которого полностью зависит от входных данных, называют детерминированным |deterministic|. Каждый его шаг заранее предопределен. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Таким образом, обработка одних и тех же входных данных всегда приводит к одинаковому результату.

Алгоритм, поведение которого невозможно предсказать (от чего оно зависит?), называют недетерминированным |nondeterministic|.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Таким образом, обработка одних и тех же входных данных может приводить как к одинаковым, так и к разным результатам.

Алгоритм, поведение которого, помимо входных данных, определяется значениями генератора случайных (псевдослучайных) чисел, называют стохастическим |randomized|

Неужели никто, кроме википедии не в состоянии дать определения этих понятий, которые в принципе, являются фундаментом программирования? Может есть подходящие книги? В общем странно, столько людей получают высшее образование, неужели профессора не дают таких базовых определений своим студентам?

Чем определяется поведение (НА) не понятно - произвольными побочными эффектами, такими, как race condition или скорость прихода пакетов по сети, если не приравнивать это к ГСЧ.

@etki детерминированность и побочные эффекты - это явления разного порядка. Вы же их смешиваете. Если разберётесь в том, что такое "чистота функции" и чистая функция, все станет понятней.

Стохастический - частный случай недетерминированного. Ну, а недетерминированный - например, в котором нет случайных чисел в чистом виде, но есть какая-нибудь многопоточность, которую вы не можете предсказать. Не уверен, но, возможно, сюда можно отнести алгоритм, который, например, зависит от количества доступной памяти.

"Стохастический - частный случай недетерминированного?". Иногда кажется, что это действительно так. Ведь они очень похожи. Если используются истинно случайные числа, результат работы обоих невозможно будет предсказать. Однако к сожалению, ваше предположение ошибочно.

Откровенно говоря, что-то я вообще не могу представить "Nondeterministic algorithm". Случайные берем числа, псевдослучайные или функцию от текущего состояния компьютера, все это можно представить также как входные данные для алгоритма. И для одинакового набора входных данных программа (на одной и той же машине (впрочем, тут уже речь опять о состоянии в качестве входных данных)) всегда пойдет одним и тем же путем.

3 ответа 3

Такие виды алгоритмов были введены в обращение в 1967 году Робертом Флойдом. Если обратиться к первоисточнику, то картина будет следующая:

Определение детерминированного алгоритма вы уже дали в вопросе.

Недетерминированный алгоритм отличается от детерминированного алгоритма не фактом использования случайных чисел, а наличием других переменных, влияющих на результат, кроме полученных из входных данных. Если вы возьмете какую-то функцию, реализующую недетерминированный алгоритм, то один раз для входного числа она вернёт один результат, а в другой раз для того же числа она может вернуть другой результат.

Таким критериям соответствуют функции, реализующие ГПСЧ. Вызывая функцию rand() вы получаете каждый раз другое число, даже если вы явно зададите исходное число для генератора случайных чисел вызовом srand() .

Как видите, поведение функции rand() предсказуемо и зависит от исходного внутреннего состояния. Вместе с тем, если вы не знаете исходного состояния, то поведение предсказать будет сложно, если вообще возможно.

Внутреннее состояние алгоритма - это не входные данные. Вы не обязательно можете на них влиять. Например, возьмём кошку. Если кошка сыта и здорова, то она будет рада ласке. Если кошка голодна или больна, то при тех же действиях с вашей стороны (входных данных) вы практически гарантировано будете поцарапаны. Таким образом можно сказать что поведение кошки определяется недетерминированным алгоритмом.

Алгоритмы, которые определяются случайными числами, являются подвидом недетерминированных. Их принято называть вероятностными алгоритмами (probabilistic algorithms). Например, к числу таких можно было бы отнести простую нейронную сеть в которой изначальные веса указываются случайными числами. При прочих равных для данного набора данных и данных исходных весов после обучения вы всегда получите те же самые конечные веса. Другим примером алгоритм, который одновременно недетерминированным и вероятностным, может быть сверточная нейронная сеть, которая содержит содержит dropout-cлой. Итоговые веса после обучения в такой сети могут случайно отличаться при тех же входных данных и исходных весах.

Читайте также: