Содержание к диссертации
Введение
1. основные положения проблематики управления рисками. анализ состава и свойств задачи оценки рисков в интеллектуальных системах поддержки принятия решений . 12
1.1. Основные понятия проблематики управления рисками 12
1.2. Анализ особенностей решения задач управления рисками 14
1.3. Классификация рисков 17
1.4. Анализ существующих моделей, методов и технологий распознавания и оценки рисков 21
1.4.1. Анализ вероятностных моделей распознавания и оценки рисков 22
1.4.2. Анализ структурных методов распознавания и оценки рисков 24
1.4.3. Комбинированные методы распознавания и оценки рисков 29
1.4.4. Сравнительный анализ моделей и методов распознавания и оценки рисков 31
1.5. Обоснование роли и места подсистемы оценки рисков в общей структуре типовой СППР и определение внешнесистемных требований к данной подсистеме 34
1.5.1. Постановка проблемы 34
1.5.2. Особенности СППР, применяемых для решения задач управления рисками 35
1.6. Сущность предлагаемого подхода к распознаванию и оценке рисков 42
Выводы 43
2. Иерархические продукционные системы как генераторы процессов распознавания и оценки рисков в автоматизированных системах управления 46
2.1. Формальная постановка задачи оценки рисков в автоматизированных системах управления 46
2.2. Обоснование целесообразности продукционного подхода к задаче оценки рисков 48
2.3. Анализ основных подходов и принципов создания перспективных систем продукционного вывода для оценки рисков 51
2.4. Иерархические продукционные системы. Базовые определения 54
2.4.1. Состав продукционной системы 55
2.4.2. Ограничения традиционных схем управления продукциями 56
2.4.3. Формализация задачи обработки рисков 59
2.4.4. Терминологический аппарат продукционных вычислений для обработки рисков 63
2.5. Разработка иерархических продукционных систем для оценки рисков 68
2.5.1. Иерархические продукционные системы как формальная основа разработки моделей процессов оценки рисков. Основные понятия и определения 68
2.5.2. Типовые продукционные модели процессов оценки рисков для заданных предметных областей на основе иерархических продукционных систем 72
2.5.3. Особенности применения иерархических продукционных систем для описания (моделирования) сложноструктурированных рисков для служб безопасности банковских структур 74
2.6. Разработка концептуальной модели процессов оценки рисков на основе продукционной парадигмы 80
Выводы 84
3. Методы и алгоритмы синтаксического анализа и оценки рисков 85
3.1. Разработка методов предобработки сложноструктурированных факторов на основе методов продукционного вывода 85
3.2. Общие принципы продукционного вывода в ИПС 86
3.3. Основные особенности детерминированного нисходящего процедурного вывода 92
3.4. Детерминированный восходящий ПВ для ИПС 96
3.5. Особенности синтаксического анализа LR (к) -ИПС 97
3.6. Эффективные процедурные выводы сверху- вниз и снизу- вверх 99
3.7. Иерархические продукционные системы с предшествованием с расширенным предшествованием и их продукционный анализ 103
3.8. Продукционный вывод в ИПС для анализа бесконтекстных программных языков 105
3.9. Стохастический анализ бесконтекстных программных языков 107
Выводы 109
4. Программная реализация и экспериментальная проверка подсистемы распознавания и оценки рисков 115
4.1. Разработка типовой иерархической структуры органов управления инновационной корпорацией 115
4.2. Разработка структурно-функциональной организации системы продукционного вывода для оценки рисков 119
4.3. Определение перечня типовых задач, решаемых программой продукционного вывода для оценки рисков 124
4.4. Структура программной среды PRODUCTION для оценки рисков в перспективных автоматизированных системах управления 127
4.4.1. Основные компоненты специального программного обеспечения PRODUCTION 128
4.4.2. Особенности программной оболочки системы продукционного вывода для оценки рисков в системах управления инновационных предприятий 130
4.5. Механизм моделирования в СПО 131
4.6. Основные результаты экспериментальных исследований программно оболочки для оценки рисков в автоматизированной системе управления 133
Выводы 139
Заключение 141
Список использованных источников
- Классификация рисков
- Анализ структурных методов распознавания и оценки рисков
- Анализ основных подходов и принципов создания перспективных систем продукционного вывода для оценки рисков
- Основные особенности детерминированного нисходящего процедурного вывода
Введение к работе
Актуальность работы.
Подготовка и выполнение управленческих решений для широкого круга информационно-аналитических задач в современных социально-экономических объектах (инновационные корпорации, банки, службы информационно-технической безопасности, информационно-аналитические центры содействия и координации и др.) осуществляется в условиях неопределенности множества информационных, организационно-технических, финансово-экономических, природно-климатических, демографических, социальных и других факторов, совместно имеющих противоречивую семантику и сложную организацию взаимосвязей. Разнородный по составу, связям, выполняемым функциям и структурно-сложный характер организации управляемых объектов предъявляет комплекс повышенных требований к автоматизированным системам управления: компактность и простота структурной модификации, сочетаемые с требованиями оперативности принятия решений, полноты анализа ситуаций, достоверности принимаемых решений.
Наибольший интерес представляет деятельность инновационных корпораций, планирующих и реализующих инвестиционные проекты различного объема и назначения в условиях неопределенности и рисков. Неопределенность и неоднозначность в планировании и реализации бизнес-процессов, являются неотъемлемыми его факторами, которые должны рассматриваться как объективно существующие особенности (для крупных инновационных корпораций число рисков может достигать 800-900), сопутствующие проекту и способные оказать значительное как отрицательное, так и положительное влияние на его реализацию. Выполнение в этих условиях повышенных требований к уровню эффективности и качества принимаемых решений может быть достигнуто путем внедрения в автоматизированные системы управления (СУ) эффективных методов распознавания и оценки сложноструктурированных рисков (ССР) и перспективных технологий распределенной обработки на их основе.
Анализ известных подходов и методов решения задач формального описа
ния (моделирования) ССР показал, что в настоящее время не создано методологи
ческих и ре'ализационных основ решения задач распознавания и оценки ССР в ди
намично-меняющейся обстановке, позволяющих специфицировать все основные
синтаксические и семантические отношения, в полной мере обеспечить выполне
ние современных повышенных требований к рассматриваемому классу систем
/ управления. Формальные описания и модели анализа получаются громоздкими,
затруднена их разработка и модификация, большинство известных методов не оснащено эффективными процедурами структурного, прежде всего синтаксического, анализа сложноструктурированных рисков.
Устранение выявленного объективного противоречия возможно путем создания перспективных автоматизированных подсистем распознавания и оценки ССР на основе обобщения и развития аппарата продукций, позволяющих повысить эффективность решения задач рассматриваемого класса.
В связи с этим решение научно-технической задачи создания систем продукционного вывода для распознавания и оценки сложноструктурированных рисков в автоматизированных СУ в динамично-меняющейся обстановке'является ак-" туальным и представляет несомненный практический интерес. Работа выполня-
лась в рамках плановой НИР: «Исследование научно-технических путей создания систем продукционного вывода для оценки рисков в автоматизированных системах управления» (шифр «Продукция-К», 2006 г.).
V Цель исследований - повышение оперативности распознавания и оценки ССР на основе создания научно-технических основ их распознавания и оценки в рамках предложенного и развиваемого иерархического продукционного похода.
Объектом исследования являются автоматизированная подсистема управления рисками в динамично-меняющейся обстановке и процессы распознавания сложноструктурированных данных.
Предмет исследования — методы и алгоритмы структурно-лингвистического анализа и оценки сложноструктурированных рисков.
Достижение поставленной цели определяется решением следующих частных задач исследования:
-
Анализ социально-экономических и научно-технических предпосылок решения задач управления рисками в современных системах поддержки принятия решений. Определение ограничений существующих методов распознавания и оценки ССР в динамично меняющейся обстановке.
-
Обоснование продукционного подхода к решению задачи управления сложноструктурированными рисками и разработка иерархической продукционной системы (ИПС) обработки ССР.
-
Разработка методов и алгоритмов синтаксического анализа в ИПС - как процедурной основы структурного распознавания ССР в динамично меняющейся обстановке.
-
Разработка структурно-функциональной организации подсистемы распознавания и оценки рисков, реализующей предложенные методы.
-
Экспериментальная проверка предложенных методов и алгоритмов распознавания и оценки ССР, а также проверка их эффективности для типовых социально-экономических объектов.
Методы и математический аппарат исследования. При проведении исследований использовались методы распознавания и оценки рисков, искусственного интеллекта, структурной лингвистики, распознавания образов, теории сложных информационно-технических систем, формальных грамматик и грамматических структур, обработки информации.
Научная новизна работы состоит в следующем:
-
Разработано теоретико-множественное описание задачи распознавания и оценки рисков, отличительной особенностью которого является системное объединения необходимых элементов и видов процессов обработки рисков с учетом структурно-лингвистической и вероятностной компонент. Выполнена расширительная модификация структуры продукции путем добавления пред- и постусловий количественной обработки индикаторов рисков в динамично меняющейся обстановке.
-
Синтезирован класс иерархических продукционных систем (ИПС), отличающийся введением дополнительных иерархических продукционных правил связи известных продукционных систем (ПС) в единую систему, что позволяет синтезировать более представительный по дескриптивным возможностям и одновре-
менно компактный класс иерархически связанных ПС, ориентированных на решение более широкого класса прикладных задач управления рисками.
-
Разработаны методы и алгоритмы неполного синтаксического анализа «сверху вниз» и «снизу вверх», обеспечивающие эффективное по временной сложности обнаружение структурно сложных рисков на основе вычисления вероятностных характеристик продукций и анализируемых риск-ситуаций и определяющие тем самым повышение оперативности обработки.
-
Разработана структурно-функциональная организация (СФО) подсистемы обработки рисков, содержащая четыре уровня и позволяющая совмещать во времени процессы измерения, предобработки и генерации дерева вывода итоговых ССР под значимые индикаторы риска. Отличительной особенностью данной СФО является введение в нее модифицированной машины продукционного вывода для ИПС, обеспечивающей генерацию вариантов по выделенным стратам в соответствии с заложенными в ИПС иерархическими продукционными правилами.
Практическая ценность работы состоит в создании инженерно-технической базы для разработки перспективных программных средств и информационных технологий распознавания и обработки ССР в динамично меняющейся обстановке. При этом получены следующие практически значимые результаты:
разработанная СФО подсистемы обработки рисков обеспечивает обоснованное уменьшение затрат и финансовых средств при учете наиболее значимых рисков;
сокращены временные затраты на решение задачи распознавания и оценки рисков за счет четырех уровневой конвейерной организации СФО, позволяющей совместить этапы предобработки, принятия и реализации решений по учету и противодействию возникающим ССР в динамично меняющейся обстановке.
Защищаемые положения.
-
Иерархические продукционные системы, отличительными особенностями которых являются дополнительно введенные правила связи, задающие номенклатуру и порядок взаимодействия регулярных и контекстно-свободных систем, входящих в ИПС, а также стратификация ИПС на синтаксически самостоятельные уровни, что, в целом, обеспечивает повышение оперативности обработки ССР.
-
Методы и алгоритмы неполного синтаксического анализа ССР, ориентированные на использование предложенного класса ИПС и отличающиеся использованием стохастических правил, которые в комбинации с вероятностными мерами оценки пути в дереве вывода позволяют досрочно обнаруживать структурно сложные значимые риски.
-
Структурно-функциональная организация подсистемы распознавания и оценки ССР, отличительной особенностью которой является введение и использование модифицированной машины продукционного вывода для ИПС, допускающей модификацию состава и связей правил в процессе генерации решений, что позволяет существенно сократить затраты на поиск, оценку и противодействие возникающим рискам.
Реализация и внедрение результатов исследования. Результаты теоретических и экспериментальных исследований внедрены в Главном управлении информационно-коммуникационных технологий и безопасности информации Администрации Курской области, в ОАО «Геомаш» (г. Щигры), в ОАО «Кореневский завод НВА». Внедрение подтвердило повышение оперативности и достоверности реше-'
ния задач управления рисками в человеко-машинных системах поддержки решений для различных экономических объектов.
Результаты, полученные в диссертационной работе, внедрены в учебный процесс Курского государственного технического университета.
Апробация и публикации. Основные положения диссертационной работы докладывались и получили положительную оценку на 3-х Международных конференциях: «Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий» (г. Сочи, 2005 г.), «Современные инструментальные системы, информационные технологии и инновации» (г. Курск, 2004 г., г. Курск, 2005 г.); на Российском форуме «Проблемы развития инновационной деятельности в современных условиях» (г. Курск, 2006 г.) и семинарах кафедр КиТ ЭВС и ПО ВТ Курского государственного технического университета. По теме диссертации опубликовано 9 печатных работ, в том числе 2 статьи по перечню центральных рецензируемых журналов и изданий ВАК, а также один итоговый отчет о НИР.
Личный вклад автора. В работах, опубликованных в соавторстве, лично соискателем разработана структурно-функциональная организация подсистемы распознавания и оценки рисков [1.41. создан аппарат иерархических продукционных систем [2,3,6,9], разработаны методы и алгоритмы синтаксического анализа и оценки сложноструктурированных данных [3,5,7,8].
Структура и объем работы. Диссертация состоит из введения, четырех разделов, заключения, приложений, списка использованной литературы (71 наименование). Текст диссертации включает 167 страниц, из них 152 страницы основного текста, 29 рисунков, 6 таблиц.
Классификация рисков
Одним из решений задачи управления рисками при планировании бизнес-процессов и распределении ресурсов инновационного проекта является применение систем моделирования и анализа процессов, поддерживающих функции описания риска, что связано с выявлением общих свойств рисков по различным предметным областям и составлению классификации рисков. В таблице 1.1 приведена классификация рисков.
Анализ существующих видов риска, сопоставление затрат на противодействие возникающим рискам показывает, что в различных системах реального уровня сложности допустимые уровни рисков значительно варьируются в диапазоне 1-Ю 000 условных единиц. Основная причина значительного варьирования заключается в особенности субъективного восприятия риска и, как следствие, субъективного понимания допустимого уровня. Обзор рисков в различных предметных областях: страховые риски, риски в строительстве, экологические риски, финансовые риски, риски в здравоохранении, информационные риски, риски в энергетических системах и др- показывает, что на уровень допустимой оценки риска влияют такие факторы как степень обязательности действий со стороны ЛПР (распознающего риск), степень контроля ситуации, степень новизны технологии, оценка масштаба возможных неблагоприятных событий, распределение рисков по времени выполнения процессов, интенсивность выполнения процессов. Таким образом, определение допустимого уровня риска связано с выделением первичных (непроизводных) индикаторов риска, которые могут быть определены только с учетом индивидуальных технических, экономических, социальных факторов.
По мнению экспертов переход риска в негативное событие начинается с накопления ряда отклонений. Затем следует некоторое инициирующее событие, связанное с неправильным управляющим воздействием со стороны ЛПР. Подобные ошибки являются следствием того, что ЛПР не имеет исчерпывающих знаний о функционировании сложного объекта. Вследствие этого возникающие отклонения не получают должной оценки. С другой стороны, ряд отклонений имеют временный, локальный характер, не оказывающий системного влияния на функционирование объекта. В связи с этим в функционировании объекта реального уровня сложности выделяют следующие результирующие состояния системы распознавания и управления рисками: ? «ложная тревога» - проявления рисков несущественно: индикаторы рисков одиночны (не превышают допустимый порог), несущественны, носят кратковременный характер или взаимно компенсируются, т.е. обычный режим функционирования объекта; ? «локальная опасность» - локальный контроль рисков - количество индикаторов рисков превышают порог или идет внутригрупповое накопление рисков, т.е. режим локального контроля деятельности подразделения по особым решениям руководства и т.д. «глобальная опасность» индикаторы рисков образуют межгрупповые структурно-подчиненные связи, что приводит к мультипликативному (общесистемному) итоговому риску, т.е. чрезвычайный режим управления, применяемый по отношению ко всему объекту. Управление рисками в режимах «локальная опасность», «глобальная опасность» основывается на использовании предварительно разработанных сценариев поведения, что позволяет уменьшить затраты времени на принятие управленческих решений. По мнению ведущих отечественных и зарубежных ученых, первичными количественными показателями индикаторов риска, ,. соотносящимися с большинством социально-экономических, организационно-технических систем, являются: 1. источник риска; 2. плотность вероятности распределения риска; 3. вес риска; 4. стоимость риска.
Задача анализа и последующей оценки рисков определяется формализованной моделью предметной области. Номенклатура существующих методов оценки риска включает качественные, количественные, структурно-логические, комбинированные методы, эффективно применимые для различных социально-экономических объектов. На рис. 1.1 приведена классификация методов оценки риска.
Анализ структурных методов распознавания и оценки рисков
В сводной таблице 1.3 приведены характеристики оценок риска в зависимости от предметной области.
Обзор существующих традиционных методов и технологий оценки рисков показывает, что большинство из них непосредственно или косвенно использует вероятностный подход. Это соответствует международным стандартам, но по признанию экспертов является трудоемким процессом, так как требует поиска и привлечения разнородной количественной информации, что не всегда возможно. Поэтому реальные методики оценки риска в подавляющем большинстве случаев основаны на упрощении процессов измерения первичных данных, т.е. потери определенной информации о рисках в силу ее слабой структурированности, неполной формализуемости, противоречивости.
Важнейшими факторами упрощения вероятностных моделей являются: 1. Структурное упрощение - каждой группе индикаторов директивно ставится в соответствие некоторый индикатор-образец—один из представителей группы или некий усредненный индикатор. Считается, что остальные индикаторы группы коррелируют более или менее синхронно с индикатором-образцом.
2. Трактовка индикаторов риска как случайных величин с наперед заданной плотностью распределения вероятности (нормальный закон). Вместе с тем нестационарность экономических, политических, социальных процессов приводит к искажениям плотности распределения. Данное противоречие требует решения дополнительной задачи восстановления плотности распределения вероятности, адекватной реальным процессам, что не всегда возможно.
3. Эффект сглаживания: индикаторы рисков с катастрофическими последствиями, но с низкой вероятностью, рассматриваются наравне с индикаторами с незначительными последствиями, но с высокой вероятностью. Это обусловлено тем, что простой (неструктурный) риск рассчитывается как произведение вероятности индикатора и оцененного последствия. Сглаживание может приводить на различных уровнях организационных мер противодействия рискам к неадекватным решениям. Требуется формализм разграничения таких индикаторов и «прозрачность» мер противодействия различным типам рисков.
Вывод: вероятностные модели и используемые допущения эффективно применимы для оценки рисков при небольшом количестве учитываемых индикаторов. Причем индикаторы, как правило, обособлены или имеют непосредственное, легко учитываемое влияние. Структурно-подчиненные связи между индикаторами не имеют успешной вероятностной оценки.
Функционрование инновационной корпорации, с одной стороны, базируется на вполне формализуемых предположениях относительно капитальных и текущих затрат, объемах ресурсов, предполагаемых объемах реализации произведенной продукции, цен на товары, сценарных рамок работ проекта, интенсивностей выполнения бизнес-процессов и др. С другой стороны, деятельность характеризуется множеством слабоформализуемых факторов, подвергающих бизнес-процессы проекта различным рискам, что придает проекту многовариантный характер исполнения в виде генерации множества возможных альтернатив, их оценке и выбору со стороны ЛПР лучшей альтернативы или группы альтернатив.
Суть мероприятий по распознаванию и оценке рисков состоит в том, чтобы оценить их размер, выработать адекватные экономичные меры снижения рисков, проконтролировать нахождение рисков в допустимом коридоре значений. Исходя из этого, задача управления рисками включает циклически чередующихся два вида деятельности: (пере)оценка (измерение) рисков; выбор адекватных экономичных мер противодействия (нейтрализация рисков).
Важность решения задачи управления рисками объекта определяется необходимостью постоянного перераспределения ресурсов (финансовых, трудовых, оборудование и др.) под меняющиеся показатели по мере реализации проекта или временного функционирования системы. Таким образом, межэтапные возвратные временные циклы в общей процедуре управления рисками, динамическое перераспределение ресурсов, необходимость выделения дополнительных затрат на оценку рисков, V разработка специализированных стратегий поиска решения придают данной научно-технической задаче свойство эмерджентности. Возникающий синергетический эффект позволяет обособленно рассматривать риски как самостоятельную сущность, имеющую устойчивые связи и определенный состав элементов. В связи с этим в типовой структуре системы поддержки принятия решений (СППР) с необходимостью должна выделяться подсистема управления рисками, обеспечивающая динамический учет возникающих рисков, оценку их важности и выработки мер по противодействию им. Вместе с тем к подсистеме управления рисками предъявляются требования компактности состава, легкой модифицируемости, оперативности работы. Другими словами, роль подсистемы распознавания и оценки рисков заключается в осуществлении «сторожевых» функций проекта с обоснованно минимальными затратами на них. Таким образом, концептуальный обзор требований к подсистеме распознавания и оценки рисков определил комплекс противоречивых внешнесистемных требований к ней. С одной стороны, данная подсистема должна быть «прозрачна» в общем цикле планирования и управления проектом в штатных ситуациях. С другой стороны, в нештатной ситуации (риск-событие) подсистема должна взять управление проектом на себя и осуществлять последнее до тех пор, пока не исчезнет воздействие риска.
Анализ основных подходов и принципов создания перспективных систем продукционного вывода для оценки рисков
Термин «продукция» введен американским логиком Э. Постом. В понимании Поста в качестве продукции выступала только та ее часть, которую теперь называют ядром. Запись «ЕСЛИ А, ТО В» трактовалась как оператор замены цепочки А цепочкой В в некотором входном слове, т. е. продукции были тем, что позже стали именовать подстановками и использовать при описании различных уточнений понятия алгоритма. Например, подстановки являются основным оператором в нормальных алгоритмах Маркова. Поэтому в языке программирования Рефал, основанном на идее такой модели уточнения понятия алгоритма, оператор подстановки играет основную роль. Идея продукции используется в языках логического программирования, нашедших применение в ИС. Среди языков подобного типа наиболее известен Пролог. Продукционный подход стал стилем нового этапа программирования.
В общем виде под продукцией понимается выражение следующего вида: (i); Q; Р, А- В; N (2.1). В выражении (2.1) і — имя продукции, с помощью которого данная продукция выделяется из всего множества продукций. В качества имени может выступать некоторая лексема, отражающая суть данной продукции (например, «покупка книги» или «набор кода замка»), или порядковый номер продукции в их множестве, хранящемся в памяти системы. Элемент Q характеризует сферу применения продукции. Такие сферы легко выделяются в когнитивных структурах человека. Наши знания как бы «разложены по по
лочкам». На одной «полочке» хранятся знания о том, как надо готовить пищу, на другой — как добраться до работы и т. п. Разделение знаний на отдельные сферы позволяет экономить время на поиски нужных знаний. Такое же разделение на сферы в базе знаний ИС целесообразно и при использовании для представления знаний продукционных моделей.
Основным элементом продукции является ее ядро: А- В. Интерпретация ядра продукции может быть различной и зависит от того, что стоит слева и справа от знака секвенции «—». Обычное прочтение ядра продукции выглядит так: ЕСЛИ А, ТО В, более сложные конструкции ядра допускают в правой части альтернативный выбор, например, ЕСЛИ А, ТО В і, ИНАЧЕ В2. Секвенция может истолковываться в обычном логическом смысле как знак логического следования В из истинного А (если А не является истинным выражением, го о В ничего сказать нельзя). Возможны и другие интерпретации ядра продукции, например А описывает некоторое условие, необходимое для того, чтобы можно было совершить действие В.
Элемент Р есть условие применимости ядра продукции. Обычно Р представляет собой логическое выражение (как правило, предикат). Когда Р принимает значение «истина», ядро продукции активизируется. Если Р ложно, то ядро продукции не может быть использовано.
Элемент N описывает постусловия продукции. Они актуализируются только в том случае, если ядро продукции реализовалось. Постусловия продукции описывают действия и процедуры, которые необходимо выполнить после реализации В.
Ограничения традиционных схем управления продукциями.
В состав системы продукций с необходимостью должна входить подсистема (схема) управления. Дело в том, что для продукций с недетерминированным характером их срабатывания, в общем случае, формируется некоторое конфликтное множество продукций, подлежащих выполнению. При этом возникает проблема выбора из конфликтного множества продукций таких, которые будут активизированы в текущий момент. Данная проблема имеет прежде всего ресурсное ограничение. Если ИС реализована на ЭВМ с параллельной архитектурой, то из конфликтного множества продукций может выбираться не одна, а столько продукций, сколько параллельных процессов, т.е. ветвей в дереве решений, может выполнять ЭВМ, вместе с тем проблема альтернативного выбора остается.
В общем случае задача управления характерна не только для систем продукций, но и для всех систем, где необходимо выполнение параллельных процессов с учетом технического ресурса. Возможны два пути ее решения: централизованный и децентрализованный. В первом случае выбор осуществляется специальной СУ, в при децентрализованном - текущей ситуацией. Если порядок выполнения продукций произволен, то решение определяется текущей ситуацией или системой управления. Если порядок выполнения продукций из конфликтного множества важен, то в составе продукций должна содержаться информация о требованиях к этому порядку. Традиционные стратегии управления выполнением продукций:
1. принцип «стопки книг», заключающийся в адаптации системы продукции к внешним условиям путем, например, подсчета частоты использования продукций с ее положительной оценкой применимости;
2. принцип наиболее «длинного» образца, заключающийся в эвристическом выборе из конфликтного множества такой продукции, у которой левая часть наиболее длинная;
3. принцип метапродукций, заключающийся во введении служебных продукций, которые должны обрабатывая конфликтное множество, выбирать приоритетную продукцию;
4. принцип «классной доски», основанный на выделении общей рабочей области памяти для записи в нее временной информации о результатах и условиях срабатывания продукций в предыдущих ситуациях;
5. принцип приоритетного выбора, связанный с введением статических или динамических приоритетов над продукциями. Статические приоритеты формируются, как правило, экспертами.
Основные особенности детерминированного нисходящего процедурного вывода
ПВ называют детерминированным, если он может быть реализован с помощью детерминированного МП-преобразователя. МП-преобразователь называется детерминированным, если для любой комбинации входного символа, внутреннего состояния преобразователя и верхнего магазинного символа функция перехода 5 может принимать лишь одно значение.
В случае детерминированного ПВ на каждом шаге анализа однозначно определяется продукция, которую следует применять для разворачивания очередного вспомогательного символа. Однако для того, чтобы сделать этот однозначный выбор, нужно построить для входной КС-ПС таблицу функций ; S(q, а, А) для всех внутренних состояний qeQ, aeVj и AeVfUViUtt, называемую таблицей МП-преобразователя. ПС или ИПС Р будем называть даоее LL(k)-UC или ИПС, если для любой цепочки coAaG(VnUVT) и первых к терминальных символов, выводящихся из подцепочки А а, существует не более одной продукции, которую можно применить к символу А, чтобы получить левый вывод какой либо терминальной цепочки, начинающейся с цепочки со и продолжающейся упомянутыми к терминальными символами.
Пусть входная цепочка языка ЦР) представлена в виде 0=caxyv, где со - уже прочитанная анализатором часть входной цепочки терминальных символов 0, х - текущий входной символ, у - цепочка терминальных символов длиной к-1, v - оставшаяся часть цепочки. Пусть также внутреннее состояние МП-преобразователя характеризуется символом q, а содержимое магазина есть А а, где А - верхний символ магазина. Зная входной символ х и еще к-1 символов входной цепочки 0, можно лишь единственным образом определить продукциюу, которую допустимо использовать для символа А , чтобы, разворачивая далее содержимое магазина Аа, получить терминальную цепочку.
Рассмотрим содержание предложенной модифицированной процедуры ПВ цепочек языка в алфавите терминальных символов VrLL(k)-ИПС S. На рис. 2.8.3.1 изображена схема МП-преобразователя, являющегося функциональным интерпретатором алгоритма нисходящего ПВ в ИПС.
На входной ленте записана цепочка 0=(wcyv=amv с маркером V, указывающим ее правый конец. При выборе такта МП-преобразователя предполагается, что он может "заглядывать" на к символов вперед, включая входной символ х , т.е. при выборе такта ему известна цепочка и=ху. В магазине находится цепочка Аа #, где А - верхний символ магазина. На выходной ленте печатается цепочка ж, символами которой являются номера подстановок, использованных при построении промежуточных деревьев вывода входной цепочки.
Конфигурацию МП-преобразователя (текущее состояние алгоритма ПВ) будем представлять тройкой со, Аа, ж , где co=uv- неиспользованная часть входной цепочки, Аа - содержимое магазина, ж - цепочка на выходной ленте.
Управляющая таблица МП-преобразователя задает отображение М(А, и) из множества (ГЦЩ) в множество Ф, где Г- множество магазинных символов, VT k - множество цепочек в алфавите терминальных символов длиной не более чем к.
Пояснение к процедуре ПВ анализа языка, порождаемого LL(k)-mc Множество Ф содержит элементы четырех типов: 1) (Р, і), РєГ, где і - номер продукции, правой частью которой или некоторым ее представлением является цепочка р; 2) "вытолкнуть"; 3) "допустить"; 4) "ошибка".
Работа МП-преобразователя (алгоритма) на каждом шаге состоит в следующем. Определяются аванцепочка и и верхний магазинный символ А. Опишем возникающие при этом ситуации и отвечающие им действия МП-преобразователя.
1. Если М(А, иНД і), то (со, Аа, я)- (со, Да, п І). Здесь верхний магазинный символ А заменяется цепочкой fi (правой частью /-Й подстановки), а к выходной цепочке добавляется символ /. При этом входная головка МП-преобразователя не сдвигается (множество обозреваемых символов входной цепочки не меняется) .
2. Если М(а, и)="вытолкнуть", a aeVT и со=асо , то (со, аа, п) (со , а, ЇЇ). Иначе говоря, если верхний символ магазина совпадает с первым символом аванцепочки, то этот символ выталкивается из магазина, а входная головка сдвигается на один символ вправо.
3. М(#, F)- допустить". Это отвечает исходной конфигурации с пустым магазином, когда входная цепочка прочитана полностью. Конфигурацию (V, #, ЇЇ) принято называть допускающей.
4. Если М(А, и)="ошибка", то в соответствующей конфигурации (со, А а, ЇЇ) анализ входной цепочки прекращается и выдается сообщение об ошибке. Содержательно это означает, что входная цепочка не принадлежит языку. Начальная конфигурация МП-преобразователя (алгоритма ПВ) имеет вид (со, S #, е), где со- входная цепочка, S - начальный нетерминальный символ, е - пустая цепочка.
Начальную и все промежуточные конфигурации МП-преобразователя можно содержательно интерпретировать как утверждение о том, что из промежуточной цепочки, находящейся в магазине, можно вывести еще неиспользованную часть входной цепочки. Процесс функционирования МП-преобразователя направлен на то, чтобы доказать это утверждение.
Для использования нисходящего детерминированного анализа необходимо показать, что рассматриваемая ИПС принадлежит к классу LL(k), а затем построить управляющую таблицу для соответствующего МП-преобразователя. Для этого можно воспользоваться достаточно простыми, хотя и громоздкими алгоритмами. Подробно они описаны в [15].
Для многих практических задач из области описания рисков, продукционного распознавания ситуаций, представления декларативных и процедурных знаний в задачах построения систем искусственного интеллекта и других оказывается достаточным использование даже более узкого, чем класс LL(k), класса формальных ИПС. В частности, многие задачи решаются применением лишь Ы(1)-ИПС.
Для этого типа ИПС процедура доказательства их принадлежности к классу LL(1), а также построение управляющей таблицы МП-преобразователя, осуществляющего ПВ, достаточно просты, хотя и несколько громоздки. С ними можно в простом изложении познакомиться в работе [10].
