Потоковый анализ программ, управляемый знаниями

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

Необходимость выполнения откатов предопределяет наличие в орграфе 0(У,Б) трех подмножеств дуг Б = и 02 и 03: - прямые связи между смежными вершинами (рис. 2); -ближние обратные связи между смежными вершинами; Б3 - дальние обратные связи между вершинами, которые не являются смежными, то есть между ними отсутствуют прямые связи, но существует опосредствованная информационная связь.

Перегруженность орграфа 0(У,Б) дугами приводит к увеличению накладных расходов при его формировании, хранении и обработке. Например, проектная процедура ПП9 (рис. 2) при трех прямых связях (ПП6-ПП9, ПП7-ПП9, ПП8-ПП9) имеет соответственно три ближних (ПП9-ПП6, ПП9-ПП7, ПП9-ПП8) и пять дальних (ПП9-ПП5, ПП9-ПП3, ПП9-ПП4, ПП9-ПП2, ПП9-ПП!) обратных связей.

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

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

кальная монитор-ная система (ЛМС), центральная информационная система (ЦИС) и центральный архив проектных решений (ЦАПР) САПР (рис. 3).

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

Для реализации информационного взаимодействия в рамках рассматриваемой инфраструктуры разработан комплекс высокоуровневых синхронных протоколов обмена. Необходимо отметить, что обмен информационными контейнерами между проектирующими подсистемами осуществляется опосредствованно, по запросу соответствующей ЛМС к ЦМС; последняя, в свою очередь, реализует запрос к ЦИС, которая является централизованным хранилищем контейнеров с проектными решениями, выработанными проектными процедурами. Аналогичный протокол используется для организации взаимодействия информационной и архивной систем. В частности, проектные решения завершенных проектов по соответствующим запросам могут быть переданы из ЦИС в ЦАПР или, наоборот, извлечены из него и помещены в ЦИС для последующей передачи в затребовавшую их проектную процедуру.

Рис. 3 Логическая звездообразная структура информационной инфраструктуры САПР

ПОТОКОВЫЙ АНАЛИЗ ПРОГРАММ, УПРАВЛЯЕМЫЙ ЗНАНИЯМИ

М.А. Князева, Д.А. Волков

Основной проблемой в сфере науки о преобразованиях программ является невозможность своевременно выполнять компьютерные экспери-

менты. Цель таких экспериментов - определить, насколько часто в реальных программах применимы те или иные преобразования, какой эффект

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

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

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

В работе А. С. Клещева и М.А. Князевой «Управление информацией о преобразованиях программ. I. Анализ проблем и пути их решения на основе методов искусственного интеллекта» (2005) для решения научных, практических и образовательных проблем в области преобразования программ, была предложена концепция управления информацией о преобразованиях программ в рамках Специализированного банка знаний о преобразованиях программ (СБкЗ_ПП).

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

В процессе потокового анализа происходит извлечение определенных семантических свойств программы. Традиционно потоковый анализ раз-

деляют на анализ потока управления и анализ потока данных.

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

Рассмотрим архитектуру и контекст подсистемы потокового анализа, управляемого знаниями, в рамках системы преобразований программ СБкЗ_ПП.

Входной информацией подсистемы потокового анализа, управляемого знаниями в системе преобразований программ, являются: модель структурной программы (МСП), методы потокового анализа и задание на потоковый анализ программ. Входная информация формируется подсистемой управления СБкЗ_ПП, которая осуществляет взаимодействие с редакторами и передает управление подсистеме потокового анализа. На выходе подсистемы формируется МСП, расширенная терминами потокового анализа программ.

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

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

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

База методов потокового анализа формируется экспертом предметной области. При помощи редактора методов потокового анализа (МПА) пользователи системы пополняют и модифицируют базу МПА. Для описания МПА разработан язык описания МПА.

При разработке языка для записи МПА были проанализированы основные формы записи МПА, описанные в литературе. Язык описания МПА содержит:

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

• основные конструкции алгоритмических языков программирования (цикл, выбор, присваивание);

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

• операции обходов деревьев и операции с древовидными структурами.

Рассмотрим пример представления МПА в базе методов потокового анализа. Неформально метод задан следующим образом: необходимо скопировать аргументные множества всех фрагментов программы в результатные. Аргументное множество есть множество переменных, значение которых могут повлиять на выполнение какого-либо оператора в программе, а результатное -множество переменных, на которые может повлиять выполнение оператора. Информация об аргументных множествах операторов используется в оптимизирующих преобразованиях «удаление неиспользуемых переменных», «вынос инвариантного оператора из цикла» и прочих. Метод_потокового_анализа

