Наконец, граф можно задать посредством списков. Например,

вариант 1: списком пар вершин, соединенных ребрами (или дугами);

вариант 2: списком списков для каждой вершины множества смежных с ней вершин.

  Метод анализа иерархий имеет аналогии с теорией графов.

Задачи принятия решения можно рассмотреть следующим образом.

Пусть имеются:

1.       несколько однотипных альтернатив (объектов, действий и т.п.),

2.       главный критерий (главная цель) сравнения альтернатив,

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

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

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

№ 7

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

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

Обобщенная Архитектура построения Брокеров Объектных Запросов разработана для поддержки интеграции самых разнообразных объектных систем. Спецификация CORBA устанавливает принципы создания Брокеров Объектных Запросов, которые и допускают такую интеграцию.

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

Во-вторых, для реального взаимодействия должным образом настроенных объектов предполагается наличие специального программного обеспечения, называемого в документах OMG брокером объектных заявок (ORB - Object Request Broker). Брокер объектных заявок должен существовать и на стороне вызывающего объекта, и на стороне вызываемого объекта. Основная задача ORB состоит в том, чтобы доставить заявку на вызов метода вызываемого объекта и возвратить результаты выполнения метода вызываемому объекту.

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

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

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

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

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

Поскольку для разработки Intranet-систем используются методы и средства Internet, и главным образом, технология WWW, то и понятия и термины Internet и Intranet совпадают. Приведем некоторые из них:

HTTP (HyperText Transfer Protocol) - протокол обмена гипертекстовой информацией;

URL (Universal Resource Locator) - универсальный локатор ресурсов. Используется в качестве универсальной схемы адресации ресурсов в сети.

HTML (HyperText Markup Language) - язык гипертекстовой разметки документов. Специальная форма подготовки документов для их опубликования в World Wide Web.

CGI (Common Gateway Interface) - спецификация на формат обмена данными между сервером протокола HTTP и прикладной программой.

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

VRML (Virtual Reality Modeling Language) - язык описания трехмерных сцен и взаимодействия трехмерных объектов.

Javaapplets - мобильные (независимые от архитектуры "железа") программные коды, написанные на языке программирования Java.

Java - объектно-ориентированный язык программирования, разработанный компанией Sun Microsystems и используемый в качестве основного средства мобильного программирования.

MIME (Multipurpose Internet Mail Exchange) - формат почтового сообщения Internet. В данном контексте стандарт MIME используется для установления соответствия между типом информационного файла, именем этого файла и программой просмотра этого файла.

CCI (Common Client Interface) - спецификация обмена данными меду прикладной программой и браузером Mosaic. В случае применения программного обеспечения, выполненного согласно CCI, браузер превращается в сервер-посредник для программного обеспечения пользователя.

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

Статистические испытания (метод Монте-Карло) характеризуются основными параметрами:

D - заданная точность моделирования;

            P – вероятность достижения заданной точности;

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

  Определим необходимое число реализаций N, тогда

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

 (1 - D) N – вероятность того, что при N испытаниях мы не получим заданной точности D.

Тогда вероятность получения заданной точности при N испытаниях можно найти по формуле

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

№ 8

Объектно-ориентированные CASE-средства (Rational Rose)

Rational Rose - CASE-средство фирмы Rational Software Corporation (США) - предназначено для автоматизации этапов анализа и проектирования программного обеспечения, а также для генерации кодов на различных языках и выпуска проектной документации. Rational Rose использует синтез-методологию объектно-ориентированного анализа и проектирования, основанную на подходах трех ведущих специалистов в данной области: Буча, Рамбо и Джекобсона. Разработанная ими универсальная нотация для моделирования объектов (UML - Unified Modeling Language) претендует на роль стандарта в области объектно-ориентированного анализа и проектирования. Конкретный вариант Rational Rose определяется языком, на котором генерируются коды программ (Си++, Smalltalk, PowerBuilder, Ada, SQLWindows и ObjectPro). Основной вариант - Rational Rose/Си++ - позволяет разрабатывать проектную документацию в виде диаграмм и спецификаций, а также генерировать программные коды на Си++. Кроме того, Rational Rose содержит средства реинжиниринга программ, обеспечивающие повторное использование программных компонент в новых проектах.

Структура и функции

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

В составе Rational Rose можно выделить 6 основных структурных компонент: репозиторий, графический интерфейс пользователя, средства просмотра проекта (browser), средства контроля проекта, средства сбора статистики и генератор документов. К ним добавляются генератор кодов (индивидуальный для каждого языка) и анализатор для Си++, обеспечивающий реинжиниринг - восстановление модели проекта по исходным текстам программ.

Репозиторий представляет собой объектно-ориентированную базу данных. Средства просмотра обеспечивают "навигацию" по проекту, в том числе, перемещение по иерархиям классов и подсистем, переключение от одного вида диаграмм к другому и т. д. Средства автоматической генерации кодов программ на языке Си++, используя информацию, содержащуюся в логической и физической моделях проекта, формируют файлы заголовков и файлы описаний классов и объектов. Создаваемый таким образом скелет программы может быть уточнен путем прямого программирования на языке Си++. Анализатор кодов Си++ реализован в виде отдельного программного модуля. Его назначение состоит в том, чтобы создавать модули проектов в форме Rational Rose на основе информации, содержащейся в определяемых пользователем исходных текстах на Си++. В процессе работы анализатор осуществляет контроль правильности исходных текстов и диагностику ошибок. Модель, полученная в результате его работы, может целиком или фрагментарно использоваться в различных проектах. Анализатор обладает широкими возможностями настройки по входу и выходу. Например, можно определить типы исходных файлов, базовый компилятор, задать, какая информация должна быть включена в формируемую модель и какие элементы выходной модели следует выводить на экран. Таким образом, Rational Rose/Си++ обеспечивает возможность повторного использования программных компонент.

В результате разработки проекта с помощью CASE-средства Rational Rose формируются следующие документы:

·                     диаграммы классов;

·                     диаграммы состояний;

·                     диаграммы сценариев;

·                     диаграммы модулей;

·                     диаграммы процессов;

·                     спецификации классов, объектов, атрибутов и операций

·                     заготовки текстов программ;

·                     модель разрабатываемой программной системы.

№9

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

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

В качестве других недостатков реляционных СУБД отмечаются следующие:

·                     негибкость структуры для развивающихся БД,

·                     затруднения в построении концептуальной модели для объектов с многочисленными связями “многие – ко – многим”,

·                     неестественность табличного представления для разреженных массивов данных.

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

1. Абстракция: Каждая реальная "вещь", которая хранится в БД, является членом какого-либо класса. Класс определяется как совокупность свойств, методов, общедоступных и частных структур данных, а также программы, применимых к объектам (экземплярам) данного класса. Классы представляют собой ни что иное, как абстрактные типы данных. Методы - это процедуры, которые вызываются для того, чтобы произвести какие-либо действия с объектом (например, напечатать себя или скопировать себя). Свойства - это значения данных, связанные с каждым объектом класса, характеризующие его тем или иным образом (например, цвет, возраст).

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

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

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

5. Сообщения: Взаимодействие с объектами осуществляется путем посылки сообщений с возможностью получения ответов.

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

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

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

№10

В Cache' реализована концепция Единой архитектуры данных. К одним и тем же данным, хранящимся под управлением Сервера многомерных данных Cache' есть три способа доступа: прямой, объектный и реляционный:

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

Cache' SQL - реляционный доступ, обеспечивающий максимальную производительность реляционных приложений с использованием встроенного SQL. Cache' SQL соответствует стандарту SQL 92. Кроме этого, разработчик может использовать разные типы триггеров и хранимых процедур. Все это позволяет Cache' успешно конкурировать с реляционными СУБД. Даже без использования прямого и объектного доступа приложения на Cache' работают быстрее за счет высокой производительности Сервера многомерных данных.

