1. Общая характеристика процесса проектирования АСОИУ

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

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

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

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

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

• обобщенный анализ обследования объекта автоматизации, функций существующей АСОИУ (если требуется модификация системы)

• совокупность предварительных исходных требований

• оценки имеющихся и доступных ресурсов

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

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

• проекты планов жизненного цикла, гарантии качества, защиты и безопасности системы

• результаты анализа существующей и возможной инструментальной среды разработки

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

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

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

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

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

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

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

2. Назначение и функции ОС

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

Функции ОС:

1) предоставление пользователю-программисту более удобной в использовании «виртуальной машины», скрывающей реальное оборудование;

2) обеспечение эффективного использования компьютера путем рационального управления его ресурсами.

Управление ресурсами включает решение двух общих, не зависящих от типов ресурсов задач: планирование ресурсов и мониторинг ресурсов.

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

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

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

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

Процесс — любое действие в системе (если система работает — в ней уже происходит некоторый процесс).

Операция — часть процесса, наделенная свойствами всей системы; управляемое мероприятие, выполняющее определенную цель, сопоставимую с целью всей системы. Например, операция составления расписания учебных занятий для учебного процесса в системе «университет».

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

Характеристика этапов:

1. повод для изучения и совершенствования системы — фиксация симптомов, которые показывают проблемы в работе системы

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

3. важнейшим этапом исследования системы является четкая формулировка проблемы, которая присутствует на данному уровне жизнедеятельности системы;

4. качественный системный анализ — расщепление целостной системы (операции) на отдельные элементы (сущности)

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

• устанавливается критерий K — величина, количественно измеряющая степень достижения цели системы (операции)

• вводятся количественные внутренние параметры системы, измеряющие факторы, участвующие в описании системы/операции

• множество параметров разбивается на две части: неуправляемые (константы) (a1, a2, …, ak) = A и управляемые (переменные) (x1, x2, …, xn) = X

6. суть математического моделирования — установление количественных связей между K, A, X в виде операционной модели (ОМ). Первая часть ОМ — модель целевой функции, устанавливающей зависимость K = f(X, A), для которой требуется достигнуть минимального или максимального значения. Это выражение определяет смысл оптимизации системы. Вторая часть ОМ — математическое описание ограничений на выбор переменных X, в общем виде записываемых как phii(X, A) <= 0, I = 1, m. Каждая функция phii называется функцией ограничения. Полученная модель позволяет поставить задачу оптимизации следующим образом: найти такие управляемые переменные X, которые удовлетворяли бы вышеприведенной системе ограничений и обеспечивали наилучшее значение критерия K.

7. Решение поставленной математической задачи требует привлечения методов оптимизации.

8. Сопоставляя полученное решение с постановкой задачи, можно обнаружить противоречия, причиной которой может быть пренебрежение рядом ограничений или ошибками в построенной модели. Для установления приемлемости решения привлекается ЛПР.

9. Найденное оптимальное решение X* позволяет подготовить управляющее решение в форме документа для ЛПР.

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

4. Декомпозиция отношений

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

Аппарат нормализации отношений разработан Коддом. В нем определены различные нормальные формы. Каждая нормальная форма ограничивает типы допустимых функциональных зависимостей отношений. Кодд выделил три нормальные формы: 1, 2, 3НФ, а сегодня определены НФБК, 4НФ, 5НФ.

Теорема Хеза: ПустьR(A,B,C) является отношением с атрибутамиA,B,C. Если оно удовлетворяет зависимостиA→B, тоRравно соединению его проекций (A,B) и (A,C).

1НФ– Отношение находится в 1НФ, если значения всех атрибутов атомарные, то есть значение атрибута не должно быть множеством или повторяющейся группой.

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

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

Пример 1:

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

Поставщик	Товар	Цена
Иванов	Мыло	2000
Иванов	Сахар	2500
Петров	Мыло	2000
Петров	Сыр	20000

Ключ: Поставщик, товар, тогда по определению ключа

Поставщик, товарцена

Кроме этого имеется зависимость атрибута «цена» от части ключа:

товар цена, значит отношение не в во 2НФ.

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

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

R₁(Поставщик, товар);R₂(товар, цена). ОтношениеR1 имеет кортежи:(«Иванов,мыло», «Иванов , сахар», «Петров,мыло», «Петров, сыр»); отношениеR2 имеет кортежи:(«мыло,2000», «сахар, 2500», «сыр, 20000»). Избыточность хранения устранена, аномалии устранены, кроме этого декомпозиция выполнена без потери информации.

В общем случае при наличии частичной ФЗ для приведения отношения Rк 2 НФ выполняется дважды операция проекции, в результате чего получается два отношения: в первое отношение включается часть ключа и все не ключевые атрибуты, от неё зависящие, во второе отношение-ключ и оставшиеся не ключевые атрибуты.

Пример 2:

1	2	3	4	5
1	2	20	1	5
2	2	20	2	1
3	3	30	2	1
3	4	40	1	5

Ключи: <1,2>,<1,3>,<1,4>,<1,5>,<2,4>,<2,5>,<3,4>,<3,5>

1, 23; 23;

В результате нормализации получим два отношения:

R₁(2, 3)

2	3
2	20
3	30
4	40

R₂(1, 2, 4, 5)

1	2	4	5
1	2	1	5
2	2	2	1
3	3	2	1
3	4	1	5

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

Анализируем второе отношение:

Ключи: <1,2>,<1,4>,<1,5>,<2,4>,<2,5>.

<1,4> 5; 45 – то есть частичная функциональная зависимость. Разбиваем отношениеR2 наR3 иR4:

R3(1,2,4)

3
1	2	4
1	2	1
2	2	2
3	3	2
3	4	1

Отношение R4 включает только два кортежа, так как два других удаляются.

R4(4,5)

4
4	5
1	5
2	1

Ответ: R1(2,3);R3(1,,2,4);R4(4,5).

3НФ– Отношение находится в 3НФ, если оно находится в 2НФ и отсутствуют транзитивные зависимости не ключевых атрибутов от ключа.

Иными словами, если выполняется совокупность условий:

A→B; В → С;

С → А; В → А; С → B, то в отношении существует транзитивная зависимость неключевых атрибутов от ключаAи отношение не находится в 3 НФ. Если хотя бы одно из условий не выполняется, то такой зависимости между атрибутамиA,B,Cнет. Причем атрибутыA,B,Cмогут быть составными.

Пример 1:

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

Фирма	Склад	Объем
МЕНАТЕП	МКЧ	200
ИКС	ДП	600
АСКО	ДП	600
ПАРУС	СК	200

Ключ в отношении атомарный: <фирма>

фирмасклад;складобъем;

объемфирма;складфирма;объемсклад.

По определению, это отношение не в 3 НФ, в результате чего возникает избыточность хранения информации. Нормализация отношения путем выполнения дважды операций проекции устраняет избыточность и приводит отношение к 3НФ: R₁(фирма, склад);R₂(склад, объем).

Такое разбиение является разбиением без потери информации. Если бы мы выполнили декомпозицию таким образом: R₁(фирма, склад);R₂(фирма, объем), то при соединении этих отношений было бы непонятно, к какому складу относится фирма, если скла имеет одинаковый объем, то есть происходит потеря информации.

Таким образом, в общем случае при нормализации отношения Rпри переходе к 3НФ, получается два отношения-R1 иR2. В первое отношение включаются атрибутыBиC, во второе –A,Bи все оставшиеся атрибуты исходного отношенияR.

Пример 2:

1	2	3
1	2	1
2	2	1
3	3	2
4	4	1

Ключи: <1>

1 2 ; 23; 31;32 ;21, поэтому необходима нормализация, в результате которой получаем:R1(1,2);R2(2,3).

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

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

Информационно-вычислительные сети, в зависимости от территории, ими охватываемой, подразделяются на:

• локальные (ЛВС или LAN — Local Area Network);

• региональные (РВС или MAN — Metropolitan Area Network);

• глобальные (ГВС или WAN — Wide Area Network).

Локальные – абоненты находятся на небольшом (до 10-15 км) расстоянии друг от друга. ЛВС объединяет абонентов, расположенных в пределах небольшой территории. Обычно такая сеть привязана к конкретному объекту.

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

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

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

