Моделирование информационных процессов

Кафедра систем телекоммуникаций, факультет физико-математических и естественных наук

Направление «Информационные технологии»

Трудоемкость – 2 кредита, 2 часа лекций в неделю

Цель курса

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

В результате изучения курса решаются следующие задачи:

· освоение теоретических основ математического и компьютерного моделирования информационно-вычислительных систем;

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

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

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

Лекции

Тема 1. Основные понятия

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

Тема 2. Общие принципы построения моделей информационных процессов и систем.

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

Тема 3. Объектно-ориентированное моделирование. Язык UML.

Объектно-ориентированное моделирование. Язык UML. ориентированном моделировании, типы данных и пакеты. Унифицированный язык моделирования UML. Использование объектно-ориентированного подхода и основные понятия и компоненты языка. Диаграммы классов. Диаграммы вариантов использования. Диаграммы взаимодействия. Диаграммы состояния и деятельности.

Тема 4. Моделирование динамических и гибридных систем

Понятие динамической и событийно-управляемой системы, гибридные системы. Принципы компонентного компьютерного моделирования. Иерархические системы. Блоки и связи между ними. Ориентированные и неориентированные блоки и связи. Неявные взаимодействия компонентов. Реализация компонентного моделирования в подсистемах Simulink и Stateflow математического пакета Matlab. Основные библиотечные блоки. Последовательность построения и отладки Simulink-моделей. Понятие карты состояния Харела. Диаграммы Stateflow Средства анализа результатов моделирования.

Тема 5. Моделирование систем массового обслуживания и функциональных процессов

Дискретно-событийный подход к моделированию. Проблемно-ориентированный язык и программная среда GPSS/PC. Предметная область GPSS – системы массового обслуживания (системы с очередями). Общие принципы моделирования информационных и вычислительных процессов в GPSS/PC. Базовые сведения о системе: объекты, переменные и выражения, функции. Модель системы: модельное время и статистика. Внутренняя организация: списки и общая внутренняя последовательность событий. Элементы языка моделирования GPSS/PC. Среда моделирования GPSS/PC: операторы, команды управления, интерактивное взаимодействие. Принципы автоматизированной разработки информационных систем с помощью инструментов анализа, проектирования и генерации кодов BPwin и ERwin. Основы методологии построения функциональных моделей и моделей данных, автоматизация написания кодов серверной и клиентской части приложения. Интеграция функциональной модели и модели данных, технология связывания объектной модели в UML и модели данных Erwin. Техника создания отчётов по моделям процессов и данных с помощью специализированного генератора отчетов RPTwin.

Тема 6. Планирование экспериментов с моделями систем

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

Тема 7. Обработка и анализ результатов моделирования

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

Литература:

Обязательная

1. Советов Б. Я., Яковлев С. А. Моделирование систем. Учебник для ВУЗов. – М.:Высшая школа, 1999. – 319 с.

2. Бусленко Н. П. Моделирование сложных систем. – М.: Наука, 1978. – 399 с.

3. Питерсон Дж. Теория сетей Петри и моделирование систем. – М.: Мир, 1984. – 264 с.

4. Д. С. Кулябов, А. В. Королькова. Введение в формальные методы описания бизнес-процессов. - М.: РУДН, 2008.

5. Бычков С. П., Храмов А. А. Разработка моделей в системе моделирования GPSS. Учебное пособие. – М.: МИФИ, 1997. – 32с.

6. Кравченко П. П., Хусаинов Н. Ш. Имитационное моделирование вычислительных систем средствами GPSS/PC. – Таганрог: ТРТУ, 2000 г. – 116 с.

7. Бенькович Е. С., Колесов Ю. Б., Сениченков Ю. Б. Практическое моделирование динамических систем – СПб.: БХВ-Петербург, 2002. – 464 с.

Дополнительная

1. Кулябов Д. С., Королькова А. В. Архитектура и принципы построения современных сетей и систем телекоммуникаций. - М. 2008.

2. Семенов Ю. А. Протоколы Internet . - Изд-во "Горячая линия – Телеком. - 2005г.