Cache' Objects - объектный доступ, для максимальной продуктивности разработки при использовании Java, EJB, C++, а также VB и других ActiveX-совместимых средств разработки, таких как PowerBuilder и Delphi. В Cache' реализована объектная модель в соответствии с рекомендациями ODMG (Группа управления объектными базами данных – Object Database Management Group). В Cache' полностью поддерживаются наследование (в том числе и множественное), инкапсуляция и полиморфизм. При создании информационной системы разработчик получает возможность использовать объектно-ориентированный подход к разработке, моделируя предметную область в виде совокупности классов объектов, в которых хранятся данные (свойства классов) и поведение классов (методы классов). Cache', поддерживая объектную модель данных, позволяет естественным образом использовать объектно-ориентированный подход как при проектировании (в Rational Rose) предметной области, так и при реализации приложений в ОО-средствах разработки (Java, C++, Delphi, VB). Постреляционная СУБД Cache' конкурирует с объектными СУБД, значительно превосходя их по таким показателям как надежность, производительность и удобство разработки.

№ 11

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

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

 б) Одноканальная система массового обслуживания с  накопителем, многоканальная система массового обслуживания с накопителем.

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

- процесс загрузки обуотовтенный параметром λ

- процесс разгрузки обуотовтенный параметром μ

 В результате чего СМО меняет свои состояния

Для расчета вероятностей  состояний используется формула связывающая вероятности двух соседних состояний из графа состояний по следующему правилу: вероятность Р_i  равна вероятности предыдущего состояния Р_i-1 умноженной на отношение показателя загрузки к показателю разгрузки S_i-1 состояния.

Все вероятности связаны между собой, поэтому выразим их через Ро

Воспользуемся формулой:

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

№ 12

С общей позиции обработки данных можно выделить два доминирующих класса информационных систем: системы, ориентированные на операционную (транзакционную) обработку данных (On-Line Transaction Processing, OLTP-системы), часто их определяют как системы обработки данных (СОД); системы, ориентированные на аналитическую обработку данных (Decision Support Systems, DSS), или системы поддержки принятия решений (СППР).

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

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

OLAP-технология. Состав аналитической информационной системы.

Основная идея OLAP-технологии заключается в построении многомерных кубов данных, которые в дальнейшем можно использовать для реализации аналитических пользовательских запросов. Исходные данные для построения OLAP-кубов обычно хранятся в реляционных базах данных, называемых также хранилищами данных (Data Warehouse). В отличие от оперативных баз данных, с которыми работают приложения ведения данных, хранилища данных предназначены исключительно для обработки и анализа информации, поэтому проектируются они таким образом, чтобы время выполнения запросов к ним было минимальным. Обычно данные копируются в хранилище из оперативных баз данных согласно определенному регламенту, например, раз в месяц, квартал или год. Типичная структура хранилища данных существенно отличается от структуры обычной реляционной БД. Как правило, эта структура денормализована (это позволяет повысить скорость выполнения запросов), поэтому может допускать избыточность данных. Основными составляющими структуры хранилищ данных являются таблица фактов (fact table) и таблицы измерений (dimension tables). Таблица фактов является основной таблицей хранилища данных. Как правило, она содержит сведения об объектах или событиях, совокупность которых будет в дальнейшем анализироваться. Обычно говорят о четырех наиболее часто встречающихся типах фактов. К ним относятся: факты, связанные с транзакциями. Они основаны на отдельных событиях (например, телефонный звонок);  факты, связанные с «моментальными снимками». Основаны на состоянии объекта (например, банковского счета) в определенные моменты времени, например на конец дня или месяца. Типичными примерами таких фактов являются объем продаж за; факты, связанные с элементами документа. Основаны на том или ином документе (например, счете за товар или услуги) и содержат подробную информацию об элементах этого документа (например, количестве, цене, проценте скидки); факты, связанные с событиями или состоянием объекта. Представляют возникновение события без подробностей о нем.

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

