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

05.05.2019

Одноклассники

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

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

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

уметь :

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

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

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

ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий курс

Лектор: проф., д.ф.-м.н. Е.И.Веремей

Введение. Информационные технологии и моделирование. Роль теории моделирования в профессиональной подготовке IT-специалистов. Примеры физических, математических и компьютерных моделей информационных процессов и систем. Глава 1. Общие принципы моделирования объектов и процессов. Основные понятия теории моделирования. Абстрактные и реальные модели. Математическое и компьютерное моделирование информационных систем. Современные методы компьютерного моделирования. Особенности компонентного и объектно-ориентированного подходов. Глава 2. Элементы теории математического моделирования динамических объектов. Основные понятия теории метрических пространств. Нормированные пространства. Операторы и функционалы в метрических пространствах. Динамические модели информационных систем. Понятие об устойчивости информационных процессов. Глава 3. Оптимизационный подход к построению математических моделей. Два базовых метода формирования математических моделей. Задачи идентификации в моделировании информационных процессов. Применение методов оптимизации в математическом моделировании. Параметрическая идентификация с заданием допустимой динамической области. Глава 4. Моделирование элементов информационных систем в среде MATLAB. Общее представление о среде. Реализация базовых численных методов, методы управляемой графики. Моделирование непрерывных и дискретных линейных стационарных систем. LTI-объекты в различных формах и операции над ними. Динамическое тестирование моделей, представленных LTI-объектами. Глава 5. Компьютерное и имитационное моделирование в системе Simulink. Общее представление о системе. Простейшие приёмы построения Simulink-моделей. Общая схема реализации имитационного моделирования в среде Simulink. Интерпретация и анализ результатов моделирования.

Литература

Веремей Е.И., Корчанов В.М., Коровкин М.В., Погожев С.В. Компьютерное моделирование систем управления движением морских подвижных объектов. - СПб.: НИИ Химии СПбГУ, 2002.- 370 с.
Бенькович Е.С., Колесов Ю.Б., Сениченков Ю.Б. Практическое моделирование динамических систем.- СПб.: БХВ-Петербург, 2002.- 464 с.
Learning MATLAB / The MathWorks, Inc.- Natick, 2001.- 296 p.
Using SIMULINK / The MathWorks, Inc.- Natick, 2001.- 846 p.
Гультяев А. Визуальное моделирование в среде Matlab: Учеб. курс. - СПб.: Питер, 2000.- 432 с.
Дьяконов В. Matlab: Учеб. курс. - СПб.: Питер, 2001.- 560 с.
Потемкин В.Г. Matlab 5 для студентов. - М.: ДИАЛОГ-МИФИ, 1998.

Учебно-методический комплекс (УМК) в составе установочного модульного лекционного массива и рабочей программы дисциплины "Моделирование информационных процессов и систем" предназначен в поддержку комплексного интегративного блока дисциплин "Информсреда образования" системы дополнительного образования в МГДД(Ю)Т и в качестве учебного пособия для студентов МИРЭА, занимающихся на кафедре ТИССУ по учебному плану специальности "Информационные системы". УМК опирается на государственный отраслевой образовательный стандарт высшей школы РФ соответствующей специальности и отображает опыт многолетней научно-исследовательской, учебно-творческой и информационно-методической работы в указанном направлении ГНИИ ИТТ "Информика", отдела технического творчества (секторов НИТ и ИВТ) МГДД(Ю)Т, кафедры ТИССУ МИРЭА, Московского межвузовского центра НИТ МИРЭА-МГДД(Ю)Т, ГОУ "Технопарк инноваций в науке и образовании" и других участников. УМК напрямую связан с практикой учебно-творческого школьно-студенческого процесса в системе дополнительного и развивающего образования в МГДТД(Ю)Т и МИРЭА. В УМК использованы многие установочные материалы Международной Академии Информатизации, ГНИИ ИТТ "Информика", ряда научных и учебных публикаций, WWW, а также материалы диссертационной работы аспиранта В.Т.Матчина.

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

