Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

15.4. МОДЕЛИРОВАНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ

815

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

ных идет речь. В частности, если определено, что некоторые элементы дан-

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

щий критерий корректности сохранения связей означает проверку этого при

удалении, а иногда и при модификации объектов. В хорошо устроенной базе

данных нарушение такого критерия приводит к активизации реакции, целью

которой является корректировка связей.

Обеспечение всех общих критериев при манипулировании данными ба-

зы называется целостностью базы данных, а действия, направленные на то,

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

последующих пользовательских обращений к базе) восстанавливалась, —

поддержанием целостности.

Теперь перейдем к аспектам, связанным с содержанием.

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

дения, которые были переданы ей на хранение. Простейший случай — аг-

регирование данных, т. е. получение интегральных характеристик для не-

скольких хранимых элементов (например, суммирование значения какого-

либо атрибута по всем элементам, его содержащим). В более сложных слу-

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

хранимых элементов. Иногда некоторый элемент данных, получаемый в ре-

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

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

туальных данных. Можно хранить вычисляемые данные, и развитая систе-

ма сама может решать, какие из них экономнее вычислять при запросах, а

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

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

вычисляемых данных.

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

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

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

базе данных предусмотрены возможности продуцирования данных с помо-

щью правил, которые хранятся как факты, то такая база превращается в базу

знаний. Граница между базами данных и знаний довольно условна, обычно

в литературе четкого их определения не дается, и это повод для появления

разного рода спекуляций.

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

данных. Для одной и той же предметной области в зависимости от назначе-

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

816

ГЛАВА 15. МОДЕЛИРОВАНИЕ

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

обеспечить все необходимое в конкретной информационной системе.

Суть информационных систем — решение задач, для которых они нуж-

ны. Это предполагает обстоятельное исследование предметной области, ре-

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

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

ка разработки информационных систем такова, что на этапе анализа в ходе

определения требований и особенно при выборе ближайшей задачи начина-

ющегося проекта необходимо сначала провести такие исследования и уже на

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

оказывается не выполненным! И так же часто именно это становится причи-

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

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

ся и требуется сохранение накопленных данных), замена интерфейса — эти и

другие дополнительные задачи приходится решать, если аналитический этап

проекта выполнен недоброкачественно.

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

рации, вязанные с ученическими завтраками, но не был выделен абстракт-

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

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

реализацию запросов переписывать заново,а базу данных целиком переструк-

турировать.

Конец примера 15.4.2.

На этапах анализа и конструирования проявляются и различия трех аспектов

информационных систем, о которых было сказано выше.

15.4.1. Информационное обеспечение моделирования

Если система строится для информационного обеспечения моделирова-

ния,то именно она оказывается тем связующим звеном между реалиями пред-

метной области, выделяемыми моделью, средствами управления модельным

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

ватель изучает получаемые результаты счета. Это обстоятельство предопре-

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

a) подсистема ввода исходных данных для модели. Анализ показывает, что

не всегда можно использовать предоставляемые внешние данные непо-

средственно. Их предварительная подготовка (о которой, как показывает

15.4. МОДЕЛИРОВАНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ

817

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

сования форматов внешних данных с данными информационной систе-

мы, так и контролем ошибок ввода. На возможности подсистемы влияет

и то, как часто будет осуществляться процедура ввода, и то, нужно или

нет редактировать входные данные;

b) подсистема модели. Часть системы, инкапсулирующая модельные алго-

ритмы и организацию управления поведением модельных процессов. Для

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

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

дели и что должно происходить после его проведения;

c) подсистема инструментария для работы с моделью.Определяет,как поль-

зователю предъявляются вычисляемые данные, какими способами он мо-

жет просматривать, сопоставлять их, что именно он сможет фиксировать

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

средства, которые предоставляются пользователю для организации про-

гона модели (в том числе, для планирования прогонов), и инструменты

анализа;

d) база данных информационной поддержки моделирования. Активное хра-

нилище поступающей информации, основных и промежуточных резуль-

татов, а также аналитической информации. Для этой части проекта все

другие подсистемы являются только поставщиками и потребителями хра-

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

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

ных — это оптимизация хранения и доступа, защита от преднамеренного

и непреднамеренного искажения хранимых данных, поддержка целостно-

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

15.4.2. Информационные системы для моделей принятия решений

Специфика информационных систем, моделирующих реальные процес-

сы для поддержки принятия решений, состоит в следующем.

Во-первых, они должны ориентироваться на работу с реальными дан-

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

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

области (поддержка контроля ошибок, организация справочников и других

818

ГЛАВА 15. МОДЕЛИРОВАНИЕ

средств обеспечения удобного и корректного ввода), а с другой — они долж-

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

тем, чтобы принимаемые решения были бы максимально точны.

Во-вторых, нужна информационная точность моделирования, в частно-

сти:

a) достоверность. Проводимые расчеты следует адаптировать к наблюде-

ниям, должны соблюдаться внешние и модельные ограничения, необхо-

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

альных процессов;

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

представлял границы применимости информации. Знание точности рас-

четов позволяет повышать и точность управления.В частности,необходи-

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