3. Таненбаум Э. Компьютерные сети (4 изд.) // Спб.: Изд-во «Питер», 2003

Программу составили

Королькова Анна Владиславовна

кандидат физико-математических наук,

доцент кафедры систем телекоммуникаций,

факультет физико-математических и естественных наук.

Кулябов Дмитрий Сергеевич,

кандидат физико-математических наук, доцент,

доцент кафедры систем телекоммуникаций,

факультет физико-математических и естественных наук.

Министерство образования Российской Федерации

Воронежская государственная технологическая академия

Кафедра математического моделирования

информационных и технологических систем

МОДЕЛИРОВАНИЕИНФОРМАЦИОННЫХ

ПРОЦЕССОВОБРАБОТКИДАННЫХ

Методические указания к практическим занятиям

по курсу "Информационные технологии".

Для студентов специальности

071900 – "Информационные системы и технологии"

дневной формы обучения

Воронеж

2001

УДК 681

Моделирование информационных процессов обработки данных: Методические указания к практическим занятиям по курсу "Информационные технологии"/ Воронеж. г ос. технол. акад.: Сост. Ю.В. Бугаев, С.В. Чикунов. Воронеж, 2001.32 с .

Методические указания разработаны в соответствии с требованиями ООП подготовки инженеров обучающихся по специальности 071900 - "Информационные системы и технологии". Они предназначены для закрепления теоретических знаний дисциплины цикла ОПД.

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

Библиогр.: 6 назв.

Составители:доцент Ю.В. БУГАЕВ,

ассистент С.В. ЧИКУНОВ

Научный редактор профессорВ.В. СЫСОЕВ

Рецензент профессорД.Б. ДЕСЯТОВ

Печатается по решению

редакционно-издательского совета

Воронежской государственной технологической академии

Ó Бугаев Ю.В.,

Чикунов С.В., 2001

Ó Воронежская

государственная

технологическая

академия, 2001

1. ОБЩИЕ СВЕДЕНИЯ ОБ УРОВНЯХ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ…………………….4

2. МОДЕЛИ ОБСЛУЖИВАНИЯ

ИНФОРМАЦИОННЫХ ПРОЦЕССОВ.

2.1. Системы массового обслуживания в организации

информационных процессов…………………………… 6

2.2. Методика составления аналитических стационар-

ных моделей СМО……………………………………..... 8

2.3. Имитационное моделирование в информационных

технологиях .

2.3.1. Основные понятия………………………………..10

2.3.2. Методы имитации……………………….………..12

2.4. Контрольные вопросы и задания…………………….. ..1 9

3. МОДЕЛИ ПЛАНИРОВАНИЯ

ИНФОРМАЦИОННЫХ ПРОЦЕССОВ.

3.1. Постановка задачи планирования…....……………….. 23

3.2. Эффективный алгоритм для частного случая задачи... 25

3.3. Алгоритм точного решения общего случая задачи….. 27

3.4. Контрольные вопросы и задания……………………… 28

БИБЛИОГРАФИЧЕСКИЙ СПИСОК…………………… ….. … 31

1. ОБЩИЕ СВЕДЕНИЯ ОБ УРОВНЯХ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ.

В связи с развитием автоматизированных систем проектирования (САПР) и управления (АСУ) все большую актуальность получают информационные технологии (ИТ), основанные на использовании ЭВМ и математического моделирования, включающего в себя методы построения и анализа математических моделей.

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

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

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

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

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

Использование базовой информационной технологии рассматривается на трех уровнях:

Концептуальном;

Логическом;

Физическом.

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

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

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

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

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

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

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

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

1) задача обслуживания – определение вероятностных характеристик систем обслуживания задач;

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

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

2. МОДЕЛИ ОБСЛУЖИВАНИЯ ИНФОРМАЦИОННЫХ

ПРОЦЕССОВ.

2.1. Системы массового обслуживания в организации

информационных процессов.

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

Анализ процесса обслуживания заявки может быть выполнен на основе теории систем массового обслуживания (СМО) . Тогда ВС может быть представлена математической моделью СМО.

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

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

Следует помнить, что случайный поток называется простейшим, если он обладает свойствами стационарности, ординарности и отсутствия последействия .

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

