Министерство образования Российской Федерации
Воронежская государственная технологическая академия
Кафедра математического моделирования
информационных и технологических систем
МОДЕЛИРОВАНИЕИНФОРМАЦИОННЫХ
ПРОЦЕССОВОБРАБОТКИДАННЫХ
Методические указания к практическим занятиям
по курсу "Информационные технологии".
Для студентов специальности
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
Модель – одна из основных категорий теории познания. В широком смысле модель – любой образ (изображение, карта, описание, схема, чертёж, график, план и другое) какого-либо объекта, процесса или явления, используемый в качестве их “заместителя” или “представителя”.
Модель (лат. “modulus” – мера) – это объект-заместитель объекта-оригинала, обеспечивающий изучение некоторых свойств последнего; упрощённое представление системы для её анализа и предсказания, для получения качественных и количественных результатов, необходимых для принятия правильного управленческого решения.
Моделирование – это представление объекта моделью для получения информации о нём путём проведения экспериментов с его моделью.
Моделирование облегчает изучение объекта с целью его создания, дальнейшего преобразования и развития. Существует два основных вида моделирования: аналитическое и имитационное.
Для управления бизнес процессами (англ. “Business Process Management”, BPM) в современных системах используют методы имитационного моделирования.
На идее модели по существу базируется любой метод научного исследования , как теоретический (при котором используются различного рода знаковые, абстрактные модели), так и экспериментальный , использующий предметные модели.
Модели предметной области – это совокупность описаний, обеспечивающих взаимопонимание между пользователями: специалистами организации и разработчиками.
Модели всегда проще реальных объектов, но они позволяют выделить главное, не отвлекаясь на детали. Различают математические, физические, ситуационные, электрические, информационные модели.
Так, например, математические модели используют для описания объектов и процессов живой и неживой природы и технологии, в том числе – в физике, биологии, экономике.
Наиболее очевидными с точки зрения применения методов моделирования, несомненно, являются процессы управления, где на основе полученной информации необходимо принимать соответствующие решения. Обычно моделирование используется для исследования существующей системы, когда реальный эксперимент проводить нецелесообразно из-за значительных финансовых и трудовых затрат, а также при необходимости проведения анализа проектируемой системы, т.е. которая ещё физически не существует в данной организации. Для человека информационная модель является источником информации, на основе которой он формирует образ реальной обстановки.
Однозначного понятия системы нет. В общем виде под системой понимают совокупность взаимосвязанных элементов, образующих определённую целостность, единство.
Процесс построения модели является творческой процедурой, трудно поддающейся формализации. Модельные представления являются абстрактными образами элементов системы (объектов, технических средств, программного обеспечения и др.). Вместе они позволяют получить достаточно полное представление о создаваемой системе.
Количество групп элементов информационной модели определяется степенью детализации описания состояний и условий функционирования объекта управления. Как правило, элемент информационной модели связан с каким-либо параметром объекта управления.
Модель данных является способом отображения самих данных и их связей. Выделяют модели иерархических, сетевых и реляционных данных, как правило, входящих в состав систем управления базами данных (СУБД). В СУБД реализуются модели процессов накопления и применения информации и знаний.
В качестве инструментальных многофункциональных информационных моделей применяют, например, модели VIEW (англ. “Virtual Instruments Engineering Workbench”).
Для формирования модели используются:
· структурная схема объекта, подлежащего автоматизации;
· структурно-функциональная схема автоматизируемого объекта;
· алгоритмы функционирования системы;
· схема расположения технических средств на объекте;
· схема связи и др.
Главная цель проведения моделирования любой системы – изыскание вариантов решений, которые позволяют улучшить основные показатели её деятельности.
Необходимым элементом моделирования является анализ потоков данных. Спрос на средства аналитической обработки данных постоянно растёт. При этом пользователи заинтересованы в получении средств, позволяющих автоматически искать не только заданные данные, но неочевидные правила и неизвестные закономерности. Для реализации подобных систем используют методы интеллектуального анализа данных , позволяющие на основе накопленной информации принимать нетривиальные решения и генерировать качественно новые знания, способствующие повышению эффективности решений и деятельности людей, предприятий, организаций и т.п. Логика интеллектуально решаемых аналитических задач заключается в том, что первичные документы, отчёты и сводные таблицы анализируются с целью выявления полученных показателей. Исследование произошедших событий и полученных результатов (Что произошло?) происходит с целью ответа на вопрос “Почему?”. В результате проведённого анализа формируются прогностические (прогнозные) модели, в которых даются варианты развития ситуации.
Сбор, обработка и анализ реальных данных функционирования системы или объекта моделирования даёт требуемые количественные оценки для разработки вариантов программно-технического обеспечения автоматизированных систем.
При моделировании сложных объектов нельзя разобщать решаемые задачи. В противном случае получатся значительные затраты ресурсов и потери при реализации модели на конкретном объекте. Использование моделирования применительно к таким объектам требует одновременного исследования их взаимосвязей с внешней средой и другими элементами метасистемы.
Под сложными системами понимаются системы, обладающие большим числом элементов, свойства которых не могут быть предсказаны, опираясь на знания свойств отдельных частей системы и способы их соединения.
Конец работы -
Эта тема принадлежит разделу:
Информация и информатика
Информационные технологии.. Результаты освоения темы.. Изучая данную тему вы будете знать основные термины связанные с определением информации и информационных..
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Все темы данного раздела:
Информация, данные, сведения, сообщения и знания
Как только на Земле появились люди, они стали собирать, осмысливать, обрабатывать, хранить и передавать разнообразную информацию. Человечество (социум) постоянно имеет дело с информацией.
Свойства информации
Информация обладает различными свойствами. Для их систематизации используют разные варианты её деления (классификации).
Классификация - деление объектов на классы
Информатика
Многовековое общение людей с информацией, изучение её видов, свойств и возможностей применения привело к созданию науки – информатики. Термином “Информатика” (франц. “informatique”
Информационные технологии
Способности и возможности людей обрабатывать информацию ограничены, особенно в условиях всё возрастающих массивов (объёмов) информации. Поэтому появилась необходимость использовать способы хранения
Эволюция информационных технологий
Хотя информационные технологии существовали с момента формирования умственной и физической деятельности человека, эволюцию информационных технологий принято рассматривать с момента изобретения в Ге
Платформа информационных технологий
Данный термин не имеет однозначного определения. Платформой называют функциональный блок, интерфейс и сервис которого определяется некоторым стандартом. К платформе (англ. “Platform”) или ба
Роль информационных технологий в развитии экономики и общества
Развитие экономики тесно связано с развитием любого общества потому, что невозможно рассматривать какие-либо экономические задачи и проблемы вне общества. В любом обществе одновременно создаётся и
Жизненный цикл информации. Информационная сфера
Информация может существовать кратковременно (например, в памяти калькулятора в процессе проводимых на нём вычислений), в течение некоторого времени (например, при подготовке какой-либо справки) ил
Негативные последствия внедрения информационных технологий
Наравне с “цифровым разрывом” и “виртуальным барьером”, изменения информационных технологий выполняемых работ часто могут оказывать негативное воздействие на людей (информационный шум и др.), участ
Виды информационных технологий
Любая информационная технология обычно нужна для того, чтобы пользователи могли получить нужную им информацию на определённом носителе данных.
При рассмотрении информационных технологий вы
Технология поиска информации
Поиск – важный информационный процесс. Возможности организации и проведения поиска зависят от наличия информации, её доступности, а также от средств и навыков организации поиска. Цель любого поиска
Виды информационных технологий, используемых в различных предметных областях
Технология как некоторый процесс повсеместно присутствует в нашей жизни. Современные информационные технологии применяются практически в любых сферах, средах и областях жизнедеятельности людей. Обо
Информационные технологии управления
В большинстве случаев информационные технологии тем или иным образом связаны с обеспечением управления и принятием управленческих решений в различных предметных областях.
Информационные технологии экспертных систем
Решение специальных задач требует специальных знаний. Технологии, включающие экспертные информационные системы, позволяют специалистам оперативно получать консультации экспертов по проблемам, котор
Реализация информационных технологий в различных предметных областях
Первой исторически сложившейся информационной технологией, использовавшей ЭВМ, была осуществляемая в вычислительных центрах централизованная обработка информации. Для её реализации создавались круп
Электронные документы
Электронный документ - документ, представленный в электронной форме (оцифрованный или подготовленный на компьютере), имеющий электронную подпись, идентифицирующую (подтвер
Электронные книги
Электронная книга - это вид книги, хранящийся в электронном форме на любом машиночитаемом электронном носителе и включающий специальные средства навигации в ней.
Электронные библиотеки
Электронная библиотека (от англ. "digital library" - "цифровая библиотека") - вид, как правило, общедоступной автоматизированной информационной системы
Электронный офис
Практически в любых организациях, предприятиях, учреждениях, ведомствах, фирмах, учебных заведениях и т.п. функционируют различные информационные потоки. Если деятельность таких организаций в значи
Системный подход к решению функциональных задач
Наиболее эффективно моделирование осуществляется при использовании общих принципов системного подхода,лежащего в основе теории систем. Он возник в процессе изучения различных объек
Жизненный цикл информационных продуктов и услуг
Концепция жизненного цикла продукта или услуги подразумевает, что они ограниченны, по крайней мере, во времени.
Жизненный цикл продукта определяется как модель движени
Жизненный цикл информационных технологий
Жизненный цикл информационных технологий является моделью их создания и использования, отражающей различные состояния информационных технологий, начиная с момента возникно
Результаты освоения темы
Изучая данную тему, вы будете знать:
основные термины в данной области; что такое безопасность и защита и как они осуществляются; какие бывают несанкционированные д
Общие положения защиты информации
Практически вся современная информация готовится или может быть достаточно легко преобразована в машиночитаемую форму. Характерной особенностью такой информации является возможность посторонних лиц
Основные виды и причины несанкционированных воздействий на информацию, здания, помещения и людей
Несанкционированные действия наинформацию, здания, помещения и людей могут быть вызваны различными причинами и осуществляться с помощью различных методов воздействия. Подобные действия могут быть о
Воздействия на информацию, здания, помещения, личную безопасность пользователя и обслуживающий персонал
Типичными причинами нарушения безопасности на объекте являются:
1) ошибки индивидов или неточные их действия;
2) неисправность и (или) отказ используемого оборудования;
Основные средства и методы защиты информации
Средства и методы защиты информации обычно делят на две большие группы: организационные и технические. Подорганизационными подразумеваются законодательные, административные
Криптографические методы защиты информации
Криптография - это тайнопись, система изменения информации с целью её защиты от несанкционированных воздействий, а также обеспечения достоверности передаваемых данных.
Биометрические методы защиты
Наиболее чётко обеспечивают защиту средства идентификации личности, использующие биометрические системы. Понятие “биометрия” определяет раздел биологии, занимающийся количественным
Сетевые методы защиты
Для защиты информации в информационных компьютерных сетях используют специальные программные, технические и программно-технические средства. С целью защиты сетей и контроля доступа в них используют
Мероприятия по обеспечению сохранности и защиты
Комплексно мероприятия по обеспечению сохранности и защиты информации, объектов и людей включают организационные, физические, социально-психологические мероприятия и инженерно-технические средства
Применение информационных технологий
Выделим наиболее важные направления применения информационных технологий:
1. Ориентация на активное и эффективное использование информационных ресурсов общества, являющихся важным с
Обработки текстовой информации
Текстовая информация может возникать из различных источников и иметь различную степень сложности по форме представления. В зависимости от формы представления для обработки текстовых сообщений испол
Обработка табличных данных
Пользователям в процессе работы часто приходится иметь дело с табличными данными при создании и ведении бухгалтерских книг, банковских счетов, смет, ведомостей, при составлении планов и распределен
Обработка экономической и статистической информации
Экономическая информация используется главным образом в сфере материального производства. Она служит инструментом управления производством и по функциям управления подразделяется на: на прогнозную,
Средства оргтехники и полиграфии для копирования и тиражирования информации
Разновидностью информационных технологий является копирование и тиражирование информации, включающее изготовление и обработку, копирование и тиражное размножение информации.
С древних врем
Методы копирования и тиражирования информации
Широко применяющиеся средства КМТ используют методы репрографии и оперативной полиграфии, состав которых представлен на Рис. 7.1.
Метод репрографии предназначен для непосредственног
Трафаретная, офсетная и гектографическая печать
В полиграфии (в т.ч. оперативной) применяют оборудование и методы, обеспечивающие высокое качество печати и значительные тиражи выпускаемых документов за счёт применения печатных форм – трафаретов.
Копировально-множительная техника
По принципу действия КМТ делят на: светокопировальные, электрографические, термографические; использующие методы трафаретной и офсетной печати с мокрым, полусухим и сухим способами формирова
Оргтехника
Средства оргтехники, применяемые на конкретном рабочем месте, называют “малой оргтехникой”. Кроме так называемой “офисной мелочи” (карандаши, ручки, ластики, дыроколы, стиплеры, клей, скрепк
Средства обработки документов
Средства обработки документов состоят из:
фальцевальных, биговальных и бумагорезательных машин (фольдеры); листоподборочных и сортировальных машин и устройств;
Оборудование для резки бумаги
Бумагорезательные аппараты (резаки) используют на любом этапе работы, например, резки рулонной или иной бумаги. С их помощью режут отпечатанные листы перед брошюровкой или тираж, если на каж
Результаты освоения темы
Изучая данную тему, вы будете знать:
что такое компьютерная программа и для чего нужны компьютерные программы; какое бывает программное обеспечение компьютерных информационн
Программное обеспечение информационных технологий
Совокупность программ, используемых при работе на компьютере, составляет его программное обеспечение.
Программное обеспечение (ПО) –
Открытые системы
Вычислительная техника развивалась стремительно. В результате было создано множество устройств и программ к ним. Такое обилие различных программно-аппаратных средств и систем привело к несовместимо
Распределенные базы данных
Распределённые базы данных (англ. "Distributed DataBase", DDB) представляют определённым образом связанные между собой БД, рассредоточенные на какой-либо тер
Результаты освоения темы
Изучая данную тему, вы будете знать:
кто такие пользователи (потребители) информационных технологий и ресурсов; для чего нужен пользовательский интерфейс; как оцени
Пользовательский интерфейс
Взаимодействуя с устройствами вычислительной техники, пользователи как бы разговаривают с ними (ведут диалог). Реакция ЭВМ на запросы и команды пользователей носит формальный характер. Поэтому прог
Результаты освоения темы
Изучая данную тему, вы будете знать:
как графическая информация отображается на экране дисплея компьютера и что такое графический пользовательский интерфейс; какие ис
Результаты освоения темы
Изучая данную тему, вы будете знать:
что такое гипертекст и гипертекстовые информационные технологии; как и какие языки используются для гипертекстовой разметки документов;
Технологии мультимедиа
Мультимедиа (англ. "multimedia" от лат. "multum" - много и "media", "medium" - средоточие; средства) - это элек
Проекционное оборудование. Мультимедиапроекторы
Средства информирования
Результаты освоения темы
Результаты освоения темы
Обычно их делят по территориальному признаку на региональные и глобальные сети
Правила работы с пакетами данных называются протоколом TCP
Web-технологии
Результаты освоения темы
Результаты освоения темы
Общий курс Лектор: проф., д.ф.-м.н. Е.И.Веремей
В общем случае
Основными средствами информирования являются различные автоответчики, стенды и табло. Простейшие автоответчикипредставляют аудиовоспроизводящие устройства (магнитофоны-приставки), подключённ
Изучая данную тему, вы будете знать:
об автоматизированных системах и автоматизированных информационных системах, их видах; об основных принципах автоматизации информационны
Изучая данную тему, вы будете знать:
что в себя включают сетевые информационные технологии; какие бывают виды сетевых информационных технологий; как коллективно раб
Региональные сети обычно охватывают административную территорию города, области и т.п., а также производственные и иные объединения, расположенные в нескольких районах
TCP-протокол (Transmission Control Protocol) служит для организации надёжной полнодуплексной связи между конечными пунктами (узлами) обмена информацией в Интернете. Он преобразует сообщения
“Web” (в дальнейшем – веб) построен на основе применения гипертекста. С его помощью создаются веб-страницы, которые размещаются на веб-сайтах. Таким образом, веб-технологии в значительной м
Электронная доска объявлений (англ. “Bulletin Board System”, BBS). Обычно так называют небольшие системы с доступом по телефонным каналам связи, предназначенные для местных пользователе
Изучая данную тему, вы будете знать:
для чего нужна интеграция информационных технологий; как она осуществляется и что является её базой; о корпоративных информацио
Изучая данную тему, вы будете знать:
что такое геоинформационная система и как она строится; какие существуют технологии распространения информации; о методах адресЛитература