С общей позиции обработки данных можно выделить два доминирующих класса информационных систем: системы, ориентированные на операционную (транзакционную) обработку данных (On-Line Transaction Processing, OLTP-системы), часто их определяют как системы обработки данных (СОД); системы, ориентированные на аналитическую обработку данных (Decision Support Systems, DSS), или системы поддержки принятия решений (СППР).

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

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

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

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

Концепция хранилища данных:

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

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

Хранилище данных, содержит большие объемы разнородных данных и, обычно, большое количество “разнородных” потребителей. Для интенсификации общения специалистов, повышения эффективности анализа и сокращения сроков принятия решений, хранилище обязательно должно обладать средствами исключения семантических разрывов или минимизации времени на их преодоление. Такие системы принято называть подсистемами управления метаданными. Модель семантических разрывов может быть полезна в процессе анализа решений и проектирования подсистем управления метаданными. Семантический разрыв – это синоним непонимания информации, которая заключена в данных. Непонимание, в свою очередь, может быть полным, частичным, и … разным у разных пользователей или, например, у пользователей и “производителей” данных.

№13

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

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

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

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

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

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

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

№ 14

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

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

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

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

Внешний уровень. Структурный уровень базы данных, определяющий пользо­вательские представления данных.

Внутренний уровень обеспечивает физический взгляд на базу данных: дисководы, физические адреса, индексы, указатели и т.д. За этот уровень отвечают проектировщики физической базы данных, которые решают, какие физические устройства будут хранить данные, какие методы доступа будут использоваться для извлечения и обновления данных и какие меры следует принять для поддержания или повышения быстродействия системы управления базами данных. Ни один пользователь (как пользователь) не касается этого уровня. Реализация этих трех уровней требует, чтобы СУБД «преобразовывала» или переводила с одного уровня на другой. Для того чтобы представить данные пользователям на концептуальном или внешнем уровне, система должна уметь преобразовывать адреса и указатели в соответствующие логические имена и отношения. Такой перевод может происходить и в об­ратном направлении — с логического уровня на физический. Цена такого перевода состоит в большой системной задержке. Выгодой же является не­зависимость логического и физического представления данных.

№15

Модель Entity-Relationship (Сущность-Связь)

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

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

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

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

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

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

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

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

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

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

·                     продавец может получить вознаграждение за 1 или более контрактов;

·                     контракт должен быть инициирован ровно одним продавцом.

Первый тип связи – связь ОДИН-К-ОДНОМУ (1:1): в каждый момент времени каждому представителю (экземпляру) сущности А соответствует 1 или 0 представителей сущности В. Например, работник и его ставка.

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

Второй тип – связь ОДИН-КО-МНОГИМ (1:М): одному представителю сущности А соответствуют 0, 1 или несколько представителей сущности В.

В концептуальной модели это соответствует включению.

На основе этих двух видов связей, Вы можете составить более сложные связи.

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

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

Если сущность В обозначает сущность А, то она должна включать внешний ключ, соответствующий первичному ключу сущности А.

Стержневая сущность (стержень) – это независимая сущность. Например, при описании накладной, стержневой сущностью является шапка накладной.

Ассоциативная сущность (ассоциация) – это связь вида "многие-ко-многим". Например, товар в накладной – это связь с шапкой накладной и справочником наименований товара, справочником единиц измерения.

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

Дискретная математика в информатике

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

№ 16

Модели данных. Структура, операции, ограничения модели.

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

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

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

Структура, операции, ограничения модели

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

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

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

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

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

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

Результатом является: множество объектов БД. То есть в начале осуществляется селекция требуемых данных, затем вид операции.

Структура данных.

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

Поле, наименьшая поименованная единица данных;

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

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

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

Аналитическое определение. Сеть Петри - набор N = (P, T, F, W, M₀), где (P, T, F) - конечная сеть (множество Х = ЗuT конечно), а W: F→ N\ {O} (знак \ здесь означает разность множеств) и M₀: P→N - две функции, называемые кратностью дуг и начальной пометкой. Первая ставит в соответствие каждой дуге число N>0 (кратность дуги). Если N>0, то при графическом представлении сети число N выписывается рядом с короткой чертой, пересекающей дугу. Дуги с кратностью 1 не помечаются. Каждой позиции p ставится в соответствие некоторое число M₀(p) N (пометка позиции).

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

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

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

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