Ординарность означает, что вероятность наступления более одного события за малый промежуток времени h практически равна нулю. Более строго:

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

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

Простейший поток обладает свойством аддитивности: сумма простейших потоков с интенсивностями l 1 и l 2 снова является простейшим потоком с интенсивностью . Например, если заявки от двух разных независимых источников представляют собой простейшие потоки и оба поступают на общий вход системы, то общий поток заявок, поступающих на вход равен сумме этих потоков и следовательно, обладает свойством аддитивности.

2.2. Методика составления аналитических

стационарных моделей СМО.

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

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

Иными словами, - это множество начальных вершин дуг, входящих в , а - множество конечных вершин дуг, выходящих из .

Тогдасимволическое уравнение баланса для состояния будет иметь вид:

(1)

Уравнения вида (1) записываются для всех состояний системы.

Пример . СМО может находиться в двух состояниях:

Состояние ожидания заявки;

Состояние обслуживания заявки.

Переход из в наступает сразу после прихода заявки и происходит с интенсивностью l . Переход из в наступает после окончания обслуживания заявки и происходит с интенсивностью m . Имеем следующий граф:

Составляем уравнения баланса:

для :

для :

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

Таким образом, получаем систему:

решение которой имеет вид: ; .

Несложно показать, что система уравнений (1) всегда вырождена и поэтому одно из уравнений системы следует заменять условием нормировки :

(2)

Итак, модель стационарного режима СМО представляет собой систему уравнений символического баланса (1), в которой любое одно уравнение заменяется условием нормировки (2).

2.3. Имитационное моделирование в информационных

технологиях .

2.3.1. Основные понятия.

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

Следует помнить, что имитация – это воспроизведение моделируемого процесса на ЭВМ. Для детерминированных объектов имитация идентична обычному методу проб. Иными словами, компьютеру задаются значения входных параметров объекта и по имитационной модели рассчитываются значения выходных параметров. Варьируя входом, получают подробную характеристику объекта.

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

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

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

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

Программы-датчики псевдослучайных чисел встроены практически во все языки высокого уровня. В языке Pascal используется функция Random. Она имеет две модификации – с аргументом и без него.

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

2.3.2. Методы имитации.

Имитация одиночного события .

Имитацию случайного события А можно связать с логической переменной W A , которая равна true, если событие А наступило в результате имитации и false, если событие не наступило.

Пусть имитируется наступление события А , вероятность которого равна p . Применяется следующий способ. Имитируется случайная величина a , равномерно распределенная на , а затем полагаем ;

Имитация полной группы событий .

Напомним, что события образуют полную группу, если

Сумма их вероятностей равна 1;

Для любых события и несовместны.

Обозначим . Разобьем интервал на части длиной каждая. Имитируется случайная величина . Если , то считается, что наступило событие .

Запишем соответствующий фрагмент на неформальной версии языка Pascal:

Здесь , если наступило событие .

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

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

Метод обратной функции .

Метод обратной функции основан на следующем свойстве случайных величин.

Пусть случайная величина x имеет функцию распределения . Тогда случайная величина

(3)

равномерно распределена на интервале . Отсюда, если нам известно какое-либо значение a , то для нахождения x надо решить уравнение (3) относительно x .

Получаем следующий метод:

(4)

Здесь - функция, обратная к F; выражение (4) соответствует формуле решения уравнения (3).

Метод исключения .

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

Метод исключения удобно проиллюстрировать следующим рисунком:

Согласно наложенным условиям, график функции целиком содержится в прямоугольнике .

Пусть - случайная точка, равномерно распределенная на S. Если находится ниже графика , то есть то полагаем . В противном случае считаем имитацию неудачной и повторяем ее.

Обоснование метода очевидно. Вероятность того, что x примет значение, равное x 0 , пропорциональна величине . Соответственно пропорциональна вероятности того, что при данном x 0 точка окажется под графиком .

Для имитации случайной точки , равномерно распределенной на S , воспользуемся методом обратной функции. Пусть нам нужна случайная величина h равномерно распределенная на . Ее плотность распределения имеет вид

