Элементы теории алгоритмов. Абстрактный алфавит, алфавитный оператор, массовость, результативность, страница 7

В общем случае ЛСА содержат один начальный А₀ и один конечный A_k операторы; за каждым логическим условием ставится стрелка, направленная вверх; не должно быть одинаково помеченных стрелок, направленных вниз; для каждой верхней (нижней) стрелки должна быть точно одна нижняя (верхняя) стрелка.

Для графической записи ЛСА используется язык граф-схем алгоритмов (ГСА). На рис. 1.3 показаны блоки (вершины) ГСА, где a₀—начальная вершина, А_k— конечная вершина, A_i—операторная вершина, P_j—условная вершина. В операторной вершине записывается оператор, в условной вершине записывается проверяемое логическое условие. Для рассмотренного выше примера записи алгоритма с помощью ЛСА на рис. 1.4 показана ГСА.

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

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

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

В САПР применяется «словесный» способ представления алгоритмов (по пунктам перечисляются блоки алгоритма и проверяемые логические условия). Словесное представление алгоритма.

 

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

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

Формализация таких расплывчатых понятий—одна из важных задач САПР. Для ее решения используется аппарат теории расплывчатых множеств и алгоритмов.

Пусть задано произвольное непустое множество Х=[х₁, х₂, ..., х_n}, \Х\=п, состоящее из n элементов. Расплывчатым множеством А множества Χ называется множество кортежей длины два:

 Функция  называется функцией принадлежности расплывчатого множества А. Для каждого элемента х. функция  принимает значение из интервала [0,1]. Если  имеет только крайние значения 1 и 0, то расплывчатое множество превращается в обыкновенное. Носителем А считают те элементы X' с X, для  которых  >0. Например, пусть Ζ—множество натуральных чисел; тогда его расплывчатое подмножество «малых» чисел может иметь вид  ={<1/0>,<0,9/1>,<0,8/2><0,7/3><0,6/4>,<0,5/5>}.

Носителем расплывчатого подмножества А является множество

Например, пусть X={ИМС1, БИС, СБИС, УБИС}  множество, состоящее из элементов: интегральная микросхема малой степени интеграции (ИМС1), большая интегральная схема (БИС), сверхбольшая интегральная схема (СБИС), ультрабольшая интегральная схема (УБИС). Тогда расплывчатое множество А —схема с наибольшей степенью интеграции элементов—может быть, с точки зрения автора, определено так: