WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

«Серия учебных пособий Информатика в техническом университете !.". #$%&#'$( !"#$%!#&'&($"!))$* +($*,#&($"!)&* Москва — 2000 Даны сведения по различным аспектам и видам обеспечения систем ...»

-- [ Страница 4 ] --

. Простейший способ задания множества C — явное перечисление всех альтернатив. Семантика и форма описания альтернатив существенно зависят от приложения. Для представления таких описаний в памяти ЭВМ и доступа к ним используют '*E#"/)='#**#-0#'+%#(.$ +'+&$/. (ИПС). Каждой альтернативе в ИПС соответствует поисковый образ, состоящий из значений атрибутов xi и ключевых слов вербальных характеристик. Явное перечисление альтернатив при представлении множества альтернатив возможно лишь при малой мощности C. Поэтому в большинстве случаев используют неявное описание C в виде способа (алгоритма или набора правил %) синтеза проектных решений из ограниченного набора элементов Q. Поэтому здесь C = , а типичный процесс синтеза проектных решений состоит из следующих этапов: 1) формирование альтернативы Ki (это может быть выбор из базы данных ИПС по сформированному поисковому предписанию или генерация из Q в соответствии с правилами %);

2) оценка альтернативы по результатам моделирования с помощью модели Мод;

3) принятие решения (выполняется ЛПР — лицом, принимающим решение, или автоматически) относительно перехода к следующей альтернативе или прекращения поиска. Для описания множеств % и Q используют следующие подходы. 1. L#"E#4#8'1$+%'$ &)24'=. ' )45&$"*)&'(*.$ D-DRD--$"$(59. 2. Представление знаний в '*&$44$%&7)45*., +'+&$/), — фреймы, семантические сети, продукции. 3. V$*$&'1$+%'$ /$&#-.. 4. Базы E'6'1$+%', BEE$%&#( и B("'+&'1$+%', 0"'$/#(, применяемые при решении задач изобретательского характера. E48H4D4@+A.,7+. -:BD+=1. L#"E#4#8'1$+%)9 &)24'=) (E) представляет собой обобщенную структуру в виде множества функций, выполняемых компонентами синтезируемых объектов рассматриваемого класса, и подмножеств способов их реализации. Каждой функции можно поставить в соответствие одну строку таблицы, каждому способу ее реализации — одну клетку в этой строке. Следовательно, в морфологических таблицах элемент Mij означает j-й вариант реализации i-й функции в классе технических объектов, описываемом матрицей E. Другими словами, множество альтернатив можно представить в виде отношения E, называемого морфологической таблицей E = , где X — множество свойств (характеристик или функций), присущих объектам рассматриваемого типа, n — число этих свойств, R = < R1, R2,...,Rn>, Ri — множество значений (способов реализации) iго свойства, мощность этого множества далее обозначена Ni. При этом собственно множество альтернатив C представлено композицией множеств Ri, т.е. каждая альтернатива включает по одному элементу (значению) из каждой строки морфологической таблицы. Очевидно, что общее число альтернатив k, представляемых морфологической таблицей, равно k = N i.

i=W n Морфологические таблицы обычно считают средством неавтоматизированного синтеза, помогающим человеку просматривать компактно представленные альтернативы, преодолевать психологическую инерцию. Последнее связано с тем, что внимание ЛПР обращается на варианты, которые без морфологической таблицы оставались бы вне его поля зрения. Собственно таблица E не содержит сведений о способе синтеза. Однако на базе E возможно построение методов синтеза с элементами алгоритмизации. В таких методах вводится метризация мор&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M фологического пространства. Морфологическое пространство составляют возможные законченные структуры, принимается, что расстояние между структурами *1 и *2 есть число несовпадающих элементов (каждая клетка E есть один элемент). Поэтому можно говорить об окрестностях решений. Далее исходят из предположения о компактности “хороших” решений, которое позволяет вместо полного перебора ограничиваться перебором в малой окрестности текущей точки поиска. Таким образом, гипотеза о “компактности” и метризация пространства решений фактически приводят к построению математической модели, к которой можно применить методы дискретной оптимизации, например локальные методы. К недостаткам E относятся неучет запрещенных сочетаний элементов в законченных структурах и отражение состава элементов в структурах без конкретизации их связей. Кроме того, морфологические таблицы строят в предположении, что множества Ri взаимно независимы, т.е. состав способов реализации i-й функции не меняется при изменении значений других функций. Очевидно, что предположение о взаимной независимости множеств Ri оправдано лишь в сравнительно простых структурах. Последний недостаток устраняется путем обобщения метода морфологических таблиц – при использовании метода альтернативных (И-ИЛИ) графов. CDF-.80:-+901. @8:H1. Любую морфологическую таблицу можно представить в виде дерева (рис. 4.12). На рисунке функции представлены вершинами И (темные кружки), значения функций — вершинами ИЛИ (светлые кружки). Очевидно, что таблица представляет множество однотипных объектов, поскольку все они характеризуются одним и тем же множеством функций. Для разнотипных объектов применяют многоярусные %+,. 4.)2. Дерево, соответствующее альтернативные графы. Например, на рис. 4.13 показан морфологической таблтце двухъярусный граф, в котором для разных типов объектов предусмотрены разные подмножества функций. Если допустить некоторую избыточность при изображении И-ИЛИ- графа, то его можно превратить в И-ИЛИ-дерево, что ведет к определенным удобствам. Очевидно, что И-ИЛИ-дерево можно представить как совокупность морфологических таблиц. Каждая И вершина дерева соответствует частной морфологической таблице, т.е. множеству функций так, что i-я выходящая ветвь отображает i-ю функцию. Каждая ИЛИ вершина, инцидентная i-й ветви, соответствует множеству вариантов реализации i-й функции, при этом j-я исходящая из ИЛИ вершины ветвь отображает j-й %+,. 4.)3. И-ИЛИ-граф вариант реализации. Алгоритмизация синтеза на базе И-ИЛИ-деревьев требует введения правил выбора альтернатив в каждой вершине ИЛИ. Эти правила чаще всего имеют эвристический характер, связаны с требованиями ТЗ, могут отражать запреты на сочетания определенных компонентов структур. Трудности эффективного решения задачи существенно возрастают при наличии ограничений, типичными среди которых являются ограничения на совместимость способов реализации разных функций, т.е. ограничения вида (4.29) :ij and :pq = false, где :ij = true, если в оцениваемый вариант вошел элемент Эij, иначе :ij = false. Условие (4.29) означает, что в допустимую структуру не могут входить одновременно элементы Эij и Эpq. Совокупность ограничений типа (4.29) можно представить как систему логических уравнений с неизвестными :ij. Тогда задачу синтеза можно решать эволюционными методами, если предварительно или одновременно с ней решать систему логических уравнений (задачу о выполнимости). &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M !,A+,D.0+>. Очевидно, что в большинстве случаев структурного синтеза вместо нереализуемого явного представления всего множества проектных решений задают множество элементов и совокупность правил объединения этих элементов в допустимые структуры (проектные решения). Эти множества элементов и правил часто представляют в виде E#"/)45*#;

+'+&$/. ('+1'+4$*'9), т.е. задача синтеза имеет вид ЗС =

#M;

C';

">, где Q — алфавит исчисления (алфавит представлен базовыми элементами, из которых синтезируется структура);

#M — множество букв, не совпадающих с буквами алфавита Q и служащих для обозначения переменных;

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

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

4.4. E.-451,-8<7-<804@4,+0-.?: 9 *C"% *+,-./1 +,7<,,-9.004@4 +0-.DD.7-:. В теории интеллектуальных систем синтез реализуется с помощью экспертных систем (ЭС) ЭС = <БД, БЗ, И>, где БД — база данных, включающая сведения о базовых элементах;

БЗ — база знаний, содержащая правила конструирования вариантов структуры;

И — интерпретатор, устанавливающий последовательность применения правил из БЗ. Системы искусственного интеллекта (СИИ) основаны на знаниях, отделенных от процедурной части программ и представленных в одной из характерных форм. Такими формами могут быть продукции, фреймы, семантические сети. Реально функционирующие в современных САПР системы с базами знаний чаще всего относятся к классу ЭС. !"#-7%='9 представляет собой правило типа “если K, то I”, где K — условие, а I — действие или следствие, активизируемое при истинности K. Продукционная БЗ содержит совокупность правил, описывающих определенную предметную область. H"$;

/ — структура данных, в которой в определенном порядке представлены сведения о свойствах описываемого объекта. Типичный вид фрейма: <имя фрейма;

x1 = p1;

x2 = p2;

...;

xN = pN;

q1, q2,...qM>, где xi — имя i-го атрибута, pi — его значение, qi — ссылка на другой фрейм или некоторую обслуживающую процедуру. В качестве pi можно использовать имя другого (вложенного) фрейма, описывая тем самым иерархические структуры фреймов. :$/)*&'1$+%)9 +$&5 — форма представления знаний в виде совокупности понятий и явно выраженных отношений между ними в некоторой предметной области. Семантическую сеть удобно представлять в виде графа, в котором вершины отображают понятия, а ребра или дуги — отношения между ними. В качестве вершин сети можно использовать фреймы или продукции. F%+0$"&*)9 +'+&$/) является типичной системой искусственного интеллекта, в которой БЗ содержит сведения, полученные от людей-экспертов в конкретной предметной области. Трудности формализации процедур структурного синтеза привели к популярности применения экспертных систем в САПР, поскольку в них вместо выполнения синтеза на базе формальных математических методов осуществляется синтез на основе опыта и неформальных рекомендаций, полученных от экспертов. O+,78.-04. /:-./:-+A.,74. 384@8://+849:0+.. Выбор метода поиска решения — вторая проблема после формализации задачи. Если при формализации все управляемые параметры удалось представить в числовом виде, то можно попытаться применить известные методы ДМП. &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M Задача ДМП определяется следующим образом:

extr F(N), XD (4.30) D = { X | W(X) > 0, Z(X) = 0 }, где F(X) — целевая функция;

W(X), Z (X) — вектор-функции, связанные с представленными в ТЗ требованиями и ограничениями;

D — дискретное множество. В полученной модели, во-первых, каждый элемент множества рассматриваемых законченных структур должен иметь уникальное сочетание значений некоторого множества числовых параметров, вектор которых обозначим X. Во-вторых, необходимо существование одной или нескольких функций J(X), значения которых могут служить исчерпывающей оценкой соответствия структуры предъявляемым требованиям. В-третьих, функции J(X) должны отражать внутренне присущие данному классу объектов свойства, что обеспечит возможность использования J(X) в качестве не только средств оценки достигнутого при поиске успеха, но и средств указания перспективных направлений продолжения поиска. Эти условия выполнимы далеко не всегда, что и обусловливает трудности формализации задач структурного синтеза. Однако наличие формулировки (4.30) еще не означает, что удастся подобрать метод (алгоритм) решения задачи (4.30) с приемлемыми затратами вычислительных ресурсов. Другими словами, применение точных методов математического программирования вызывает непреодолимые трудности в большинстве случаев практических задач типичного размера из-за их принадлежности к классу NPтрудных задач. Поэтому лидирующее положение среди методов решения задачи (4.30) занимают приближенные методы, в частности, декомпозиционные методы, отражающие принципы блочно-иерархического проектирования сложных объектов. Декомпозиционные методы основаны на выделении ряда иерархических уровней, на каждом из которых решаются задачи приемлемого размера. Основу большой группы математических методов, выражающих стремление к сокращению перебора, составляют операции разделения множества вариантов на подмножества и отсечения неперспективных подмножеств. Эти методы объединяются под названием /$&#-) ($&($;

' 8")*'=. Основная разновидность метода ветвей и границ относится к точным методам решения комбинаторных задач. Рассмотрим эту разновидность. Пусть имеется множество решений M, в котором нужно выбрать оптимальный по критерию F(Xj) вариант, где Xj — вектор параметров варианта mj M;

пусть также имеется алгоритм для вычисления нижней границы L(Mk) критерия F(Xj) в любом подмножестве Mk множества M, т.е. такого значения L(Mk), что F(Xj) L(Mk) при любом j (подразумевается минимизация F(X)). Тогда основная схема решения задач в соответствии с методом ветвей и границ содержит следующие процедуры: 1) в качестве Mk принимаем все множество M;

2) ветвление: разбиение Mk на несколько подмножеств Mq;

3) вычисление нижних границ L(Mq) в подмножествах Mq;

4) выбор в качестве Mk подмножества Mp с минимальным значением нижней границы критерия (среди всех подмножеств, имеющихся на данном этапе вычислений), сведения об остальных подмножествах Mq и их нижних границах сохраняются в отдельном списке;

5) если | Mk| > 1, то переход к процедуре 2, иначе одноэлементное множество Mk есть решение. Метод ветвей и границ в случае точного вычисления нижних границ относится к точным методам решения задач выбора и потому в неблагоприятных ситуациях может приводить к экспоненциальной временной сложности. Однако метод часто используют как приближенный, поскольку можно применять приближенные алгоритмы вычисления нижних границ. Среди других приближенных методов решения задачи ДМП отметим /$&#- 4#%)45*#;

#0&'/'6)=''. Так как пространство D метризовано, то можно использовать понятие )-окрестности Sa(Xk) текущей точки поиска Xk. Вместо перебора точек во всем пространстве D осуществляется перебор точек только в Sa(Xk). Если F(Xj) F(Xk) для всех Nj Sa(Xk), то считается, что найден локальный минимум целевой функции в точке Xk. В противном случае точку Xq, в которой достигается минимум F(X) в Sa(Xk), принимают в качестве новой текущей точки поиска. &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M QD./.0-1 -.48++,D4L04,-+. В теории сложности выделяют массовые и индивидуальные задачи. Первые из них сформулированы в общем виде, вторые представлены с конкретными числовыми значениями исходных данных. Исследования сложности проводятся в отношении массовых задач и получаемые выводы, как правило, относятся к наихудшему случаю — к наиболее неблагоприятному возможному сочетанию исходных данных. Цель исследований — установление вида зависимости объема Q требуемых вычислений от размера задачи N. Объем вычислений может определяться числом арифметических и логических операций или затратами процессорного времени ЭВМ с заданной производительностью. Размер задачи в общем случае связывают с объемом описания задачи, но в приложениях понятие размера легко наполняется более конкретным содержанием. Далее, в теории сложности задач выбора вводят понятие эффективных и неэффективных алгоритмов. К эEE$%&'(*./ относят алгоритмы с полиномиальной зависимостью Q от N, например, алгоритмы с функцией Q(N) линейной, квадратичной, кубической и др. Для *$BEE$%&'(*., алгоритмов характерна экспоненциальная зависимость Q(N). Важность проведения резкой границы между полиномиальными и экспоненциальными алгоритмами вытекает из сопоставления числовых примеров роста допустимого размера задачи с увеличением быстродействия Б используемых ЭВМ (табл. 4.1, в которой указаны размеры задач, решаемых за одно и то же время ? на ЭВМ с быстродействием Бi при различных зависимостях сложности Q от размера N). Эти примеры показывают, что выбирая ЭВМ в O раз более быстродействующую, получаем увеличение размера решаемых задач при линейных алгоритмах в O раз, при квадратичных алгоритмах в К1/2 раз и т.д. M:BD+=: 4.) Иначе обстоит дело с неэффективными Q(N) Б1 Б2 = 100 Б1 Б3 = 1000 Б1 алгоритмами. Так, в случае сложности 2N для одного и того же процессорного времени разN N1 100 N1 1000 N1 мер задачи увеличивается только на lgK / lg2 N2 N2 10 N2 31.6 N2 единиц. Следовательно, переходя от ЭВМ с Б = 1 Gflops к суперЭВМ с Б = 1 Tflops, можN3 N3 4.64 N3 10 N3 но увеличить размер решаемой задачи только 2N N4 6.64+N4 9.97+N4 на 10, что совершенно недостаточно для практических задач. Действительно, в таких задачах, как например, синтез тестов для БИС число входных двоичных переменных может составлять более 150 и поэтому полный перебор всех возможных проверяющих кодов потребует выполнения более 2150 вариантов моделирования схемы. В теории сложности все комбинаторные задачи разделены на классы: — класс неразрешимых задач, в который входят массовые задачи, решение которых полным перебором принципиально невозможно с точки зрения современных научных представлений;

этот класс отделяется от других задач так называемым пределом Бреммермана, оцениваемым величиной N = 1093;

отметим, что реальный предел неразрешимости значительно ниже;

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

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

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

— класс NP-полных задач, характеризующийся следующими свойствами: 1) для этих задач неизвестны полиномиальные алгоритмы точного решения;

2) любые задачи внутри этого класса могут быть сведены одна к другой за полиномиальное время. Последнее означает, что если будет найден полиномиальный алгоритм для точного решения хотя бы одной NP-полной задачи, то за полиномиальное время можно будет решить любую задачу этого класса. Из результатов теории сложности следуют важные практические рекомендации: 1) приступая к решению некоторой комбинаторной задачи, следует сначала проверить, не принадлежит ли она к &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M классу NP-полных задач, и если это так, то не следует тратить усилия на разработку алгоритмов и программ точного решения;

2) отсутствие эффективных алгоритмов точного решения массовой задачи выбора отнюдь не означает невозможности эффективного решения индивидуальных задач из класса NP-полных или невозможности получения приближенного решения по эвристическим алгоритмам за полиномиальное время. Q94D;

=+4001. /.-451. F(#4<='#**.$ /$&#-. (ЭМ) предназначены для поиска предпочтительных решений и основаны на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому состоянию систем. В отличие от точных методов математического программирования ЭМ позволяют находить решения, близкие к оптимальным, за приемлемое время, а в отличие от известных эвристических методов оптимизации характеризуются существенно меньшей зависимостью от особенностей приложения (т.е. более универсальны) и в большинстве случаев обеспечивают лучшую степень приближения к оптимальному решению. Универсальность ЭМ определяется также применимостью к задачам с неметризуемым пространством управляемых переменных (т.е. среди управляемых переменных могут быть и лингвистические). Важнейшим частным случаем ЭМ являются 8$*$&'1$+%'$ /$&#-. ' )48#"'&/.. Генетические алгоритмы (ГА) основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции. Свойства объектов представлены значениями параметров, объединяемыми в запись, называемую в ЭМ,"#/#+#/#;

. В ГА оперируют хромосомами, относящимися к множеству объектов — 0#0749=''. Имитация генетических принципов — вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции — ведет к эволюционному улучшению значений целевой функции (функции полезности) от поколения к поколению. Среди ЭМ находят применение также методы, которые в отличие от ГА оперируют не множеством хромосом, а единственной хромосомой. Так, метод дискретного 4#%)45*#8# 0#'+%) (его англоязычное название Hillclimbing) основан на случайном изменении отдельных параметров (т.е. значений полей в записи или, другими словами, значений генов в хромосоме). Такие изменения называют /7&)='9/'. После очередной мутации оценивают значение E7*%='' 0#4$6*#+&' F (Fitness Function) и результат мутации сохраняется в хромосоме только, если F улучшилась. В другом ЭМ под названием “L#-$4'"#()*'$ #&@'8)” (Simulated Annealing) результат мутации сохраняется с некоторой вероятностью, зависящей от полученного значения F. "4,-:0497: ?:5:A+ 34+,7: 43-+/:DF016 8.I.0+2, 34/4RF;

@.0.-+A.,7+6 :D@48+-/49. Для применения ГА необходимо: 1) выделить совокупность свойств объекта, характеризуемых внутренними параметрами и влияющих на его полезность, т.е. выделить множество управляемых параметров X = (x1,x2,...xn);

среди xi могут быть величины различных типов (real, integer, Boolean, enumeration). Наличие нечисловых величин (enumeration) обусловливает возможность решения задач не только параметрической, но и структурной оптимизации;

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

3) Разработать математическую модель объекта, представляющую собой алгоритм вычисления F для заданного вектора N;

4) Представить вектор N в форме хромосомы — записи следующего вида P P P....

Pn В ГА используется следующая терминология: 8$* — управляемый параметр xi;

)44$45 — значение гена;

&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M 4#%7+ (0#6'='9) — позиция, занимаемая геном в хромосоме;

8$*#&'0 — экземпляр хромосомы, генотип представляет совокупность внутренних параметров проектируемого с помощью ГА объекта;

8$*#E#*- — множество всех возможных генотипов;

E7*%='9 0#4$6*#+&' (приспособленности) F — целевая функция;

E$*#&'0 — совокупность генотипа и соответствующего значения F, под фенотипом часто понимают совокупность выходных параметров синтезируемого с помощью ГА объекта. "84,-42 @.0.-+A.,7+2 :D@48+-/. Вычислительный процесс начинается с генерации исходного поколения — множества, включающего N хромосом, N — размер популяции. Генерация выполняется случайным выбором аллелей каждого гена. Далее организуется циклический процесс смены поколений: for (k=0;

k

k++) { for (j=0;

j

j++) { D6&)" ")1,.#(/25)7 8$"6 @")%)2)%;

F")22):#";

='.$>,,;

9>#+5$ C'+5>,, 8)(#3+)2., F 8).)%5):;

G#(#5>,4;

} H$%#+$.#5'?#*) 8)5)(#+,4 +):6%;

} Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, на котором формируются экземпляры нового (следующего за текущим) поколения. Во внутреннем цикле повторяются операторы выбора родителей, кроссовера родительских хромосом, мутации, оценки приспособленности потомков, селекции хромосом для включения в очередное поколение. Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме. I.2#" "#-'&$4$;

. Этот оператор имитирует естественный отбор, если отбор в родительскую пару хромосом с лучшими значениями функции полезности F более вероятен. Например, пусть F требуется минимизировать. Тогда вероятность Si выбора родителя с хромосомой Ci можно рассчитать по формуле Si = (Fmax-Fi) / (Fmax - Fj) j=W N (4.31) где Fmax — наихудшее значение целевой функции F среди экземпляров (членов) текущего поколения, Fi — значение целевой функции i-го экземпляра. Правило (4.31) называют 0")('4#/ %#4$+) "74$&%'. Если в колесе рулетки выделить секторы, пропорциональные значениям Fmax-Fi, то вероятности попадания в них суть Pi, определяемые в соответствии с (4.31).

+ - 0 B. -. Пусть N=4, значения Fi и Pi приведены в табл. 4.2. M:BD+=: 4. i 1 2 3 Fi 2 7 6 Fmax-Fi 5 0 1 Pi 0,5 0 0,1 0, &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M O"#++#($" (+%"$A'()*'$). Кроссовер, иногда называемый кроссинговером, заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном) кроссовере хромосомы родителей разрываются в некоторой позиции, одинаковой для обоих родителей, выбор места разрыва равновероятен, далее происходит рекомбинация образующихся частей родительских хромосом, как это показано в табл. 4.3, где разрыв подразумевается между пятым и шестым локусами.

M:BD+=: 4. Хромосома родителя A родителя B потомка * потомка D f a f a a b a b c c c c d d d d Гены g e g e k f f k v g g v e h h e L7&)=''. Оператор мутации выполняется с некоторой вероятностью Sм, т.е. с вероятностью Sм происходит замена аллеля случайным значением, выбираемым с равной вероятностью в области определения гена. Именно благодаря мутациям расширяется область генетического поиска. :$4$%='9. После каждого акта генерации пары потомков в новое поколение включается лучший экземпляр пары. Внутренний цикл заканчивается, когда число экземпляров нового поколения станет равным N. Количество повторений G внешнего цикла чаще всего определяется автоматически по появлению признаков вырождения (стагнации) популяции, но с условием не превышения заданного лимита машинного времени. %:?049+504,-+ @.0.-+A.,7+6 43.8:-4849. Возможны отклонения от представленной выше в простом генетическом алгоритме схемы вычислений. O"#++#($". Во-первых, допустимы схемы многоточечного кроссовера. Во-вторых, отметим ситуации, когда на состав аллелей наложены некоторые дополнительные условия. Например, пусть в задаче разбиения графа число вершин в подграфах C1 и C2 должно быть N1 и N2 и пусть k-й аллель, равный 1, означает, что вершина k попадает в C1, если же k-й аллель равен 0, то в C2. Очевидно, что число единиц в хромосоме должно равняться N1, число нулей — N2. Тогда при рекомбинации левый участок хромосомы берется от одного из родителей без изменений, а в правом участке (от другого родителя) нужно согласовать число единиц с N1 тем или иным способом. Один из способов — метод PMX (Partially Matched Crossover). Для иллюстрации PMX рассмотрим пример двухточечного кроссовера в задаче, когда в хромосоме должны присутствовать, причем только по одному разу, все значения генов из заданного набора. Пусть в примере этот набор включает числа от 1 до 9. M:BD+=: 4.4 В табл. 4.4 первые две строки представляют родительские хромосомы. Третья стро) 2 3 4 5 6 7 8 9 ка содержит хромосому одного из потомков, 3 7 ) 9 2 4 8 6 5 сгенерированного в результате применения ) 2 ) 9 2 6 7 8 9 двухточечного кроссовера (после второго и пятого локусов). Полученная хромосома не ) 2 3 9 5 6 7 8 4 относится к числу допустимых, так как в ней значения генов 1, 2 и 9 встречаются дважды, а значения 3, 4 и 5 отсутствуют. Четвертая строка показывает результат применения РМХ. В этом методе выделяются сопряженные пары аллелей в одноименных локусах одной из рекомбинируемых частей. В нашем примере это пары (3 и 1), (4 и 9), (5 и 2). Хромосома потомка просматривается слева направо;

если повторно встречается некоторое значение, оно заменяется на сопряженное значение. Так, в примере в локусах 3, 5 и 9 повторно встречаю&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M щиеся аллели 1, 2 и 9 последовательно заменяются на значения 3, 5 и 4. L7&)=''. Бывают точечными (в одном гене), макромутациями (в нескольких генах) и хромосомными (появление новой хромосомы). Обычно вероятность появления мутации указывается среди исходных данных. Но возможно автоматическое регулирование числа мутаций при их реализации только в ситуациях, когда родительские хромосомы различаются не более чем в K генах. :$4$%='9. После определения и положительной оценки потомка он может быть сразу же включен в текущую популяцию вместо худшего из своих родителей, при этом из алгоритма исключается внешний цикл (что однако не означает сокращения общего объема вычислений). Другой вариант селекции — отбор после каждой операции скрещивания двух лучших экземпляров среди двух потомков и двух родителей. Часто член популяции с минимальным (лучшим) значением целевой функции принудительно включается в новое поколение, что гарантирует наследование приобретенных этим членом положительных свойств. Такой подход называют B4'&'6/#/. Обычно элитизм способствует более быстрой сходимости к локальному экстремуму, однако в многоэкстремальной ситуации ограничивает возможности попадания в окрестности других локальных экстремумов.

+ - 0 B.F 6 9 0.. Хромосому N* будем называть точкой локального минимума, если F(X*)

Следующий вариант селекции — отбор N экземпляров среди членов репродукционной группы, которая составляется из родителей, потомков и мутантов, удовлетворяющих условию Fi < t, где t — пороговое значение функции полезности. Порог может быть равен или среднему значению F в текущем поколении, или значению F особи, занимающей определенное порядковое место. При этом мягкая схема отбора — в новое поколение включаются N лучших представителей репродукционной группы. Жесткая схема отбора — в новое поколение экземпляры включаются с вероятностью qi: qi = (Fmax-Fi) / (Fmax - Fj) j=W Nr где Nr — размер репродукционной группы. !$"$70#"9-#1$*'$. Кроме перечисленных основных операторов, находят применение некоторые дополнительные. К их числу относится оператор переупорядочения генов — изменения их распределения по локусам. Назначение переупорядочения связано со свойством, носящим название эпистасис. F0'+&)+'+ имеет место, если функция полезности зависит не только от значений генов (аллелей), но и от их позиционирования. Наличие эпистасиса говорит о нелинейности целевой функции и существенно усложняет решение задач. Действительно, если некоторые аллели двух генов оказывают определенное положительное влияние на целевую функцию, образуя некоторую связку (схему), но вследствие эпистасиса при разрыве связки эти аллели оказывают уже противоположное влияние на функцию полезности, то разрывать такие схемы не следует. А это означает, что связанные эпистасисом гены желательно располагать близко друг к другу, т.е. при небольших длинах схем. Оператор переупорядочения помогает автоматически “нащупать” такие совокупности генов (они называются хромосомными блоками или building blocks) и разместить их в близких локусах. K.0.-+A.,7+2 /.-45 74/B+0+849:0+> T98+,-+7. Возможны два подхода к формированию хромосом. Первый из них основан на использовании в качестве генов проектных параметров. Например, в задаче размещения микросхем на плате локусы соответствуют посадочным местам на плате, а генами являются номера (имена) микросхем. Другими словами, значением k-го гена будет номер микросхемы в k-й позиции. Во втором подходе генами являются не сами проектные параметры, а номера эвристик, используемых для определения проектных параметров. Так, для задачи размещения можно применять несколько эвристик. По одной из них в очередное посадочное место нужно помещать микросхему, имеющую наибольшее число связей с уже размещенными микросхемами, по другой — микросхему с минимальным числом связей с еще не размещенными микросхемами и т.д. Генетический поиск в этом &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! %!#*%!#&F*:,$* $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M случае есть поиск последовательности эвристик, обеспечивающей оптимальный вариант размещения. Второй подход получил название — /$&#- %#/2'*'"#()*'9 B("'+&'%. Этот метод оказывается предпочтительным во многих случаях. Например, в задачах синтеза расписаний распределяется заданное множество работ во времени и между обслуживающими устройствами — серверами, т.е. проектными параметрами для каждой работы будут номер сервера и порядковый номер в очереди на обслуживание. Пусть N — число работ, M — число серверов. Если гены соответствуют номерам работ, то в первом подходе в хромосоме нужно иметь 2N генов и общее число отличающихся друг от друга хромосом W заметно превышает наибольшее из чисел N! и MN. Согласно методу комбинирования эвристик, число генов в хромосоме в два раза меньше, чем в первом подходе, и равно N. Поэтому если число используемых эвристик равно K, то мощность множества возможных хромосом уже несравнимо меньше, а именно W = KN. Очевидно, что меньший размер хромосомы ведет к лучшей вычислительной эффективности, а меньшее значение W позволяет быстрее найти окрестности искомого экстремума. Кроме того, в методе комбинирования эвристик все хромосомы, генерируемые при кроссовере, будут допустимыми. В то же время при применении обычных генетических методов необходимо использовать процедуры типа PMX для корректировки генов, относящихся к номерам в очереди на обслуживание, что также снижает эффективность поиска.

P38:L0.0+> + 94384,1 5D>,:/4740-84D> 1. Дайте формулировку задачи математического программирования. 2. В чем заключаются трудности решения многокритериальных задач оптимизации? 3. Что такое “множество Парето”? 4. Для функции, заданной своими линиями равного уровня (рис. 4.14), постройте траектории поиска методами конфигураций, деформируемого многогранника, наискорейшего спуска из исходной точки N0. 5. Как Вы считаете, можно ли применять метод проекции градиента для решения задач оптимизации с ограничениями типа неравенств? 6. Что такое “овражная целевая функция”? Приведите пример такой функции для двумерного случая в виде совокупности %+,. 4.)4. Пример для построения траекторий линий равного уровня. поиска 7. Какие свойства характеризуют класс NP-полных задач? 8. Морфологическая таблица содержит 8 строк и 24 столбца. Сколько различных вариантов структуры представляет данная таблица? 9. Приведите пример И-ИЛИ графа для некоторого знакомого Вам приложения. 10. Приведите примеры продукций из знакомого Вам приложения. 11. Дайте предложения по постановке задачи компоновки модулей в блоки для ее решения генетическими методами. Какова структура хромосомы?

&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :01=.B9?. 1-./? 0 ;

-3O-6BB93B.=3/0F.1<0. <3B;

2.<1? :!+( 5.). J<07=++,.-.94@4 384@8://04@4 4B.,3.A.0+> J<07=++ + 6:8:7-.8+,-+7+,.-.916 43.8:=+40016,+,-./. В ПО АС принято выделять общесистемное ПО, системные среды и прикладное ПО. К общесистемному ПО относят операционные системы (ОС) используемых ЭВМ и вычислительных систем и сетевое ПО типовых телекоммуникационных услуг. Различают ОС со встроенными сетевыми функциями и оболочки над локальными ОС. В соответствии с другим признаком классификации сетевые ОС подразделяют на одноранговые и функционально несимметричные (ОС для систем клиент-сервер). Основные функции сетевой ОС: — управление каталогами и файлами;

— управление ресурсами;

— коммуникационные функции;

— защита от несанкционированного доступа;

— обеспечение отказоустойчивости;

— управление сетью. Q0")(4$*'$ %)&)4#8)/' ' E);

4)/' является одной из первоочередных функций сетевой ОС, обслуживаемых специальной сетевой файловой подсистемой. Пользователь получает от этой подсистемы возможность обращаться к файлам, физически расположенным в сервере или в другой станции данных, применяя привычные для локальной работы языковые средства. Q0")(4$*'$ "$+7"+)/' включает в себя функции запроса и предоставления ресурсов. O#//7*'%)='#**.$ E7*%='' обеспечивают адресацию, буферизацию, маршрутизацию сообщений. Z)A'&) #& *$+)*%='#*'"#()**#8# -#+&70) возможна на любом из следующих уровней: ограничение доступа в определенное время, и (или) для определенных станций, и (или) заданное число раз;

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

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

пометка файлов символами типа “только чтение”, “скрытность при просмотре списка файлов”. U&%)6#7+&#;

1'(#+&5 определяется наличием у серверов автономных источников питания, отображением или дублированием информации в дисковых накопителях. Отображение заключается в хранении двух копий данных на двух дисках, подключенных к одному контроллеру, а дублирование означает подключение каждого из этих двух дисков к разным контроллерам. Сетевая ОС, реализующая дублирование дисков, обеспечивает более высокий уровень отказоустойчивости. Дальнейшее повышение отказоустойчивости связано с дублированием серверов. Чем сложнее сеть, тем острее встают вопросы 70")(4$*'9 +$&5<. Основные функции управления сетью реализуются в ПО, поддерживающем протоколы управления такие, как ICMP и SNMP в стеке TCP/IP или протокол CMIP (Common Management Information Protocol) в семиуровневой модели ISO. Как рассмотрено выше, это ПО представлено менеджерами и агентами. Менеджер — прикладная программа, выдающая сетевые команды. Агенты доводят эти команды до исполнительных устройств и сигнализируют о событиях в состоянии устройств, они следят за трафиком и фиксируют аномалии, помогают восстановлению информации после сбоев, борются с вирусами и т.п. В сетевых ОС обычно выделяют ядро, реализующее большинство из перечисленных функций и ряд дополнительных программ (служб), ориентированных на реализацию протоколов верхних уровней, организацию распределенных вычислений и т.п. К сетевому ПО относятся также драйверы сетевых плат, различные для разных типов ЛВС (Ethernet, TR, AppleTalk и др.). В настоящее время выбор среди ОС происходит преимущественно между тремя основными операционными системами — UNIX, Windows NT, Novell Netware. Областью применения ОС UNIX остаются крупные корпоративные сети со стеком протоколов TCP/IP. Отличительные свойства UNIX — высокая надежность, возможность легкого масштабирования сети. &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( Windows NT предназначена для работы в сетях клиент-сервер, ориентирована преимущественно на рабочие группы и средние по своим масштабам сети. ОС асимметрична — включает в себя серверную (Windows NT Server) и клиентскую (Windows NT Workstation) части. Novell Netware пока сохраняет свои позиции в небольших сетях. Состоит из серверной части и оболочек Shell, размещаемых в клиентских узлах. *+,-./1 8:,38.5.D.0016 91A+,D.0+2. При выполнении проектных процедур с использованием более чем одного узла сети различают режимы удаленного узла и дистанционного управления (рис. 5.1). %+,. 5.). Удаленный узел и дистанционное управление В режиме 7-)4$**#8# 764) основные процедуры приложения исполняются на терминальном узле. Связь с удаленным узлом используется для пересылки файлов. В большинстве случаев режим удаленного узла приводит к более заметной инерционности связи, чем режим дистанционного управления. N'+&)*='#**#$ 70")(4$*'$ обеспечивает передачу клавишных команд в прямом направлении и экранных изображений (обычно лишь изменений в них) в сжатом виде в обратном направлении, поэтому задержки меньше. Системы распределенных вычислений основаны на режиме диcтанционного управления, при котором терминальный узел используется преимущественно для интерфейса с пользователем и передачи команд управления, а основные процедуры приложения исполняются на удаленном узле (сервере). Поэтому в сетях распределенных вычислений должны быть выделены серверы приложений. Программное обеспечение организации распределенных вычислений называют ПО 0"#/$@7*#8# +4#9 (Middleware). Современная организация распределенных вычислений в сетях Internet/Intranet основана на создании и использовании программных средств, которые могут работать в различных аппаратно-программных средах. Совокупность таких средств называют также /*#8#04)&E#"/$**#;

")+0"$-$4$**#;

+"$-#;

— МРС (Сrossware). Находят применение технологии распределенных вычислений RPC (Remote Procedure Call), ORB (Object Request Broker), DCE (Distributed Computing Environment), мониторы транзакций ТРМ (Тransaction Рrocessing Мonitors) и др. Средства RPC входят во многие системы сетевого ПО. RPC — процедурная блокирующая синхронная технология, предложенная фирмой Sun Microsystems. Вызов удаленных программ подобен вызову функций в языке С. При пересылках на основе транспортных протоколов TCP или UDP данные представляются в едином формате обмена. Синхронность и блокирование означают, что клиент, обратившись к серверу, для продолжения работы ждет ответа от сервера. Для систем распределенных вычислений разработаны специальные языки, например для RPC — язык IDL (Interface Definition Language), который позволяет пользователю оперировать различными объектами безотносительно к их расположению в сети. На этом языке можно записывать обращения к серверам приложений. Рассмотрим типичную схему реализации RPC. Удаленная программа характеризуется атрибутами: имя узла, номер программы (часто номер означает совокупность программ определенного назначения), версия программы (версия — это идентификатор копии программы, например, версия — это время создания копии, копии создаются для использования в многопользовательском режиме), имя процедуры в программе. Процедуры, которые пользователь собирается применять, необходимо зарегистрировать в узлеклиенте, т.е. указать имена узла, программы, процедуры. Обращение по RPC — это обращение к сетевой программе Postmapper, находящейся в узле-клиенте. При обращении в запросе указываются процедура, аргумент, память под результат. Аргумент должен быть единственный, поэтому если аргументов много, то программист должен создать агрегат данных. Postmapper находит регистрационные данные и с помощью средств транспортного уровня устанавливает соединение и передает запрос серверу. В сервере имеется диспетчер, который находит ис&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( полнителя запроса. В ответе сервера содержатся результаты выполнения процедуры. ОRB — технология объектно-ориентированного подхода, базирующаяся на спецификациях CORBA. Спецификации CORBA устанавливают способы использования удаленных объектов (серверных компонентов) в клиентских программах. Взаимодействие клиента с сервером происходит с помощью программы-посредника (брокера) ORB. В случае применения ORB (в отличие от RPC) хранить сведения о расположении серверных объектов в узле-клиенте не нужно, достаточно знать расположение в сети брокера ORB. Поэтому доступ пользователя к различным объектам (программам, данным, принтерам и т.п.) существенно упрощен. Брокер должен определять, в каком месте сети находится запрашиваемый ресурс и инициализировать серверную программу. После этого клиент может направлять запрос в серверный узел, а после выполнения запроса сервер будет возвращать результаты пользователю. Для описания интерфейсов распределенных объектов используют язык IDL, предложенный в CORBA. Этот язык отличается от языка IDL технологии RPC, в нем имеются средства описания интерфейсов, но нет средств описания операций. При использовании ORB может увеличиться нагрузка на сеть, однако имеется и ряд преимуществ: обеспечивается взаимодействие разных платформ, не требуется дублирования прикладных программ во многих узлах, упрощается программирование сетевых приложений и поддержка мультимедиа. В CORBA создан протокол IIOP (Internet Inter-ORB Protocol), который обеспечивает взаимодействие между брокерами разных производителей. L#*'&#". &")*6)%=';

отличаются от RPC наличием готовых процедур обработки транзакций (в том числе отката транзакций), что упрощает работу программистов. Принимая запросы от клиентов и мультиплексируя их, монитор транзакций избавляет от необходимости создавать для каждого клиента отдельное соединение с БД. Мониторы транзакций могут оптимально распределять нагрузку на серверы, выполнять автоматическое восстановление после сбоя и перезапуск системы. DCE разработана консорциумом OSF (Open Software Foundation). Она не противопоставляется другим технологиям (RPC, ORB), а является средой для их использования, например, в одной из реализаций DCE пакет Encina есть монитор транзакций, а пакет Orbix ORB представляет собой технологию ORB. В DCE возможны одно- или многоячеечная структуры сети. Выделение ячеек производится по функциональным, а не по территориальным признакам. В каждой ячейке должен быть главный сервер данных и возможно несколько дополнительных серверов с копиями содержимого главного сервера, причем доступ к дополнительным серверам разрешен только для чтения. Обновление данных осуществляется исключительно через главный сервер. Ячейка может занимать значительную территорию, главный сервер размещается вблизи от центра ячейки, дополнительные серверы — по периферии. К функциям DCE относятся распределение вычислений по технологии RPC;

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

защита данных;

синхронизация (согласование времени);

поддержка распределенной файловой системы. Работая в DCE, пользователь дополнительно к своей прикладной программе пишет IDL-файл, в котором указывает свое имя, требуемые операции и типы данных. IDL-компилятор на основе этого файла создает три модуля: клиентский стаб (Сl), серверный стаб (Sr), головной файл (Hd). Cl содержит вызовы процедур, Sr — обращения к базе процедур, Hd устанавливает связь между стабами. Определение нужного сервера в DCE либо происходит автоматически с помощью ORB, либо возлагается на программиста, как в RPC. "8+7D:501. 384-474D1 + -.D.74//<0+7:=+4001. +0H48/:=+4001. <,D<@+. Основные услуги телекоммуникационных технологий — электронная почта, передача файлов, телеконференции, справочные службы (доски объявлений), видеоконференции, доступ к информационным ресурсам (информационным базам) сетевых серверов и др. Эти услуги обеспечиваются соответствующими прикладными протоколами. Среди прикладных протоколов наиболее известны протоколы, связанные с Internet, и протоколы ISO-IP (ISO 8473), относящиеся к семиуровневой модели открытых систем. К важным прикладным протоколам Internet относятся следующие: Telnet — протокол эмуляции терминала, или, другими словами, протокол реализации дистанци&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( онного управления, он используется для подключения клиента к серверу при их размещении на разных компьютерах, пользователь через свой терминал имеет доступ к компьютеру-серверу;

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

HTTP (Hypertext Transmission Protocol) — протокол для связи Web-серверов и Web-клиентов;

SMTP, IMAP, POP3 — протоколы электронной почты;

SNMP — протокол управления сетью. Указанные протоколы поддерживаются с помощью соответствующего ПО. Как правило, прикладной протокол реализуется серверной и клиентской программами. Клиентская программа запрашивает информационную услугу, серверная программа выполняет запрос. Для Telnet, FTP, SMTP на серверной стороне выделены фиксированные номера протокольных портов. F4$%&"#**)9 0#1&) — средство обмена сообщениями по электронным коммуникациям (в режиме off-line). Посылка сообщения осуществляется по инициативе отправителя. Можно пересылать текстовые сообщения и архивированные файлы. В последних могут содержаться данные (например, тексты программ, графические данные) в различных форматах. На ЭВМ пользователя должна быть установлена программа-клиент, поддерживающая функции создания, передачи и приема сообщений. На почтовом сервере, выделяемом в корпоративной или локальной сети, организуется промежуточное хранение поступающих сообщений. Связь индивидуальных пользователей с почтовым сервером осуществляется по протоколам IMAP или POP3. В территориальных сетях почтовые сообщения проходят через ряд промежуточных федеральных или региональных узлов. В таких узлах устанавливают ПО (так называемый агент передачи сообщений), выполняющее функции сортировки и маршрутизации сообщений. Разработан ряд альтернативных протоколов электронной почты для прикладного уровня. Расширение числа возможных кодировок и форматов данных по сравнению с SMTP сделано в MIME (Multipurpose Internet Mail Extensions). Применение MIME упрощает пересылку графических и звуковых файлов, реализацию шифрования и электронной подписи. Примерами программ могут служить Lotus cc: mail, Microsoft Mail, Outlook Express и др.. Они позволяют посылать сообщения индивидуальному пользователю, на доску объявлений, последовательный просмотр несколькими исполнителями с возможностями коррекции сообщения;

осуществляют поиск сообщений, пришедших в почтовый сервер, по контексту, по адресу, по времени отправки. В настоящее время при разработке многих программных систем предусматривают интерфейс со средствами электронной почты, клиентские программы E-mail стараются включать в Web-браузеры сети Internet, а также во многие прикладные программные системы САПР, АСУ, документооборота. Письма в E-mail состоят из заголовка и тела (текста). В заголовке указывается кому предназначено письмо, от кого оно поступило, кому посланы копии, дата отправки, указатель ключа, по которому пользователь может определить ключ для декодирования текста. В протоколе IMAP (Internet Message Access Protocol) сначала клиенту передается заголовок, а текст остается на сервере, затем пользователь при желании может получить и весь текст. В протоколе POP3 при обращении к почтовому серверу на клиентский узел переписывается все сообщение. H);

4#(.;

#2/$* — доступ к файлам, распределенным по различным компьютерам. Доступ возможен в режимах off-line и on-line. В режиме off-line посылается запрос к FTP-серверу, сервер формирует и посылает ответ на запрос. В режиме on-line осуществляется интерактивный просмотр каталогов FTP-cервера, выбор и передача нужных файлов. На ЭВМ пользователя устанавливается FTP-клиент. При запросе файла по протоколу FTP пользователь должен знать, где находится нужный ему файл. Обращение к FTP-клиенту происходит по команде ftp [<параметры>] [<имя сервера>] (5.1) В качестве имени сервера указывается IP-имя или IP-адрес удаленного компьютера. В большинстве серверов Internet для входа по FTP-команде нужны предварительная регистрация пользователя и указание пароля. Однако это не требуется при обращениях к общедоступным (анонимным) серверам. Такие серверы создают и обслуживают организации, заинтересованные в распростра&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( нении информации определенного вида. После выполнения команды (5.1) FTP-клиент переходит в командный режим. Примеры субкоманд, которые могут выполняться в командном режиме (ниже удаленный компьютер обозначен S, локальный компьютер — T ): open [<имя S>] — устанавливает связь с удаленным компьютером;

close [<имя S>] — разрывает связь с удаленным компьютером, оставаясь в командном режиме;

quit — то же, что и close, но с выходом из командного режима (из ftp);

cd [<имя каталога в S>] — выбор каталога на сервере;

get [<имя файла в S>[<имя файла в T >]] — перепись файла с S на T;

mget [<имена файлов в S>] — то же, что и get, но нескольких файлов;

put [<имя файла в Т>[<имя файла в S>]] — обратная перепись;

mput <имена файлов в S> — то же, что и put, но более одного файла;

user <имя/пароль> — идентификация пользователя на сервере. Каждый обмен порождает два процесса. Управляющий (командный) процесс инициирован в течение всего сеанса связи, а процесс передачи файла — только на время передачи. Протокольные порты сервера имеют номера 20 и 21, у клиента могут быть различные номера портов, в том числе несколько в одно и то же время. На каждый процесс обмена создаются свои копии FTP-сервера и клиента. С помощью 0"#&#%#4) B/749='' &$"/'*)4) Telnet пользователь сети Internet может работать на удаленном компьютере. Связь устанавливается при обращении к Telnet-программе командой telnet <имя базы данных или системы каталогов> | <имя удаленного компьютера S> После установления связи все данные, которые пользователь набирает на клавиатуре своего компьютера, передаются в S, а содержимое экрана S отображается на экране пользователя. Примерами команд в клиентской программе могут служить: установление связи (open), возвращение в командный режим клиентской программы Тelnet (close), завершение работы (quit). Telnet должен иметь возможность работать в условиях разных аппаратных платформ клиента и сервера. Это требование выполняется с помощью промежуточного виртуального терминала (аналогично SQL сервису в ODBC). В терминале зафиксирована интерпретация различных символов управления, поскольку их разновидностей не так уж много. ?$4$%#*E$"$*='' — доступ к информации, выделенной для группового использования. Телеконференции могут быть глобальными или локальными. Включение материалов в телеконференцию, рассылка извещений о новых поступивших материалах, выполнение заказов — основные функции программного обеспечения телеконференций. Возможны режимы E-mail и on-line. Самая крупная система телеконференций — USENET. В этой системе информация организована иерархически. Сообщения рассылаются или лавинообразно, или через списки рассылки. В режиме on-line можно прочитать список сообщений, а затем и выбранное сообщение. В режиме off-line из списка выбирается сообщение и на него посылается заказ. Телеконференции могут быть с модератором (руководителем) или без него. Существуют также средства аудиоконференций (голосовых телеконференций). Вызов, соединение, разговор происходят для пользователя как в обычном телефоне, но связь идет через Internet. Электронная “доска объявлений” BBS (Bulletin Board System) — технология, близкая по функциональному назначению к телеконференции, позволяет централизованно и оперативно направлять сообщения для многих пользователей. Программное обеспечение BBS сочетает в себе средства электронной почты, телеконференций и обмена файлами. В настоящее время интенсивно развиваются технологии настольной конференц-связи в реальном масштабе времени. Возможны несколько уровней настольной конференц-связи. В зависимости от вида разделяемой пользователями информации различают уровни: простая E-mail сессия, совместная работа над проектом без голосовой связи (shared whiteboard — разделяемая “доска”), то же с голосовой связью (разновидность аудиоконференций), видеоконференция. По мере повышения уровня возрастают требования к пропускной способности используемых каналов переда&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( чи данных. Для простых видов конференц-связи, а также и для аудиоконференций (конечно, при применении современных эффективных способов сжатия информации) можно использовать даже обычные телефонные линии, начиная с пропускной способности 8-10 кбит/с. Но лучше использовать в качестве “последней мили” цифровую ISDN или xDSL линию. В зависимости от числа участников и способа интерактивной связи между ними различают двухточечную (unicast), широковещательную (broadcast) и многоточечную (multicast) телеконференции. Если в широковещательной конференции информация от центрального узла доставляется всем участникам, то в многоточечной конференции она рассылается избирательно, т.е. одновременно может идти обмен разной информацией внутри нескольких подгрупп одной группы пользователей. Очевидно, что применение настольной конференц-связи в проектных организациях повышает эффективность работы, поскольку упрощает процесс принятия и согласования проектных решений, сокращает непроизводительные затраты времени на организацию совещаний, консультаций и т.п. Программное обеспечение телеконференций включает в себя серверную и клиентскую части. В клиентской программе должны быть, как минимум, средства E-mail, многооконный текстовый редактор (так, принимаемый и отправляемый партнеру тексты помещаются в разные окна, отдельное окно может быть выделено для видеоинформации в случае видеоконференций), средства файлового обмена. Наиболее известными клиентскими программами являются ProShare (Intel) и NetMeeting (Microsoft). Серверная часть служит для распределения потока данных между пользователями с согласованием форматов окон с видеоинформацией, способов сжатия данных, скоростей потоков, идущих от разных сетей (пользователей). Примеры серверов: Whute Pine’s Meeting Point для видеоконференций, DataBeam’s Learning Server для систем дистанционного обучения. I'-$#%#*E$"$*='9 — способ связи, при котором осуществляется передача видеоизображений по телекоммуникационным каналам связи с возможностями интерактивного общения (в режиме online). Очевидно, что требования к пропускной способности каналов передачи данных в видеоконференциях существенно выше, чем в обычных телеконференциях. Видеоконференции стали доступными (для достаточно крупных организаций) после развития высокоскоростных каналов связи и эффективных алгоритмов сжатия данных при их передаче. В настоящее время широко внедряются сравнительно недорогие (от 1,5 до 7 тыс. долл.) настольные системы видеоконференц-связи. :0$=')4'6'"#()**)9 ('-$#%#*E$"$*=-+'+&$/) содержит дистанционно управляемую видеокамеру, монитор с большим экраном, микрофоны, динамики, устройство для считывания графических документов, кодеки – устройства для прямого и обратного преобразований информации из исходной в сжатую форму (кодек — совокупность первых слогов слов кодирование и декодирование). Цена комплекта — не менее 100 тыс. долл., что дешевле аналогового телевидения. Требуется выделенный канал со скоростью выше 64 кбит/с. Пример программного обеспечения — PictureTel. В случае проведения видеоконференции для двух собеседников на базе ПЭВМ или рабочих станций (двухточечные настольные видеоконференции) требуется применение мультимедийных средств. Используются компьютер с аудио-, видео- и сетевой платами, микрофон, динамик, видеокамера. Примеры ПО: Intel Proshare или Sharevision, работающие под Windows. Эти системы можно использовать с телефонными линиями и высокоскоростными модемами, но качество будет низкое. Так, при 28,8 кбит/с частота кадров 7...10 Гц, размер окна 176144 пикселей. При использовании ISDN можно повысить частоту кадров до 10...30 Гц. В большинстве систем предусмотрено наличие дополнительного окна, в котором виден совместно разрабатываемый документ. D*E#"/)='#**)9 +'+&$/) WWW (World Wide Web — всемирная паутина) — гипертекстовая информационная система сети Internet. Другое ее краткое название — Web. V'0$"&$%+& — структурированный текст с введением в него перекрестных ссылок, отражающих смысловые связи частей текста. Слова-ссылки выделяются цветом и/или подчеркиванием. Выбор ссылки вызывает на экран связанный со словом-ссылкой текст или рисунок. Можно искать нужный материал по ключевым словам. Информация, доступная в Internet по Web-технологии, хранится в Web-серверах (сайтах). Сервер имеет программу Listener, постоянно отслеживающую приход на определенный порт запросов от клиентов. Сервер удовлетворяет запросы, посылая клиенту содержимое запрошенных Web-страниц &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( или результаты выполненных процедур. Клиентские программы WWW называют 2")76$")/' (brousers). Имеются текстовые (например, Lynx) и графические (наиболее известны Netscape Navigator и MS Explorer) браузеры. Фирма Sun Microsystems разработала браузер HotJava. В браузерах имеются команды листания, перехода к предыдущему или последующему документу, печати, перехода по гипертекстовой ссылке и т.п. Из браузеров доступны различные сервисы, например, FTP, E-mail. Для подготовки материалов к их включению в базу WWW разработаны специальный язык HTML (Hypertext Markup Language) и реализующие его программные редакторы, например Internet Assistant в составе редактора Word или SiteEdit, подготовка документов предусмотрена и в составе большинства браузеров. Для связи Web-серверов и клиентов разработан протокол HTTP, работающий на базе TCP/IP. Web-сервер получает запрос от браузера, находит соответствующий запросу файл и передает его для просмотра в браузер.

Популярными серверами являются Apache Digital для ОС Unix, Netscape Enterprise Server и Microsoft Internet Information Server (IIS), которые могут работать как в Unix, так и в Windows NT, и Netware Web Server, предназначенный для работы в ОС Netware. Эти серверы поддерживают язык CGI, имеют встроенный HTML-редактор. Во многих серверах поддерживается стандарт шифрования SSL (Secure Sockets Layer) для защиты передаваемых по сети данных от несанкционированного доступа.

Опыт показывает, что для крупных серверов предпочтительнее платформа Unix, тогда как для серверов с малым числом транзакций лучше подходит ОС Windows NT. На базе HTML создан язык виртуальной реальности VRML (Virtual Reality Modeling Language) — в нем дополнительно можно использовать 3D графику. В новых ОС ожидается появление специальных средств поиска информации в серверах Internet. Пример такой технологии RDF (Resource Definition Format) — упорядочение метаинформации наподобие библиотечных каталогов (классификация по содержанию). В настоящее время для облегчения поиска применяют информационно-поисковые системы (ИПС), располагаемые на доступных пользователям Internet серверах. В этих системах собирается, индексируется и регистрируется информация о документах, имеющихся в обслуживаемой группе Web-серверов. Индексируются или все значащие слова, имеющиеся в документах, или только слова из заголовков. Пользователю предоставляется возможность обращаться к серверу с запросами на естественном языке, со сложными запросами, включающими логические связки. Примером таких ИПС может служить AltaVista. Для функционирования AltaVista выделено шесть компьютеров, самый мощный из них — 10-процессорная ЭВМ Alpha-8400, база данных имеет объем в 45 Гбайт. \6.% HTML — гипертекстовый язык для заполнения информационных Web-серверов. Он описывает структуру документа, вид которого на экране определяется браузером. Описание на HTML — это текст в формате ASCII и последовательность включенных в него команд (управляющих кодов, называемых также -$+%"'0&#")/', или &$8)/'). Эти команды расставляются в нужных местах текста, они определяют шрифты, переносы, появление графических изображений, ссылки и т.п. В редакторах WWW вставка команд осуществляется нажатием соответствующих клавиш. Так, в Internet Assistant, входящем как дополнение в редактор MS Word, текст и команды набираются в едином процессе.

Собственно команды имеют форму , где вместо XXX записывается имя команды. Структура текста в WWW имеет вид: 4 Серия учебных пособий Информатика в техническом университете !. #$%&#'$( !#$%!#&'&($!))$* +($*,#&($!)&* Москва — 2000 Даны сведения по различным аспектам и видам обеспечения систем Текст документа В клиентской области окна при просмотре появляется только текст, помещенный между командами и . Заголовок между командами 4 Серия учебных пособий Информатика в техническом университете !. #$%&#'$( !#$%!#&'&($!))$* +($*,#&($!)&* Москва — 2000 Даны сведения по различным аспектам и видам обеспечения систем выполняет только служебные функции. Приведем примеры команд HTML. Команды форматирования текста (дескрипторы %#/0#*#(%'):

— конец абзаца;


— перевод строки;