Тип-фрагмент: Текущий_фрагмент;

Тип-атрибут: Временный_атрибут;

{

Дерево_обхода_программы(Функция_Главная;

Текущий_фрагмент;Класс_фрагмента(Теьущий_фрагмент)==

Присваивание){

Атрибут_фрагмента(Текущий_фрагмент;

Аргументное_множество; Временный_атрибут);

Создание_атрибута(Текущий_фрагмент;

Результатное_множество; Временный_атрибут);

}

}

Первая строка метода имеет следующий вид:

Метод_потокового_анализа

Описание метода на языке методов МПА начинается с ключевого слова Метод _потоково-го_анализа, за которым в круглых скобках указывается название метода.

Далее следует раздел описания переменных:

Тип-фрагмент: Текущий_фрагмент;

Тип-атрибут: Временный_атрибут;

В данном примере описано две переменных: первая имеет тип Тип-фрагмент и называется Текущий _фрагмент, вторая, Тип-атрибут, называется Временный_атрибут. Тип переменной Тип-фрагмент обозначает, что данная переменная может в качестве значения принимать ссылку на фрагмент конкретной программы на МСП или на объект, находящийся в памяти, который отображает все свойства фрагмента МСП. Описание переменных разных типов разделяются точкой с запятой. Если есть описание нескольких переменных одного типа, их перечисляют через запятую.

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

последовательности конструкций: {

Дерево_обхода_программы(...) {

Атрибут_фрагмента(...);

Создание_атрибута(...);

}

}

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

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

Дерево_обхода_программы(Функция_Главная;

Текущий_фрагмент; Класс_фрагмента(Текущий_фрагмент) ==

Присваивание) {

}

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

Конструкция Атрибут_фрагмента называется формулой:

Атрибут_фрагмента(Текущий_фрагмент, Аргументное_множество, Временный_атрибут);

По сути Атрибут_фрагмента есть функция с тремя аргументами. Данная формула для заданного фрагмента возвращает атрибут с заданным именем. Первый аргумент - это фрагмент МСП, на который ссылается переменная Теку-щий_фрагмент. Второй аргумент - название атрибута МСП, который необходимо получить. Третий аргумент - переменная типа Тип-атрибут которая является результатом и принимает значение ссылки на заданный атрибут фрагмента Теку-щий_фрагмент.

Создание_фрагмента, как и Атрибут_фраг-мента, является формулой:

Создание_атрибута(Текущий_фрагмент, Результатное_множество, Временный_атрибут);

Атрибут_фрагмента имеет три аргумента. Данная функция для заданного фрагмента создает атрибут с заданным названием и значением. Первый аргумент - это фрагмент МСП, на который ссылается переменная Текущий_фрагмент. Второй аргумент - название атрибута МСП, который необходимо создать, в данном случае - Результатное _множество. Третий аргумент - перемен-

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

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

лиза, управляемого знаниями, разработана подсистема потокового анализа в рамках системы преобразований программ в СБкЗ_ПП. Система реализована в среде программирования Java Intel-liJ Idea с использованием ресурсов многоцелевого банка знаний (http://www.iacp.dvo.ru/es/mpk-bank).

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ОБУЧАЮЩЕЙ СИСТЕМЫ НА ОСНОВЕ АДАПТИВНОЙ МОДЕЛИ ОБУЧЕНИЯ

С.К. Дулин, А.В. Репьев

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

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

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

АОС можно классифицировать с точки зрения ресурса адаптации и предмета адаптации.

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

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

Адаптивная модель обучения

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

обучаемого. Наиболее распространенным способом проверки является тест. При наличии адаптации к уровню знания обучаемого процесс взаимодействия с обучаемым выглядит следующим образом. Пусть имеется множество заданий Т по некоторой предметной области (1=1, ... ЭД. Каждое задание имеет определенный уровень сложности р1. Тестирование обычно начинается с задания средней сложности. Если обучаемый правильно отвечает на тестовое задание, сложность следующего задания повышается, если неправильно - понижается. Тестирование заканчивается, когда обучаемый выходит на некоторый постоянный уровень сложности, например, отвечает на некоторое критическое количество вопросов одного уровня сложности.

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

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

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