№17

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

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

    Доминирующее влияние на развитие СМД в соответствии со стандартами СУБД  оказала группа Кодасил (стандарт ISO)  Модель Кодасил постоянно развивается , по мере совершенствования вычислительной техники. По мере появления новой версии, появляется новый стандарт.

Основная конструкция сетевой модели данных КОДАСИЛ - набор.

Набор - это поименованное двухуровневое дерево, которое реализует связь между записями двух типов: владельцем набора и членом набора. Разрешаются только связи 1 : М или М : 1 , но связи M : N в явном виде не поддерживаются. Для каждого набора, устанавливающего связь между предком P и потомком C должны выполняться два условия:

1.                  Каждый экземпляр Р является предком только в одном экземпляре набора;

2.                  Каждый экземпляр C является потомком не более чем в одном экземпляре набора.

Основные свойства набора:

·                     набор имеет имя,

·                     в каждом наборе только один владелец,

·                     в каждом наборе 0, 1 или несколько членов,

·                     набор существует, только если существует запись - владелец.

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

·                     экземпляр записи может входить только в один экземпляр набора данного типа.

·                     в общем случае каждый набор - это вход в БД;

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

Типы наборов

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

Реляционная модель

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

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

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

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

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

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

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

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

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

·                     заносить в базу новые данные;

·                     создавать и уничтожать таблицы;

·                     добавлять строки и столбцы к ранее созданным таблицам;

·                     создавать и уничтожать индексы;

·                     определять и отменять представления хранимых данных;

·                     изменять привилегии различных пользователей.

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

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

Игры двух лиц с нулевой суммой

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

Итак, пусть имеется два игрока. В распоряжении первого игрока имеется всего n возможных ходов i=1,2,3,...,n; в распоряжении второго игрока имеется m возможных ходов j=1,2,3,...,n. Эти возможные ходы называются чистыми стратегиями игроков.

Оба игрока делают одновременно по одному ходу, после чего партия считается законченной. Если первый игрок делает ход i, а второй - ход j,

то первый игрок получает выигрыш, равный , очевидно, что выигрыш второго игрока равен .

Эти данные можно записать в виде матрицы

,

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

№ 18

Операции над отношениями

В число определенных Коддом операций входят перестановка (permutation), проекция (projection), соединение (join), связывание (tie) и композиция (composition) (в статье 1970-го г. добавлена операция ограничения (restriction), которую я описываю здесь для удобства). Интересно заметить, что определения ограничения и соединения отличаются от тех, которые используются сегодня, а операции связывания и композиции теперь редко принимаются во внимание. В том, что следует ниже, символы X, Y, ... (и т.д.) по мере необходимости обозначают либо индивидуальные атрибуты, либо комбинации атрибутов. Кроме того, по причинам, которые скоро будут понятны, определение соединения откладывается до конца раздела.

Перестановка. Переупорядочение атрибутов отношения слева направо.

Проекция. Понималась более или менее так же, как и сегодня (хотя синтаксис был другим; далее будем использовать синтаксис R{X} для обозначения проекции R на X). Замечание: название "проекция" происходит из того факта, что отношение степени n можно рассматривать как представление точек в n-мерном пространстве, и к проекции этого отношения на m его атрибутов (m<=n) можно относиться как к проекции этих точек на соответствующие m осей.

Связывание. Для данного отношения A{X1,X2,...,Xn} связывание A - это ограничение A до тех строк, в которых A.Xn = A.X1 (если использовать термин "ограничение" в его современном смысле, а не в специальном смысле, определяемом ниже.)

Композиция. Для данных отношений A{X,Y} и B{Y,Z} композицией A c B называется проекция на X и Z соединения (a join) A с B (причина, по которой я говорю "a join", а не "the join", объясняется ниже). Замечание: естественная композиция - это проекция на X и Z естественного соединения.

