Понятие конвейеров ввода и вывода графической информации

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

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

1. Определение состояния объектов (Situation modeling);

2. Определение соответствующих текущему состоянию геометрических моделей (Geometry generation) ;

3. Разбиение геометрических моделей на примитивы (Tesselation) ;

4. Привязка текстур и освещения (Texture and light definition);

5. Видовые геометрические преобразования (Projection);

6. Отбрасывание невидимых примитивов (Culling);

7. Установка примитивов (Setup);

8. Закраска примитивов (Fill);

9. Финальная обработка (Post processing);

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

Рис. 1– Конвейер 3D визуализации.

Программируемый интерфейс приложений (API, Application Programming Interface) состоит из функций, управляющих 3D конвейером на программном уровне, но при этом может использовать преимущества аппаратной реализации 3D, в случае наличия этой возможности. Если имеется аппаратный ускоритель, API использует его преимущества, если нет, то API работает с оптимальными настройками, рассчитанными на самые обычные системы. Таким образом, благодаря применению API, любое количество программных средств может поддерживаться любым количеством аппаратных 3D ускорителей.

Для 3D приложений существуют следующие API:

• Microsoft Direct3D

• Criterion Renderware

• Argonaut BRender

• Intel 3DR

Компания Apple продвигает свой собственный интерфейс Rave, созданный на основе их собственного API Quickdraw 3D.

66. Уровни представления данных

Цель трехуровневой архитектуры заключается в отделении пользовательского представления БД от ее физического представления. Причины:

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

• Внутренняя структура БД не должна зависеть от таких изменений физических аспектов хранения информации, как переключение на новое устройство хранения;

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

• Администратор БД должен иметь возможность изменять структуру хранения данных в базе на свое усмотрение, не оказывая влияния на пользовательское представление;

• Администратор БД должен иметь возможность модернизировать концептуальную структуру БД без какого-либо влияния на всех пользователей.

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

• концептуальный

• логический

• физический

Концептуальный уровень представления данных в виде понятий.

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

Физический – представление данных в виде совокупности бит, байт, хранящихся в файлах.

67. Средства моделирования и модели, применяемые в процессе проектирования АСОИУ

68. Основные понятия исследования операций и системного анализа (=3)

69. Самосинхронизирующиеся коды

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

Код RZ (Return to Zero – с возвратом к нулю) – этот трехуровневый код получил такое название потому, что после значащего уровня сигнала в первой половине битового интервала следует возврат к некоему "нулевому", среднему уровню (например, к нулевому потенциалу). Переход к нему происходит в середине каждого битового интервала. Логическому нулю, таким образом, соответствует положительный импульс, логической единице – отрицательный (или наоборот) в первой половине битового интервала.

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

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

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

Как и в RZ, обязательное наличие перехода в центре бита позволяет приемнику манчестерского кода легко выделить из пришедшего сигнала синхросигнал и передать информацию сколь угодно большими последовательностями без потерь из-за рассинхронизации. Допустимое расхождение часов приемника и передатчика может достигать 25%.

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

Бифазный код часто рассматривают как разновидность манчестерского, так как их характеристики практически полностью совпадают. Данный код отличается от классического манчестерского кода тем, что он не зависит от перемены мест двух проводов кабеля. Особенно это удобно в случае, когда для связи применяется витая пара, провода которой легко перепутать. Именно этот код используется в одной из самых известных сетей Token-Ring компании IBM.

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

70. Стандарты в области разработки графических систем

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

Инвариантность– обеспечивается на основе создания математических моделей геометрических объектов и алгоритмов их преобразований, инвариантных по отношению к проектируемым объектам. С точки зрения инвариантности относительно объекта проектирования можно выделить 4 уровня систем КГ:

1) Объектно-ориентированные, - в их функцию входит связь с проектирующими системами САПР.

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

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

4) Приборно-ориентированные системы, - обеспечивают формирование вывода объекта на графическое устройство.

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

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

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

71. Понятия схемы и подсхемы данных

МЕСТАМИ ХУЙНЯ СОБАЧЬЯ

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

Подсхема данных – часть описания БД с учетом представления отдельного пользователя или логического проекта системы.

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

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

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

72. Аналитическое моделирование

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

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