По принципу организации передачи данных сети можно разделить на две группы:

• последовательные;

• широковещательные.

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

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

По топологии ИВС могут быть:

• шинные (линейные, bus);

• кольцевые (петлевые, ring);

• радиальные (звездообразные, star);

• распределенные радиальные (сотовые, cellular);

• иерархические (древовидные, hierarchy);

• полносвязные (сетка, mesh);

• смешанные (гибридные).

6. Структура информационно-логической модели АСОИУ

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

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

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

источники информации

входные, выходные, основные и промежуточные массивы информации

процедуры обработки и преобразования информации

процедуры выработки решений

потребители информации

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

7. Операционные системы и мультипрограммирование (Оля, где мультипрограммирование? И зачем столько всего? Почему так много про СРВ?)

Основные требования, предъявляемые к операционным системам (ОС), используемым в АСУ и СРВ:

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

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

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

ОС, удовлетворяющие требованию масштабируемости, называются встраиваемыми операционными системами.

ОС, предназначенные для использования в АСУ и СРВ, обычно удовлетворяют обоим требованиям.

3.1.1. Архитектурные особенности

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

Рис. 3.1.

Многослойная структура программного обеспечения Практически все современные процессоры (Intel 80x86/Pentium, Motorola MC 68K, PowerPC и т.п.) поддерживают как минимум два режима выполнения программного кода:

• «привилегированный режим» (или «режим супервизора», или «режим ядра», или «kernel mode», или «защищенный режим»);

• «непривилегированный режим» (или «режим приложений»). Основное отличие между ними заключается в том, что программы, работающие в режиме супервизора, имеют непосредственный доступ ко всем ресурсам ЭВМ - ко внешним устройствам, к оперативной памяти по физическим адресам и пр.; программы же режима приложений работают в виртуальной среде, сформированной программами режима супервизора.

Различают два больших класса архитектур операционных систем: «монолитная» и «микроядерная» (см. рис. 3.2).

Рис. 3.2.Варианты архитектур операционных систем

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

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

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

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

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

• предельное время выполнения запроса прикладной программы к ядру ОС;

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

3.1.2. Организация многозадачности

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

• очередь готовых для исполнения задач;

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

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

Рис. 3.3. Граф многозадачности

Существуют два основных способа организации многозадачности:

• кооперативный;

• вытесняющий.

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

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

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

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

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

• фоновые – задачи, которые выполняются по мере наличия свободного процессорного времени

Эффективность системы реального времени зависит и от использованной дисциплины диспетчеризации.

1. Дисциплина Round Robin (RR, «карусельная», «круговорот») – наиболее проста. Предполагается, что все задачи имеют равные и постоянные приоритеты, соответственно, очередь устроена по правилу: «FIFO - первый пришел, первый вышел».

Рис. 3.5. Пример работы в режиме «RR»

Данная дисциплина не позволяет учитывать «важность» задач.

2. Дисциплина Rate Monotonic (RM) - алгоритм с монотонно возрастающей частотой выполнения задач. Правила:

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

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

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

Рис. 3.6. Пример работы в режиме «RM»

Для дисциплины RM критерий корректности имеет вид (2 1) 1/ ≤ ⋅ − N µ N .

3. Дисциплина Earliest Deadline First (EDF) – алгоритм приоритетности раннего завершения. Правила:

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

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

Рис. 3.7. Пример работы в режиме «EDF»

Доказано, что дисциплины RM и EDF обеспечивают операционным системам реального времени выполнение всех задач в указанные сроки.

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

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

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

Особенности задачи выбора решений:

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

• часто множество альтернатив сначала неизвестно, поэтому говорят о генерации альтернатив в процессе решения задачи;

• оценка ценности каждой альтернативы часто не сводится к сравнению количественных параметров, поэтому в ТПР применяют специальные методы измерения полезности альтернатив;

• критерий является не скалярной величиной, а вектором. Встает вопрос о многокритериальной оптимизации;

• во многих задачах присутствуют нечеткие переменные и нечеткие критерии, поэтому в ТПР есть специальный раздел принятия решений в «расплывчатых» ситуациях;

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

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

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

9. Проектирование БД с использованием метода «сущность-связь»

БД - совокупность данных, хранящихся во внешней памяти ЭВМ, описывающих некоторую предметную область.

Три уровня абстракции:

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

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

– физический (уровень реализации базы данных).

Сущность ­– объект предметной области.

Атрибут – характеристика, свойство сущности.

Экземпляр сущности ­– конкретный объект с конкретными значениями атрибутов. Каждый экземпляр сущности уникален.

Связь – отображение/соответствие экземпляра одной сущности на экземпляр другой сущности.

Виды связей:

– 1:1 – каждому экземпляру одной сущности соответствует один экземпляр другой

– 1:n – каждому экземпляру одной сущности соответствует несколько экземпляров другой.

– n:m – многие ко многим. Допустимо на концептуальном и логическом уровне. На физическом уровне добавляется новая зависимая сущность, связанная идентифицирующими связями один ко многим с сущностями, находившимися в исходном отношении.

Модель Чена. Концептуальный уровень

Модель Бахмана. Концептуальный уровень

IDEF1X. Логический и физический уровень

Методология IDEF1Х предназначена для моделирования структур баз данных на основе диаграмм сущность-связь (ER-диаграмм).

Атрибут или группа атрибутов, которые однозначно идентифицируют экземпляры сущности, называются первичным ключом (Primary key).

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

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

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

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

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

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

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

• коммутация каналов (circuit switching);

• коммутация пакетов (packet switching);

• коммутация сообщений (message switching).

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

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

Коммутация сообщений – разбиение информации на сообщения, каждый из которых состоит из заголовка и информации. Понимается передача единого блока данных между транзитными компьютерами сети с временной буферизацией этого блока на диске каждого компьютера.  Сообщение в отличие от пакета имеет произвольную длину, которая определяется не технологическими соображениями, а содержанием информации, составляющей сообщение (текстовый документ, файл с кодом программы, электронное письмо).   Транзитные компьютеры могут соединяться между собой как сетью с коммутацией пакетов, так и сетью с коммутацией каналов. Сообщение хранится в транзитном компьютере на диске, причем время хранения может быть достаточно большим, если компьютер загружен другими работами или сеть временно перегружена. По такой схеме обычно передаются сообщения, не требующие немедленного ответа, чаще всего сообщения электронной почты. Режим передачи с промежуточным хранением на диске называется режимом «хранение-и-передача» (store-and-forward).

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

Такой режим работы сети называется дейтаграммным. При его использовании коммутатор может изменить маршрут какого-либо пакета в зависимости от состояния сети – работоспособности каналов и других коммутаторов, длины очередей пакетов в соседних коммутаторах и т. п. Существует и другой режим работы сети - передача пакетов по виртуальному каналу (virtual circuit или virtual channel). В этом случае перед тем, как начать передачу данных между двумя конечными узлами, должен быть установлен виртуальный канал, который представляет собой единственный маршрут, соединяющий эти конечные узлы.  Виртуальный канал может быть динамическим или постоянным.  Динамический виртуальный канал устанавливается при передаче в сеть специального пакета - запроса на установление соединения. Этот пакет проходит через коммутаторы и "прокладывает" виртуальный канал. Это означает, что коммутаторы запоминают маршрут для данного соединения и при поступлении последующих пакетов данного соединения отправляют их всегда по проложенному маршруту.  Постоянные виртуальные каналы создаются администраторами сети путем ручной настройки коммутаторов.

11. Функциональная модель АСОИУ

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

В разработке функциональной модели принимают участие наиболее квалифицированные специалисты по системному анализу и созданию АСУ совместно с экспертами по создаваемой системе. Такая группа не должна быть многочисленной (3-5 квалифицированных человек). Ошибки в функциональной модели приводят к неправильному построению системы.

Разработка функциональной модели включает в себя:

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

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

• Распределение функций по уровням иерархии системы. (Например, президент не должен инспектировать заборы в Челябинской области.)

• Разделение функций и задач между персоналом и вычислительными средствами.

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

• Описание в самом общем виде алгоритмов и процедур обработки информации в создаваемой системе.

