Суббота, 16.12.2017, 23:50
Главная Регистрация RSS
Приветствую Вас, Гость
Категории раздела
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Наш опрос
Помог ли Вам наш сайт?
Всего ответов: 408
Форма входа
Логин:
Пароль:
Поиск
Главная » Статьи » Материал к уроку » Информатика и ИКТ

Детерминированные и стохастические алгоритмы

Алгоритм — понятное и точное предписание исполнителю на выполнение конечной последовательности действий, приводящей от исходных данных к искомому результату.

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

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

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

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

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

Чтобы задать конечную игру с полной информацией, нужно:

· указать конечное множество, элементы которого называются позициями игры;

· указать начальную позицию игры;

· указать множество заключительных позиций и задать результат игры в каждой из них;

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

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

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

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

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

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

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

Детерминированность. При применении алгоритма к одним и тем же исходным данным должен получаться всегда один и тот же результат, поэтому, например, процесс преобразования информации, в котором участвует бросание монеты, не является детерминированным и не может быть назван алгоритмом.
 Стохастическое преобразование информационной последовательности {xi}

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

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

К одним из наиболее известных методов стохастической аппроксимации относится метод Роббинса-Монро отыскания корней уравнений регрессии, в виде которых в отмеченных задачах часто записываются условия оптимальности параметров фильтрационных оценок. Являясь относительно простым и в то же время достаточно эффективным аппаратом решения широкого класса задач оптимизации в условиях априорной неопределенности процедуры Роббинса-Монро имеют ограниченную область применения, прежде всего, из-за необходимости соблюдения известных требований сходимости. При этом на практике имеют место случаи, когда априорная информация о справедливости некоторых из них отсутствует. Неучет условий сходимости при синтезе алгоритмов адаптивного оценивания может привести к неработоспособности последних.

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

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

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

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

Категория: Информатика и ИКТ | Добавил: aleksdom (14.02.2011)
Просмотров: 3353 | Рейтинг: 4.7/3
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]