численным, когда не удается найти решение уравнений в общем виде и их решают для конкретных начальных данных;

качественным, когда при отсутствии решения находят некоторые его свойства.

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

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

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

(1.1)

Это линейное дифференциальное уравнение(ДУ) и является аналитической моделью данной простой линейной цепи. Его аналитическое решение, при начальном условии, означающем разряженныйконденсаторв момент начала моделирования, позволяет найти искомую зависимость – в виде формулы:

(1.2)

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

Безусловно, нахождение аналитических решений при аналитическом моделировании оказывается исключительно ценным для выявления общих теоретических закономерностей простых линейных цепей, систем и устройств. Однако его сложность резко возрастает по мере усложнения воздействий на модель и увеличения порядка и числа уравнений состояния, описывающих моделируемый объект. Можно получить более или менее обозримые результаты при моделировании объектов второго или третьего порядка, но уже при большем порядке аналитические выражения становятся чрезмерно громоздкими, сложными и трудно осмысляемыми. Например, даже простой электронный усилительзачастую содержит десятки компонентов. Тем не менее, многие современные СКМ, например, системы символьной математики Maple, Mathematica или среда MATLAB способны в значительной мере автоматизировать решение сложных задач аналитического моделирования.

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

73. Методологические основы теории принятия решений (=8)

74. Способы контроля правильности передачи информации

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

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

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

Суммы по модулю двух всех байтов пакета (при этом однократные ошибки обнаруживаются с вероятностью 100%, двукратные с вероятностью 7/8). Искажение нескольких битов выявляется при помощи такого метода достаточно плохо. Достоинство метода контрольной суммы – простота вычисления.

Арифметическая сумма всех байтов или слов пакета. При вычислении отбрасываются старшие разряды для сохранения разрядности контрольной суммы (8 или 16). Однократные ошибки обнаруживаются с вероятностью 100% двукратные с вероятностью 31/32 (в худшем случае). Такая наихудшая ситуация наблюдается, когда в каждом из 8-ми разрядов всех байт пакета присутствует половина логических нулей и половина логических единиц, двукратная ошибка не выявляется, если в одном разряде один из битов переходит из нуля в единицу, а другой бит в этом же разряде из единицы в ноль, что не меняет общей суммы. Арифметическая сумма также легко вычисляется программным методом.

Циклическая контрольная сумма. Применение данного метода связывают с необходимостью повышения вероятности обнаружения ошибки. При вычислении циклической контрольной суммы весь пакет рассматривается как двоичное число разрядности N, где N – количество бит в пакете. Для вычисления контроля суммы это число делится по модулю двух на некоторое постоянное число выбранное специальным образом. Частное от деления отбрасывается, а остаток используется в качестве контроля суммы. Этот метод выявляет однократные ошибки с вероятностью 100%, а любое другое количество ошибок с вероятностью , где n – количество разрядов контрольной суммы. В качестве делителя выбирается число простое (в смысле деления по модулю двух), а его разрядность берется на единицу больше, чем требуемая разрядность контрольной суммы.

75. Технические средства компьютерной графики: мониторы, графические адаптеры, плоттеры, принтеры, сканеры

Мониторы.

Монитор (дисплей) является универсальным устройством вывода информации.

Классификация:

• ЭЛТ – на основе электронно-лучевой трубки (англ. cathode ray tube,

CRT);

• ЖК – жидкокристаллические мониторы (англ. liquid crystal display,

LCD);

• плазменный – на основе плазменной панели;

• проекционный – видеопроектор и экран, размещённые отдельно или объединённые в одном корпусе (как вариант – через зеркало или систему зеркал);

• OLED-монитор — на технологии OLED (англ. organic light-emitting diode – органический светоизлучающий диод);

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

Основные параметры мониторов:

• вид экрана — квадратный или широкоформатный (прямоугольный);

• размер экрана — определяется длиной диагонали;

• разрешение — число пикселей по вертикали и горизонтали;

• глубина цвета — число отображаемых цветов (от монохромного до 32-битного);

• размер зерна или пикселя;

• частота обновления экрана;

• скорость отклика пикселей (не для всех типов мониторов).

Графические адаптеры.

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