Принципы построения функциональной модели:

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

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

• абстрагирования – выделение существенных свойств и отвлечение от несущественных.

• формализация – строгий методический подход к решению проблемы.

• непротиворечивость – обоснованность и согласованность элементов.

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

Средства:

• DFD – диаграмма потоков данных;

• SADT – IDEF0, IDEF1, … – функциональные диаграммы;

• ERD – диаграмма "сущность–связь" и т.д.

12. Режим разделения времени

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

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

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

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

Режим разделения времени

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

Рис. 13.6. Организация работы ЭВМ в режиме разделения времени

Основные характеристики:

Многотерминальная многопользовательская система.

Любой пользователь со своего терминала может обратиться к любым ресурсам ЭВМ.

У пользователя создается впечатление, что он один работает на ЭВМ.

Реализация.

Время работы машины разделяется на кванты tk.

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

Единого способа выбора времени кванта не существует. Иногда оно выбирается по количеству команд, которое должна выполнить ЭВМ за это время.

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

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

Представляют собой задачу поиска показателя эффективности Wв виде функции:

где – заранее известные факторы;

x– элементы решения;

–неизвестные факторы.

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

Наглядные примеры задач принятия решений (для лучшего понимания):

Методы решения задач принятия решений зависят от природы неизвестных факторов , т.е. от вида неопределенности:

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

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

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

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

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

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

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

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

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

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

Общая постановка. Задачей принятия решения назовем пару (Ω, P), где Ω — множество вариантов, P – принцип оптимальности. Решение задачи — множество Ω _P ≤ Ω, полученное с помощью принципа оптимальности P. Математическим выражение принципа оптимальности P служит функция выбора C_P. Она сопоставляет любому множеству X ≤ Ω его часть C_P(X). Элементы множества Ω называются альтернативами (вариантами). Принцип оптимальности P задает понятие лучших альтернатив: лучшими считают альтернативы, принадлежащие C_P(Ω).

Пусть некоторое свойство альтернатив из Ω выражается числом, то есть существует отображение φ: Ω →E₁. Такое свойство называется критерием, а число φ(x) – оценка альтернативы x по критерию. Одновременный учет нескольких свойств может быть затруднительным. При этом можно выделить группы свойств, называемых аспектами.

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

Пусть все свойства k_1, …, k_m, учитываемые при решении задачи (Ω, P), являются критериями. Критериальным пространством называют пространство E_m, координаты которого – оценки соответствующих критериев.

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

Техническое обслуживание – число станций, сроки выполнения ремонтных работ и т. д. ТО – аспект.

Стоимость маршрута – стоимость топлива, обслуживания и т. д. Это тоже аспект. Но так как стоимость вычислима, то это критерий.

Сформулируем схему процесса принятия решения. Формируется множество Ω. Его подготавливают для последующего решения задачи выбора. Для формирования Ω используют условия возможности и допустимости альтернатив, которые определяют конкретными ограничениями задачи. При этом считают известным универсальное множество альтернатив Ω_у. Таким образом, задача формирования Ω есть задача выбора (Ω_у, P₁), где P₁ – принцип оптимальности, выражающий условия допустимости.

Множество Ω = C_P1(Ω_у), полученное в результате решения, называют исходным множеством альтернатив (ИМА).

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

В процессе решения участвуют лицо, принимающее решение (ЛПР), эксперты, консультанты. ЛПР имеет цель и служит мотивом постановки задачи, дает полномочия и несет ответственность. Его функция – выделять Ω_P. ЛПР дает информацию о принципе оптимальности P.

Эксперт не несет ответственности, он дает оценки альтернатив для формирования ИМА и решения задачи выбора.

Консультант – специалист по теории выбора и принятия решений. Он разрабатывает модель принятия решений, организует работу ЛПР и экспертов.

14. Создание и модификация БД

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

Механизм создания в СУБД MS SQL Server, используется оператор CREATE DATABASE.

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

Создание базы данных в системе SQL-сервер осуществляется командой CREATE DATABASE. Следует отметить, что процедура создания базы данных в SQL-сервере требует наличия прав администратора сервера.

<определение_базы_данных> ::=

CREATE DATABASE имя_базы_данных

[ON [PRIMARY]

[ <определение_файла> [,...n] ]

[,<определение_группы> [,...n] ] ]

[ LOG ON {<определение_файла>[,...n] } ]

[ FOR LOAD | FOR ATTACH ]

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

<определение_файла>::=

([ NAME=логическое_имя_файла,]

FILENAME='физическое_имя_файла'

[,SIZE=размер_файла ]

[,MAXSIZE={max_размер_файла |UNLIMITED } ]

[, FILEGROWTH=величина_прироста ] )[,...n]

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

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

<определение_группы>::=FILEGROUP имя_группы_файлов

<определение_файла>[,...n]

МОДИФИКАЦИЯ БД

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

<изменение_базы_данных> ::=

ALTER DATABASE имя_базы_данных

{ ADD FILE <определение_файла>[,...n]

[TO FILEGROUP имя_группы_файлов ]

| ADD LOG FILE <определение_файла>[,...n]

| REMOVE FILE логическое_имя_файла

| ADD FILEGROUP имя_группы_файлов

| REMOVE FILEGROUP имя_группы_файлов

| MODIFY FILE <определение_файла>

| MODIFY FILEGROUP имя_группы_файлов

<свойства_группы_файлов>}

Может быть изменено не более одного параметра конфигурации базы данных.

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

Параметры файлов и групп файлов можно изменять (MODIFY).

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

READONLY – группа файлов используется только для чтения; READWRITE – в группе файлов разрешаются изменения; DEFAULT – указанная группа файлов принимается по умолчанию.

15. Разработка модели защиты данных в АСОИУ

На основе имеющегося опыта можно сформулировать следующие фундаментальные принципы организации защиты информации:

• системность;

• специализированность;

• неформальность.

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

Специализированностькак принцип организации защиты предполагает два аспекта:

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

2) для обеспечения эффективного функционирования механизма защиты в составе АСОИУ должны функционировать специалисты по защите информации.

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

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

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

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

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

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

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

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

Основные положенияпо разработке систем ЗИ могут быть сформулированы так:

1) защита информации является не разовым мероприятием и даже не совокупностью мероприятий, а непрерывным процессом, который должен протекать (осуществляться) во все время и на всех этапах жизненного цикла АСОИУ;

2) осуществление непрерывного процесса защиты информации возможно лишь на базе промышленного производства средств защиты;

3) создание эффективных механизмов защиты может быть осуществлено высококвалифицированными специалистами-профессионалами в области защиты информации;

4) поддержание и обеспечение надежного функционирования механизмов защиты информации в АСОИУ сопряжено с решением специфических задач и поэтому может осуществляться лишь профессионально подготовленными специалистами.

16. Многопользовательский режим работы (ТОЧНО ПРО СУБД?)

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

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

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

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

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

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

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

1. Чётко сформулировать цель, задачу и требуемый результат.

2. Классифицировать характеристики вариантов.

3. Беспристрастно выбрать критерии.

Критерий должен позволять ответить на один из следующих вопросов:

1. Является ли альтернатива допустимой: может ли она при условии, что остальные будут хуже, рассматриваться как решение?

2. Является ли альтернатива удовлетворительной, иначе говоря, можно ли её рассматривать в качестве решения задачи независимо от других альтернатив?

3. Какая из двух сравниваемых альтернатив лучше?

4. Является ли альтернатива оптимальной?

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

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

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

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

Отсюда следуют следующие требования к критериям:

a. Соответствие цели и задаче.

b. Критичность. «Чувствительность» к изменению варианта выбора.

c. Вычислимость критериев.

d. Полнота и минимальность.

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

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

Например, перед принятием важного решения руководитель должен решить вопрос о страховании своей ответственности. Обозначим ожидаемый выигрыш величиной В, потери величиной (-В), полезность выигрыша - П(В) и вредность потерь - П(-В). Тогда, если договор страхования заключен, «полезность» составит П(-В) в соответствии с величиной отдаваемого страхового взноса. «Полезность» потерь при отсутствии страховки должна быть скорректирована в соответствии с вероятностью неудачи Р и составит Р × П(-н). Следовательно, страховать риск следует в том случае, если П(-В) > Р × П(-н).

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

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

18. Поиск и сортировка данных, индексирование БД

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

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

Доступ по ключу базы данных определяет местоположение записи в памяти ЭВМ. Зная его, система может извлечь нужную запись за одно обращение к памяти.

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

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

Для ускорения доступа к записям по ключевому атрибуту создаётся специальная структура – индекс, который определяет соответствие значения атрибута и местоположения записи. Индекс обычно хранится в отдельном файле или отдельной области памяти. Пустые значения атрибутов (null) не индексируются. Обращение к записи через индексы осуществляется в два этапа: сначала в индексной структуре находится требуемое значение атрибута и соответствующий адрес записи, затем по этому адресу происходит обращение к внешнему запоминающему устройству (ВЗУ). Индекс загружается в ОП целиком (или хранится в ней постоянно во время работы с БД). Если каждому значению индекса соответствует уникальное значение ключа, то ключ первичный. Если же индекс строится по ключу, допускающему дубликаты значений, такой индекс называется вторичным. Различают одиночные индексы и составные. 

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

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

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

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

19. «Клиент/серверные» сети

Клиент-серверная сеть –распределенная система, компонентами которой являются клиенты, запрашивающие некоторые ресурсы или сервисы, и серверы, их представляющие.

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

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

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

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

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

Сервер печати (принт-сервер) — обеспечивает пользователей возможностью распечатки документов на сетевом принтере.

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

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

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

Клиент-серверные сети разделяются на двухзвенные, трёхзвенные и многозвенные в зависимости от используемых архитектур. Двухзвенные – клиент <-> сервер, который для ответа клиенту использует только свои ресурсы. Трёхзвенная – клиент <-> сервер <-> сервер БД (это пример!) и многозвенная архитектуры разбивают нагрузочную составляющую сервера на множество серверов, закрепляя за каждым из них определенную задачу.

20. Разработка пользовательского интерфейса (Евдошка)

21. ОС реального времени

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

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

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

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

ОС должна быть многозадачной и допускающей вытеснение (preemptable),

ОС должна обладать понятием приоритета для потоков,

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

ОС должна обеспечивать механизм наследования приоритетов,

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

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

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

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

Как правило, большинство современных ОСРВ построено на основе микроядра (kernel или nucleus), которое обеспечивает планирование и диспетчеризацию задач, а также осуществляет их взаимодействие. Несмотря на сведение к минимуму в ядре абстракций ОС, микроядро все же должно иметь представление об абстракции процесса. Все остальные концептуальные абстракции операционных систем вынесены за пределы ядра, вызываются по запросу и выполняются как приложения.

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

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

задачи управления запасами;

задачи распределения ресурсов;

задачи ремонта и замены оборудования;

задачи массового обслуживания;

задачи календарного планирования (теории расписаний);

задачи транспортного типа (выбора маршрутов перевозок);

задачи сетевого планирования и управления;

задачи планировки и размещения объектов;

комбинированные задачи.

Рассмотрим их содержательные постановки и особенности.

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

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

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

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

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

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

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

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

Заданы как работы, так и ресурсы. Распределить ресурсы между роботами таким образом, чтобы максимизировать определенный критерий эффективности (например, прибыль) или минимизировать ожидаемые затраты (производственные издержки).

Заданы лишь наличные ресурсы. Определить, какой состав работ можно выполнить с этими ресурсами, чтобы обеспечить максимум некоторой меры эффективности.

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

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

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

.

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

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

Задачи календарного планирования относятся к комбинаторным задачам. Общее количество возможных вариантов расписаний общей задаче для m станков и n деталей. Поэтому для решения таких задач применяются, в основном, приближенные эвристические методы, за исключением частных случаев задачи дляm = 1; m = 2 и m = 3.

Задачи КП различаются по следующим признакам: по числу станков m; по виду технологических маршрутов: с одинаковыми ТМ (задачи конвейерного типа) и с неодинаковыми ТМ; по используемым критериям оптимальности; по виду станков: с идентичными и неидентичными станками.

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

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

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

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

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

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

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

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

а) характеристики существующих и новых объектов;

б) характер взаимодействия между ними;

в) тип пространства решений (размещений);

г) мера расстояния между объектами (метрика пространства размещений);

д) критерий оценки вариантов решений.

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

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

Мера расстояния (метрика пространства размещений) также может учитываться при формулировке задач размещения.

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

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

Часто вводят ограничения на пропускные способности коммуникаций.

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

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

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

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

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

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

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

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

23. Создание форм и отчетов для баз данных (Ваня Осипов)

24. Уровни и протоколы в сетях (=94)

Модель OSI
Уровень (layer)	Тип данных (PDU[1])	Функции	Примеры
7. Прикладной (application)	Данные	Доступ к сетевым службам	HTTP,FTP,SMTP
6. Представления (presentation)		Представление ишифрование данных	ASCII,EBCDIC,JPEG
5. Сеансовый (session)		Управление сеансом связи	RPC, PAP
4. Транспортный (transport)	Сегменты(segment)	Прямая связь между конечными пунктами и надежность	TCP, UDP
3. Сетевой (network)	Пакеты(packet)/ Дейтаграммы(datagram)	Определение маршрута и логическая адресация	IP,IPv4, IPv6,IPsec,AppleTalk
2. Канальный (data link)	Биты (bit)/ Кадры(frame)	Физическая адресация	PPP, IEEE 802.2,L2TP, ARP
1. Физический (physical)	Биты (bit)	Работа со средой передачи, сигналами и двоичными данными	DSL, USB

Основные функции протоколов уровней OSI

  1.Физический уровень (Physical Layer)

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

  2. Канальный уровень (Data-Link Layer)

Основные функции протокола канального уровня:

 А. Формирование кадра (пакета) для передачи по сети.Протокол канального уровня добавляет к данным полученным от сетевого уровня заголовок и трейлер, превращая их в кадр.Б. Реализация механизма контроля доступа к среде (методы доступа CSMA/CD, CSMA/CA, Token Passing и др). Функции протокола канального уровня реализуются сетевыми адаптерами и их драйверами.

3. Сетевой уровень (Network Layer)

Протоколы сетевого уровня обеспечивают «сквозную» передачу пакета от передающего до принимающего компьютера (end-to-end). При этом передатчик и приемник могут находится в одной ЛВС или в разных ЛВС, соединенных между собой специальными устройствами – маршрутизаторами (шлюзами). Пример: протокол сетевого уровня – IP (Internet Protocol), который входит в стек протоколов TCP/IP.