41 Приведение модели к требуемому уровню нормальной формы является основой построения реляционной БД. В процессе нормализации элементы данных группируются в таблицы, представляющие объекты и их взаимосвязи. Теория нормализации основана на том, что определенный набор таблиц обладает лучшими свойствами при включении, модификации и удалении данных, чем все остальные наборы таблиц, с помощью которых могут быть представлены те же данные. Введение нормализации отношений при разработке информационной модели обеспечивает минимальный объем физической, то есть записанной на каком-либо носителе БД и ее максимальное быстродействие, что впрямую отражается на качестве функционирования информационной системы. Нормализация информационной модели выполняется в несколько этапов. Данные, представленные в виде двумерной таблицы, являются первой нормальной формой реляционной модели данных. Первый этап нормализации заключается в образовании двумерной таблицы, содержащей все необходимые свойства информационной модели, и в выделении ключевых свойств. Очевидно, что полученная весьма внушительная таблица будет содержать очень разнородную информацию. В этом случае будут наблюдаться аномалии включения, обновления и удаления данных, так как при выполнении этих действий нам придется уделить внимание данным (вводить или заботиться о том, чтобы они не были стерты), которые не имеют к текущим действиям никакого отношения. Например, может наблюдаться такая парадоксальная ситуация. Отношение задано во второй нормальной форме, если оно является отношением в первой нормальной форме и каждое свойство, не являющийся первичным свойством в этом отношении, полностью зависит от любого возможного ключа этого отношения. Если все возможные ключи отношения содержат по одному свойству, то это отношение задано во второй нормальной форме, так как в этом случае все свойства, не являющиеся первичными, полностью зависят от возможных ключей. Если ключи состоят более чем из одного свойства, отношение, заданное в первой нормальной форме, может не быть отношением во второй нормальной форме. Приведение отношений ко второй нормальной форме заключается в обеспечении полной функциональной зависимости всех свойств от ключа за счет разбиения таблицы на несколько, в которых все имеющиеся свойства будут иметь полную функциональную зависимость от ключа этой таблицы. В процессе приведения модели ко второй нормальной форме в основном исключаются аномалии дублирования данных. Отношение задано в третьей нормальной форме, если оно задано во второй нормальной форме и каждое свойство этого отношения, не являющийся первичным, не транзитивно зависит от каждого возможного ключа этого отношения. 42 Использованная литература 1. Костогрызов А.И., Петухов А.В., Щербина А.М. Основы оценки, обеспечения и повышения качества выходной информации в АСУ организационного типа. М.: Изд. ⌠Вооружение. Политика. Конверсия, 1994. 278с. 2. Костогрызов А.И., Липаев В.В. Сертификация функционирования автоматизированных информационных систем. М.: Изд. Вооружение. Политика. Конверсия, 1996. 280с. 3. Климов Г.П. теория вероятностей и математическая статистика. М.: МГУ, 1983. 328с. 4. Вентцель Л.Д. Курс теории случайных процессов.- М.,1975. 5. Зубов В.И. Процессы управления и устойчивость.- СПб.,1999. 6. Э.М. Димов, О.Н. Маслов, С.К. Швайкин. Имитационное моделирование, реинжиниринг и управление в компании сотовой связи. Москва. «Радио и связь». 2001. 7. М.С. Колосков. Время доставки пакета и пропускная способность локальной вычислительной сети. Автоматика и вычислительная техника. 1990 г. № 3. Академия наук Латвийской ССР. 8. http://www.niikte.com.ru/ 9. http://book.od.ua/books/book/case/introduc.htm 10. М.С. Колосков. Время доставки пакета и пропускная способность локальной вычислительной сети. Автоматика и вычислительная техника. 1990 г. № 3. Академия наук Латвийской ССР. 11. http://www.cfin.ru/ 12. http://sc.imis.ru/ 13. http://www.compulog.ru/ 14. http://www.iro.yar.ru, 15. www.work.kemsu.ru 16. www.glossary.basegroup.ru 17. www.exponenta.ru, 18. www.levin.ru 19. www.iro.yar.ru 20. www.work.kemsu.ru 21. www.enckl.by.ru 22. www.soc-gw.univ.kiev.ua 23. www.exponenta.ru 24. on.wplus.net/koulon/first.htm 25. В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин “Введение в теорию автоматов” 26. В. Брауэр “Введение в теорию конечных автоматов” 27. www.sgu.ru 28. www.citforum.ru 29. www.mari.su 30. www.stu.ru 31. Зуховицкий С. И., Авдеева Л. И., Линейное и выпуклое программирование, 2 изд., М., 1967; 32. Хедли Дж., Нелинейное и динамическое программирование, перевод с английского, М., 1967 43 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) «УТВЕРЖДАЮ» «СОГЛАСОВАНО» Декан факультета кибернетики Председатель учебно-методической комиссии по направлению 654700 ________________ М.П.РОМАНОВ __________________ В.В.НЕЧАЕВ «____»__________________ 2001 г. «____»__________________ 2001 г. РАБОЧАЯ ПРОГРАММА ПО ДИСЦИПЛИНЕ «МОДЕЛИРОВАНИЕ СИСТЕМ» ЧАСТЬ 1 Направление подготовки дипломированного специалиста 654700 «Информационные системы» Специальность 071900 «Информационные системы и технологии» Очная форма обучения Составлена на основании Государственного образовательного стандарта высшего профессионального образования по направлению подготовки дипломированного специалиста 654700 «Информационные системы» в соответствии с учебным планом по специальности 071900 «Информационные системы и технологии» (федеральный компонент блока общепрофессиональных дисциплин) Факультет кибернетики Кафедра технических и информационных средств систем управления ОБЪЕМ УЧЕБНОЙ НАГРУЗКИ И ВИДЫ ОТЧЕТНОСТИ Лекции (часов) 34 Лабораторные занятия (часов) - Практические занятия (часов) 17 Индивидуальные занятия с преподавателем (часов) 17 Самостоятельные занятия (часов) 17 ВСЕГО (часов) 85 44 Курсовые проекты и работы (номер семестра) - Зачеты (номер семестра) 6 Экзамены (номер семестра) - МОСКВА 2001 1. ЦЕЛИ И ЗАДАЧИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ, ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ 1.1. ЦЕЛЬ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ: целью изучения дисциплины является получение: - представления о системном анализе, иерархической декомпозиции систем, алгебраических системах и моделях, основных понятиях теории моделей; - знания модальных языков первого порядка, временной логики предикатов, моделей данных, логики умолчаний и исключений; - умения выбирать метод моделирования и производить оценку вариантов структуры и параметров информационных систем; - навыков применения языков программирования VISUAL BASIC, PASCAL, C++ для разработки алгоритмов обработки информации, средств ACCESS и EXCEL для моделей баз данных; - умения анализировать результаты моделирования и формировать реко- мендации по построению и функционированию информационных систем; 1.2. ЗАДАЧИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ: Изложение теоретического материала и проведение практических занятий построенных по блочному принципу (принципу вложенности) на объектно- ориентированных языках программирования, что позволяет из отдельных программ-блоков собирать модель информационной системы функционально полную, но в ограниченном масштабе (объеме обрабатываемых данных). 1.3. ПЕРЕЧЕНЬ ДИСЦИПЛИН И РАЗДЕЛОВ, ЗНАНИЕ КОТОРЫХ ТРЕБУЕТСЯ ДЛЯ ИЗУЧЕНИЯ ДАННОЙ ДИСЦИПЛИНЫ: - математика; - информатика; - алгоритмические языки и программирование; - вычислительная математика; - инженерия знаний; - теория информационных процессов и систем; - информационные технологии; - технология программирования; - архитектура ЭВМ и систем. 45 2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 2.1. ТЕМАТИЧЕСКИЙ ПЛАН ЛЕКЦИОННОГО КУРСА: №№ Содержание тем Кол-во п.п. часов 1 Основные понятия общей теории систем и 4 моделирования 2 Теоретические основы моделирования 4 3 Алгебраическая модель базы данных 4 4 Модели пользовательского интерфейса и семантики в 6 информационных системах 5 Формализация и алгоритмизация процессов 8 классификации 6 Моделирование и алгоритмизация упорядочения данных 8 Всего (часов): 34 2.2. ПРОГРАММА ЛЕКЦИОННОГО КУРСА: Тема 1. Основные понятия общей теории систем и моделирования Классификация видов моделирования. Имитационные, статистические и оптимизационные модели. Инструментальные средства моделирования. Тема 2. Теоретические основы моделирования Многосновные алгебраические системы, алгебры и модели. Сигнатуры. Модели как гомоморфизмы. Категории и функторы. Языки первого порядка, интерпретации и теории. Тема 3. Алгебраическая модель базы данных Модель базы данных. Динамическая база данных. Структура функциональных зависимостей. Произведения и объединения баз данных. Модель информационной системы Д. Скотта. Тема 4. Модели пользовательского интерфейса и семантики в информационных системах Модели представления текстов и документального поиска в информационных системах. Интенсиональная логика и естественный язык. Типизированная экстенсиональная логика. Семантика и грамматика Монтегю. Модальные логики и семантика возможных миров. Временные логики и верификация программ. Немонотонная логика, очерчивание, гипотеза замкнутого мира. Тема 5. Формализация и алгоритмизация процессов классификации Классификационные схемы и модели кластерного анализа. Методы автоматического построения классификаций, алгоритмы партициальной и иерархической класстеризации. Агломеративный алгоритм по методу минимального расстояния. Алгоритм кластеризации, использующий минимальное покрывающее дерево. Анализ ковариационных зависимостей документального файла. 46 Тема 6. Моделирование и алгоритмизация упорядочения данных Частично упорядоченные множества. Ранг элемента в частично упорядоченном множестве. Аксиома выбора. Теорема Цермело. Перестановки, подстановки и транспозиции. Представление перестановки в виде произведения транспозиций. Основные алгоритмы сортировки. Решетки разбиений множества, ключи и индексы. Комбинаторное просеивание. Формула включения и исключения. Разбиения множеств. Решетки разбиений. Фильтры и идеалы. Индексы и методы доступа. Мультисписковые структуры. Инвертированные файлы. 2.3. ЛАБОРАТОРНЫЕ РАБОТЫ: учебным планом не предусмотрены. 2.4. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ: №№ Темы практических занятий Кол-во п.п. часов 1 Разработка модели базы данных и нормализация отношений 4 2 Кластерный анализ записей базы данных 6 3 Индексирование полнотекстовых документов 7 Всего (часов): 17 2.5. ТЕМАТИКА КУРСОВЫХ РАБОТ: учебным планом не предусмотрены. 2.6. ТЕМАТИКА И ФОРМЫ ИНДИВИДУАЛЬНОЙ РАБОТЫ СТУДЕНТОВ С ПРЕПОДАВАТЕЛЯМИ: тематика индивидуальной работы определяется тематикой практических зданий; основное содержание индивидуальных занятий заключается в разработке контрольных примеров к разрабатываемым моделям, обсуждению содержательной интерпретации результатов моделирования и формам наглядного представления его результатов. 2.7. ТЕМАТИКА И ФОРМЫ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ: самостоятельная работа студентов реализуется в форме освоения теоретических основ моделирования информационных процессов и систем и приобретения навыков практической работы с прикладными программами; рекомендуемые задания: - привести примеры применения языков первого порядка для записи фактов в информационной системе; - привести интерпретацию модели информационной системы Д. Скотта; - привести примеры использования семантики и грамматики Монтегю для формализации анализа естественного языка; - дать содержательную интерпретацию результатов работы агломеративный алгоритм по методу минимального расстояния на примере программных комплексов. 3. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ 3.1. ОСНОВНАЯ ЛИТЕРАТУРА: 47 1. Романов В.П., Теоретические основы информации. М., Изд-во РЭА им. Г.В.Плеханова. 1993, -159 с. 2. Романов В.П., Теоретические основы информатики. Информационные структуры и фактографический поиск информации. М., Изд-во РЭА им. Г.В.Плеханова. 1996, -190 с. 3. Тозе А., Грибомон Р. И др. Логический подход к искусственному интеллекту. М., Мир, 1990, -428 с. 4. Кофман А. Введение в комбинаторику. М., Наука, - 479 с. 5. Плоткин Б. И. Универсальная алгебра, алгебраическая логика и базы данных. М., Наука, 1991, -446 с. 3.2. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА: 1. М.Месарович, Я.Такахара. Общая теория систем: математические основы. М.:, Мир, 1978, -311 с. 2. Голуб Дж., Ван Лоун Ч. Матричные вычисления: Пер. с англ. - М.: Мир,1999.- 548 с. , ил. 3. Алгоритмы и программы решения задач на графах и сетях. Нечепуренко М.И. и др.- Новосибирск: Наука. Сиб. Отделение. 1990.- 515 с. 4. Логика и компьютер. Вып. 3.-М.: Наука. 1996- 255 с. Рабочую программу составил: доцент кафедры технических и информационных средств систем управления, к.т.н. В.П.Романов Рабочая программа обсуждена и одобрена на заседании кафедры технических и информационных средств систем управления « 19 » декабря 2001 г. (протокол № 5) Заведующий кафедрой технических и информационных средств систем управления, профессор В.А.Мордвинов 48 Оглавление Введение. Информационные системы как инструмент управления информационной средой образования..............................................................................................................3 Аналитическое моделирование..........................................................................................5 Имитационные модели........................................................................................................6 Модели массового обслуживания......................................................................................7 Кластерный анализ..............................................................................................................7 Объект и признак.................................................................................................................8 Метрика.................................................................................................................................8 Плотность и локальность кластеров..................................................................................9 Расстояние между кластерами............................................................................................9 Факторный анализ..............................................................................................................10 Логические модели............................................................................................................12 Реляционная алгебра.........................................................................................................13 Регрессионный анализ.......................................................................................................14 Алгебраические модели....................................................................................................15 Комбинаторное программирование.................................................................................15 Теоретико-графовое программирование.........................................................................16 Дискретные модели...........................................................................................................17 Реинжиниринг....................................................................................................................17 Теория очередей.................................................................................................................18 CASE-технологии..............................................................................................................25 Детерминированные модели.............................................................................................29 Формирование запроса к БД на Web-клиенте.............................................................30 Формирование запроса к БД на Web-сервере.............................................................31 Сравнительная характеристика двух механизмов доступа к базам данных............32 Линейное программирование. ..........................................................................................33 Моделирование информационных процессов и систем................................................33 Математическое программирование................................................................................36 Создание информационной модели.................................................................................38 Использованная литература..............................................................................................42

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

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

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

Трудоемкость – 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 с.