Обычно видеокарта выполнена в виде печатной платы (плата расширения) и вставляется в разъём расширения, универсальный либо специализированный (AGP, PCI Express). Также широко распространены и встроенные (интегрированные) в системную плату видеокарты — как в виде отдельного чипа, так и в качестве составляющей части северного моста чипсета или ЦПУ; в этом случае устройство, строго говоря, не может быть названо видеокартой.

Видеокарта состоит из следующих частей: графический процессор, видеоконтроллер, видео-ПЗУ, видео-ОЗУ, ЦАП, коннектор и система охлаждения.

Плоттеры.

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

Типы графопостроителей:

• рулонные и планшетные;

• перьевые, струйные и электростатические;

• векторные и растровые.

Назначение графопостроителей: высококачественное документирование чертёжно-графической информации.

Принтеры.

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

Принтеры бывают струйные, лазерные, матричные и сублимационные; по цвету печати: чёрно-белые (монохромные) и цветные. Иногда из лазерных принтеров выделяют в отдельный вид светодиодные принтеры.

Сканеры.

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

Сканеры бывают различных конструкций:

• ручной,

• планшетный,

• барабанный,

• проекционный.

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

76. Классификация информационно-вычислительных сетей (=5)

77. Планирование имитационных экспериментов с моделями

Теория планирования эксперимента сложилась в шестидесятые годы двадцатого века благодаря работам выдающегося английского математика, биолога, статистика Рональда Айлмера Фишера (1890-1962 гг.). Несколько позже сложилась теория и практика планирования имитационных экспериментов.

Сущность и цели планирования эксперимента

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

Для организации экспериментов наиболее важно следующее.

1. Простота повторений условий эксперимента.

2. Возможность управления экспериментом, включая его прерывание и возобновление.

3. Легкость изменения условий проведения эксперимента (воздействий внешней среды).

4. Исключение корреляции между последовательностями данных, снимаемых в процессе эксперимента с моделью.

5. Определением временного интервала исследования модели ( ).

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

Что же такое компьютерный (машинный) эксперимент?

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

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

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

План эксперимента определяет:

• объем вычислений на компьютере;

• порядок проведения вычислений на компьютере;

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

Планирование экспериментов имеет следующие цели:

• сокращение общего времени моделирования при соблюдении требований к точности и достоверности результатов;

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

• создание структурной основы процесса исследования.

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

• стратегическое планирование;

• тактическое планирование.

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

Тактическое планирование обеспечивает достижение заданных точности и достоверности результатов.

78. Задачи выбора решений (=13)

79. Способы конструирования и верификации программ

Способы конструирования программ:

Псевдокод — это искусственный и неформальный язык, который помогает программисту разрабатывать алгоритмы. Псевдокод используется для разработки алгоритмов, которые потом должны быть преобразованы в структурированную программу на C++. Псевдокод подобен разговорному языку; он удобный и дружелюбный, но это не язык программирования. Программы на псевдокоде не могут выполняться на компьютере. Их назначение — помочь программисту «обдумать программу» прежде, чем по­пытаться написать ее на таком языке программирования, как C++. Тщательно подго­товленная программа на псевдокоде может быть легко преобразована в соот­ветствующую программу на C++. Во многих случаях для этого достаточно просто заменить предложения псевдокода их эквивалентами в языке С++. Псевдокод включает только исполняемые операторы — те, которые вы­полняются, когда программа переведена из псевдокода на C++ и запущена на счет. Объявления не являются исполняемыми операторами.

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

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

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

Часто оба метода применяются одновременно:

Сверху-вниз: при объединении в единое целое;

Снизу-вверх: при разработке общих хорошо отлаженных блоков.

Способы верификации программ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

80. Способы коммутации в сетях (=10)

81. Оценка точности и достоверности результатов моделирования

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

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

Число испытаний N определяет точность получаемых результатов моделирования. Если необходимо оценить величину случайного параметра Х по результатам моделирования x_{1, x2, … xn,} то за оценку следует брать величину хср. Но из-за случайности хср будет отличаться от истинного значения параметра Х

а если мы зададимся какой-то точностью оценки (назовем ее -  ), то должно выполняться неравенство:

|Х-хср|<

 - точность оценки величины случайного параметра Х; (половина ширины доверительного интервала)

хср - среднее значение результатов моделирования x1, x2, … xn.

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

P(|Х-xср|<)=

 - уровень значимости, доверительная вероятность, (1-) - достоверность.

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

α и ε - задаем сами.

Определение количества реализаций для оценки вероятности наступления события.

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

Пусть целью моделирования будет определение вероятности наступления некоторого события А, определяющего какое-то состояние моделируемой системы. В любой из реализаций процесс наступления события А является случайной величиной, которая может приобретать значение x1=1 с вероятностью р (т.е. событие наступило) и x2=0 с вероятностью 1-р.

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

Центральная предельная теорема: распределение суммы независимых наблюдений n различных СВ стремится к нормальному, при n, независимо от характера распределения СВ.

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

Число степеней свободы: ν = k - 1 - m, (k - число значений или интервалов СВ; т - число определяемых параметров).

Для определения вероятности р делают пробные испытания (N=50…100) и получают частоту m/N, после чего определяют конечное количество испытаний.

р=m/N

Определение количества реализаций для оценки среднего значения случайной величины.

Случайная величина имеет математическое ожидание  и дисперсию ².

На основе центральной предельной теоремы количество реализаций N для оценки среднего значения случайной величины будет

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

Если мы имеем представление о пределах, в которых может изменяться отклик системы, то грубую оценку величины σ можно получить из условия, что размах переменной отклика равен примерно 4σ: Если известен разумный размах переменной отклика - d, то σ=d/4.

Для определения оценки 2 проводят 50…100 испытаний и определяют по формуле:

82. Функции полезности и критерии при принятии решений (17 – первый вариант)

Полезность – некоторое число, приписываемое лицом, принимающим решение, каждому возможному исходу. Функция полезности Неймана-Моргенштерна для лица, принимающего решение, (ЛПР) показывает полезность, которую он приписывает каждому возможному исходу. У каждого ЛПР своя функция полезности, которая показывает его предпочтение тем или иным исходам в зависимости от его отношения к риску.

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

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

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

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

Принятие решений в условиях определенности характеризуется однозначной или детерминированной связью между принятым решением и его результатом. Это наиболее простой класс задач принятия решений, когда состояние, которое будет определённо иметь место, известно заранее, т.е. до выполнения действия. ЛПР в данном случае может всегда точно предсказать последствия от выбора каждого действия. Это фактически означает, что число состояний сводится к одному, т.е.m= 1.

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

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

1) критерий равновозможных состояний (критерий Лапласа):

2) критерий максимина Вачьда:

3) критерий пессимизма-оптимизма Гурвица;

4) критерий минимакса сожалений Сэвиджа.

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

83. Универсальные ОС и ОС специального назначения (=26)

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

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

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

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

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

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

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

Операционные системы специального назначения

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

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

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

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

ОС должны осуществлять контроль за прохождением блока данных в течение всего периода его пребывания в сети;

необходимы программные и аппаратные средства, предотвращающие потерю или искажения блоков данных при одновременном нахождении их в вычислительной сети;

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

84. Модульные программы, пример.

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

Модуль характеризуют:

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

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

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

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

обозримый по размеру и сложности программный элемент.

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

Модульная структура программных продуктов

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

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

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

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

принятие основных решений в алгоритме выносится на максимально "высокий" по иерархии уровень;

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

Пример

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

Какие модули можно выделить в данной задаче?

Есть следующие группы задач:

ввод-вывод (модуль file)

геометрия (модуль geometry) (для рассчета расстояния между двумя точками и нахождения площади по трем координатам)

поиск треугольников наибольшей площади (модуль search)

85. Одноранговые сети

Однора́нговая, децентрализо́ванная или пи́ринговая (англ. peer-to-peer, P2P — равный к равному) сеть — это компьютерная сеть, основанная на равноправии участников. Часто в такой сети отсутствуют выделенные серверы, а каждый узел (peer) является как клиентом, так сервером. В отличие от архитектуры клиент-сервера, такая организация позволяет сохранять работоспособность сети при любом количестве и любом сочетании доступных узлов. В этом случае, операционная система, называемая одноранговой, не только позволяет обращаться к ресурсам других компьютеров, но и предоставляет собственные ресурсы в распоряжение пользователей других компьютеров. Например, если на всех компьютерах сети установлены и клиенты, и серверы файловой службы, то все пользователи сети могут совместно применять файлы друг друга. Компьютеры, совмещающие функции клиента и сервера, называют одноранговыми узлами.

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