4. Транспортный уровень (Transport Layer)

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

 А. Протоколы ориентированные на соединение (connection-oriented)Такие протоколы перед передачей данных обмениваются сообщениями, чтобы установить связь друг с другом. Пример: протокол ТСР (Transmission Control Protocol) .

 Б. Протоколы не ориентированные на соединение (connectionless)Передают информацию целевой системе не проверяя готова ли она к приему и существует ли она вообще Пример: протокол UDР (User Datagram Protocol.

5. Сеансовый уровень (Session Layer) 

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

 6. Уровень представления (Presentation Layer)

На этом уровне выполняется функция трансляции синтаксиса между различными системами (например, различная кодировка символов в разных системах – ASCII и EBCDIC).

 7. Прикладной уровень (Application Layer) 

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

25. Проектирование распределенной обработки данных (Ваня Осипов)

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

27. Детерминированные задачи исследования операций (=91)

Детерминированная задача. Все параметры задачи заранее известны. Для решения детерминированных задач в основном применяются методы математического программирования.

Если в операционной модели

K=f(X,A)→min(max) (1.4)

(X ,A) ≤ 0, i = 1..m (1.5)

все неуправляемые переменные А – заранее точно известные величины (const), а f – детерминированная функция, то такая модель называется детерминированной.

Определение 6. Задача исследования операций называется детерминированной задачей, если в ней отсутствуют неконтролируемые факторы y . Такие задачи, по сути, являются задачами на поиск экстремума: . В зависимости от вида X , W (x) детерминированные задачи, в свою очередь, делятся на классы, которые приводим ниже. Определение 7. Задачей линейного программирования (ЗЛП) называют детерминированную задачу исследования операций, в которой математические соотношения, определяющие область допустимых решений X и целевую функцию W(x), линейны. Примером ЗЛП является транспортная задача.

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

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

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

• продать и купить новый;

• отремонтировать и ездить дальше;

• ездить дальше, не ремонтируя?

Каждый вариант влечет за собой определенные затраты. Целью за-дачи является определение такого плана действий на m лет вперед, чтобы связанные с ним затраты были минимальны. В данной задаче прослеживается явное разбиение на несколько этапов. Задачи такого типа относятся к так называемым задачам динамического программирования.

28. Физическая организация БД

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

Физическая модель указывает, каким образом записи размещаются в базе данных, как они упорядочиваются, как организуются связи, каким путем можно найти записи и осуществить их выборку. Внутренняя модель разрабатывается средствами СУБД. Механизмы среды хранения БД служат для управления двумя группами ресурсов – ресурсами хранимых данныхиресурсами пространства памяти. В задачу этого механизма входит отображение структуры хранимых данных в пространство памяти, позволяющее эффективно использовать память и определить место размещения данных при запоминании и при поиске данных. В большинстве случаевв качестве единицы хранения принимается хранимая запись. Ресурсам пространства памяти соответствуют объекты внешней памяти ЭВМ, управляемые средствами операционной системы или СУБД. Для обеспечения естественной структуризации хранимых данных, более эффективного управления ресурсами и/или для технологического удобства всё пространство памяти БД разделяется на части (области, разделы и др.). Области памяти используются для размещения хранимых записей одного или нескольких типов и разбиваются на пронумерованные страницы фиксированного размера. В большинстве систем обработку данныхна уровне страниц ведёт операционная система (ОС),а обработку записейвнутри страницы обеспечивает только СУБД.

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

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

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

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

Хранимая запись состоит из двух частей:

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

2. Информационная часть. Содержит значения элементов данных.

Элементы хранимой записи могут иметь фиксированную или переменную длину. При этом обычно элементы фиксированной длины хранятся в начале записи и размещаются в памяти с заранее определённых позиций, а за ними размещаются элементы переменной длины. Хранение элементов переменной длины осуществляется одним из двух способов: размещение через разделитель или хранение размера элемента данных. Наличие полей переменной длины позволяет не хранить незначащие символы и тем существенно снижает затраты памяти на хранение данных; но при этом увеличивается время на извлечение элементов записи.Каждой записи БД система присваивает внутренний идентификатор, называемый (по стандарту CODASYL) ключом базы данных (КБД). Значение КБД формируется системой при размещении записи и содержит информацию, позволяющую однозначно определить место размещения записи (её адрес). В качестве КБД может выступать, например, последовательный номер записи в файле или совокупность адреса страницы и смещения от начала страницы. Виды адресации хранимых записей. Прямая адресация предусматривает указание непосредственного местоположения записи в пространстве памяти. Простейший вариант адресации используется в том случае, если в памяти хранится один вид записи фиксированной длины. Тогда в качестве адреса записи может использоваться её порядковый номер. Прямая адресация не позволяет перемещать записи в памяти без изменения ключа базы данных. Такие изменения привели бы к необходимости коррекции различных указателей на записи в среде хранения, что было бы чрезвычайно трудоемкой процедурой. В связи с отсутствием возможности перемещения при этом возникает явление фрагментации, т.е. появление разрозненных незаполненных участков памяти.

косвенную адресацию. Существует множество способов косвенной адресации. Один из них состоит в том, что часть адресного пространства страницы выделяется под индекс страницы. Число статей (слотов) в нем одинаково для всех страниц. Ключом БД по-прежнему служит номер этой записи в области. С помощью простых арифметических действий можно получить по номеру записи номер нужной страницы и номер требуемого слота в индексе этой страницы. Найденный слот укажет местоположение записи на этой странице, где N, n – это соответственно номер страницы памяти и номер слота на этой странице, в котором хранится адрес записи (смещение от начала страницы).При перемещении записи она остаётся на той же странице, и слот по-прежнему указывает на неё (меняется его содержимое, но не сам слот). Если запись не вмещается на страницу, она помещается на специально отведённые в данной области страницы переполнения, и соответствующий слот продолжает указывать место её размещения. Этот подход позволяет перемещать записи на странице, исключать фрагментацию, возвращать освободившееся пространство для повторного использования. При этом приложения БД остаются нечувствительными к таким операциям. Таким образом, косвенная адресация входит в группу методов, обеспечивающих физическую независимость данных. Также с адресацией связана другая функция среды хранения – поддержка связей между хранимыми записями. Для сетевой и иерархической моделей данных эти связи поддерживаются на физическом уровне. Способы представления связей определяются схемой хранения и чаще всего основаны на использовании указателей или на размещении данных в смежных областях памяти.

29. Эталонная модель взаимосвязи открытых систем (Нурсиня)

30. Логический анализ структур АСОИУ (Ваня Осипов)

31. Классификация ОС

По признаку поддержки многозадачности различают однозадачные и многозадачныеоперационные системы.

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

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

Еще одним аспектом реализации многозадачности является использование концепции нитей(потоков) исполнения – многозадачности внутри одного процесса. Нити использовались в Windows.

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

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

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

жёсткого реального времени — с режимом работы системы, при котором нарушение временных ограничений равнозначно отказу системы (RTLinux,AutomationRuntime,ART-Linux); системы мягкого реального времени — с режимом работы системы, при котором нарушения временных ограничений приводят к снижению качества работы (QNX, RT-11, WindowsCE).

По особенностям работы в сети операционные системы делятся на сетевые и распределенные. Сетевая операционная система – это обычная система, расширенная поддержкой сетевого взаимодействия. По методам реализации сетевых функций системы различаются по способам реализации справочной информации о сетевых ресурсах и адресации; механизмам обеспечения прозрачности доступа. (WindowsforWorkgroups 3.1) Распределённая операционная система, динамически и автоматически распределяя работы по различным машинам системы для обработки, заставляет набор сетевых машин обрабатывать информацию параллельно. Пользователь распределённой операционной системы не имеет сведений, на какой машине выполняется его работа. (Amoeba, Plan 9)

По аппаратным средствам, на которых функционируют операционные системы, их можно разделить на системы для мэйнфреймов (IBM System/360), миникомпьютеров (Unix), микрокомпьютеров (CP/M,MSDOS).

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

32. Стохастические задачи исследования операций (=96)

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

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

искусственное сведение к детерминированной задаче (неизвестные параметры заменяются их средними значениями).

"оптимизация в среднем" (вводится и оптимизируется некоторый статистический критерий).

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

33. Хеширование данных

Хеширование(илихэширование, англ.hashing) – это преобразование входного массива данных определенного типа и произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называютсяхеш-функциямиили функциямисвертки, а их результаты называютхешем, хеш-кодом, хеш-таблицейилидайджестомсообщения (англ.message digest).

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

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

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

функция должна распределять ключи в хеш-таблице наиболее равномерно;

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

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

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

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

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

Хеш-таблицы должны соответствовать следующим свойствам.

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

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

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

Механизм разрешения коллизийявляется важной составляющей любой хеш-таблицы.

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

34. Аналоговые каналы передачи данных, способы модуляции, модемы

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

Изменение параметров несущей по закону передаваемого сообщения называется модуляция. Если это изменение относится к амплитуде, то модуляцияамплитудная, если к частоте, точастотная, если к фазе –фазовая.

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

1) При амплитудной модуляциина входы модулятора поступают сигнал V и несущая U. Например, если сигнал есть гармоническое колебание V = Vm*sin(W *t+j) с амплитудой Vm, частотой W и фазой j , то на выходе нелинейного элемента в модуляторе будут модулированные колебанияUАМ =Um*(1+m*sin(W*t+j))*sin(v*t+y), где m = Vm/Um - коэффициент модуляции. На выходе модулятора в спектре сигнала присутствуют несущая частота v и две боковые частоты v +W и v -W. Если сигнал занимает некоторую полосу частот, то в спектре модулированного колебания появятся две боковые полосы.

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