,

а функция распределения:

Отсюда .

Таким образом имеем следующие соотношения:

где a 1 и a 2 – две независимых реализации случайной величины, равномерно распределенной на . Окончательно имеем следующий фрагмент программы:

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

Имитация нормального распределения .

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

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

(5)

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

Если необходимо получить величины, соответствующие распределению , то используют следующую формулу:

где x получено по формуле (5).

Имитация распределения Эрланга .

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

В простейшем потоке длительности ожидания каждого следующего события распределены по показательному закону . Получить случайную, показательно распределенную величину очень легко методом обратной функции. Тогда распределение Эрланга k-го порядка имитируется с помощью формулы , где x i – независимые случайные величины, распределенные по показательному закону.

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

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

Случайная выборка .

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

Высказанную идею можно оформить в виде следующего алгоритма:

Модификацию этого алгоритма, когда значение M заранее неизвестно, можно найти в .

Случайное перемешивание .

Задачу о выборке можно рассматривать как вычисление случайного сочетания n объектов из M . Рассмотрим теперь задачу вычисления случайной перестановки n объектов. Предлагается следующий алгоритм.

Пусть - набор из n чисел, из которых надо составить заданное число M перестановок.

В заключении раздела опишем алгоритм имитации функционирования информационно-поисковой системы (ИПС), осуществляющей поиск информации в соответствии с поступающими заявками. Заявки поступают в случайные моменты времени. Время поиска нужной информации по одной заявке – случайная величина a , равномерно распределенная на . Если в момент прихода заявки система не занята поиском, то обслуживание заявки начинается немедленно. Если система в момент прихода заявки занята поиском, то заявка ставится в очередь. Как только система освободится, начинается поиск по заявкам, стоявшим в очереди. Поиск по k заявкам осуществляется одновременно, время поиска - , где (см. задание 10).

Предлагается следующий алгоритм при заданном числе заявок N.

1). Определяем время поступления всех заявок :

где x - случайное время ожидания очередной заявки (интервал времени). Распределение x задано плотностью .

2). Определяем время начала и конца поиска i-й порции информации: и :

Begin := 0; := a ;i:= 1;k 1:= 0;m 1:=1;

repeati:= i +1; определить k i – число значений таких что (* )

{ k i – длина очереди}.

ifk i ³ 1then

begin ; ; для всех j, таких что удовлетворяет условию (* ) положить .

{ - номер поисковой порции j-й заявки}.

endelse

begin .

; ;

end;

until ; ; {n–число запусков системы на поиск}.

End.

Этим алгоритмом можно воспользоваться для вычисления среднего времени ожидания конца обслуживания :

и средней длины очереди

2.4. Контрольные вопросы и задания.

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

2. Каким образом составляется графовая модель стационарного режима СМО?

3. Доказать, что система уравнений (1) вырождена.

4. Составьте графовые и балансовые модели следующих СМО и найдите вероятности .

а). Система имеет 1 канал обслуживания и накопитель из 3 ячеек. Если заявка поступает в момент, когда канал обслуживания свободен, а накопитель пуст, то СМО приступает к обслуживанию заявки. Если заявка поступает в момент обслуживания, то заявка становится в очередь и помещается в свободную ячейку накопителя. Если все ячейки заняты – заявка покидает систему не обслуженной. Как только закончится обслуживание заявки, система приступает к обслуживанию заявки из накопителя, ячейка при этом освобождается. Если после окончания обслуживания накопитель пуст, то СМО переходит в состояние ожидания. Интенсивность поступления заявок ; интенсивность обслуживания .

б). СМО содержит 4 обслуживающих канала и не имеет накопителя. Поступающая заявка попадает на первый свободный канал и обслуживается. Если все каналы заняты, заявка покидает систему не обслуженной . Интенсивность поступления заявок ; интенсивность обслуживания заявки одним каналом .

Указание. На основании свойства аддитивности простейшего потока, интенсивность обслуживания заявок n каналами равна . Иными словами, если в данный момент загружено n каналов, то интенсивность освобождения одного занятого канала равна . Одновременное освобождение более одного канала невозможно в силу свойства ординарности.

в). СМО имеет два обслуживаемых канала и две ячейки накопителя. Интенсивность поступления заявок ; интенсивность обслуживания .

г). СМО имеет два обслуживаемых канала, которые в случайные моменты времени выходят из строя. После поломки канал подлежит ремонту и в это время не работает. После восстановления обслуживание заявки продолжается. Интенсивность поступления заявок ; интенсивность обслуживания ; интенсивность поломок ; интенсивность восстановления .

5. Составить программу автоматического формирования системы уравнений (1) - (2) по данному графу, представленному списком дуг с весами интенсивностей .

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

а). ;

б). . Найти константу b.

в). . Найти константу b.

г). .

д). . Найти константу b.

е). р аспределение Эрланга k-го порядка: , .

7. Почему метод получения нормальных чисел по формуле (5) является приближенным ?

8. Почему для имитации нормального распределения нельзя применять методы обратной функции и исключения ?

9. Случайные величины независимы и одинаково распределены с функцией распределения . Доказать, что для имитации случайных величин и можно воспользоваться следующими формулами , , где b 1 и b 2 – две независимые случайные величины, равномерно распределенные на .

Указание . Воспользоваться тем, что

10. Случайные величины a 1 , a 2 , …, a k , b 1 , b 2 независимы и равномерно распределены на . Воспользовавшись результатом задачи 9 доказать, что имитация случайных величин и может быть осуществлена по формулам ; .

11. Написать процедуру реализации схемы независимых испытаний: в результате одного испытания происходит какое-либо событие из полной группы событий, вероятности которых заданы. Задано общее число испытаний N. Проимитировать целочисленный случайный вектор , в котором равны числу наступлений события за N испытаний.

12. Проимитируйте работу двоичного симметричного канала связи с помехами, передающего текст в кодах ASCII. В этом канале символ 0 с вероятностью p заменяется 1 и наоборот .

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

14. Проимитируйте работу СМО, описанных в задании 4.

15. Проимитируйте работу ИПС в соответствии с изложенным алгоритмом, когда поток заявок имеет:

а) показательное распределение, ;

б) нормальное распределение, ;

в) распределение Эрланга 3-го порядка, .

3. МОДЕЛИ ПЛАНИРОВАНИЯ ИНФОРМАЦИОННЫХ

ПРОЦЕССОВ.

3.1. Постановка задачи планирования.

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

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

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

При планировании вычислительного процесса необходимо учитывать следующие ограничения:

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

2) каждое устройство на данной фазе может выполнять только одну информационно - вычислительную работу;

3) начавшаяся работа не должна прерываться до полного ее завершения.

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

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

После того, как все виды работ будут упорядочены в очереди, по формулам (6) рассчитывается общее время их выполнения Q , которое является минимальным.

Пример: Установить оптимальную очередность выполнения работ для известной матрицы трудоемкости

В соответствии с алгоритмом оптимального планирования выполняем следующие действия:

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

3.3. Алгоритм точного решения общего случая задачи.

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

3.4. Контрольные вопросы и задания.

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

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

3. Составить программу точного решения задачи Джонсона методом полного перебора для произвольного количества задач и фаз.

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

а) номера j 1 и j 2 соответствуют двум столбцам с максимальной суммой элементов;

б) номера j 1 и j 2 соответствуют двум столбцам, в которых присутствуют максимальные элементы матрицы V;

в) номераj 1 иj 2 пробегают все возможные значения , выбирается пара, имеющая .

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

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

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

где

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Советов Б.Я. Информационная технология: Учеб. д ля вузов по спец. “Автоматизир. системы обработки информ. и упр.”. - М.: Высш. шк., 1994. - 368 с.

2. Вентцель Е.С. Исследование операций. - М.: Советское радио, 1972. - 552 с .

3. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. - М.: Наука, 1987. - 336 с .

4. Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. - М.: Мир, 1977. - 724 с .

5. Ермаков С.М., Михайлов Г.А. Курс статистического моделирования. - М.: Наука, 1976. - 320 с .

6. Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с .

Учебное издание

МОДЕЛИРОВАНИЕ ИНФОРМАЦИОННЫХ