Ограничение. Для данных отношений A{X,Y} и B{Y} ограничение A по B определяется как максимальное подмножество A такое, что A{Y} является подмножеством -- не обязательно точным -- B.

Для данных отношений A{X,Y} и B{Y,Z} соединение A с B в статье определяется как любое отношение C{X,Y,Z} такое, что C{X,Y} = A и C{Y,Z} = B. Заметим, что следовательно A и B можно соединить (или они "соединяемы"), только если их проекции на Y идентичны -- т.е. только если A{Y} = B{Y}, условие, которое вряд ли удовлетворяется на практике. Также заметим, что если A и B соединяемы, то могут существовать различные соединения (в общем случае). Хорошо известное естественное соединение -- называемое в статье линейным естественным соединением, чтобы отличить его от другого вида, именуемого циклическим соединением -- это важный частный случай, но не единственно возможный.

Имитационное моделирование.

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

Задача имитации функционирования системы на ее объектной модели приводит к необходимости моделирования различных функциональных (аналитических, логических и т.д.) зависимостей. Для решения данной задачи в рамках проекта по созданию инструмента UFO - toolkit разработан специальный язык сценариев ( scripting language ), а также компилятор и интерпретатор для него. Данный язык позволяет описывать и визуализировать поведение УФО-элементов на этапе имитационного моделирования.

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

Статистические испытания (метод Монте-Карло) характеризуются основными параметрами:

D - заданная точность моделирования;

            P – вероятность достижения заданной точности;

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

  Определим необходимое число реализаций N, тогда

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

 (1 - D) N – вероятность того, что при N испытаниях мы не получим заданной точности D.

Тогда вероятность получения заданной точности при N испытаниях можно найти по формуле

Формула (19) позволяет определить заданное число испытаний для  достижения заданной точности D с заданной вероятностью Р.Случайные числа получаются в ЭВМ с помощью специальных математических программ или спомощью физических датчиков. Одним из принципов получения случайных чисел является алгоритм Неймана, когда из одного случайного числа  последовательно выбирается середина квадрата. Кроме того данные числа проверяются на случайность и полученные числа заносятся в базу данных. Физические датчики разрабатываются на электронных схемах и представляют собой генераторы белого (нормального) шума, то есть когда в спектральном составе шума имеются гармоничные составляющие с частотой F  ®¥. Из данного белого шума методом преобразования получаются случайные числа.

№19

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

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

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

Разрешение неспецифических отношений (отношений n*m).

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

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

Пример НФ. Рассмотрим все три нормальные формы на примере Группы Студентов. У Студента ключом является реквизит Номер (№ личного дела), к описательным реквизитам относятся: Фамилия (Фамилия студента), Имя (Имя студента), Отчество (Отчество студента), Дата (Дата рождения), Группа (N группы). Если отсутствует реквизит Номер, то для однозначного определения характеристик конкретного студента необходимо использование составного ключа из трех реквизитов: Фамилия + Имя + Отчество.

Первая нормальная форма

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

Например, отношение Студент=(Номер, Фамилия, Имя, Отчество, Дата, Группа) находится в первой нормальной форме.

Вторая нормальная форма

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

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

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

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

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

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

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

Отношение Студент = (Номер, Фамилия, Имя, Отчество, Дата, Группа) находится в первой и во второй нормальной форме одновременно, так как описательные реквизиты однозначно определены и функционально зависят от ключа Номер. Отношение Успеваемость = (Номер, Фамилия, Имя, Отчество, Дисциплина, оценка) находится в первой нормальной форме и имеет составной ключ Номер+Дисциплина. Это отношение не находится во второй нормальной форме, так как атрибуты Фамилия, Имя, Отчество не находятся в полной функциональной зависимости с составным ключом отношения.

Третья нормальная форма

Понятие третьей нормальной формы основывается на понятии нетранзитивной зависимости.

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

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

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

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

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

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