Одноранговая сеть характеризуется рядом стандартных решений:

компьютеры расположены на рабочих столах пользователей;

пользователи сами выступают в роли администраторов и собственными силами обеспечивают защиту информации;

для объединения компьютеров в сеть применяется простая кабельная система.

Одноранговая сеть вполне подходит там, где:

количество пользователей не превышает нескольких человек;

пользователи расположены компактно;

вопросы защиты данных не критичны;

потоки данных невелики;

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

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

Преимущества сети	Недостатки сети
Простая и дешевая в создании	Отсутствует возможность административного управления пользователями и ресурсами
Не требует управляющих компьютеров	Каждый пользователь должен самостоятельно следить за состоянием программного обеспечения
Работа сети не зависит от работоспособности узлов сети	За обновление баз данных и другого программного обеспечения отвечает пользователь
легкость в установке и настройке	Отсутствует централизованное хранилище ресурсов
	Низкий уровень защиты информации Возможность общего доступа не более 10 пользователям.

86. Инструментальные средства и языки моделирования

ХУЙНЯ – комментарий Макса

Чтобы реализовать на ЭВМ модель сложной системы, нужен аппарат моделирования, который в принципе должен быть специализированным. Он должен предоставлять исследователю:

- удобные способы организации данных, обеспечивающие простое и эффективное моделирование;

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

- возможность имитации стохастических систем, т.е. процедур генерации ПСЧ и вероятностного (статистического) анализа результатов моделирования;

- простые и удобные процедуры отладки и контроля программы;

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

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

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

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

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

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

Язык программирования GPSS.

Язык GPSS представляет собой интерпретирующую языковую систему, применяющуюся для описания пространственного движения объектов. Такие динамические объекты в языке GPSS называются транзактами и представляют собой элементы потока. В процессе имитации транзакты «создаются» и «уничтожаются». Функцию каждого из них можно представить как движение через модель М_мс поочередным воздействием на ее блоки. Функциональный аппарат языка образуют блоки, описывающие логику модели, сообщая транзактам, куда двигаться и что делать дальше. Данные для ЭВМ подготавливаются в виде пакета управляющих и определяющих карт, который составляется по схеме модели, набранной из стандартных символов. Созданная GPSS-программа, работая в режиме интерпретации, генерирует и передает транзакты из блока в блок в соответствии с правилами, устанавливаемыми блоками. Каждый переход транзакта приписывается к определенному моменту системного времени.

Язык программирования SIMULA

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

Основные свойства языков имитационного моделирования

Возможность моделирования стохастических факторов.

Управление модельным временем.

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

Наличие средств управления имитационным экспериментом.

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

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

ЯИМ

Универсальные алгоритмические языки Проблемно-ориентированные языки

Специализированные языки

Моделирование Моделирование

непрерывных дискретных

процессов процессов

Dynamo-III

CSMP Схема Схема Схема

DIHYSYS событий активностей процессов

SIMSCRIPT-II CSL SIMULA

SLAM-II ESL ASPOL

GASP-V GPSS

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

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

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

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

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

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

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

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

87. Классы задач исследования операций (=22)

88. Классификация ОС (=31)

89. Линейные списки и способы их реализации, пример программы

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

Линейный список F, состоящий из элементов D1,D2,...,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически (см.рис.1).

D1		D2		D3		...		Dn
Рис.1. Изображение линейного списка.

Например, F1=<2,3,1>,F2=<7,7,7,2,1,12>, F3=< >. Длина списков F1, F2, F3 равна соответственно 3,6,0.

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

• найти элемент с заданным свойством;

• определить первый элемент в линейном списке;

• вставить дополнительный элемент до или после указанного узла;

• исключить определенный элемент из списка;

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

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

Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. Рассмотрим простейшие варианты этих методов для списка с целыми значениями F=<7,10>.

При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида

float d[100]; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d[0]=7; d[1]=10; l=2;

Полученный список хранится в памяти согласно схеме на рис.13.

l:	2
d:	7	10			...
	[0]	[1]	[2]	[3]		[98]	[99]
Рис. 2 Последовательное хранение линейного списка.

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