ПРОЦЕССОВ ОБРАБОТКИ ДАННЫХ

Методические указания к практическим занятиям

по курсу "Информационные технологии"

Для студентов специальности

071900 – “Информационные системы и технологии”.

СоставителиБУГАЕВ Юрий Владимирович,

ЧИКУНОВ СергейВладимирович

Компьютерный набор и версткаС.В. Чикунов

ЛР N 020449 от 31.10.97. Подписано в печать.2001.

Формат 60х84 1/16. Бумага офсетная. Гарнитура. Таймс. Ризография.

Усл.п еч. л. 1,6. Уч.-изд. л. 1,4. Тираж 100 экз. Заказ. С-.

Воронежская государственная технологическая академия (ВГТА)

Участок оперативной полиграфии ВГТА

Адрес академии и участка оперативной полиграфии ВГТА:

394000 Воронеж, пр. Революции, 19

Методы и технологии моделирования

Технология – совокупность методов и инструментов для достижения желаемого результата; метод преобразования данного в необходимое; способ производства.

Метод (лат. methodus, от греч. methodos - "путь, следование, способ исследования") - в науке - способ достижения поставленной цели, предполагающий совокупность приемов и средств.

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

Базы данных

Базы данных представляют связанную совокупность структурированных данных, относящихся к определенному процессу или явлению, в конкретной предметной области. Система управления базами данных представляет собой программный комплекс для создания, организации необходимой обработки, хранения и передачи баз данных. Ядром любой БД является модель представления данных. Модель данных представляет множество структур данных и взаимосвязи между ними. Различают иерархическую, сетевую и реляционнуюмодели данных.

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

- узел - набор атрибутов данных, описывающих объект;

- связь - линия, связывающая узлы нижнего уровня с одним узлом вышележащего уровня. При этом узел вышележащего уровня называют предком для соответствующих ему узлов нижнего уровня, в свою очередь, узлы нижнего уровня называют потомками связанного с ними вышележащего узла (например, на рисунке 5.2 узел В1 - предок для узлов С1, С2, а узлы С1, С2 - потомки узла В1);

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

Рисунок 5.2 – Иерархическая модель данных

Количество деревьев в БД определяется числом корневых записей. К каждому узлу существует единственный путь от корня.

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

Рисунок 5.3 – Сетевая модель данных

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

Искусственный интеллект

Идеи моделирования человеческого разума известны с древнейших времен. Впервые об этом упоминается в сочинении философа и теолога Раймунда Луллия (ок.1235 - ок.1315) «Великое искусство», который не только высказал идею логической машины для решения разнообразных задач, исходя из всеобщей классификации понятий (XIV в.), но и попытался ее реализовать. Рене Декарт (1596-1650) и Готфрид Вильгельм Лейбниц (1646-1716) независимо друг от друга развивали учение о прирожденной способности ума к познанию и всеобщих и необходимых истин логики и математики, работали над созданием универсального языка классификации всех знаний. Именно на этих идеях базируются теоретические основы создания искусственного интеллекта. Толчком к дальнейшему развитию модели человеческого мышления стало появление в 40-х гг. XX в. ЭВМ. В 1948 г. американский ученый Норберт Винер (1894-1964) сформулировал основные положения новой науки - кибернетики. В 1956 г. в Стенфордском университете (США) на семинаре под названием «Artificial intelligence» (искусственный интеллект), посвященном решению логических задач, признано новое научное направление, связанное с машинным моделированием человеческих интеллектуальных функций и названное искусственный интеллект . Вскоре эта отрасль разделилась на два основных направления: нейрокибернетику и кибернетику «черного ящика».

Нейрокибернетика обратилась к структуре человеческого мозга как единственно мыслящему объекту и занялась его аппаратным моделированием. Физиологи давно выявили нейроны - связанные друг с другом нервные клетки как основу мозга. Нейрокибернетика занимается созданием элементов, аналогичных нейронам, и их объединением в функционирующие системы, эти системы называют нейросетями . В середине 80-х гг. XX в. в Японии был создан первый нейрокомпьютер, моделирующий структуру человеческого мозга. Его основная область применения - распознавание образов .

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

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

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

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

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

Базы знаний

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

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

Кроме того, знания делят на процедурныеи декларативные. Исторически первыми появились процедурные знания, «рассыпанные» в алгоритмах. Они управляли данными. Для их изменения требовалось вносить изменения в программы. С развитием искусственного интеллекта все большая часть знаний формировалась в структурах данных: таблицах, списках, абстрактных типах данных, знания все больше становились декларативными.

Декларативные знания - это совокупность сведений о характеристиках свойств конкретных объектов, явлений или процессов, представленных в виде фактов и эвристик. Исторически такие знания накапливались в виде разнообразных справочников, с появлением ЭВМ приобрели форму баз данных. Декларативные знания часто называют просто данными, они хранятся в памяти информационной системы (ИС) так, что имеют непосредственный доступ для использования.

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

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

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

Исследования процессов принятия решений человеком показали, что рассуждая и принимая решение, человек использует продукционные правила (от англ. production - правило вывода, порождающее правило). Продукционная модель , основанная на правилах, позволяет представить знания в виде предложений: ЕСЛИ (список условие), ТО (следует выполнить перечень действий). Условие -это предложение, по которому происходит поиск в базе знаний, а действие есть некоторая операция, выполняемая при успешно осуществленном поиске. Действия могут быть как промежуточными, выступающими далее как условия, так и целевыми, завершающими работу ИС. В продукционной модели база знаний состоит из совокупности правил. Программа, управляющая перебором правил, называется машиной вывода. Механизм выводов связывает знания и создает из их последовательности заключение. Вывод бывает прямой (метод сопоставления, от данных к поиску цели) или обратный (метод генерации гипотезы и ее проверки, от цели - к данным). Продукционная модель привлекает разработчиков наглядностью, модульностью, легкостью внесения дополнений и изменений, простотой механизма логического вывода, чаще всего используется в промышленных экспертных системах.

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

Рисунок 5.4 – Семантическая сеть

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

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

{ИМЯ ФРЕЙМА: (имя 1-го слота: значение 1-го слота);

(имя 2-го слота: значение 2-го слота);

(имя N-ro слота: значение N-ro слота)}. Важным свойством фреймов является наследование свойств, заимствованное из теории семантических сетей. Наследование происходит по АКО-связям (от A Kind Of, что означает «эт.е.»). Слот АКО указывает на фрейм более высокого уровня иерархии, откуда неявно наследуется, т.е. переносятся значения аналогичных слотов. Например, в сети фреймов на рисунке 5.5 «конструктор» наследует свойства фреймов «инженер» и «человек», которые стоят на более высоком уровне иерархии.

Рисунок 5.5 – Сеть фреймов

Модель фрейма достаточно универсальна, позволяет отобразить все многообразие знаний о мире через:

- фреймы-структуры, для обозначения объектов и понятий (лекция, конспект, кафедра);

- фреймы-роли (студент, преподаватель, декан);

- фреймы-сценарии (сдача экзамена, празднование именин, получение стипендии);

- фреймы-ситуации (тревога, рабочий режим учебного дня) и др.

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

2) Наиболее мощными являются смешанные модели представления знаний.

Экспертные системы

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

Современные экспертные системы способны:

По совокупности признаков заболевания установить диагноз, назначить лечение, дозировать медикаменты, выработать программу курса лечения;

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

Распознавать речь, на данном этапе в ограниченной области применения;

Распознавать человеческие лица, отпечатки пальцев и др.

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

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

Рисунок 5.6 – Структура модели экспертной системы

Система управления

Представляет совокупность взаимосвязанных структурных моделей подсистем, осуществляющих следующие функции:

- планирование (стратегическое, тактическое, оперативное);

- учет - отображает состояние объекта управления в результате выполнения производственных процессов;

- контроль - определяет отклонение учетных данных от плановых целей и нормативов;

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

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

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

Моделирование информационных процессов

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

Рисунок 5.7 – Метод «водопада» с введением временных прототипов

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

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

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

Один входной и один выходной поток данных;

Все операции, необходимые для преобразования входного потока в выходной, выполняются внутри модуля;

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

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

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

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

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

В начале 90-х гг. из всего множества языков объектно-ориентированного анализа и проектирования выделились три, наиболее часто используемых при разработке систем: Booch, созданный Грейди Бучем, OOSE (Object-Oriented Software Engineering), разработанный Айваром Джекобсоном, и ОМТ (Object Modeling Technique), автором которого является Джеймс Рамбо. Каждый из этих методов является вполне законченным языком ООП, однако метод ВООСН особенно удобен на этапах проектирования модели, OOSE - на этапе анализа и формулирования требований, а ОМТ - удобен при проектировании СУБД. Создание языка, объединяющего достоинства этих трех методов, началось в начале 1995 г., когда эти три автора объединили свои методы для создания унифицированного языка для фирмы Rational Software. В 1997 г. была принята версия UML 1.1, взятая на вооружение всеми компаниями - производителями систем автоматизированного проектирования. В 2001 г. появилась версия 2.0. В настоящее время идет утверждение UML в качестве стандарта ISO.

Многие продукты, реализующие CASE-технологии (Computer Aided Software Engineering - автоматизированное проектирование и создание программ), в настоящее время поддерживают нотацию UML. Такие пакеты, как Paradigm Plus, System Architect, Microsoft Visual Modeler, Delphi и др., поддерживают нотацию UML. Наиболее мощный пакет проектирования, разработанный компанией Rational Software - Rational Rose (RR), позволяет использовать при разработке все возможности языка UML.

Похожая информация.

Результаты освоения темы

Изучая данную тему, вы будете знать , что:

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

уметь :

• осуществлять моделирование информационных процессов;
• определять жизненный цикл информационных продуктов и услуг.

Основные понятия:

• Модель;
• Информационная модель;
• Системный подход;
• Жизненный цикл информационных продуктов и услуг, а также информационных технологий.

Модель – одна из основных категорий теории познания. В широком смысле модель – любой образ (изображение, карта, описание, схема, чертёж, график, план и другое) какого-либо объекта, процесса или явления, используемый в качестве их “заместителя” или “представителя”.

Модель (лат. “modulus” – мера) – это объект-заместитель объекта-оригинала, обеспечивающий изучение некоторых свойств последнего; упрощённое представление системы для её анализа и предсказания, для получения качественных и количественных результатов, необходимых для принятия правильного управленческого решения.

Моделирование – это представление объекта моделью для получения информации о нём путём проведения экспериментов с его моделью.

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

Для управления бизнес процессами (англ. “Business Process Management”, BPM) в современных системах используют методы имитационного моделирования.

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

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

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

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

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

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

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

Количество групп элементов информационной модели определяется степенью детализации описания состояний и условий функционирования объекта управления. Как правило, элемент информационной модели связан с каким-либо параметром объекта управления.

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

В качестве инструментальных многофункциональных информационных моделей применяют, например, модели VIEW (англ. “Virtual Instruments Engineering Workbench”).

Для формирования модели используются:

· структурная схема объекта, подлежащего автоматизации;

· структурно-функциональная схема автоматизируемого объекта;

· алгоритмы функционирования системы;

· схема расположения технических средств на объекте;

· схема связи и др.

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

Необходимым элементом моделирования является анализ потоков данных. Спрос на средства аналитической обработки данных постоянно растёт. При этом пользователи заинтересованы в получении средств, позволяющих автоматически искать не только заданные данные, но неочевидные правила и неизвестные закономерности. Для реализации подобных систем используют методы интеллектуального анализа данных , позволяющие на основе накопленной информации принимать нетривиальные решения и генерировать качественно новые знания, способствующие повышению эффективности решений и деятельности людей, предприятий, организаций и т.п. Логика интеллектуально решаемых аналитических задач заключается в том, что первичные документы, отчёты и сводные таблицы анализируются с целью выявления полученных показателей. Исследование произошедших событий и полученных результатов (Что произошло?) происходит с целью ответа на вопрос “Почему?”. В результате проведённого анализа формируются прогностические (прогнозные) модели, в которых даются варианты развития ситуации.

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

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

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