расчеты остаются достоверными;

c) неизбыточность. Предъявляемая информация должна быть очищена от

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

d) своевременность. Предъявление информации должно происходить в точ-

но установленные сроки, когда она нужна. Обычно достаточно просто

установить критический временной интервал полезности информации (см.

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

мента, когда сведения реально можно использовать) и простирается до то-

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

ности достигается в начале этого интервала, какое-то время полезность

сохраняется, а затем резко падает. За критическим интервалом информа-

ция для принятия решений чаще всего бесполезна

Сравнивая использование информационных систем для моделирования ре-

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

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

альном сравнении вариантов можно говорить только для самых квалифици-

рованных руководителей

. Зато повышается роль оперативности получения

результатов. Возрастает нагрузка на интерфейс, т. к. нужны разнообразные

наглядные средства предъявления как исходных, так и расчетных данных.

Она может быть использована лишь в качестве поучительного примера.

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

не захочет следовать однозначной подсказке.

15.5. СИСТЕМЫ С ДИСКРЕТНЫМИ СОБЫТИЯМИ

819

Ценность

информации для

управления

Время

Момент

возникновения

информации

Критический интервал

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

Интервал максимальной

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

Рис. 15.1. Полезность информации для пользователя

Информационные системы как самостоятельные, не связанными с моде-

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

ществующей литературе (см., например, [31, 78]). Несмотря на то, что сего-

дня делается крен в сторону реляционных систем, из-за которого у многих

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

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

отделимы от реализационной платформы. По этой причине нет смысла оста-

навливаться на них особо.

§ 15.5. СИСТЕМЫ С ДИСКРЕТНЫМИ СОБЫТИЯМИ

Концепция времени является одной из важнейших во многих областях.

Более того, в известном американском аформзме Time is money абсолютная

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

от кого, не можем сохранить, можем лишь тратить.

Поэтому при рассмотрении компьютерного моделирования поведения объ-

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

820

ГЛАВА 15. МОДЕЛИРОВАНИЕ

• образы действующих объектов и

• моделирование времени.

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

ного мира, говорят о системах реального времени. Если же время является

частью виртуального мира системы, то говорят об условном, или модельном,

времени.

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

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

шагами,можно считать неделимыми.Тогда на временной оси у нас есть лишь

дискретная совокупность точек, в которых нужно поддерживать целостность

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

ется модельным, то говорят о системе с дискретными событиями. Эта си-

стуация хорошо подходит как для применения, так и для моделирования как

конвейерного, так и ∨-параллелизма (см. Приложение А).

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

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

программирования. В данном случае модифицируем ее следующим образом.

Пусть нам нужно найти кратчайший путь в нагруженном ориентированном

графе, где каждая дуга оснащена числом. интерпретируемым как ее длина.

Это традиционно интерпретируется как определение кратчайшего пути меж-

ду городами A и B, связанными сетью однонаправленных дорог.

Покажем, что решение задачи можно построить как систему взаимодей-

ствующих процессов с дискретным временем. Это является хорошим мето-

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

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

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

довательной программы

. Идея этого подхода восходит к У.-И. Далу и К. Хо-

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

системы с дискретными событиями, предоставляемой языками

SIMULA 60

SIMULA 67

, совпадавшими по модели времени и структуре управления про-

цессами.

Базовой концепцией в данной задаче естественно является vee-паралле-

лизм.Определение кратчайшего расстояния можно представить как соревно-

Поскольку здесь мы переходим от сравнительно идеальных к низкоуровневым поняти-

ям. такая задача ‘распоследовательностнивания’ является методологически и практически

правильно поставленной, в отличие от обратной задачи распараллеливания.

15.5. СИСТЕМЫ С ДИСКРЕТНЫМИ СОБЫТИЯМИ

821

вание действующих агентов

, «разбредающихся» по разным дорогам, в ско-

рости достижения цели. Сразу же разграничиваются два класса алгоритмов:

прямые,когда общий процесс начинается с A, и обратные, для которых стар-

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

точно рассмотреть по одному прямому и обратному алгоритму.

Прямой алгоритм разбредающихся агентов можно описать как поведение

каждого агента по следующей схеме, в качестве параметра которой задается

местонахождение агента:

1. Если агент стоит в городе, то

(a) Если местонахождение агента есть B, то цель достигнута. В каче-

стве результата выдается пройденный путь.

(b) Агент проверяет, является ли город запретным. Если это так, агент

ликвидируется (понятно, что при этом информация по системе в

целом не теряется — другие агенты продолжают действовать).

(d) Порождается столько наследников агента, сколько дорог исходит

из текущего местонахождения данного агента. При этом в каче-

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

запомненный родительским агентом от A до текущего местонахо-

ждения (не принципиально, уничтожается ли родительский агент,

или он становится одним из экземпляров наследников). Если нет

дорог из текущего местонахождения, то агент ликвидируется —

он зашел в тупик.

2. Переход к следующему моменту времени — для каждого агента осу-

ществляется один шаг передвижения по текущей дороге. Это можно

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

необходимое для перемещения в свой следующий пункт (мерой време-

ни в данном случае служит расстояние между пунктами).

3. Осуществляется переход к пункту 1.

Видно, что алгоритм завершает работу, когда найден путь из A в B, либо

когда все агенты оказываются ликвидированы.

В данном случае для подчеркивания специфики экземпляры объектов лучше называть

так.

822

ГЛАВА 15. МОДЕЛИРОВАНИЕ

Как и оычно, более жесткие условия на окончательную программу влекут

за собой во многих отношениях более мягкие требования к прототипу (нужн

расширить возможности его перестройки в разные варианты окончательной

программы), но при этом желательно максимально возможное повышение

уровня понятий прототипа. Если в конце концов программа будет реализо-

ывана на фон Неймановской системе, не нужно обращать внимание на то,

сколько агентов могут действовать одновременно. В частности, в случае га-

рантированного наличия пути из A в B можно не проверять запретность либо

ослабить ее до случая,когда предок данного агента посещал данный город,и,

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

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

о графе дорог и городов.

Приведенный алгоритм нуждается в запоминании сведений о пройден-

ном пути в локальных данных агентов. Это означает большую избыточность

хранения: локальные данные каждого из агентов, которые будут ликвидиро-

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

получен, получаются лишь некоторые его характеристики. Этого недостатка

лишено решение с помощью обратного блуждания, т. е. от B к A. Для него

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

a) локальная информация об агентах и их путях не запоминается;

b) в качестве пометки о посещении указывается, из какого города агент при-

шел в данный город (это можно называть пометкой-рекомендацией).

В результате, когда какой-либо из агентов достигнет A, последовательность,

начинающаяся с A и выстраивающаяся по пометкам-рекомендациям,дает ис-

комый путь (именно этот обратный алгоритм излагается Далом и Хоором).

Рис. 15.2 иллюстрирует работу всех трех алгоритмов: прямого (a), прямо-

го с пометками (b) и обратного с пометками-рекомендациями (c). Надписи на

дугах-дорогах обозначают агентов, верхние индексы на них — порядок по-

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

посещаемых городах.Зачеркнутые надписи указывают на уничтожение аген-

та в связи с использованием сведений о посещениях городов.

Как прямой,так и обратный алгоритмы работоспособны,если обеспечить

одновременную работу сразу всех процессов агентов. Если модель вычисле-

ний отражает возможность многопроцессорной обработки, причем с потен-

циально неограниченным

числом процессоров, то это условие выполнено

По крайней мере с заведомо большим. чем нужно для данной задачи.

15.5. СИСТЕМЫ С ДИСКРЕТНЫМИ СОБЫТИЯМИ

823

114

A, t

, t

211

A, t

, t

211

A, t

, t

111

A, t

, t

112

A, t

, t

113

A, t

, t

A, t

2111

A, t

, t

211

A, t

, t

111

A, t

, t

112

A, t

, t

113

A, t

, t

A, t

114

A, t

, t

1212

211

212

1211

121

A/t

b) прямой алгоритм с пометками

a) прямой алгоритм с локальным запоминанием пути

Рис. 15.2. Логика алгоритмов поиска пути

824

ГЛАВА 15. МОДЕЛИРОВАНИЕ

автоматически.

Если параллелизм возможен,но процессов недостаточно (например, если

Вы решите воспользоваться для реализации этих алгоритмов

Prolog

-систе-

мой

Muse

), то мы находимся в самой трудной ситуации, требующей творче-

ских решений, комбинации научного и инженерного подхода.

Для языка, отвечающего фон Неймановской модели вычислений, парал-

лелизм очевидно невозможен, а значит, решение подсказывается само собой:

необходима имитация параллелизма. Одним из подходов к такой имитации

является, к примеру, хорошо известный метод волны, который исходит из

строго упорядоченного последовательного перебора вариантов, соответству-

ющих агентам-процессам. Но данный метод есть полное устранение агентов,

поскольку все их параллельные действия заменяются выстраиванием кон-

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

а потому агенты нужны лишь в качестве призраков. Метод выстраивания про-

цессов в линейную последовательность — одно из самых широко применя-

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

дела все детерминированные переборные алгоритмы (с разным успехом) за-

нимаются именно таким выстраиванием.

Но с общих позиций линейное выстраивание — вырожденный метод. Бо-

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

ются и вовсю эксплуатируются конкретные свойства конкретного линейного

порядка

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

SIMULA 67

. Он в

явном виде провозглашает имитацию параллелизма и, следовательно, оста-

вляет для человека возможность мыслить в категориях действующих аген-

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

многих алгоритмов. Систему с дискретными событиями можно рассматри-

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

альным параллелизмом и реальной последовательностью реализации, име-

ющим то преимущество, что концепции остаются нетронутыми и тем самым

качество и гибкость программ резко повышаются.

Классическая реализация систем с дискретными событиями —это общая

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

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

пытается точно решить конкретную задачу.

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

чившегося линейного — концептуальный тупик (сравни

PROLOG

,угодивший в данную кон-

цептуальную яму, и

CLOS

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

и антистандартностью конкретного алгоритма линеаризации).