2) В сравнительно простых модемах применяют частотную модуляциюсо скоростями передачи до 1200 бит/с. Так, если необходима дуплексная связь по двухпроводной линии, то возможно представление 1 и 0 в вызывном модеме частотами 980 и 1180 Гц соответственно, а в ответном модеме - 1650 и 1850 Гц.

3) Фазовая модуляциядвумя уровнями сигнала (1 и 0) осуществляется переключением между двумя несущими, сдвинутыми на полпериода друг относительно друга. Другой вариант изменение фазы на p/2 в каждом такте при передаче нуля и на 3/4*p , если передается единица.

4) Квадратурно-амплитудная модуляцияоснована на передаче одним элементом модулированного сигнала n бит информации, где n = 4...8 (т.е. используются 16... 256 дискретных значений амплитуды).

35. Анализ и оценка производительности АСОИУ

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

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

Есть два показателя производительности процессов по «чистому» времени:

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

MIPS– отношение числа команд в программе к времени ее выполнения

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

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

 процессоры разной архитектуры имеют различный набор команд

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

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

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

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

36. Диспетчеризация и синхронизация процессов

При исполнении процесс может изменять свое состояние

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

Очереди, связанные с диспетчеризацией процессов

Очередь заданий(job queue) – cодержит множество всех процессов в системе. В нее попадает каждый новый процесс и остается в ней в течение всего пребывания в системе.

Очередь готовых процессов(ready queue) –содержащая множество всех процессов, находящихся в основной памяти и готовых к выполнению. В нее попадает каждый новый процесс, который система допускает к выполнению, а также каждый процесс после выполнения ввода-вывода или наступление ожидаемого события.

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

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

Схема диспетчеризации процессов и работа с очередями представлена на рис.

Синхронизация процессов:

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

Примером задачи синхронизации является проблема потребителя – производителя с общим буфером, к которому каждый из процессов может параллельно обращаться во время работы. Такая ситуация называется конкуренцией за общие данные (race condition).Для предотвращения подобных ситуаций процессы следует синхронизировать.

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

Синхронизация на основе аппаратной поддержки атомарных операций

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

Кроме рассмотренных способов существует метод Синхронизации на основе общих семафоров ( Общий семафор (counting semaphore) - это целая переменная S, над которой определены две атомарных семафорных операции wait (S) и signal (S) )

37. Задачи в условиях неопределенности (=101)

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

2,б). Задача в условиях (полной) неопределенности. Статистические данные о неизвестных параметрах отсутствуют. Задачи ИСО в условиях неопределенности в основном изучаются в рамках теории игр.

Постановка задачи исследования операций в детерминированном случае и в условиях неопределенности

Если в операционной модели

K=f(X,A)→min(max) (1.4)

(X ,A) ≤ 0, i = 1..m (1.5)

все неуправляемые переменные А – заранее точно известные величины (const), а f – детерминированная функция, то такая модель называется детерминированной.

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

Z=(z1, z2, …, zl),

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

K=f(X, A, Z).

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

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

Предположим, что ЛПР имеет п альтернатив решения ситуации, которые обозначим A1, A2.. An. Результат выбора (выигрыш ЛПР) зависит от того, как будит развиваться ситуация, на которую ЛПР повлиять ни как не может. Предположим, что ЛПР выделяет m вариантов развития ситуации, которые обозначим S1, S2.. Sm. Данные варианты в теории принятия решений называют «Состояниями природы», т.к. в большинстве реальные задачи этого типа связаны с погодными, климатическими, социальными и другими неопределенностями.

Допустим, что известен результат для ЛПР (выраженный количественно) при каждой альтернатива Ai и развитии ситуации Bj . Обозначим его aij. Получаем матрицу A=(aij), которую называют матрицей выигрышей или матрицей потерь, в зависимости от того, максимизируется или минимизируется результат для ЛПР.

В соответствии с реальными условиями, существует несколько критериев принятия решений в условиях неопределенности:

Критерий Лапласа

Критерий Вальда

Критерий максимального оптимизма

Критерий Сэвиджа

Критерий Гурвица

38. Индексированные файлы

В БД. Индекс – структура данных, которая помогает СУБД быстрее обнаружить отдельные записи в файле и сократить время выполнения запросов пользователей. Структура индекса связана с определенным ключом поиска и содержит записи, состоящие из ключевого значения и адреса логической записи в файле, содержащей это ключевое значение. Файл, содержащий логические записи, называется файлом данных, а файл, содержащий индексные записи, - индексным файлом. Значения в индексном файле упорядочены по полю индексирования, которое обычно строится на базе одного атрибута.

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

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

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

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

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

первичная область хранения;

отдельный индекс или несколько индексов;

область переполнения

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

Файл может иметь не больше одного первичного индекса или одного индекса кластеризации, но дополнительно к ним может иметь несколько вторичных индексов. Индекс может быть разреженным (sparse) или плотным (dense). Разреженный индекс содержит индексные записи только для некоторых значений ключа поиска в данном файле, а плотный индекс имеет индексные записи для всех значений ключа поиска в данном файле. Ключ поиска для индекса может состоять из нескольких полей.

В ОС.

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

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

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

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

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

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

39. Цифровые каналы передачи данных

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

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

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

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

К способам модуляции относятся:

амплитудная модуляция;

частотная модуляция;

фазовая модуляция.

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

потенциальное;

импульсное.

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

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

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

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

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

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

симплексная (однонаправленная) передача (телевидение, радио);

полудуплексная (прием/передача информации осуществляется поочередно);

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

Методы передачи на канальном уровне

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

В составе любого пакета должна присутствовать следующая информация:

данные или информация, предназначенная для передачи по сети;

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

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

Существует три принципиально различные схемы коммутации в вычислительных сетях:

коммутация каналов;

коммутация пакетов;

коммутация сообщений.

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

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

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

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

40. Управление проектом АСОИУ

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

централизованное хранение информации по графику работ, ресурсам и стоимости;

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

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

ПО для управления проектами традиционно разделяется на профессиональные системы и системы для массового пользователя.

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

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

MicrosoftProject- один из лидеров по возможностям объединения участников проекта средствами электронной почты или Интранет. Информация о работах проекта может сохраняться в формате HTML и публиковаться навнутреннем Web-сервере. Кроме стандартных форматов файлов MicrosoftProject (MPP и МРХ) можно сохранять информацию о проекте в форматах ODBC, Excel и Access. Формат MPD (MicrosoftProjectDatabase) позволяет хранить все данные о проекте в структуре, доступной как из MicrosoftProject 98, так и из Access. В MSProject для планирования можно использовать графики Ганта и сетевые графики. Диаграмма Ганта названа в честь Генри Ганта (1861-1919), соратника «отца научного менеджмента» Фредерика Тейлора (1856-1915).В MS Project диаграмма Ганта (GanttChart) является основным средством визуализации плана проекта.

41. Понятия приоритета и очереди процессов (Мирош)

42. Задачи линейной оптимизации (=106)

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

Линейная оптимизация (линейное программирование ) применяется в оптимизационных моделях в случае поиска экстремума целевой функции L, линейно зависящей от управляемых параметровXi.

Множество, на котором ищется экстремум целевой функции, задается системой mлинейных неравенств:

И представляет собой многогранник в n-мерном пространстве (отрезок приn=1, многоугольник, ограниченный прямыми линиями на плоскости приn=2, многогранник, ограниченный плоскостями приn=3). Каждое ограничение задает одну грань многогранника (точку приn=1, отрезок приn=2 или плоскость приn=3). Пересечения нескольких ограничений (граней многогранника) называется вершиной множества допустимых значений.

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

Симплексный метод решение ЗЛП

Рассмотрим следующую задачу линейного программирования:

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

Здесь x — переменные из исходного линейного функционала, xs — новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство, c — коэффициенты исходного линейного функционала, Z — переменная, которую необходимо максимизировать. Полупространства ив пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми». Остальные переменные при этом будут вычисляться однозначно и называться «простыми». Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этом начальное допустимое решение вычисляется однозначно : 

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

где cB — коэффициенты вектора c, соответствующие простым переменным (переменным xs соответствуют 0), B — столбцы , соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг.

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

