1. Аналитический раздел. 4




Название1. Аналитический раздел. 4
страница4/15
Дата публикации22.06.2013
Размер0.94 Mb.
ТипДокументы
lit-yaz.ru > Математика > Документы
1   2   3   4   5   6   7   8   9   ...   15
^

1.4Математические модели формализации дискретных систем.


Для проведения моделирования необходимо формализовать устройство. Это можно сделать, используя одну из существующих типовых математических схем (табл. 1.3).

Тип

Описание

D-схемы (непрерывно-детерминированные)

Используются дифференциальные уравнения. Не подходит для дискретных систем.

F-схемы (конечные автоматы)

Конечный автомат имеет множество внутренних состояний и входных сигналов, являющихся конечными множествами.

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

P-схемы (вероятностные автоматы)

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

Q-схемы (системы массового обслуживания)

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

А-схемы

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

Табл.1.3 Типовые математические схемы формализации дискретных систем.
Сложность дискретной системы не позволяет сделать однозначный выбор в пользу той или иной математической схемы для построения модели. Для различных дискретных устройств могут подойти различные схемы.

В данной квалификационной работе в качестве схемы формализации системы рассматривается P-схема (далее - вероятностный автомат). Перечислим основные достоинства вероятностных автоматов по сравнению с другими способами формализации моделей:

  • Автоматы имеют хорошо определённую семантику, однозначно определяющую поведение этого автомата;

  • Имеют наглядное графическое представление;

  • Позволяют моделировать широкий класс сложных систем, имеющих стохастический характер;

  • Устойчивы к незначительным изменениям моделируемой системы.

Основным недостатком P-схем является невозможность формализации параллельных алгоритмов.

^

1.5Декомпозиция и методы декомпозиции сложных дискретных систем.



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

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

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

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

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

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

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

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

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

Параллельный

Последовательный

Последовательно-параллельный

Метод декомпозиции

Структурный

Алгоритмический

Объектный

Разбиение на подпроцессы

Сильно-связанные подструктуры

КА

Графы

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

1   2   3   4   5   6   7   8   9   ...   15

Похожие:

1. Аналитический раздел. 4 iconС. М. Горбенко (раздел 1), С. Ю. Кацко (раздел 12-14), С. А. Вдовин (раздел 5-7)
Данный материал будет полезен для самостоятельной подготовки студентов к лабораторным работам

1. Аналитический раздел. 4 iconКурс «управление проектами» Авторы: Сооляттэ Андрей Юрьевич (Раздел...
Тем не менее, некоторые приведенные в тексте примеры и рассуждения несут неизбежный отпечаток «традиций», сложившихся в какой-либо...

1. Аналитический раздел. 4 iconАналитический отчет раздел «социальная сфера» Руководитель фцб «Развитие...
Руководитель фцб «Развитие человеческого потенциала» первый заместитель главы муниципального района Шитова В. Л

1. Аналитический раздел. 4 iconАналитический отчет раздел «культура и искусство» Руководитель фцб...
Руководитель фцб «Развитие человеческого потенциала» первый заместитель главы муниципального района Шитова В. Л

1. Аналитический раздел. 4 iconКонтрольная работа по бух. Учету На тему основные средства. Синтетический...
На тему основные средства. Синтетический и аналитический учет основных средств

1. Аналитический раздел. 4 iconУчебное пособие по курсу: “Общая и возрастная психофизиология” раздел...
Методы изучения и диагностики эмоций раздел III. Психофизиология познавательной сферы

1. Аналитический раздел. 4 iconГиа) в новой форме Единого государственного экзамена (егэ). Обязательными
Зачетная сессия III четверти проводится в соответствии с календарем зачетных сессий (раздел V информационного письма №2 от 10. 09....

1. Аналитический раздел. 4 iconСодержание программы раздел I пояснительная записка (цели и задачи...
Учебно-методическое и материально-техническое обеспечение образовательного процесса

1. Аналитический раздел. 4 iconТ з «Программное обеспечение для образовательных учреждений» Тарификация
Выполнение приказа №1 – это процедура формирования нового модуля Текущая тарификация и внесение изменений в модуль Кадры – в раздел...

1. Аналитический раздел. 4 iconАналитический отчёт заместителя директора по воспитательной работе...
Аналитический отчёт заместителя директора по воспитательной работе по итогам организации процесса воспитания в моу сош №15



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница