Ивановский Государственный Энергетический Университет

Специальность 05.13.12 - Системы автоматизации проектирования (Электротехника и энергетика)

Специальность 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Диссертация на соискание ученой степени
кандидата технических наук

Научный руководитель

д.т.н. Нуждин В.Н.

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

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

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

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

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

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

Эта работа посвящена методам поиска совершенства.

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

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

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

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

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

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

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

Основные положения и результаты диссертационной работы доложены и обсуждены на 7-х Бенардосовских чтениях (Иваново, 1994).

По теме работы опубликовано 5 печатных работ.

Работа выполнена в Ивановском государственном энергетическом университете (разработка и исследование детерминированных методов синтеза) и Сиракузском Университете (Нью-Йорк) (разработка недетерминированных методов синтеза).

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

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

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

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

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

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

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

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

При планировании мы должны сделать определенные допущения и предположения.

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

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

Определенность и уверенность в наших действиях.

Структурирование времени.

Концентрация энергии на конкретных, определенных направлениях.

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

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

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

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

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

Частный случай задачи планирования ресурсов - это когда каждое отношение обмена построено по типу 1:1. Легко видеть, что этот частный случай полностью сводится к планированию в пространстве состояний.

Рисунок 2 Частный случай задачи планирования ресурсов, когда элементы имеют единственный вход и единственный выход, сводящийся к поиску кратчайшего пути

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

Аналогия между планированием ресурсов и планированием задач становится очевидной, если рассмотреть другой частный случай планирования ресурсов и представить сценарии обмена в виде И/ИЛИ-графа:

Рисунок 3 Частный случай задачи планирования ресурсов, сводящийся к задаче PR-планирования

Более общий случай приведен на нижнем рисунке. Как видно из рисунка, здесь уже возникают сложности с представлением задачи в виде И/ИЛИ-графа. Прибавление еще одного элемента F5 привело к появлению двух не вписывающихся в И/ИЛИ-граф ИЛИ-разветвлений, связанных с тем, что ресурс D может использоваться либо модулем F2 либо модулем F5 и, аналогично, ресурс G - либо модулем F5, либо F4, но никак не обоими. Это весьма необычная форма И/ИЛИ-графа сильно отличается от привычного дерева с И/ИЛИ-разветвлениями и алгоритмы поиска в неизменном виде в ней работают без успеха

Рисунок 4 Частный случай задачи обмена ресурсов, который не сводится к ранее рассмотренным.

Например, при имеющихся ресурсах G и D при стандартной интерпретации этого графа можно получить ресурс I. Однако это не так, если G - материальный ресурс, поскольку необходимы две единицы G. Узел, соответствующий ресурсу G, в общем случае может быть либо узлом ИЛИ в случае общественного блага (будет разобран в следующей главе) либо узлом ИСКЛЮЧАЮЩЕЕ-ИЛИ (XOR) в случае материального ресурса. Наличие таких вершин делает задачу достаточно сложной.

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

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

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

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

Подробно рассмотрены знания как ресурс и степень уверенности, как мера качества определенного знания. Степень качества знания как ресурса предложено указывать в процентном выражении. Разработана примерная шкала качества знания, где +100% соответствует вера, а -100% - полное отрицание.

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

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

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

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

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

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

Предлагается структура данных для хранения информации об операциях с ресурсами.

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

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

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

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

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

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

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

Большинство товаров и услуг имеют два общих свойства:

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

Как правило, наличие этих свойств у товара определяется легкостью его воспроизведения (отношения стоимости воспроизведения к стоимости создания)

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

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

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

Обязательства являются активами в двояком смысле:

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

Патент или лицензия - это документ, дающий право заниматься определенной деятельностью.

Как пример права можно привести право пользования. Атрибутом является объект, дата и срок пользования.

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

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

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

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

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

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

Потребность в структурировании времени настолько же важна для человека, как потребность в питании. Если человек не может структурировать свое время, он испытывает чувство структурного голода (тоски)[32].

Говоря о времени, мы подразумеваем время конкретного субъекта. Каждый субъект владеет, как минимум, одним ресурсом - потоком своего времени. Цена времени субъекта отражает его ценность для сообщества.

Но время, будучи ресурсом, является еще и шкалой, в рамках которой осуществляется планирование. В этой связи планирование - это структурирование целей во времени.

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

Короче, общественное благо

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

Информация может рассматриваться с трех основных точек зрения:

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

Идея представляет собой активно-пассивный объект. С одной стороны она имеет результат (effect), а с другой она требует затрат на осуществление, предпосылок (cause). В то время как результат является активом, предпосылки пассивны.

Законы ограничивают права и определяют обязанности. Любой закон активно-пассивен: в активе Ваши ограничиваемые права, в пассиве - плата за эти права или штрафные санкции. В этом смысле закон подобен "договору", от которого вы не можете отказаться. Такой "договор" можно расторгнуть лишь сменив гражданство и/или место проживания.

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

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

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

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

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

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

Активы субъекта - это то, чем он владеет в данный момент времени.

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

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

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

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

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

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

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

Обязательства

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

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

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

1. Исходное состояние

   1. Проект

   2. Объект

   3. Время

   4. Место

   5. Принадлежность (субъект)

   6. Количество

   7. Скрипт

2. Конечное состояние

   1. Проект

   2. Объект

   3. Время

   4. Место

   5. Принадлежность (субъект)

   6. Количество

   7. Скрипт

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

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

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

Ниже приведен пример иерархии:

БАЛАНС
Актив
Дом
Автомобиль
Деньги
Банковский депозит $88,000
Наличные $2,000
Пассив ($200,000)
Ссуда ($200,000)

Вершиной иерархии является БАЛАНС. На бумаге он представляет собой обычно два-три верхних уровня верхушки пирамиды классификации по ликвидности в суммовом выражении.

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

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

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

При этом активы и пассивы могут быть удовлетворенными (замкнутыми) и неудовлетворенными (разомкнутыми)

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

На основании рассмотрения внешних и внутренний активов/пассивов мы можем сделать важный вывод об оптимальном распоряжении имеющимися ресурсами.

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

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

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

Рисунок 6 Вариант обмена иммобилизованного актива

Структура данных для хранения информации об операциях

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

В импортных программах бухгалтерского учета (напр. QUICKEN, QUICKBOOKS) более распространен другой подход:

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

Формат, предложенный ниже, является обобщением предыдущего на случай планируемых операций (поле Проект). Кроме того поле Счет заменено на поля Субъект и Место.

Это означает, что Швейная фабрика хотела бы обменять 30000 единиц своей продукции на 100 км ситца.

Другой пример:

Это пример предложения летнего курса, который дает знания Экономики в размере 2 кредита, занимает 30 часов, требует от студента знания математического анализа в размере 2 кредитов, $500, и разрешение инструктора. В третьей строке цифра 2 стоит и в кредите, и в дебете. Это означает, что данный ресурс не потребляется в процессе обучения, он только является условием зачисления на курс.

Поле "Скрипт" используется для проектов, где некоторые поля, например дата/время изначально не определены и получают значение только в процессе синтеза структур. Поле "Скрипт" накладывает ограничения на значения, которые могут принимать эти поля.

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

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

Тип вершины И/ИЛИ-графа имеет критическое отношение для определения перспективности частично-синтезированной структуры.

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

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

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

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

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

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

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

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

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

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

Предикат этот - логическая функция

chng: S x 2G x 2G --> {true,false}

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

Теперь введем три новые необходимые нам функции

Тогда, очевидно

где

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

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

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

Докажем для начала следующую теорему.

Теорема 1

Если Pn - разбиение множества S, то

Доказательство:

из (3) и (4) видно, что

Поэтому . Таким образом, теорема доказана для USup(S). Два оставшихся утверждения доказываются аналогично.

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

Эти выражения описывают изменение параметров структуры при добавлении к ней еще одного элемента x.

Назовем такую операцию над структурой ее "расширением". Из выражений (9)-(11) нетрудно получить также выражения для "сокращения" структуры" или удаления из нее элемента x. Самый легкий (и не совсем строгий) способ получить их, это определив элемент `x так, чтобы Dem(`x)=Sup(x) и Sup(`x)=Dem(x). Понятно, что добавление элемента `x к структуре, содержащей x будет эквивалентно удалению из этой структуры элемента x. Поэтому, пользуясь выражениями (9)-(11), можно записать

Учитывая определение элемента `x, получаем

Аналогично поступив с оставшимися выражениями (10) и (11), получим

Эти более сложные выражения вычисляются быстрее, чем предыдущие. Дело в том, что в данном случае мы на каждом этапе используем результаты предыдущего этапа USup(Si\{x}), UDem(Si\{x}) вместо того, чтобы все начинать с нуля.

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

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

За каждый шаг расширения к текущей структуре добавляется один элемент. Параметры новой "расширенной" структуры легко определяются в соответствии с (9)-(11). Аналогичные соотношения применимы, если структура "сокращается" на один элемент.

Как было отмечено, наша задача состоит в нахождении таких множеств Si, чтобы . Используем процедуру поиска, широко известную под названием generate-and-test [7]: будем генерировать и проверять условие с помощью выражения (10). Существуют несколько способов генерации или перебора вариантов. Попытаемся найти оптимальный.

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

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

Выражение (13) показывает ту часть удовлетворенного спроса, которая получается за счет предложения элемента х, а выражение (14) - за счет спроса элемента х.

Распространение по спросу

Назовем его расширением (или распространением) по спросу. Упрощенно можно объяснить его так: рассматриваются только те предложения, которые смогут удовлетворить наш спрос. Математически это запишется в виде условия ASDem(Si)<>0. Метод основан на выражении (13)

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

Расширение по предложению: рассматриваются только те предложения, которые используют то, что у нас уже имеется в наличии. Математически это формулируется так ASSup(Si)<>0. Метод основан на выражении (14).

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

Методы расширения по спросу и по предложению оказываются эффективны, но каждый в своей области. Наоборот, если применить расширение по предложению к задаче построения учебного плана, то у нас не хватит терпения дождаться результата. Все это говорит о том, что весьма неплохо было бы иметь алгоритм, который бы сам определял, какой метод из двух избрать. Вариантов построения такого алгоритма может быть очень много. Их сразу разделим на статические и динамические [7].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Редактор, 4

Бейсик, 3

Паскаль, 3

FoxPro, 2

Ассемблер, 2

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

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

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

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

Рисунок 11 Взаимосвязь между анализом, синтезом и планированием

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

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

Рисунок 12 Сохранение знаний как функция времени

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

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

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

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

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

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

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

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

1. Определение целей (Цели)

2. Выбор учебных действий (Анализ)

3. Организация учебных действий (Синтез)

4. Определение процессов оценки полученных знаний (Оценка)

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

Мы должны учесть при планировании:

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

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

3. Уровень подготовки преподавателей, уровень знания ими преподаваемого предмета.

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

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

6. Интересы и мотивация студента (спрос целевого модуля).

7. Материальные ресурсы: чем преподаватель будет пользоваться для занятия -- учебники, видеофильмы, компьютеры, программы.

8. Время очень важно в процессе планирования. Время служит точкой отсчета и мерой эффективности учебы.

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

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

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

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

Недетерминированный метод, предлагаемый здесь, основан на применении к синтезу структур идеи эволюционного метода, предложенного Джоном Холландом. Автор имел возможность на протяжении полутора месяцев изучать его в Сиракузском Университете шт. Нью-Йорк. Таким образом зародилась идея применения его к синтезу структур обмена ресурсов, чему и посвящена данная глава.

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

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

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

Общие принципы генетических алгоритмов

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

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

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

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

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

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

Кольцевое представление генома

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

Рисунок 13 Представление генома в виде кольца

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

Рисунок 14 Кроссовер кольцевого генома

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

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

Рисунок 17 Абсолютное преимущество кольцевого кроссовера

Видно, что использование кольцевого генома дает нам в большинстве случаев на 1-2 решения больше. Это решения, которые содержат в себе "некомпактные полезные строительные блоки".

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

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

Рисунок 18 Разность числа структур между случайным и кольцевым скрещиванием

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

В приведенном выше фрагменте популяции вероятность одиночного перекрещивания разрушить строительный блок 1*********1 равна 1/12, а вероятность его сохранения 11/12.

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

Рик Риоло в своей работе [18] отмечает, что большая часть популяции состоит из очень похожих, если не идентичных, цепочек. Этот результат, называемый сходимостью, объясняется тем, что генетический алгоритм загоняет популяцию во все более узкие целевые области. Зачастую популяция сходится к одной особи, которая не является оптимальной. По существу алгоритм застревает на локальном экстремуме. Сходимость может практически привести к вырождению, поскольку она означает, что скрещивание не даст существенного эффекта в поисках лучших особей. Скрещивая две идентичные цепочки, мы получим такие же две цепочки, и ничего нового не произойдет. Поиск способов избежать нежелательносй сходимости - очень активная область исследований.

Предлагаемый здесь алгоритм с переменным размером популяции позволяет избежать сходимости. Кроме того, как видно из графиков, приведенных в предыдущем разделе, эффективность работы генетического алгоритма сильно зависит от размера популяции: чем он больше, тем лучше. Хотя генетические алгоритмы имитируют механизм естественного отбора, до сих пор они действовали в значительно меньших масштабах по сравнению с биологической эволюцией. Холланд [17] отмечает, что в своей лаборатории он и его коллеги исследовали поведение генетического алгоритма на популяциях, содержащих до 8000 генетических цепочек. Судя по всему, сдерживающим фактором являются ограничения по ресурсам вычислительной системы: памяти и быстродействию. Использованный здесь алгоритм позволяет хранить популяцию в "сжатом виде", существенно экономя память и время на ее обработку. С помощью этого метода можно обрабатывать популяции, насчитывающие сотни тысяч и более особей.

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

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

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

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

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

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

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

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

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

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

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

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

Эта таблица построена на основе контрольного примера из приложения II и содержит 27*30=810 бит информации. Каждая единица в ней соответствует связи между выходом и входом. Очевидно, развертка соответствует требованию, предъявляемому к генотипу: любой набор бит фиксированной длины (=810 бит) дает нам структуру.

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

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

Недостатком подобного подхода является то, что различные номера не будут равновероятными при случайном изменении генома. Однако мне не известно лучшего варианта представления. И более того, похожий принцип используется в природе для кодирования аминокислот в триплетах ДНК, каждый элемент которых может принимать по четыре значения. Всего комбинаций 4*4*4=64. Нужно кодировать 20 аминокислот и поэтому "лишние" комбинации рассматриваются как псевдонимы. В результате некоторые аминокислоты имеют одно, а другие - много представлений [19].

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

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

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

1. Требования каждого элемента структуры должны быть удовлетворены в пределах этой структуры.

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

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

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

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

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

Тем выше, чем сильнее связаны элементы внутри структуры

При определении критерия внутренней связности мне показалось удобным использовать финансовые понятия дебета D, кредита K, оборота по дебету OD, оборота по кредиту OK.

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

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

1. D/OD - степень удовлетворения первоначального спроса

2. (D-K)/(OD+OK) - в финансовом анализе коэффициент оборачиваемости средств

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

Рисунок 19 Элементарный классификатор

Рисунок 20 Каскад из трех классификаторов

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

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

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

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

Традиционные виды оценки кривой оказались слишком трудоемкими. Коэффициент разделения - отношение абсцисс точек, ординаты которых 0.25 и 0.75. Этот критерий требует либо первоначального построения всей кривой разделения, а затем ее интерполяции, либо численного решения двух нелинейных уравнений, где для того, чтобы получить одну точку кривой требуется решить систему уравнений порядка N. Это требует неприемлемо большого времени.

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

Рисунок 21 Характеристики каскадов классификации

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

Коэффициенты соответствующих аппроксимирующих кривых Больцмана:

Sigmoidal(Boltzman) fit to F893A6A2_Y
Chisqr = 9.1837E-7
---------------------------------
Init(A1) = 1.0004 1.71E-4
Final(A2) = 5.8908E-4 1.67E-4
XatY50(x0) = 0.49026 4.69E-5
Width(dx) = 0.026533 4.08E-5
---------------------------------
XatY20 = 0.45348
XatY80 = 0.52705

Sigmoidal(Boltzman) fit to F2831425_Y
Chisqr = 5.7801E-6
---------------------------------
Init(A1) = 0.99907 4.38E-4
Final(A2) = -0.0013175 4.28E-4
XatY50(x0) = 0.49156 1.3E-4
Width(dx) = 0.031431 1.13E-4
---------------------------------
XatY20 = 0.44799
XatY80 = 0.53513

Как видно ширина полосы разделения уменьшилась на 16 процентов.

Рисунок 24 Синтезированный оптимальный каскад

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

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

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

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

Моделирование синтезированных вариантов проводилось с использованием математической модели произвольного каскада классификации, приведенной в работе [27]. Критерий оптимизации для синтеза был придуман автором из интуитивных соображений, а затем математически обоснован. Приведенные в работах [27,29] критерии оценки кривой оказались слишком трудоемкими, для того чтобы рассмотреть большое множество схем. Однако, оказалось, что простой и технологичный критерий, оказался хорошим для синтеза, и последующая проверка синтезированных вариантов с помощью более сложных критериев показала его корректность. Были определены оптимальные по кривой разделения структуры, состоящие из 2-15 однотипных классификаторов. Были получены новые схемы, которые по характеристикам кривой разделения превзошли известные схемы, считавшиеся оптимальными. Выявлено, что вид оптимальной структуры каскада в общем случае неинвариантен относительно кривой разделения элементарного классификатора (особенно при ассимметричной кривой разделения одного классификатора). Эксперименты по применения алгоритма синтеза показали, что разработанная система синтеза может быть успешно использована для автоматического проектирования оптимальных каскадов классификации с заданными параметрами. Кроме того, синтез и последующее моделирование позволили получить результаты, которые, несомненно, дадут толчок новым исследованиям в области систем классификации.

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

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

2. Разработаны базовые детерминированные методы синтеза структур.

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

4. Были проведены исследования базовых методов, показавшие, при каких условиях их использование наиболее эффективно. Эти исследования позволили сформулировать эвристические правила для адаптивных методов синтеза.

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

6. Разработана и реализована система генетического синтеза. Проведены сравнительные исследования различных вариантов построения недетерминированного алгоритма.

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

8. Были получены оптимальные схемы каскадов для количества классификаторов от 2 до 15, в том числе новые, превосходящие известные по показателям ширины полосы разделения на величину до 16%

Децентрализация синтеза

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

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

Мне кажется перспективным в связи с этим развитие разработка принципиально новых, несравненно более децентрализованных алгоритмов синтеза, или, по крайней мере, развитие потенциальной децентрализованности уже имеющихся алгоритмов синтеза. Что здесь имеется в виду под "потенциальной децентрализованностью", так это во-первых децентрализованная идея распространения, когда модули, лежащие на границе распространения сами решают, куда им удобнее проводить экспансию (наподобие клеточного алгоритма), и во-вторых, применение распределенных алгоритмов поиска, наподобие тех, которые применяются в адаптивной каналообразующей аппаратуре сетей передачи данных [7].

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

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

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

Списки и приложения

Программная система синтеза структур проста в обращении. Это руководство поможет удобно ее использовать. Основная программа называется MAINPS.EXE

╔════════════════ Tree ════════════════╗╔════════════ D:\PSYS\BASE ═════╤══11 00

║ ├──ET ║║ Name │ Size │ Date │ Time ║

║ │ ├──RIXAI ║║TXT │_SUB-DIR_│13/03/95│ 18:41║

║ │ ├──UTILITY ║║TXTA │_SUB-DIR_│11/12/95│ 19:01║

║ │ ├──VESA ║║base arj│ 150473│14/03/95│ 9:35║

║ │ └──WIN31 ║║base3 exe│ 88347│26/05/92│ 14:25║

║ ├──D&G ║║colors dbi│ 28│21/05/94│ 23:08║

║ │ ├──MMPI ║║courstru txt│ 17457│ 1/11/95│ 16:47║

║ │ └──DMP ║║dbase dbi│ 0│ 1/11/95│ 22:16║

║ ├──PSYS ║║g_old dba│ 14714│ 7/04/92│ 9:15║

║ │ ├─▌BASE ▐ _║║goods sbj│ 10028│ 1/01/80│ 0:16║

║ │ │ ├──TXTA ║║goods1 sbj│ 18903│ 1/01/80│ 0:31║

║ │ │ ├──TM ║║lineinp pro│ 5372│15/05/91│ 18:58║

║ │ │ ├──INFKA ║║main log│ 4053│11/12/95│ 18:54║

║ │ │ ├──COMMAT ║║mainp pro│ 15773│10/10/93│ 12:02║

║ │ │ ├──ECON ║║mainpa pro│ 14710│ 6/10/93│ 15:47║

║ │ │ ├──DBIS ║║mainpas dif│ 15052│13/03/95│ 22:27║

║ │ │ ├──DBI ║║mainps bak│ 20653│11/12/95│ 17:01║

║ │ │ └──TXT ║║mainps exe│ 186470│11/12/95│ 18:49║

║ │ ├──BGI ║║mainps obj│ 97484│11/12/95│ 18:49║

╟──────────────────────────────────────╢╟────────────┴─────────┴────────┴──────╢

║D:\PSYS\BASE ║║mainps.exe 186470 11/12/95 18:49║

╚══════════════════════════════════════╝╚══════════════════════════════════════╝

D:\PSYS\BASE>

1Help 2Menu 3View 4Edit 5Copy 6RenMov 7Mkdir 8Delete 9PullDn 10Quit

Экран программы после запуска выглядит примерно так:

┌──────────────────────────────────────────────────────────────────────────────┐

└──────────────────────────────────────────────────────────────────────────────┘

┌──────────────────────────────────────┐┌───────Info───────┐┌─────Subjects─────┐

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

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

┌─────────────────────── StructSynthesizer (c) ROSE,Ltd. ──────────────────────┐

│╧Ёхфыюцхэшх │

│root │

│ ├──car │

│ │ ├──toyota │

│ │ │ ├──Corolla │

│ │ │ └──Carina │

│ │ ├──nissan │

│ │ └──ford │

│ └──electronics │

│ ├──telephone │

│ ├──copier │

│ │ ├──Xerox │

│ │ ├──Canon │

│ │ └──Ricoh │

│ ├──fax │

│ └──computer │

│ ├──IBM │

│ │ ├──486 │

│ │ ├──386DX │

│ │ ├──386SX │

└──────────────────────────────────────────────────────────────────────────────┘

└─────────────────────────────────────────────────────────────────────────┘ бв░

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

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

┌─────────────────────── StructSynthesizer (c) ROSE,Ltd. ──────────────────────┐

│╧Ёхфыюцхэшх │

│root │

│ ├──car ┌──Owner choise──┐ │

│ │ ├──toyota │abc │ │

│ │ │ ├──Corolla │Steave │ │

│ │ │ └──Carina │Paul │ │

│ │ ├──nissan │Bob │ │

│ │ └──ford │Bill │ │

│ └──electronics │AL │ │

│ ├──telephone │┬тхёЄш эютюую │ │

│ ├──copier └────────────────┘ │

│ │ ├──Xerox │

│ │ ├──Canon │

│ │ └──Ricoh │

│ ├──fax │

│ └──computer │

│ ├──IBM │

│ │ ├──486 │

│ │ ├──386DX │

│ │ ├──386SX │

└──────────────────────────────────────────────────────────────────────────────┘

│F2-Ident F5-Browse F6-Dem/offer F7-Add F10-Exit │ ║п┐

└─────────────────────────────────────────────────────────────────────────┘ бв░

┌─────────────────────── StructSynthesizer (c) ROSE,Ltd. ──────────────────────┐

│╧Ёхфыюцхэшх Variant - 1 Curent owner - Paul │

│root │

│ ├──car │

│ │ ├──toyota │

│ │ │ ├──Corolla ┌──────────┐ │

│ │ │ └──Carina 286 ────>│ │ │

│ │ ├──nissan telephone────>│Paul │────>386DX │

│ │ └──ford └──────────┘ │

│ └──electronics │

│ ├──telephone │

│ ├──copier │

│ │ ├──Xerox │

│ │ ├──Canon │

│ │ └──Ricoh │

│ ├──fax │

│ └──computer │

│ ├──IBM │

│ │ ├──486 │

│ │ ├──386DX │

│ │ ├──386SX │

└──────────────────────────────────────────────────────────────────────────────┘

│F2-Ident F5-Browse F6-Dem/offer F7-Add F10-Exit │ ║п┐

└─────────────────────────────────────────────────────────────────────────┘ бв░

Если мы решили создать новый класс ресурсов или просто ресурс, мы нажимаем F7-Add, предварительно установив курсор на тот класс, который будет родителем нового класса или ресурса, в данном случае родительский класс "CAR".

┌─────────────────────── StructSynthesizer (c) ROSE,Ltd. ──────────────────────┐

│root │

│ │ ├──toyota │

│ │ └──ford └──────────┘ │

│ └──electronics │

│ ├──telephone │

│ ├──copier │

│ │ ├──Xerox │

│ │ ├──Canon │

│ │ └──Ricoh │

│ ├──fax │

│ └──computer │

│ ├──IBM │

│ │ ├──486 │

│ │ ├──386DX │

│ │ ├──386SX │

└──────────────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────┐ и╕к

└─────────────────────────────────────────────────────────────────────────┘ бв░

Новый класс занимает свое место в иерархии, как показано на следующем рисунке:

┌─────────────────────── StructSynthesizer (c) ROSE,Ltd. ──────────────────────┐

│╧Ёхфыюцхэшх Variant - 1 Curent owner - Paul │

│root │

│ ├──car │

│ │ ├──toyota ┌──────────┐ │

│ │ │ ├──Corolla 286 ────>│ │ │

│ │ │ └──Carina telephone────>│Paul │────>386DX │

│ │ ├──nissan └──────────┘ │

│ │ └──ford │

│ └──electronics │

│ ├──telephone │

│ ├──copier │

│ │ ├──Xerox │

│ │ ├──Canon │

│ │ └──Ricoh │

│ ├──fax │

│ └──computer │

│ ├──IBM │

│ │ ├──486 │

│ │ ├──386DX │

└──────────────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────┐ и╕к

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

┌─────────────────────── StructSynthesizer (c) ROSE,Ltd. ──────────────────────┐

│╧Ёхфыюцхэшх Variant - 1 Curent owner - Paul │

│ │

│ │

│ │

│ root.electronics.computer.IBM.386DX │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

└──────────────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────┐ и╕к

Нажимая клавишу F6-Dem/Offer, переходи от предложения к спросу и обратно. Где мы в текущий момент находимся указано в верхнем левом углу экрана:

┌─────────────────────── StructSynthesizer (c) ROSE,Ltd. ──────────────────────┐

│╤яЁюё Variant - 1 Curent owner - Paul │

│ │

│ │

│ │

│ root.electronics.computer.IBM.286 │

│ root.electronics.telephone │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

└──────────────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────┐ и╕к

│F2-Ident F5-Browse F6-Dem/offer F7-Add F10-Exit │ ║п┐

└─────────────────────────────────────────────────────────────────────────┘ бв░

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

Выход из системы ввода и экспорт всех данных в файл обмена SALES.DBI производится при нажатии F10 в дереве классификатора ресурсов. Система спрашивает подтверждение и при утвердительном ответе выходит из системы ввода.

┌─────────────────────── StructSynthesizer (c) ROSE,Ltd. ──────────────────────┐

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ ┌───────────────────────────────────┐ │

│ │Do you really want to quit (y/n) │ │

│ └───────────────────────────────────┘ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

└──────────────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────┐ и╕к

│F2-Ident F5-Browse F6-Dem/offer F7-Add F10-Exit │ ║п┐

└─────────────────────────────────────────────────────────────────────────┘ бв░

После выхода из системы ввода возврашаемся к меню системы синтеза. Загрузим теперь экспортированный файл SALES.DBI, выбрав команду Load all из меню Files, как показано на рисунке

┌──────────────────────────────────────────────────────────────────────────────┐

└───────────────────────────────────┬───────────────┬──────────────────────────┘

┌───────────────────────────────────│Load │──────┐┌─────Subjects─────┐

│ │Load translated│ ││ │

│ │View database │ ││ │

│ │View Log file │ ││ │

│ │Set NMax value │ ││ │

│ │Disable Sorting│ ││ │

│ └───────────────┘ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

┌──────────────────────────────────────────────────────────────────────────────┐

└───────────────────────────────────┬───────────────┬──────────────────────────┘

┌──────────────────────── Directory: D:\PSYS\BASE\*.DBI ───────────────────────┐

│ COMMAT\ DBI\ DBIS\ ECON\ INFKA\ │

│ TM\ TXT\ TXTA\ ..\ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

│ │

└──────────────────────────────────────────────────────────────────────────────┘

│ ││ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

F2-Save F3-Load F4-File mask F5-Zoom Shift-F10-Resize F10-End

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

┌──────────────────────────────────────────────────────────────────────────────┐

└─────────────────┬────────────────┬───────────────────────────────────────────┘

│ │Offer expansion │ ││ ││ │

│ │CSA │ ││ ││ │

│ │SFA │ ││ ││ │

│ └────────────────┘ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

│ ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

Результаты синтеза отражаются одновременно в двух окнах: окне синтеза и окне системных сообщений.

┌──────────────────────────────────────────────────────────────────────────────┐

└─────────────────┬────────────────┬───────────────────────────────────────────┘

┌──────────────────────────────────────┐┌───────Info───────┐┌─────Subjects─────┐

│ ││ ││ abc │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│───────────────────────────────────────── ││ │

│<<< Bob >>> 11:4:19.59 ││ │

│<<< Paul >>> 11:4:19.65 ││ │

│<<< Steave >>> 11:4:19.65 ││ │

│<<< abc >>> 11:4:19.65 ││ │

│--- Elapsed time 0.16 ...Simulation engine stopped ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

Мы можем рассматривать результаты синтеза в окне синтеза, не дожидаясь окончания всего процесса синтеаз и не останавливая его. Установив курсор на поле "Bill" и нажав Enter, получим следующую картинку:

┌──────────────────────────────────────────────────────────────────────────────┐

└─────────────────┬────────────────┬───────────────────────────────────────────┘

┌──────────────────────────────────────┐┌───────Info───────┐┌─────Subjects─────┐

│ ││ ││ abc │

│ ││ ││ │

│ ┌────────┐ ││ ││ │

│ Steave ───>│ ├───>Paul ││ ││ │

│ │ │ ││ ││ │

│ └────────┘ ││ ││ │

│ ││ ││ │

│ ═ BROWSE ═ ││ ││ │

│ ││ ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│───────────────────────────────────────── ││ │

│<<< Bob >>> 11:22:50.35 ││ │

│<<< Paul >>> 11:22:50.35 ││ │

│<<< Steave >>> 11:22:50.40 ││ │

│<<< abc >>> 11:22:50.40 ││ │

│--- Elapsed time 0.11 ...Simulation engine stopped ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

Если мы переведем курсор на поле "Paul" и нажмем Enter, то получим аналогичную картинку графического представления другого элемента. В информационном окне можно видеть, какие ресурсы перемещаются от изображенного элемента к тому, на котором стоит курсор, в данном случает от элемента "Paul" к элементу "Steave".

┌──────────────────────────────────────────────────────────────────────────────┐

│ Input Synthesis Files Windows Quit │

└─────────────────┬────────────────┬───────────────────────────────────────────┘

┌──────────────────────────────────────┐┌───────Info───────┐┌─────Subjects─────┐

│ ││ ││ abc │

│ ││obj("root.electron││ │

│ ┌────────┐ ││ics.computer.IBM.3││ │

│ │Paul │ ││86DX",1,[att("moni││ │

│ Bill ───>│ ├───>Steave ││tor","=","SVGA"),a││ │

│ │ │ ││tt("memory","=","8││ │

│ └────────┘ ││"),att("hard disk"││ │

│ ││,"=","120"),att("p││ │

│ ═ BROWSE ═ ││rice","=","2400")]││ │

│ ││) ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│───────────────────────────────────────── ││ │

│<<< Bob >>> 11:22:50.35 ││ │

│<<< Paul >>> 11:22:50.35 ││ │

│<<< Steave >>> 11:22:50.40 ││ │

│<<< abc >>> 11:22:50.40 ││ │

│--- Elapsed time 0.11 ...Simulation engine stopped ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

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

┌──────────────────────────────────────────────────────────────────────────────┐

└─────────────────┬────────────────┬───────────────────────────────────────────┘

┌─────────────────│Demand expansion│───┐┌───────Info───────┐┌─────Subjects─────┐

│ │Offer expansion │ ││ ││ abc │

│ │CSA │ ││obj("root.electron││ │

│ ┌──│SFA │ ││ics.computer.IBM.3││ │

│ │Pa└────────────────┘ ││86DX",1,[att("moni││ │

│ Bill ───>│ ├───>Steave ││tor","=","SVGA"),a││ │

│ │ │ ││tt("memory","=","8││ │

│ └────────┘ ││"),att("hard disk"││ │

│ ││,"=","120"),att("p││ │

│ ═ BROWSE ═ ││rice","=","2400")]││ │

│ ││) ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│───────────────────────────────────────── ││ │

│<<< Bob >>> 11:22:50.35 ││ │

│<<< Paul >>> 11:22:50.35 ││ │

│<<< Steave >>> 11:22:50.40 ││ │

│<<< abc >>> 11:22:50.40 ││ │

│--- Elapsed time 0.11 ...Simulation engine stopped ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

После прерывания или окончания синтеза мы можем просмотреть его протокол, т.е. текстовый документ, описывающий синтезированные структуры. Формат его подробно описан ранее, поэтому здесь не будем его разбирать. Получим этот протокол, выбрав в меню Files опцию View Log file.

┌──────────────────────────────────────────────────────────────────────────────┐

└───────────────────────────────────┬───────────────┬──────────────────────────┘

┌───────────────────────────────────│Load │──────┐┌─────Subjects─────┐

│ │Load all │ ││ abc │

│ │Load translated│ectron││ │

│ ┌────────┐ │View database │.IBM.3││ │

│ Bill ───>│ ├───>Steave │Set NMax value │GA"),a││ │

│ │ │ │Disable Sorting│"=","8││ │

│ └────────┘ └───────────────┘ disk"││ │

│ ││,"=","120"),att("p││ │

│ ═ BROWSE ═ ││rice","=","2400")]││ │

│ ││) ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│───────────────────────────────────────── ││ │

│<<< Bob >>> 11:22:50.35 ││ │

│<<< Paul >>> 11:22:50.35 ││ │

│<<< Steave >>> 11:22:50.40 ││ │

│<<< abc >>> 11:22:50.40 ││ │

│--- Elapsed time 0.11 ...Simulation engine stopped ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

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

Line 1 Col 1 Indent Insert

<<< AL >>>

<<< Bill >>>

["Bill","Paul","Steave"]

UnsOff:[]

OS = ["Paul","Steave","Bill"] Sig= 4

Steave --> 1 root.electronics.copier.Xerox --> Bill

Paul --> 1 root.electronics.computer.IBM.386DX --> Steave

Bill --> 1 root.electronics.computer.IBM.286 --> Paul

Bill --> 1 root.electronics.telephone --> Paul

─────────────────────────────────────────

<<< Bob >>>

<<< Paul >>>

<<< Steave >>>

<<< abc >>>

F1-Help F2-Save F3-Load F5-Zoom F6-Next F7-Xcopy F8-Xedit F10-End

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

Выйти из него можно по клавише Escape или F10.

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

┌──────────────────────────────────────────────────────────────────────────────┐

└─────────────────────────────────────────────────┬────────┬───────────────────┘

┌──────────────────────────────────────┐┌───────In│Demand │┌─────Subjects─────┐

│ ││ │Offer ││ abc │

│ ││obj("root│Subjects││ │

│ ┌────────┐ ││ics.compu│Message ││ │

│ │Paul │ ││86DX",1,[└────────┘│ │

│ Bill ───>│ ├───>Steave ││tor","=","SVGA"),a││ │

│ │ │ ││tt("memory","=","8││ │

│ └────────┘ ││"),att("hard disk"││ │

│ ││,"=","120"),att("p││ │

│ ═ BROWSE ═ ││rice","=","2400")]││ │

│ ││) ││ │

│ ││ ││ │

└──────────────────────────────────────┘└──────────────────┘│ │

┌──────────────────────────Message─────────────────────────┐│ │

│ Line 2 Col 1 Indent Insert ││ │

│<<< AL >>> ││ │

│<<< Bill >>> ││ │

│ ││ │

│["Bill","Paul","Steave"] ││ │

│UnsOff:[] ││ │

└──────────────────────────────────────────────────────────┘└──────────────────┘

Select with arrows or use first upper case letter

Выход из программы осуществляется по выбору опции Quit главного меню.

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

• Контрольный пример

• Синтез курса компьютерной математики

• Синтез курса экономики

• Синтез курсов информатики, математики и физики

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

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

Далее приведено описание 15 элементарных модулей в виде предикатов первого порядка.

chng("p1",

<-- [obj("a",1,[]),

obj("b",1,[])],

--> [obj("c",1,[]),

obj("d",1,[]),

obj("e",1,[]),

obj("f",1,[])])

chng("p2",

obj("d",1,[])],

obj("h",1,[])])

chng("p3",

obj("f",1,[])],

obj("i",1,[])])

chng("p4",

obj("h",1,[])],

chng("p5",

obj("j",1,[])],

chng("p6",

chng("p7",

chng("p8",

obj("f",1,[])],

chng("p10",

obj("i",1,[])],

obj("f",1,[])])

chng("p11",

obj("d",1,[]),

obj("e",1,[]),

obj("f",1,[])],

obj("b",1,[])])

chng("p12",

obj("h",1,[]),

obj("m",1,[])],

obj("n",1,[])])

chng("p13",

chng("p14",

obj("j",1,[]),

obj("z",1,[])],

obj("x",1,[])])

chng("p15",

chng("p16",

obj("d",1,[])],

obj("b",1,[])])

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

<<< p1 >>>

["p1","p2","p4","p6","p8"]

UnsOff:[ob("p4",obj("k",2,[]))]

OS = ["p2","p4","p6","p8","p1"] Sig= 16

OS = ["p2","p4","p8","p6","p1"] Sig= 15

OS = ["p8","p2","p4","p6","p1"] Sig= 14

-----------------------------------------

["p1","p12","p13","p2","p6","p8"]

UnsOff:[]

-----------------------------------------

Данные о пререквизитах и постреквизитах элементарных модулей в области экономики основаны путем формализации мной пререквизитов наиболее удачной, с моей точки зрения, концепции изложения экономических знаний, приведенной в [3].

Целевой модуль:

chng("А1 Студент",

Модули элементарных учебных дисциплин:

chng("Г1 Экон обр мышления",

obj("Экономика",1,[]),

obj("Модель",1,[]),

obj("Теории",1,[]),

obj("Стих порядок",1,[]),

obj("Сравнит преимущ",1,[]),

obj("Рынки",1,[]),

obj("Предпринимательство",1,[]),

obj("Спрос",1,[]),

obj("Предложение",1,[]),

obj("Экономика.Нормативная",1,[]),

obj("Экономика.Позитивная",1,[]),

obj("Общественные блага",1,[]),

obj("Затраты.Непроизводственные",1,[]),

obj("Иерархии",1,[]),

obj("Закон.Непредвиденных посл",1,[]),

obj("Стоимость.Альтернативная",1,[])])

chng("Г2 Спр и пред:Основы",

obj("Рынки",-1,[]),

obj("Закон.Непредвиденных посл",-1,[]),

obj("Стоимость.Альтернативная",-1,[])],

obj("Товары.Низшие",1,[]),

obj("Товары.Нормальные",1,[])])

chng("Г3 Пред,спр,эласт",

obj("Товары.Субституты",-1,[]),

obj("Спрос",-1,[]),

obj("Предложение",-1,[]),

obj("Товары.Нормальные",-1,[]),

obj("Товары.Низшие",-1,[])],

obj("Налогообложение.Структура",1,[]),

obj("Спрос.Совершенно эласт",1,[]),

obj("Налогообложение.Распределение бремени",1,[]),

obj("Налогообложение",1,[])])

chng("Г4 Введ в микроэк-ку",

obj("Предпринимательство",-1,[]),

obj("Спрос",-1,[]),

obj("Предложение",-1,[]),

obj("Экономика.Нормативная",-1,[]),

obj("Экономика.Позитивная",-1,[]),

obj("Закон.Непредвиденных посл",-1,[])],

obj("Выбор.Варианты",1,[]),

obj("Выбор.Ограничения",1,[]),

obj("Выбор.Цели",1,[]),

obj("Рынки.Функционирование",1,[]),

obj("Фиаско.Рынка",1,[]),

obj("Фиаско.Правительства",1,[]),

obj("Теории.Обществ выбора",1,[]),

obj("Права.Собственности",1,[]),

obj("Рациональность.Ограниченная",1,[]),

obj("Рациональность.Полная",1,[]),

obj("рента.Поиск",1,[]),

obj("Монополия",1,[]),

obj("Внешние эффекты",1,[])])

chng("Г5 Потреб выбор",

obj("Товары.Субституты",-1,[]),

obj("Товары.Низшие",-1,[]),

obj("Товары.Нормальные",-1,[]),

obj("Налогообложение",-1,[])],

obj("Излишки.Производителя",1,[]),

obj("Доход и эфф замещения",1,[])])

chng("Г6 Произв и издержки",

obj("Предпринимательство",-1,[]),

obj("Стоимость.Альтернативная",-1,[])],

obj("Предельный продукт.Физический",1,[]),

obj("Издержки.На кратко и долгоср",1,[]),

obj("Закон.Убывающей доходн",1,[])])

chng("Г7 Пред в усл сов конк",

obj("Выбор.Цели",-1,[]),

obj("Выбор.Ограничения",-1,[]),

obj("Выбор.Варианты",-1,[]),

obj("Рынки.Функционирование",-1,[]),

obj("Модель",-1,[]),

obj("Теории",-1,[]),

obj("Спрос.Совершенно эласт",-1,[]),

obj("Предпринимательство",-1,[]),

obj("Монополия",-1,[]),

obj("Издержки.На кратко и долгоср",-1,[])],

obj("Конкуренция.Совершенная",1,[]),

obj("Прайс-тейкеры",1,[])])

chng("Г8 Теор монополии",

obj("Фиаско.Рынка",-1,[]),

obj("Налогообложение.Структура",-1,[]),

obj("рента.Поиск",-1,[]),

obj("Излишки.Потребителя",-1,[]),

obj("Излишки.Производителя",-1,[])],

obj("Теории.Монополии",1,[]),

obj("Ценообразование.Лимитирующее",1,[]),

obj("Монополия.Виды.Естественная",1,[]),

obj("Монополия.Виды",1,[])])

chng("Г9 Орг.пр-сти",

obj("Налогообложение.Структура",-1,[]),

obj("Ценообразование.Лимитирующее",-1,[]),

obj("Излишки.Производителя",-1,[]),

obj("Излишки.Потребителя",-1,[]),

obj("Монополия.Фирмы-монопол",-1,[])],

obj("Индекс.Герфиндаля",1,[])])

chng("Г10 Ценообр на рын рес",

obj("Монополия.Фирмы-монопол",-1,[]),

obj("Теории.Монополии",-1,[]),

obj("Товары.Субституты",-1,[]),

obj("Товары.Комплементы",-1,[]),

obj("Конкуренция.Совершенная",-1,[]),

obj("Предельный продукт.Физический",-1,[]),

obj("Закон.Убывающей доходн",-1,[]),

obj("Доход и эфф замещения",-1,[])],

obj("Теории.Эфф зарплаты",1,[]),

obj("Рынки.Ресурсов (спр/пред)",1,[]),

obj("рента.Поиск политич",1,[]),

obj("Предельный продукт.Денежная форма",1,[])])

chng("Г11 Рынк кап и пр рес",

obj("Налогообложение.Структура",-1,[]),

obj("Налогообложение.Распределение бремени",-1,[]),

obj("Закон.Убывающей доходн",-1,[]),

obj("рента.Инфрамаржинальная",1,[])])

chng("Г12 Фирма",

obj("Экон на масштаб",-1,[]),

obj("Стих порядок",-1,[]),

obj("Рациональность.Ограниченная",-1,[]),

obj("Рациональность.Полная",-1,[]),

obj("Излишки.Потребителя",-1,[]),

obj("Излишки.Производителя",-1,[]),

obj("Иерархии",-1,[])],

obj("Затраты.Непроизводственные*",1,[]),

obj("Стимулы.Мощные",1,[])])

chng("Г13 Экон инф и неопр",

obj("Экономика.Невозобн ресурсов",-1,[]),

obj("Уменьш пред полез",-1,[]),

obj("Конкуренция.Совершенная",-1,[]),

obj("Затраты.Непроизводственные",-1,[])],

obj("Риск.Предпочтение",1,[]),

obj("Информация.Ассимметричная",1,[])])

chng("Г15 Теор общест выб",

obj("рента.Поиск политич",-1,[]),

obj("Общественные блага",-1,[]),

obj("Эффект.Дохода",1,[]),

obj("Теории.Общест выбора*",1,[]),

obj("Модель.Усредненного избир",1,[])])