Второй шаг

Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выраженияпростые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть— простые, а— непростые переменные на данной итерации. Уравнениеможно переписать, как. Умножим его наслева:. Таким образом мы выразили простые переменные через непростые, и в выражении, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенствуравенство, то в полученном равенстве все простые переменные будут иметь нулевой коэффициент — все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение.

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

.

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

Третий шаг

Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовемвыходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами — входящая «войдёт» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор cB в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу. x''

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

43. Защита БД

Защита БД должна охватывать следующие моменты:

- используемое оборудование

- ПО

- персонал

- сами данные.

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

1.      Авторизация пользователей.

2.      Использование представлений.

3.      Средства копирования и восстановления.

4.      Шифрование.

5.      Вспомогательные процедуры.

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

Аутентификация – механизм определений того, является ли пользователь тем, за кого се6я выдает.

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

Резервное копирование – процесс периодического создания копий БД из файла журнала БД.

Средство поддержания целостности средства данных предназначены для исключения перехода данных в несогласованное состояние.

Шифрование данных – кодирование данных с помощью специальных алгоритмов, которые делают данные непригодными для чтения, если не известен ключ шифрования.

К основным средствам защиты относятся:

Защита паролем

Шифрование данных и программ

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

Защита полей и записей таблиц БД

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

Шифрование является более продвинутым способом защиты. Шифрование это преобразование информации, посредством алгоритма шифрования.

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

Вот некоторые из них по отношению к таблицам:

Просмотр данных

Изменение данных

Добавление новых записей

Добавление или удаление данных

Изменение структуры таблицы

По отношению к полям относятся:

Полный запрет доступа

Только чтение

Полное разрешение всех операций

Защита отдельных полей таблицы(могут быть совсем скрыты от пользователя)

Дополнительные средства защиты БД:

Встроенные средства контроля значений данных в соответствии с типами

Повышение достоверности вводимых данных

Обеспечение целостности связей таблиц

Организации совместного использования объектов БД в сети

44. Разделение каналов по времени и частоте (Мирош)

45. Проектная документация АСОИУ

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

1.Формирование требований к АС

2. Разработка концепции АС

3. Техническое задание

4. Эскизный проект

5. Технический проект

6. Рабочая документация

7. Ввод в действие

8. Сопровождение АС.

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

Виды и комплектность документов регламентированы ГОСТ 34.201.Требования к содержанию документов РД 50-34.698-90- Содержание документов является общим для всех видов АС и, при необходимости, может дополняться разработчиком документов в зависимости от особенностей создаваемой АС.

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

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

3. Описание автоматизируемых функцийсодержит разделы: исходные данные; цели АС и автоматизированные функции; характеристика функциональной структуры; типовые решения (при наличии).

4. Описание постановки задачи(комплекса задач): характеристики комплекса задач; выходная информация; входная информация.

5. Общее описание системы: назначение системы; описание системы; описание взаимосвязей АС с другими системами; описание подсистем (при необходимости).

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

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

8.Описание организационной структуры: изменения в организационной структуре управления объектом; организация подразделений; реорганизация существующих подразделений управления.

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

10. Перечень входных сигналов и данных.

11. Перечень выходных сигналов(документов).

12. Описание информационного обеспечения системы: состав информационного обеспечения; организация информационного обеспечения; организация сбора и передачи информации; построение системы классификации и кодирования; организация внутримашинной информационной базы; организация внемашинной информационной базы.

13. Описание организации информационной базысостоит из двух частей: описание внутримашинной информационной базы; описание внемашинной информационной базы.

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

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

46. Средства коммуникации процессов

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

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

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

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

Для организации коммуникации между одновременно работающими процессами применяются средства межпроцессного взаимодействия (Interprocess Communication - IPC).

Выделяются три уровня средств IPC:

локальный;

удаленный;

высокоуровневый.

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

Удаленные IPCпредоставляют механизмы, которые обеспечивают взаимодействие как в пределах одного процессора, так и между программами на различных процессорах, соединенных через сеть. Сюда относятсяудаленные вызовы процедур (Remote Procedure Calls - RPC),сокеты Unix, а такжеTLI (Transport Layer Interface - интерфейс транспортного уровня)фирмы Sun.

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

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

Каналы

Канал (pipe) представляет собой средство связи стандартного вывода одного процесса со стандартным вводом другого. Каналы старейший из инструментов IPC, существующий приблизительно со времени появления самых ранних версий оперативной системы UNIX.

Сигналы

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

Очереди сообщений

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

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

Семафоры

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

Двоичный семафор может принимать только значения 0 или 1. Считающий семафор может принимать целые неотрицательные значения.

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

Разделяемая память

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

Сокеты

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

47. Задачи дискретной оптимизации

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

1) Множество целых чисел – число людей, число датчиков, число самолетов и т.д.

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

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

Такого рода задачи принадлежат классу задач дискретной оптимизации:

Задачей линейного целочисленного программирования (ЛЦП) называют

задачу вида:

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

Тогда речь идет о задаче линейного булевского программирования (ЛБП).

Наиболее распространенные задачи дискретной оптимизации:

1) Задача о назначениях (о выборе).

Имеется n работ и n кандидатов на эти работы. Известен эффект того, что i-ая работа будет занята j-м работником c_ij. Необходимо распределить работы по работникам так, чтобы суммарный эффект был максимальным.

2) Задача о покрытии.

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

3) Задача о коммивояжёре.

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

4) Задача о ранце.

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

48. Целостность БД

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

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

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

К инструментальным ограничениям относят проверку правильности данных при вводе. Например, поле числа не может содержать текстовые символы, а поле даты должно содержать допустимое значение даты. Средства реализации инструментальных ограничений встроены в СУБД.

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

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

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

Ограничения могут найти свое выражение:

– при описании атрибутов отношений в концептуальной схеме;

– в запросе к базе данных;

– в процедуре базы данных ;

– в правиле (в триггере).

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

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

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

ПРототипом правил послужили триггеры (triggers), которые впервые появились в СУБД Sybase и впоследствии были реализованы в том или ином виде и под тем или иным названием в большинстве многопользовательских СУБД.

Транзакция – неделимая с точки зрения воздействия на БД последовательность операторов манипулирования данными (чтения, удаления, вставки, модификации), такая, что: 1) либо результаты всех операторов, входящих в транзакцию, отображаются в БД; 2) либо воздействие всех операторов полностью отсутствует. При этом для поддержания ограничений целостности на уровне БД допускается их нарушение внутри транзакции так, чтобы к моменту завершения транзакции условия целостности были соблюдены. Для обеспечения контроля целостности каждая транзакция должна начинаться при целостном состоянии БД и должна сохранить это состояние целостным после своего завершения. Если операторы, объединенные в транзакцию, выполняются, то происходит нормальное завершение транзакции, и БД переходит в обновленное (целостное) состояние. Если же происходит сбой при выполнении транзакции, то происходит так называемый откат к исходному состоянию БД. Модели транзакций.: модель автоматического выполнения транзакций и модель управляемого выполнения транзакций, обе основаны на инструкциях языка SQL – COMMIT и ROLLBACK.

Автоматическое выполнение транзакций. В стандарте ANSI/ISO зафиксировано, что транзакция автоматически начинается с выполнения пользователем или программой первой инструкции SQL. Далее происходит последовательное выполнение инструкций до тех пор, пока транзакция не завершается одним из двух способов: • инструкцией COMMIT, которая выполняет завершение транзакции: изменения, внесенные в БД, становятся постоянными, а новая транзакция начинается сразу после инструкции COMMIT; • инструкцией ROLLBACK, которая отменяет выполнение текущей транзакции и возвращает БД к состоянию начала транзакции, новая транзакция начинается сразу после инструкции ROLLBACK. Такая модель создана на основе модели, принятой в СУБД DB2. Управляемое выполнение транзакций. Отличная от модели ANSI/ISO модель транзакций используется в СУБД Sybase, где применяется диалект Transact-SQL, в котором для обработки транзакций служат четыре инструкции: • инструкция BEGIN TRANSACTION сообщает о начале транзакции, т.е. начало транзакции задается явно; • инструкция COMMIT TRANSACTION сообщает об успешном выполнении транзакции, но при этом новая транзакция не начинается автоматически; • инструкция SAVE TRANSACTION позволяет создать внутри транзакции точку сохранения и присвоить сохраненному состоянию имя точки сохранения, указанное в инструкции; • инструкция ROLLBACK отменяет выполнение текущей транзакции и возвращает БД к состоянию, где была выполнена инструкция SAVE TRANSACTION (если в инструкции указана точка сохранения – ROLLBACK TO имя_точки_сохранения), или к состоянию начала транзакции.