&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+(


— перевод строки с печатью горизонтальной линии, разделяющей части текста;

Текст — для представления листингов программ;

Текст
— для выделения цитат. Команды форматирования заголовков (дескрипторы +&'49):

Текст

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

Текст

— для следующего уровня и т.д. вплоть до команды
;

 Текст 
— указанный текст представлен заданным при его записи шрифтом. Команды форматирования символов представлены парными символами B, I, U;

текст между открывающей и закрывающей командами будет выделен соответственно полужирным шрифтом, курсивом, подчеркиванием. Дескрипторы +0'+%) : Команды форматирования списков

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

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

    • . В словарях и глоссариях удобно применять команды
      — начало списка,
      — перед каждым новым термином словаря и
      — перед текстом определения каждого термина. Дескрипторы +(96' : В командах вставки графики и гипертекстовых ссылок используются адреса вставляемого или ссылочного материала, называемые URL (Uniform Resourse Locator). Ссылаться можно как на определенные места в том же документе, в котором поставлена ссылка, так и на другие файлы, находящиеся в любом месте сети. Перед простановкой внутренней ссылки, т.е. ссылки на некоторую позицию в данном файле, нужно разместить метку в этой позиции. Тогда URL есть указание этой метки, например, URL= #a35 есть ссылка на метку a35. URL может представлять собой имя файла в данном узле сети или IP-имя другого узла с указанием местоположения файла в этом узле и, возможно, также метки внутри этого файла. Команда вставки графики ALIGN — параметр выравнивания, указывает место в окне для расположения рисунка;

      ALT — задает текст, который выводится на экран вместо рисунка в текстовых браузерах типа Lynx. Сами изображения должны быть в определенном формате (обычно это gif или jpeg). Экран может быть разделен на несколько окон (областей, фреймов) с помощью парного тега . В каждом окне помещается содержимое файла (текст, изображение) указанием источника в теге , например . Команда гипертекстовой ссылки Текст Текст в окне будет выделен цветом или подчеркиванием. Можно ссылаться на определенное место в документе. Тогда Текст Сама метка в документе имеет вид Текст Ссылки на фрагменты данного документа можно упростить Текст Включение рисунка выполняется с помощью дескриптора или где fgr.gif и www.abc.ru/de.htm — конкретные имена, взятые для примера.

      Расширение языка HTML — это язык XML (подмножество языка из стандарта SGML). Другое направление развития HTML — его динамическая версия DHTML. SGML (Standard Generalized Markup Language — стандартный обобщенный язык разметки) определяет форму документов в виде последовательности объектов данных. Объектные данные могут храниться в различных файлах. Их включение в финальный документ происходит в форматах, задаваемых в специальном файле DTD (Document Type Definition). Шаблоны DTD упрощают хранение и поиск документов в базах данных. XML (Extensible Markup Language) позволяет использовать в документах типы элементов, создаваемые для конкретных приложений, в нем также используются шаблоны DTD. Расширение заключается в возможности представления в одном XML-объекте информации разных типов (текст, графические данные, видео, звук). Для обмена документами на XML между Web-узлами разработан протокол ICE (Information and Content Exchange). Наиболее известен среди 96.%#( +#6-)*'9 Web-0"'4#@$*';

      язык Java — язык и технология программирования сетевых приложений, разработанный фирмой Sun Microsystems для систем распределенных вычислений. Особенности языка Java: объектно-ориентированный, прототипом является С++, но более прост в использовании (так, например, убраны указатели);

      введены многопотоковость (например, оператор &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( синхронизации), дополнительная защита от вирусов. Для пользователей важны также следующие особенности языка: — аппаратная независимость (мобильность) за счет создания приложений в виде байт-кодов для некоторой виртуальной машины (рис. 5.2) — каждая платформа интерпретирует эти байт-коды;

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

      — интеграция с браузерами;

      — используемые программные объекты могут располагаться в разных узлах, интерпретатор находит их и загружает в компьютер пользователя. Другими словами, в узле-клиенте достаточно иметь лишь браузер, остальные программы и данные можно полу%+,. 5.2. Компоненты программного обеспечения для языка Java чить по сети. Однако при этом обостряется проблема информационной безопасности. В связи с этим загружаемым из сети программам (их называют )04$&)/') обычно запрещается обновлять и читать файлы, кроме тех, которые находятся на хосте самого аплета. Java-аплеты доступны из HTML-документов (обращение к ним через тег ), хотя могут использоваться и независимо от них. CGI (Common Gateway Interface — #2A';

      >4<6#(#;

      '*&$"E$;

      +) — ПО связи HTML браузеров с другими прикладными программами и (или) текстами, находящимися на серверной стороне. Программа CGI — посредник между браузером и приложениями. Обычно программа CGI находится на сервере в специальном каталоге CGI_BIN, она является обработчиком запросов, идущих от браузера. Обращение к файлу из этого каталога означает запуск соответствующего обработчика. Если браузер обращается к документу не в HTML формате, то CGI преобразует форму документа в HTML и возвращает ее браузеру. Пример CGI-программы — WebDBC, организующей связь Web-сервера через ODBC-драйверы с нужными СУБД. Наряду с интерфейсом CGI существуют и более частные интерфейсы, например, ISAPI (Internet Server Application Program Interface) фирмы Microsoft или NSAPI фирмы Netscape. JavaScript — язык и интерпретатор этого языка для генерации и управления просмотром составных гипертекстовых документов. JavaScript более прост, чем Java, и тексты JavaScript исполняются быстрее, чем тексты Java или запросы к CGI, поскольку обработчики событий JavaScript реализованы в браузере, а не в сервере. Тексты на JavaScript записываются непосредственно в HTML документе с помощью специальных тегов и имеют вид (5.2) где — текст в виде комментария. Браузеры, не имеющие JavaScript-обработчиков, просто игнорируют комментарий, а современные браузеры исполняют записанные в (5.2) вместо многоточия команды. В отличие от Java программы на JavaScript полностью интерпретируются в браузере. Рассмотренные языки являются основой для создания программ межплатформенной распределенной среды. При этом в настоящее время создание крупных корпоративных приложений чаще опирается на применение CGI. !0H48/:=+400:> B.?43:,04,-F. Проблема информационной безопасности (ИБ) выходит за рамки сетевой ОС. Назначение систем ИБ сводится к защите от несанкционированных доступа и модификации информации, а также восстановлению информации после разрушений. Функции систем ИБ: аутентификация, разграничение доступа, защита на сетевом уровне. K7&$*&'E'%)='9 чаще всего выполняется с помощью паролей. Разработан сервер Kerberos, предназначенный для аутентификации пользователя, выходящего в сеть с любого узла. Целесообразна периодическая смена паролей, доступ к файлам пароля должен быть только у администратора и т.п. S)68")*'1$*'$ -#+&70) должно обеспечиваться на нескольких уровнях. Так, существует четырехуровневая модель. На внешнем уровне устанавливаются права доступа к корпоративной сети извне и выхода из нее. На сетевом, системном и прикладном уровнях регламентируются права доступа к се&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( тевым информационным ресурсам, ресурсам ОС и пользовательским данным соответственно. Другая модель устанавливает уровни входа в систему, доступа к БД, доступа к приложениям. Права доступа часто представляются трехразрядным восьмеричным кодом ABC, в котором A — права владельца, B — членов группы, C — остальных пользователей, а три бита выражают право чтения, записи и исполнения соответственно.

      Например, в САПР Euclid Quantum права доступа контролирует администратор системы, задавая список ACL (Access Control List). В ACL указываются имена, роли пользователей и их права доступа, которые выбираются среди следующих вариантов: просмотр, копирование, модификация, стирание данных, создание новых версий проектов, редактирование самого ACL, изменение статуса данных (варианты статуса — данные, доступные только конкретному разработчику, доступные членам рабочей группы, представленные на утверждение, уже утвержденные).

      Между общедоступными и секретными объектами в сети (между общедоступными и частными сетями) можно установить специальное ПО, называемое 2")*-/)7B"#/ (или firewall), которое либо запрещает выполнение определенных действий на сервере, либо фильтрует пакеты, разрешая проход только от оговоренных узлов. C#"52) + 0$"$,()&#/ +##2A$*';

      *) +$&$(#/ 7"#(*$ осуществляется методами криптографии. Криптография — это наука об обеспечении безопасности данных путем их шифрования. Различают симметричную и асимметричную схемы шифрования. В +'//$&"'1*., +,$/), (другое название – схемы с закрытым ключом) секретный ключ должен быть известен как отправителю, так и получателю. Ключ – это дополнение к правилу шифрования, представленное некоторым набором символов (например, двоичным кодом), управляющее преобразованием сообщения из исходного в зашифрованный вид. Например, ключ может быть операндом в действиях, выполняемых алгоритмом шифрования. Различают алгоритмы шифрования, основанные на перестановках, заменах символов исходного сообщения или на комбинациях этих действий. В частности, шифрование сообщения, выраженного двоичным кодом, может сводиться к поразрядной операции логического сложения кодов ключа и исходного текста. Чем чаще обновляются ключи, чем они длиннее, тем труднее злоумышленнику их рассекретить. Поэтому очевидна полезность периодической смены ключей. Однако в симметричных схемах их обновление требует передачи вновь вводимого секретного ключа ' участникам связи. Если эта передача осуществляется по каналу связи, то требуется шифрование ' с помощью некоторого другого секретного ключа *. В )+'//$&"'1*., +,$/), (схемах с открытым ключом) шифрование производится открытым ключом, а дешифрование — секретным ключом, известным только получателю. Возможность асимметричного шифрования вытекает из наличия так называемых односторонних функций Y = f(X), для которых обратное преобразование X = f—1(Y) относится к трудным задачам, требующим полного перебора вариантов. Однако использование в обратном преобразовании ключа, который и является секретным, делает вычисление N сравнительно простой процедурой. Случайно подобрать секретный ключ злоумышленник не может, так как полный перебор при достаточной длине ключа за приемлемое время практически не осуществим. В настоящее время все большее распространение получает комбинация симметричных и асимметричных схем. При этом сообщение кодируется закрытым ключом ' по симметричной схеме, но сам ключ ' для каждого сообщения новый и передается в закодированном по асимметричной схеме виде вместе с сообщением. Получатель декодирует сначала ключ ' своим закрытым ключом *, а затем и все сообщение ключом '. Такая комбинация выгодна, во-первых, тем, что труднее взломать защиту, во-вторых, получатель быстрее дешифрирует сообщения, так как алгоритмы симметричного дешифрования заметно более экономичны. Одним из применений шифрования является электронная подпись, предназначенная для удостоверения подлинности документа, пересылаемого по сети. Документ (чаще его аннотация) перед отправкой шифруется секретным ключом отправителя, а дешифрируется открытым ключом получателя.

      &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( 5.2. #:?0:A.0+. +,4,-:9,+,-./016,8.5 *C"% *+,-./01.,8.51 :9-4/:-+?+849:0016,+,-./. Системы автоматизированного проектирования относятся к числу наиболее сложных и наукоемких автоматизированных систем (АС). Наряду с выполнением собственно проектных процедур необходимо автоматизировать также управление проектированием, поскольку сам процесс проектирования становится все более сложным и зачастую приобретает распределенный характер. На крупных и средних предприятиях заметна тенденция к интеграции САПР с системами управления предприятием и документооборота. Для управления столь сложными интегрированными системами в их составе имеется специальное ПО — системная среда САПР или АС. Первые системные среды САПР, называвшиеся мониторными подсистемами или Framework (FW), появились на рубеже 70...80-х г.г. В настоящее время основными функциями системных сред САПР являются управление данными, управление проектированием, интеграция ПО, реализация интерфейса с пользователем САПР, помощь в разработке и сопровождении ПО САПР.

      Tермин Framework применительно к системным средам САПР был введен в 1980 г. фирмой Cadence — одним из пионеров в создании системных сред САПР. Кроме Cadence, тематикой Frameworks для САПР электронной промышленности занималось несколько ведущих в этой области фирм (Mentor Graphics, IBM, DEC, Sun Microsystems и др.), создавших международную ассоциацию CFI (CAD Framework Initiative). Широкую известность получили такие системные среды, как Falcon Framework фирмы Mentor Graphics, Design Framework-2 фирмы Cadence и JCF (Jessy-Common Framework) европейской программы ESPRIT.

      Важно отметить, что проблема системных сред САПР, зародившаяся в процессе становления САПР электронной промышленности, получила развитие при реализации CALS-технологии в различных отраслях машиностроения. В типичной структуре ПО системных сред современных САПР можно выделить следующие подсистемы. \-"# отвечает за взаимодействие компонентов системной среды, доступ к ресурсам ОС и сети, возможность работы в гетерогенной среде, настройку на конкретную САПР (конфигурирование) с помощью специальных языков расширения. !#-+'+&$/) 70")(4$*'9 0"#$%&#/, называемая также подсистемой сквозного параллельного проектирования CAPE (Concurrent Art-to-Product Environment), выполняет функции слежения за состоянием проекта, координации и синхронизации параллельно выполняемых процедур разными исполнителями. Примерами подсистем управления проектами в машиностроении могут служить Design Manager в САПР Euclid, UG/Manager в Unigraphics. Иногда в отдельную подсистему выделяют управление методологией проектирования. При этом под /$&#-#4#8'$;

      понимают совокупность методов и средств образования /)">"7&#( проектирования — последовательностей проектных операций и процедур, ведущих к цели проектирования. Методы построения маршрутов проектирования (workflow) зависят от типа проектных задач. Различают простые задачи, выполняемые одной программой, линейные, в которых нет разветвлений в межпрограммных связях, и комплексные. Методы построения маршрутов могут быть основаны на предварительном описании задач или на предварительном описании правил конструирования задач. В описании задач фигурируют порты, с которыми соотнесены данные. Порты могут быть обязательными и необязательными, порождающими дополнительные данные или данные нового объекта. Описания задач даются в виде графов или на языках расширения. !#-+'+&$/) 70")(4$*'9 /$&#-#4#8'$;

      0"#$%&'"#()*'9 представлена в виде базы знаний. В этой базе содержатся такие сведения о предметной области, как информационная модель (например, в виде диаграмм сущность-отношение), иерархическая структура проектируемых объектов (например, в виде И-ИЛИ-дерева), описания типовых проектных процедур, типовые фрагменты маршрутов проектирования — так называемые потоки процедур, соответствие между процедурами и имеющимися пакетами прикладных программ, ограничения на их применение и т.п. Часто такую БЗ дополняют обучающей подсистемой, используемой для подготовки специалистов к использованию САПР. Современные +'+&$/. 70")(4$*'9 0"#$%&*./' -)**./' называют PDM ( Product Data Manager), иногда применительно к АСУ используют название EDM (Enterprise Data Manager). PDM предназначены для информационного обеспечения проектирования и выполняют следующие функции: &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( — хранение проектных данных и доступ к ним, в том числе ведение распределенных архивов документов, их поиск, редактирование, маршрутизация и визуализация;

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

      — создание спецификаций;

      — защита информации;

      — интеграция данных (поддержка типовых форматов, конвертирование данных). Основной компонент PDM — 2)*% -)**., (БнД). Он состоит из системы управления базами данных и баз данных (БД). Межпрограммный интерфейс в значительной мере реализуется через информационный обмен с помощью банка данных. PDM отличает легкость доступа к иерархически организованным данным, обслуживание запросов, выдача ответов не только в текстовой, но и в графической форме, привязанной к конструкции изделия. Поскольку взаимодействие внутри группы проектировщиков в основном осуществляется через обмен данными, то в системе PDM часто совмещают функции управления данными и управления параллельным проектированием. !#-+'+&$/) '*&$8")='' !U предназначена для организации взаимодействия программ в маршрутах проектирования. Она состоит из ядра, отвечающего за интерфейс на уровне подсистем, и оболочек процедур, согласующих конкретные программные модули, программы и/или программно-методические комплексы (ПМК) со средой проектирования. Интеграция ПО базируется на идеях объектно-ориентированного программирования. Следует различать синтаксический и семантический аспекты интеграции. Синтаксическая интеграция реализуется с помощью унифицированных языков и форматов данных, технологий типа ODBC для доступа к общему банку данных или компонентно-ориентированных (CBD — Component-Based Development) технологий. Пример унифицированного формата — TES (Tool Encapsultion Specification), предложенного консорциумом CFI. Информация из TES используется для создания оболочек модулей при инкапсуляции. Семантическая интеграция подразумевает автоматическое распознавание разными системами смысла передаваемых между ними данных и достигается значительно труднее. !#-+'+&$/) 0#456#()&$45+%#8# '*&$"E$;

      +) включает в себя текстовый и графический редакторы и поддерживается системами многооконного интерфейса типа Х Window System или Open Look. !#-+'+&$/) CASE предназначена для адаптации САПР к нуждам конкретных пользователей, разработки и сопровождения прикладного ПО. Ее можно рассматривать как специализированную САПР, в которой объектом проектирования являются новые версии подсистем САПР, в частности, версии, адаптированные к требованиям конкретного заказчика. Другими словами, такие CASE-подсистемы позволяют пользователям формировать сравнительно с малыми затратами усилий варианты прикладных ПМК из имеющегося базового набора модулей под заданный узкий диапазон конкретных условий проектирования. В таких случаях СASE-подсистемы называют '*+&"7/$*&)45*./' +"$-)/'. CASE-система, как система проектирования ПО, содержит компоненты для разработки структурных схем алгоритмов и “экранов” для взаимодействия с пользователем в интерактивных процедурах, средства для инфологического проектирования БД, отладки программ, документирования, сохранения “истории” проектирования и т.п. Наряду с этим, в CASE-подсистему САПР входят и компоненты с специфическими для САПР функциями.

      Так, в состав САПР Microstation (фирма Bentley Systems) включена инструментальная среда Microstation Basic и язык MDL (Microstation Development Language) c соответствующей программной поддержкой. Язык MDL — С-подобный, с его помощью можно лаконично выразить обращения к проектным операциям и процедурам. В целом среда Microstation Basic близка по своим функциям к среде MS Visual Basic, в ней имеются генератор форм, редактор, конструктор диалога, отладчик. САПР Спрут (российская фирма Sprut Technologies) вообще создана как инструментальная среда для разработки пользователем потоков задач конструкторского и технологического проектирования в машиностроении с последующим возможным оформлением потоков в виде пользовательских версий САПР. Сконструированный поток поддерживается компонентами системы, в число которых входят графические 2D и 3D подсистемы, СУБД, продукционная экспертная система, документатор, технологический процессор создания программ для станков с ЧПУ, постпроцессоры.

      Наиболее известной CASE-системой в составе САПР в настоящее время является описываемая ниже система CAS.CADE фирмы MatraDatavision, с ее помощью фирма разработала очередную версию Euclid Quantum своей САПР Euclid. &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( "456451 7 +0-.@8:=++ "$ 9 *C"%. Для создания ПО САПР так же, как и других сложных автоматизированных информационных систем, определяющее значение имеют вопросы интеграции ПО. Теоретической базой для создания технологий интеграции ПО в САПР являются: 1) методология автоматизированного проектирования, в соответствии с которой осуществляются типизация проектных процедур и маршрутов проектирования в различных предметных областях, выявление типичных входных и выходных данных процедур, построение информационных моделей приложений и их обобщение, сравнительный анализ альтернативных методов и алгоритмов выполнения типовых процедур;

      2) объектно-ориентированная методология, в соответствии с которой множества сущностей, фигурирующих в процессах проектирования, подразделяются на классы, в классах появляются свои процедуры и типы данных с отношениями наследования. Эти классы могут быть инвариантными и прикладными. Их обобщение и унификация приводят к появлению таких понятий и средств, как интегрированные ресурсы и прикладные протоколы, фигурирующие в стандартах STEP, или унифицированные программные компоненты типа графических ядер конструкторских САПР. Именно наличие типовых процедур и единообразное толкование атрибутов объектов в рамках конкретных протоколов позволяют разным программным системам “понимать” друг друга при взаимодействии. Наряду с типовыми графическими ядрами, известны типовые ПМК имитационного моделирования, конструирования деталей и механизмов, технологической подготовки производства и др. Возможность использования типовых программ в составе программных комплексов обусловлена именно унификацией интерфейсов при обменах данными. В некоторых маршрутах проектирования обмены данными должны происходить с высокой частотой, что обусловливает специфические требования к интерфейсам. Примером могут служить задачи имитационного моделирования, в которых требуется имитировать взаимодействие процессов, описываемых с помощью различного МО (например, на сосредоточенном и распределенном иерархических уровнях, или с помощью аналоговых и дискретных моделей). Для таких задач при моделировании характерно воспроизведение временной последовательности событий, происходящих в анализируемых взаимодействующих системах. Соответственно взаимодействие программ моделирования может происходить через фиксированное число временных шагов или по мере совершения тех или иных событий в моделируемых системах.

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

      Другими словами, в каждом приложении совокупность используемых при обменах понятий, предметных переменных и числовых параметров существенно ограничена и достаточно определена для того, чтобы можно было ставить вопрос о типизации моделей и языка взаимодействия. Такие вопросы решаются в рамках технологий STEP/CALS. Число приложений, нашедших свое описание в прикладных протоколах STEP ограничено, но совокупность таких протоколов может расширяться. Прикладные протоколы STEP представляют семантическую сторону интеграционных технологий. Для интеграции нужна не только унификация моделей приложений, но и унификация механизмов взаимодействия, примерами которых являются технологии OLE, DDE, а также компонентно-ориентированные технологии. &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( M.604D4@++ +0-.@8:=++ "$ -+3: DDE + OLE. Современные ОС позволяют работать одновременно с несколькими задачами с выделением каждой задаче своего окна на экране дисплея. Межпрограммные взаимодействия осуществляются путем посылки сообщений, как это принято в объектно-ориентированном программировании. Используются специальные средства организации взаимодействий. Так, ОС Unix поддерживает взаимодействие асинхронных параллельных процессов, в том числе в разных узлах сети. Каждый клиент должен предварительно зафиксировать свои потребности в виде имен используемых сообщений. Сообщения имеют структуру фрейма. Получатель сообщения определяет, что сообщение относится к нему, вызывает обработчик сообщения и использует полученные данные в соответствии с своими функциями. В операционных системах Microsoft для организации межпрограммных взаимодействий были предложены средства Clipboard, DDE, OLE и в дальнейшем технология ActiveX. Работа Clipboard основана на традиционном способе обменных зон — выделении кармана (некоторой области оперативной памяти, разделяемой взаимодействующими программами). При обменах одна программа посылает сообщение в карман, а другая извлекает, интерпретирует и использует это сообщение. Аналогичный режим работы осуществляется с помощью технологии формирования составных документов OLE, но здесь расширены возможности комбинирования данных различных типов в передаваемых документах. Различают два способа взаимодействия: связь (linking) и внедрение (embedding). При связи в создаваемый документ включается не сам текст из источника, а лишь ссылка на него. Очевидно, что здесь меньше затраты памяти, изменения в источнике автоматически переходят в документ. При внедрении текст из источника физически переносится в документ. После чего документ можно редактировать независимо от источника. Оба этих способа реализованы в технологии OLE, что и зафиксировано в ее названии (OLE — Object Linking and Embedding). При обмене с помощью DDE (Dynamic Data Exchange) программа-клиент запрашивает режим диалога с программой-сервером. В сообщении указывается имя сервера, имя раздела (обычно раздел — это файл), имя элемента (обмениваемая порция информации). Предварительно такой элемент (атом) должен быть создан, его адрес зафиксирован в таблице атомов. В ответ на запрос создается канал, по которому сервер передает данные или, что реализуется чаще, пересылает адрес нужного атома. По этому адресу клиент дополнительной командой может получить данные. Подход к реализации интероперабельности, имеющийся в DDE и OLE, получил развитие в современных компонентно-ориентированных технологиях разработки ПО, рассматриваемых ниже. P38:9D.0+. 5:001/+ 9 *C"%. В большинстве автоматизированных информационных систем применяют СУБД, поддерживающие реляционные модели данных. Среди общих требований к СУБД можно отметить: 1) обеспечение целостности данных (их полноты и достоверности);

      2) защита данных от несанкционированного доступа и от искажений из-за сбоев аппаратуры;

      3) удобство пользовательского интерфейса;

      4) в большинстве случаев важна возможность распределенной обработки в сетях ЭВМ. Первые два требования обеспечиваются ограничением прав доступа, запрещением одновременного использования одних и тех же обрабатываемых данных (при возможности их модификации), введением контрольных точек (checkpoints) для защиты от сбоев и т.п. C)*% -)**., в САПР является важной обслуживающей подсистемой, он выполняет функции информационного обеспечения и имеет ряд особенностей. В нем хранятся как редко изменяемые данные (архивы, справочные данные, типовые проектные решения), так и сведения о текущем состоянии различных версий выполняемых проектов. Как правило, БнД работает в многопользовательском режиме, с его помощью осуществляется информационный интерфейс (взаимодействие) различных подсистем САПР. Построение БнД САПР — сложная задача, что обусловлено следующими особенностями САПР: 1. Разнообразие проектных данных, фигурирующих в процессах обмена как по своей семантике (многоаспектность), так и по формам представления. В частности, значительна доля графических данных. 2. Нередко обмены должны производиться с высокой частотой, что предъявляет жесткие требо&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( вания к быстродействию средств обмена (полагают, что СУБД должна работать со скоростью обработки тысяч сущностей в секунду). 3. В САПР проблема целостности данных оказывается более трудной для решения, чем в большинстве других систем, поскольку проектирование является процессом взаимодействия многих проектировщиков, которые не только считывают данные, но и изменяют их, причем в значительной мере работают параллельно. Из этого факта вытекают следствия: во-первых, итерационный характер проектирования обычно приводит к наличию по каждой части проекта нескольких версий, любая из них может быть принята в дальнейшем в качестве основной, поэтому нужно хранить все версии с возможностью возврата к любой из них;

      во-вторых, нельзя допускать использования неутвержденных данных, поэтому проектировщики должны иметь свое рабочее пространство в памяти и работать в нем автономно, а моменты внесения изменений в общую БД должны быть согласованными и не порождать для других пользователей неопределенности данных. 4. Транзакции могут быть длительными и трудоемкими. ?")*6)%='$;

      называют последовательность операций по удовлетворению запроса. В САПР внесение изменений в некоторую часть проекта может вызвать довольно длинную и разветвленную сеть изменений в других его частях из-за существенной взаимозависимости компонентов проекта (многошаговость реализации запросов). В частности, транзакции могут включать в себя такие трудоемкие операции, как верификация проектного решения с помощью математического моделирования. В результате транзакции могут длиться даже несколько часов и более. Одна из трудностей заключается в отображении взаимозависимости (ассоциативности) данных. При хранении компонентов проекта во внешней памяти затраты времени на обработку запросов оказываются значительно выше, чем в большинстве других автоматизированных систем, с менее выраженными взаимозависимостями данных. 5. Иерархическая структура проектных данных и, следовательно, отражение наследования в целях сокращения объема базы данных. В определенной мере названные особенности учитываются в СУБД третьего поколения, в которых стали применяться черты объектно-ориентированных (объектных) СУБД. В них наборы данных, характеризующих состояние предметной области (состояние проекта в случае САПР), помещаются в отдельные файлы. Интерпретация семантики данных осуществляется с помощью специальных процедур (методов), сопровождающих наборы. Наследование свойств объектов предметной области выражается с помощью введения категорий класса, надкласса, подкласса. Информационные модели приложений для таких СУБД разрабатываются на основе методик типа IDEF1X. Объектные БД выгодны, во-первых, тем, что данные по конкретным объектам проектирования не разбросаны по множеству таблиц, как это имеет место в реляционных БД, а сосредоточены в определенных местах. Во-вторых, для каждого объекта могут быть назначены свои типы данных. В результате проще решаются задачи управления и удовлетворения запросов. Наряду с чисто объектными СУБД (pure ODBMS), применяют СУБД объектно-реляционные. В последних происходит объединение свойств реляционных и объектно-ориентированных СУБД: объектно-ориентированная СУБД снабжается непроцедурным языком запросов или в реляционную СУБД вводятся наследование свойств и классы. Непроцедурность входного языка обеспечивается использованием языка SQL. Его операторы непосредственно включаются в программы на языке С. Возможно написание дополнительных программ, интерпретирующих SQL-запросы. Отличительные особенности СУБД третьего поколения: расширенный набор возможных типов данных (это абстрактные типы, массивы, множества, записи, композиции разных типов, отображение величин с значениями разных типов), открытость (доступность из разных языков программирования, возможность обращения к прикладным системам из СУБД), непроцедурность языка (общепринятым становится язык запросов SQL), управление асинхронными параллельными процессами, состояние которых отражает БД. Последнее свойство позволяет говорить о тесной взаимосвязи СУБД и подсистемы управления проектами DesPM. Названные особенности управления данными в САПР нашли свое выражение в современных подсистемах управления проектными данными PDM. В PDM разнообразие типов проектных данных поддерживается их классификацией и соответст&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( вующим выделением групп с характерными множествами атрибутов. Такими группами данных являются описания изделий с различных точек зрения (аспекты). Для большинства САПР машиностроения характерными аспектами являются свойства компонентов и сборок (эти сведения называют Bill of materials — BOM), модели и их документальное выражение (основными примерами могут служить чертежи, 3D модели визуализации, сеточные представления для конечно-элементого анализа, текстовые описания), структура изделий, отражающая взаимосвязи между компонентами и сборками и их описаниями в разных группах. Вследствие большого объема проектных данных и наличия ряда версий проектов PDM должна обладать развитой системой поиска нужных данных по различным критериям. Рассмотренные особенности банков данных в САПР позволяют квалифицировать их как системы Data Warehouse (DW), т.е. хранилища данных. Для хранилищ данных характерен ряд особенностей, совпадающих с названными выше особенностями банков данных САПР: 1) длительное хранение информации, отражающей историю разработок;

      2) частота операций чтения данных выше частоты операций обновления данных;

      3) использование единых форматов для однотипных данных, полученных из различных источников (например, от разных программно-методических комплексов). Эти особенности позволяют управлять конфигурацией проектов, что, в частности, означает хранение в САПР всех версий проекта и, возможно, данных по проектам предыдущих разработок, удовлетворение сложных запросов, для ответа на которые требуется извлечение и обработка данных из различных частей хранилища (так называемая многомерная обработка). Модели данных в DW отличаются от реляционных моделей (RM): в RM использованием нормальных форм стремятся максимально уменьшить избыточность данных, что приводит к увеличению числа таблиц, но уменьшенных размеров, однако многомерный поиск, требующийся в DW, в множестве таблиц затруднен. Поэтому в DW чаще используется модель данных “звезда”, в которой имеется общая таблица фактов (Fact Table) и каждому факту ставится в соответствие несколько таблиц с необходимыми атрибутами. Целостность данных в DW обеспечивается проверкой и трансформацией данных (data cleaning), вводимых из внешних источников, наличием дисциплины обновления данных, централизованным хранением основной базы, при этом достаточное быстродействие поддерживается передачей копий определенных частей базы в локальные базы, называемые киосками данных (Data Mart) и ориентированные на отдельные группы пользователей.

      Примером СУБД, учитывающей требования, предъявляемые со стороны САПР, является система IMAN фирмы EDS Unigraphics. Это система управления объектно-ориентированными базами данных, ее можно также назвать системой интеграции данных. Она выполняет функции подсистемы PDM, которые являются функциями хранения данных, управления доступом к ним, контроля вносимых изменений, создания спецификаций изделий, интегрирования прикладных подсистем. Внутри IMAN используется реляционная модель данных, а на интерфейсном уровне — объектно-ориентированная информационная модель. Для синхронизации изменений предусматривается блокировка доступа пользователей, если с БД уже начал работу некоторый пользователь. Другими известными примерами подсистем управления проектными данными могут служить системы Optegra (фирма Computervision), Euclid Design Manager (Matra Datavision), ProPDM в составе САПР Pro/Engineer (PTC), TechnoDOCS (Российская фирма “Весть”).

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

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

      (:8+:0-1 <38:9D.0+> 5:001/+ 9,.->6 C*. При сетевой организации АС информационное обеспечение может быть реализовано по одному из следующих вариантов: 1) FS — файловый сервер;

      2) RDA — доступ к удаленным данным;

      3) DBS — сервер баз данных;

      4) AS — сервер приложений. Варианты различаются распределением между разными узлами сети функций хранения данных, управления данными, обработки данных в приложениях и интерфейса с пользователем. На рис. 5.3 место среды передачи данных %+, 5.3. Варианты двухзвенных схем распределенных вычислений &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( показано вертикальной чертой для первых трех вариантов. Каждый вариант имеет свою область применения. Вариант файл-сервера характерен для локальных сетей на персональных ЭВМ с небольшим числом пользователей. Вследствие интенсивного трафика и трудностей с защитой информации эта структура для большинства АС малоэффективна. Поэтому предпочтительнее иметь СУБД в узле сервера. Вариант RDA — это модель удаленного узла, она наиболее распространена в настоящее время среди АС. В ней уменьшен трафик по сравнению с FS, унифицирован интерфейс с СУБД на основе языка SQL.

      + - 0 B.F 6 9 0.. Клиентов в FS и RDA иногда именуют “толстыми” клиентами, так как в них сосредоточены средства выполнения приложений.

      Дальнейший переход к системе распределенных вычислений приводит к перемещению прикладного ПО или его части на специальный сервер или сервер БД, т.е. реализуются двух- и трехзвенные схемы. DBS — двухзвенная структура дистанционного управления, основанная на разделении прикладных процедур на две части: индивидуальные для каждого пользователя и общие для многих задач. В этой структуре под приложением понимают совокупность именно общих процедур. Эта совокупность обычно представляется на процедурных расширениях SQL и сохраняется в специальном словаре БД. В альтернативных вариантах (например, в RDA) все прикладные процедуры включаются в прикладные программы и, следовательно, при необходимости их изменения приходится модифицировать практически все прикладное ПО. Выделение таких процедур в отдельное приложение облегчает их модификацию. Кроме того, в DBS снижается трафик, так как обмены по сети происходят не для каждой операции с БД, а для каждой транзакции, состоящей из нескольких операций. Вариант AS реализуется по &"$,6($**#;

      +,$/$, в которой для приложений используются узлы, отделенные от терминального (локального) узла и от сервера БД, т.е. одновременно используются модели DBS и RDA. Помимо проблемы распределения серверных функций между узлами сети, имеется проблема разделения этих функций между многими пользователями АС. Эта проблема решается либо по +,$/$ “#-'*-%-#-*#/7”, либо по /*#8#0#&#%#(#;

      +,$/$. В первой из них для каждого активного пользователя создается своя копия СУБД. Во второй СУБД должна быть реентерабельной программой, обслуживающей одновременно многих пользователей. !0-.DD.7-<:DF01.,.89.81 XO. Особенности СУБД в таких сложных системах, как САПР, определяют их квалификацию, как '*&$44$%&7)45*., (их еще называют СУБД третьего поколения). К числу признаков интеллектуальной СУБД (дополнительно к охарактеризованным выше) относятся реализация в СУБД части прикладных процедур, что характерно для структуры DBS, #0#($A$*'$ пользователей (прикладных программ) об интересующих их изменениях состояния БД, +'*,"#*'6)='9 +#2.&';

      в БД, способность обслуживать прикладные программы, первоначально ориентированные на разные типы СУБД (назовем это свойство /*#8#0"#&#%#45*#+&5<). Оповещение заключается в информировании программы K о совершении события, вызванного программой I и влияющего на работу программы K (рис. 5.4). Примером события может быть выход значения некоторого параметра в БД за допустимые пределы. Наиболее просто информирование можно организовать периодическим опросом состояния БД со стороны K. Однако это усложняет ПО и не эффективно по затратам времени и загрузке сети. Лучше возложить функцию оповещения на СУБД, что и присуще интеллектуальным СУБД. Но для этого нужно иметь обратные ссылки на программы, обращающиеся к БД, 0")('4) (иначе называемые &"'88$")/и), фиксирующие наступления событий, и процедуры обработки событий (см. рис. 5.4). Удобный вариант оповещения — информирование программы K о происшедших событиях во время ее активизации. Для реализации многопротокольности разрабатывают специальные технологии. Наиболее известной среди них является технология ODBC (Open Data Base Connection) фирмы Microsoft. Фактически ODBC представляет собой библиотеку функций для обращений %+, 5.4. Схема оповещения &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( прикладных программ (ПП) к различным СУБД на основе языка SQL. Из ПП обращение происходит к виртуальной СУБД, в которой с помощью драйверов осуществляется переход к реальной СУБД. %:,38.5.D.001. B:?1 5:0016 (%XO). В крупных АС, построенных на основе корпоративных сетей, не всегда удается организовать централизованное размещение всех баз данных и СУБД на одном узле сети. Поэтому появляются ")+0"$-$4$**.$ 2)6. -)**.,. При построении РБД приходится решать ряд сложных проблем, связанных с минимизацией трафика, обеспечением интероперабельности обработки данных и целостности данных. L'*'/'6)='9 &")E'%) нужна в связи с тем, что при обслуживании запроса могут потребоваться данные из многих узлов, пересылаемые по сети. Возможности минимизации видны из примера обработки данных нескольких таблиц из разных узлов. Очевидно, что целесообразна однократная пересылка таблиц (причем таблиц именно меньшего размера) на один узел, на котором и будет обрабатываться запрос. D*&$"#0$")2$45*#+&5 выражает способность взаимодействия программ, работающих в гетерогенных сетях (в разных операционных средах или с разными СУБД). Интероперабельность обеспечивается или с помощью программ-шлюзов (конверторов) для каждой пары взаимодействующих сред, или с помощью единого унифицированного языка взаимодействия. Таким языком для доступа к БД является язык SQL, интероперабельность на его основе имеет место в системе ODBC (Open Data Base Connectivity), пример реализации которой показан на рис. 5.5. В примере СУБД FoxPro находится в локальном узле, а СУБД Ingres и Informix – в удаленных узлах. Прикладная программа имеет ОDBC-интерфейс, не зависимый от особенностей различных СУБД. Менеджер драйверов реализует на базе унифицированного языка SQL все нюансы доступа к БД, общие для разных %+,. 5.5. Структура ODBC СУБД. Драйвер конкретной СУБД преобразует инвариантные к СУБД запросы в форму, принятую в данной СУБД. В трехзвенной структуре менеджер драйверов может быть размещен ан промежуточном сервере. Обеспечение целостности в РБД намного сложнее, чем в одноузловых БД. Различают два подхода к построению РБД: 1) тиражирование (репликация), при котором на нескольких серверах (узлах) сети расположены копии БД;

      2) полномасштабная распределенность, при которой разные части БД находятся на разных серверах сети (классическая распределенность). Применяют два способа тиражирования. Способ, называемый репликацией первой копии, основан на выделении среди серверов с копиями БД одного первичного сервера (репликатора). Внесение изменений пользователями возможно только в БД первичного сервера, который в дальнейшем осуществляет тиражирование. ?'")@'"#()*'$ — это перенос изменений БД из первичного сервера во все вторичные (локальные) серверы, которые используются клиентами только для чтения данных. Репликатор реагирует на события, фиксируемые триггерами, периодически пересылает обновленные данные в копии БД. Недостаток способа — невысокая надежность, присущая любым централизованным структурам. Надежность повышается при использовании способа голосования. Здесь изменения посылаются не в один первичный, а в некоторые N серверов. При этом любой запрос на чтение направляется к некоторым M серверам, причем N+M > K, где K — общее число серверов. Принимается последняя по времени обновления версия ответа. Тиражирование вносит избыточность в хранимые данные, появляются трудности с разрешением конфликтов из-за возможных несогласованных изменений в локальных БД. Однако по сравнению с классическими РБД, в которых данные не дублируются, заметно уменьшается трафик, надежнее и проще работа с локальными БД. Обеспечение надежности и удобства работы особенно актуально в случае ненадежных и медленных каналов связи, что имеет место во многих сетях в России. В классических распределенных СУБД (РСУБД) необходимо 70")(49&5 #-*#("$/$**./ -#+&7&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( 0#/, что должно гарантировать целостность (сериализуемость) БД. Наиболее широко используются алгоритмы управления, основанные на механизме блокировки. При этом 24#%'"#(%#;

      называют ситуацию, при которой некоторая транзакция объявила о желании получить полномочия на доступ к странице памяти и, следовательно, другие транзакции не имеют права занимать этот ресурс. Одним из способов управления является централизованное блокирование, при котором на одном из узлов поддерживается единая таблица блокировок. Такой узел устанавливает очередность выполнения транзакций, что исключает конфликты. Однако при централизованном управлении невысока надежность и требуется мощный сервер. В РСУБД с репликацией нет проблемы согласования при записи действий многих узлов. Собственно тиражирование чаще всего выполняется по правилу полной эквивалентности — обновленные данные сразу же после изменившей их транзакции рассылаются по всем локальным БД. Чтение же выполняется из БД одного конкретного узла, наиболее близкого к пользователю в функциональном или географическом смысле. Сложнее решать проблемы распределенного управления, что требуется в РСУБД без тиражирования. Одним из распространенных протоколов распределенного управления является протокол двухфазной фиксации транзакций (2РС). На первой фазе инициатор транзакции (координатор) рассылает участникам выполнения транзакции оповещения о блокировке. В ответ узлы сообщают о своей готовности или неготовности. На второй фазе координатор сообщает либо о “глобальной фиксации”, т.е. о выполнении транзакции, либо об откате транзакции. Неприятности возможны при сбоях, которые могут оставить некоторый узел в заблокированном состоянии: он не может ни выполнять транзакцию, ни отменять ее в одностороннем порядке. "84@8://01.,8.5,-9: <38:9D.0+> 384.7-+849:0+./ 9 *C"%. В зависимости от степени автоматизации управляющих функций можно выделить несколько уровней управления проектированием: 1) компонентный;

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

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

      другими словами, системная среда лишь предоставляет сведения о имеющихся программах и их интерфейсах;

      2) ресурсный;

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

      3) задачный;

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

      покрытие маршрута программами выполняет системная среда;

      4) проблемный;

      пользователь формулирует задания в форме “что нужно сделать”, а не “как это сделать”, т.е. не определяет маршрут проектирования, а ставит проектную проблему. В системных средах САПР 70")(4$*'$ 0"#$%&'"#()*'$/ возлагается на подсистему CAPE, в некоторых системах обозначаемую как DesPM (Design Process Manager). DesPM должна включать в себя компоненты: комплексы базовых знаний по тем предметным областям, которые определяются объектом проектирования, а также знаний о языках представления характеристик и ограничений;

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

      средства выполнения плана;

      средства оценки результатов. DesPM позволяет выбирать объекты проектирования, производить декомпозицию моделей, для каждого компонента выбирать проектные процедуры из имеющегося набора. По каждому объекту DesPM выдает сообщения, примерами которых могут быть: “объект проектируется другим разработчиком”, “проектирование преждевременно, не выполнены предшествующие процедуры”, “не подготовлены исходные данные”. Одной из важнейших функций DesPM является помощь в реализации параллельного проектирования. Желательно в DesPM предусмотреть возможности создания “суперпроцедур” — командных файлов для выполнения часто повторяющихся фрагментов маршрутов проектирования. Расширение возможностей управления проектированием и адаптация системной среды к конкретным САПР связано с применением языков расширения. \6.% ")+>'"$*'9 — это язык программирования, позволяющий адаптировать и настраивать системную среду САПР на выполнение новых &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( проектов. Язык расширения должен обеспечивать доступ к различным компонентам системной среды, объединять возможности базового языка программирования и командного языка, включать средства процедурного программирования. Для большинства языков расширения базовыми являются ЛИСП или С.

      Так, язык Skill из Design Framework-2 фирмы Cadence или язык ССL (CASE Comment Language) фирмы Matra Datavision являются ЛИСП-подобными, а язык AMPLE из Falcon Framework фирмы Mentor Graphics базируется на языках : и ПАСКАЛЬ.

      Управление процессом проектирования включает в себя большое число действий и условий, поддерживающих параллельную работу многих пользователей над общим проектом. Управление выполняется на основе моделей вычислительных процессов. Используются спецификации моделей, принятые в CASE-системах, например, диаграммы потоков данных, ориентированные графы. Сначала модели составляют для задачного уровня, а затем система осуществляет их покрытие. Применяют также описания на языках расширения или 4GL. В системной среде Ulyses спецификации даны в виде набора модулей с указанием условий их активизации, что близко к представлению моделей в системах, управляемых знаниями. Так, каждый проектирующий программный модуль может быть активизирован только в том случае, если входные данные готовы. Для этого специальная 0"#8")//) 70")(4$*'9 /#-749/' системной среды отслеживает соблюдение отношений следования между проектными операциями и процедурами, заданными в маршруте проектирования. На эту же программу возлагаются функции регулирования прав доступа к модулям, сбор статистики (протоколирование) по обращениям к модулям и некоторые другие. Необходимо обеспечение синхронизации изменения данных, разделяемых многими пользователями. Для этого, во-первых, пользователи подразделяются на классы (администрация системы, руководство проектом и частями проекта, группы исполнителей-проектировщиков) и для каждого класса вводят определенные ограничения, связанные с доступом к разделяемым данным;

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

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

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

      В общем случае полная формализация управления проектированием не может быть достигнута, поэтому полезную роль играют +'+&$/. 0#--$"@%' "$>$*';

      , принимаемых людьми, DSS (Decision Support Systems). В качестве таких систем часто используют хранилища данных и OLAP-средства (On-Line Analytical Processing). Использование хранилищ данных имеет ряд преимуществ в управлении большими объемами данных: имеется единое ядро, что исключает чрезмерно разветвленные и длительные транзакции, легче синхронизировать внесение изменений, поддерживать единство форматов данных, хранить предыдущие версии и т.п. OLAP-средства должны обеспечивать оперативный доступ к данным, на основе которого выявляются зависимости между параметрами (измерениями в многомерной модели приложения). В OLAP-системах на реляционных СУБД аналитическая обработка, или, другими словами, многомерный динамический анализ данных требует просмотра большого числа записей из разных таблиц. Поэтому производительность оказывается невысокой. В специализированных OLAP-системах, обеспечивающих более быстрый многомерный анализ, но с более существенными ограничениями на объем БД, данные хранятся в виде гиперкубов или поликубов — многомерных таблиц с постоянным или пе&.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( ременным числом ячеек соответственно. Пример OLAP системы — Oracle Express, помогающей менеджерам и аналитикам получать данные в виде разрезов таких многомерных таблиц, готовить отчеты, обосновывать решения. В составе подсистем управления методологией проектирования полезно иметь средства консультирования по принятию проектных решений. Они могут быть представлены в виде множества модулей, объединяемых гипертекстовой оболочкой. Каждый модуль содержит некоторый совет по выбору решения, преодолению противоречий, возникающих в процессе проектирования. Здесь уместно использование методов и приемов решения изобретательских задач.

      Примером программы консультирования и прогнозирования результатов принимаемых решений может служить программа Clio в упомянутой выше подсистеме Minerva.

      "8+/.81 345,+,-./ <38:9D.0+> 5:001/+ + 384.7-+849:0+./. В ряде системных сред САПР (прежде всего САПР в машиностроении) в подсистемах PDM объединяются функции управления данными и проектированием. Пример такой PDM — подсистема Design Manager в САПР Euclid Quantum. Функциями этой PDM являются управление потоками проектных данных, версиями проекта, взаимодействием разработчиков, защита информации, конфигурирование и адаптация версий системы для конкретных пользователей.

      Подсистема Design Manager в Euclid Quantum состоит из частей пользовательской, админиcтратора и управления структурой продукта. В пользовательской части данные при выполнении проектирования могут находиться либо в распоряжении конкретного разработчика, в частности, в его индивидуальной БД (User Area), либо в зоне работы рабочей группы (Workgroup Area), в частности, в ее БД. Утвержденные данные пересылаются в центральную БД (Repository). Пересылка данных из User Area (UA) в Workgroup Area (WGA) происходит по инициативе разработчика командами check in или share. Первая из них начинает процедуру контроля данных, вторая обеспечивает разделение данных всеми участниками рабочей группы. Контроль данных выполняет уполномоченный член группы, результатом является или утверждение и, следовательно, направление их в репозиторий R, или неутверждение и отправка данных в UA на доработку. Разработчик может запрашивать данные для начала нового проекта по команде copy out или для модификации существующего проекта по команде check out (рис 5.6).

      %+,.5.6. Потоки данных в PDM Design Manager (САПР Euclid Quantum) В БД данные организованы иерархически, группируются по именам проектов или по типам данных. Вызов данных из любой БД (UA, WGA, R) выполняется командой retrieve, посылка в БД — командой store. При обращении к БД пользователь видит структуру данных (директорию — имена папок и их частей) и определенный аспект данных выделенного в директории проекта. Такими аспектами могут быть свойства документа (имя, автор, дата, статус и т.п.), список версий проекта, 3D изображение. В функции администратора системы входят упорядочение данных с их распределением по дискам, контроль за правами доступа пользователей, связь с внешними системами (управление импортом/экспортом данных) и др.

      В системной среде NELSIS CAD Framework имеются части: 1) DMS (Design Management Services) для поддержки иерархии данных, управления версиями и потоками задач;

      2) DMI (Design Management Interface) с функциями открытия и закрытия баз данных, вызова и пересылки данных, доступа к DMS;

      3) FUS (Framework User Services), включающая ряд браузеров для визуализации информации.

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

      &.+.)$(*),$". !"#$%!#&'&($"!))$* +($*,#&($"!)&* 5@!"! :&:#*%)K* :(*AK & +($5(!%%)$-%*#$A&F*:,&*,$%+@*,:K :!+( Предусмотрены следующие статусы: 1) ")2#1';

      – объект находится в работе, его можно модифицировать, в модуле хотя бы один объект должен иметь этот статус;

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

      2) принятый (аctual version) – именно эта версия служит для обмена между объектами, автоматически не стирается, ее модификации осуществляются через рабочий статус;

      3) архивный (Backup);

      4) порождаемый (Derived version) – статус зарезервирован для вновь создаваемых объектов, например, при синтезе проектных решений. Разработчик сам изменяет статус объектов. Любое изменение должно отражаться в отношениях объекта. NELSIS CAD Framework не изменяет существующие отношения, а создает новые. Например, если изменяется объект “топология”, то новая версия не наследует отношение со схемой, которая была получена экстракцией из старой топологии. Целостность данных поддерживается тем, что нельзя одновременно работать и изменять один и тот же объект разным разработчикам, так как каждый из них будет работать со своей рабочей версией. Данные проекта могут находиться в нескольких БД распределенного банка данных. Данные одной части проекта доступны другим частям, что позволяет выполнять параллельное проектирование. Для интеграции программных компонентов в системную среду (т.е. для согласования по данным этих компонентов с БД среды) используются обычные модификации компонента, если известен его код, или создается оболочка – модульная абстракция. В NELSIS CAD Framework имеется несколько браузеров для общения с пользователем. Для каждого браузера может быть открыто свое окно. 1. Design flow browser – показывает взаимосвязь между проектными процедурами, историю получения объекта, список процедур, которые могут быть выполнены над объектом, позволяет задавать маршруты проектирования, вызывать проектные процедуры и задавать их параметры, 2. Hierarchy Browser – показывает граф иерархии и место объекта в ней. 3. Version Browser – показывает все виды (viewtypes), статусы и номера версий выбранного объекта. Он может показать отношения эквивалентности, т.е. объекты, выражающие разные аспекты, например, топологию, схему, результаты моделирования физического объекта. 4. Equivalence Browser показывает отношения эквивалентности для выбранного объекта. 5. Schema Browser показывает сущности и их отношения в виде схемы данных, в отдельном окне показываются запросы к БД и ответы на них.

      5.3. !0,-8 *8.51 B1,-842 8:?8:B4-7+ 38+D4L.0+2. CASE-системы часто отождествляют с инструментальными средами разработки ПО, называемыми +"$-)/' 2.+&"#;

      ")6")2#&%' 0"'4#@$*';

      Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.