№20

Иерархические СУБД

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

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

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

Сетевые СУБД

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

Сетевые СУБД имели гораздо больший успех и долго господствовали на рынке СУБД. В немалой степени их успеху способствовала энергичная деятельность Data Base Task Group (DBTG) Комитета по языкам программирования Conference on Data Systems Languages (CODASYL). Эта организация тщательно проработала спецификации сетевой модели и ее архитектуру, что позволило создать ряд успешных коммерческих продуктов, не последнее место среди которых занимал некогда весьма популярный COBOL.

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

Реляционные СУБД

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

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

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

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

·                     при удалении записи в родительской таблицы следует удалить соответствующие записи и в дочерней таблице.

№ 21

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

команда SQL работает с данными на уровне машинного представления поэтому скорость обработки возрастает в сотни раз по сравнению с традиционными командами СУБД.

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

Каждая СУБД имеет свой собственный диалект по SQL, который отличается полнотой поддержки стандарта и некоторыми незначительными отличиями синтаксиса.

Для построения запроса в диалоговом режиме может быть использован конструктор запросов. Где генерируется тело команды SQL и создаётся файл с  .qpr. Этот файл можно выполнить используя команду

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

Обобщённый алгоритм построения запроса ---- Описание полей данных в результате---- Список источников данных----Условия связи между различными источниками данных----*Усл. отбора данных-----*Усл. Суммирования данных

*Задание порядка записей в результате

* - необязательные блоки алгоритма

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

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

Дизъюнктивные нормальные формы (ДНФ)

Конъюнктивные нормальные формы (КНФ)

Элементарной конъюнкцией (ЭК) называется выражение вида

X₁^a1 X₂^a2…X_n^an

Элементарной конъюнкцией (ЭК) называется выражение вида

X₁^a1 X₂^a2…X_n^an

ЭК называется правильной, если все входящие в неё переменные различны.

Правильная ЭК называется полной относительно данного набора переменных, если в неё входят все эти переменные.

Для  элементарных дизъюнкций (ЭД) – аналогичный набор определений.

ЭД – выражение вида

X₁^a1 V X₂^a2 V…V X_n^an

ДНФ – дизъюнкция разных правильных элементарных конъюнкций.

__

X₁ V X₁X₂ V X₁X₂X₃ – ДНФ.

ДНФ называется совершенной (СДНФ), если все входящие в неё элементарные конъюнкции полны относительно данного набора переменных.

ДНФ называется совершенной (СДНФ), если все входящие в неё элементарные конъюнкции полны относительно данного набора переменных.

Дизъюнктивной нормальной формой (ДНФ) называется произвольная дизъюнкция элементарных конъюнкций. Конъюнктивной нормальной формой (КНФ) называется произвольная конъюнкция элементарных дизъюнкция. СКНФ – совершенная КНФ. У нее все ЭД полны.

СКНФ – совершенная КНФ. У нее все ЭД полны.

Алгоритм представления функции в виде СДНФ.

1.      Выписываем носитель функции.

2.      Для каждого вектора из носителя выписываем конъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем с отрицанием, если единице – без отрицания). Это и будут все полные ЭК.

3.      Выписываем дизъюнкцию всех этих ЭК.

Алгоритм представления функции в виде СКНФ.

1. Выписываем носитель функции

2. Для каждого вектора из носителя выписываем дизъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем без отрицания, . если единице – с отрицанием). Это и будут все полные ЭД.

4.      Выписываем конъюнкцию всех этих ЭД.

Булевы функции

Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры).

1.      X & Y = Y&X, X V Y = Y V X – коммутативность.

2.      (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

3.      (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

4.      Поглощение – X & X = X, X V X = X.

5.      Свойства констант

X & 0 = 0

X & I = X, где I – аналог универсального множества.

6.      Инвальтивность (X*)* = X

7.      Дополнимость X V X* = I, X & X* = 0.

8.      Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Применение дискретной математики в информатике

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

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

F = {0…1}

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