49. Характеристики проводных линий связи (Ира)

50. Инструментальные средства проектирования АСОИУ

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

При разработке АСОИУ организационными объектами преимущественно используются так называемые CASE-средства (Computer Aided Software Engineering). Это программные средства, поддерживающие анализ и формулировку требований к системе, проектирование программного обеспечения и баз данных, тестирование, документирование и управление проектами. Большинство существующих CASE-средств применяют методологию структурного или объектно-ориентированного анализа и проектирования и представляют собой интегрированные системы из отдельных CASE- компонентов.

В качестве CASE-компонентов выступают:

– репозитарий (специальным образом организованное хранилище различных версий проектов);

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

– средства разработки программ

– средства тестирования;

– средства документирования;

– средства управления проектом;

– средства интеграции с наиболее известными базами данных.

Примерами развитых CASE-систем могут служить система ERWIN, предназначенная для автоматизации проектирования баз данных и семейство объектно-ориентированных CASE-средств Rational Rose (RR), которые основаны на использовании языка моделирования UML. Система RR может генерировать коды разрабатываемых программ на языках С++, Small Talk, Java и ряде других. Кроме того, RR имеет средства для разработки проектной документации в виде диаграмм и спецификаций, а также имеет средства для реверсного инжиниринга программ. В состав RR входят следующие компоненты:

– репозитарий;

– графический интерфейс пользователя;

– средства просмотра проекта;

– средства контроля проекта;

– средства сбора статистики;

– средства генерации документации;

– средства генерации кода программ;

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

Разработка баз данных в ERWIN состоит из двух этапов: этапа составления логической модели базы данных и этапа разработки на ее основе физической модели базы данных. Логическая модель означает прямое описание фактов проблемной области задач АСОИУ, то есть реальных объектов этой области и их связей. Объекты именуются на естественном языке, при этом не указываются типы данных (например, целое, вещественное и так далее) и не рассматривается использование конкретной СУБД. Конкретная СУБД, ее таблицы и типы данных составляют физическую модель. ERWIN поддерживает ряд СУБД, таких как Microsoft SQL, Oracle, Sybase, Microsoft Access, FoxPro, INFORMIX и многие другие.

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

– работа в режиме реального времени;

– избыточность информации;

– сетевая архитектура открытых систем;

– модульность исполнения.

Современные SCADA-системы, и выполняют следующие функции:

 прием информации о контролируемых параметрах управляемых объектов;

 сохранение информации;

 обработка принятой информации;

 графическое представление хода технологического процесса;

 прием и передача команд оператора;

 регистрация событий;

 оповещение персонала об аварийных ситуациях;

 формирование сводок и других отчетов;

 обмен информацией с автоматизированной системой управления предприятием.

51. Язык SQL(Нурсиня)

52. Многокритериальные задачи

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

Формально М. з. задается множеством X «допустимых решений» и набором целевых функций на {X}, принимающих действительные значения. Сущность М. з. состоит в нахождении оптимального ее решения, т.е. такого, к-рое в том или ином смысле максимизирует значения всех функцийСуществование решения, буквально максимизирующего все целевые функции, является редким исключением. Поэтому в теории М. з. понятие оптимальности получает различные и притом нетривиальные истолкования. Содержание теории М. з. состоит в выработке таких концепций оптимальности, доказательстве их реализуемости (т. е. существования оптимальных в соответствующем смысле решений) и нахождении этих реализаций (т. е. в фактич. решении задачи).

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

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

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

53. Иерархическая модель данных

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

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

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

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

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

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

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

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

54. Спутниковые каналы связи

В основе построения спутниковой системы связи лежит идея размещения ретранслятора на космическом аппарате (КА). Движение КА длительное время происходит без затрат энергии, а энергоснабжение всех систем осуществляется от солнечных батарей. КА, находящийся на достаточно высокой орбите, способен «охватить» очень большую территорию — около трети поверхности Земли. Через его бортовой ретранслятор могут связываться любые станции, находящиеся на этой территории. Принцип спутниковой связи заключается в ретрансляции аппаратурой спутника сигнала от передающих наземных станций к приёмникам. Спутник - устройство связи, которое принимает сигналы от земной станции (ЗС), усиливает и транслирует в широковещательном режиме одновременно на все ЗС, находящиеся в зоне видимости спутника. Спутник не инициирует и не терминирует никакой пользовательской информации за исключением сигналов контроля и коррекции возникающих технических проблем и сигналов его позиционирования. Спутниковая передача начинается в некоторой ЗС, проходит через спутник, и заканчивается в одной или большем количестве ЗС. ССС состоит из трех базисных частей: космического сегмента, сигнальной части и наземного сегмента (рис. 1). Космический сегмент охватывает вопросы проектирования спутника, расчета орбиты и запуска спутника. Сигнальная часть включает вопросы используемого спектра частоты, влияния расстояния на организацию и поддержание связи, источники интерференции сигнала, схем модуляции и протоколов передачи. Наземный сегмент включает размещение и конструкцию ЗС, типы антенн, используемых для различных приложений, схемы мультиплексирования, обеспечивающие эффективный доступ к каналам спутника.

Преимущества и ограничения ССС

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

ССС имеет ряд преимуществ:

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

· Широкая полоса пропускания.

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

Выделим также ряд ограничений в использовании ССС:

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

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

· Защита от несанкционированного доступа к информации. Широковещание позволяет любой ЗС, настроенной на соответствующую частоту, принимать транслируемую спутником информацию. Лишь шифрование сигналов, зачастую достаточно сложное, обеспечивает защиту информации от несанкционированного доступа.

· Интерференция. Спутниковые сигналы, действующие в Ku- или Ka-полосах частот (о них ниже), крайне чувствительны к плохой погоде. Спутниковые сети, действующие в C-полосе частот, восприимчивы к микроволновым сигналам. Интерференция вследствие плохой погоды ухудшает эффективность передачи в Ku- и Ka-полосах на период от нескольких минут до нескольких часов. Интерференция в С-полосе ограничивает развертывание ЗС в районах проживания с высокой концентрацией жителей.

Космический сегмент

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

Сигнальная часть

1)Ширина полосы

Ширина полосы (bandwidth) спутникового канала характеризует количество информации, которую он может передавать в единицу времени. Типичный спутниковый приемопередатчик имеет ширину полосы 36 МГц на частотах от 4 МГц до 6 МГц.

Обычно ширина полосы спутникового канала велика. Например, один цветной телевизионный канал занимает полосу 6 МГц. Каждый приемопередатчик на современных спутниках связи поддерживает полосу в 36 МГц, при этом спутник несет 12 или 24 приемопередатчиков, что дает в результате 432 МГц или 864 МГц, соответственно.

2)Спектр частот

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

Современные спутниковые каналы чаще всего применяют одну из двух полос: C-полосу (от спутника к ЗС в области 6 ГГц и обратно в области 4 ГГц), или Ku-полосу (14 ГГц и 12 ГГц, соответственно). Каждая полоса частот имеет свои характеристики, ориентированные на разные задачи связи .

Спутниковые диапазоны полос передачи, L (GHz)	Полоса, С (MHz)	Диапазон частот, Ku (GHz)	Доступная ширина, Ka (Hz)
1.6/1.5	15	6/4	500
14/12	500	30/120	2500

Наземный сегмент

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

55. Типизация проектных решений АСОИУ

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

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

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

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

Рис. 3.1. Подходы к построению АСОИП

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

2) Заказные системы.При данном подходе вы заказываете разработку АСОИП, как, например, заказывают нестандартную мебель. Это второй исторически сложившийся подход к построению АСОИП. В «чистом виде» он предполагает разработку системы, полностью соответствующей особенностям конкретного предприятия, что и является его основным преимуществом. В потенциале этот подход характеризуется сравнительно меньшей стоимостью и меньшими сроками реализации, чем самостоятельная разработка.