Содержание к диссертации
Введение
1. Обучающие системы контроля знаний и генерации заданий 14
1.1. История создания обучающих систем 14
1.2. Классификация обучающих систем 17
1.3. Обзор обучающих систем 19
1.3.1. Контролирующие системы 20
1.3.2. Генерирующие системы 21
1.4. Архитектура интеллектуальной обучающей системы (ИОС) 23
1.4.1. Общая структура интеллектуальной системы 23
1.4.2. Архитектура экспертной обучающей системы 25
1.5. Модели представление знаний 28
1.6. Декларативный и процедурный подходы к построению ИОС 29
1.6.1. Использование декларативных знаний для контроля знаний учащихся 30
1.6.2. Использование процедурных знаний в инструментарии эксперта 31
1.7. Архитектура интегрированной ИОС 32
1.8. Выводы 33
2. Представление формульных данных и знаний 34
2.1. Представление данных 34
2.1.1. Представление математического содержания формул 34
2.1.2. Вычисление формул 37
2.1.3. Визуальное представление формул 38
2.2. Представление знаний 40
2.2.1. Виды знаний 41
2.2.2. Языки представления знаний 42
2.3. ЯзыкТ-РЕФАЛ 44
2.3.1. Понятие синтаксического отождествления 45
2.3.2. Сопоставление с образцом на деревьях математических выражений 46
2.3.3. Базисный РЕФАЛ 50
2.3.4. Синтаксис Т-РЕФАЛа 55
2.3.5. Семантика Т-РЕФАЛа 56
2.3.6. Т-РЕФАЛ-машина 57
2.3.7. Сравнение РЕФАЛа и Т-РЕФАЛа 60
2.3.8. Области применения Т-РЕФАЛа 65
2.4. Выводы 65
3. Интеллектуальная обучающая система контроля знаний 67
3.1. Методы контроля знаний 67
3.2. Модель ошибок 69
3.3. Каталог ошибок 70
3.4. Сопоставление формул 73
3.4.1. Классы эквивалентности формул 74
3.4.2. Унификация синтаксических ошибок 77
3.4.3. Унификация математических ошибок в Т-РЕФАЛ . 77
3.4.4. Унификация неформализованных ошибок 79
3.5. База знаний ошибок 79
3.6. Интеллектуальный диалог 81
3.7. ИОС контроля знаний по химии 83
3.8. Выводы 85
4. Инструментарий генерации заданий 86
4.1. Классификация методов генерации 86
4.2. Параметрический метод генерации заданий 88
4.2.1. Модель задачи 88
4.2.2. Выделение семейств задач 89
4.2.3. Упрощение формул с помощью Т-РЕФАЛ-предложений 90
4.2.4. Решатель задач 95
4.3. Контроль знаний в генерирующей ИОС 99
4.4. Алгоритм генерации заданий 100
4.5. Применение метода генерации для печатных изданий . 103
4.6. Выводы 104
Заключение 106
Список литературы 109
Приложения 124
- Декларативный и процедурный подходы к построению ИОС
- Сопоставление с образцом на деревьях математических выражений
- Унификация математических ошибок в Т-РЕФАЛ
- Упрощение формул с помощью Т-РЕФАЛ-предложений
Введение к работе
Первый этап исследования возможностей создания обучающих систем приходится на 50-е и 60-е годы двадцатого столетия. В это время американский психолог Б.Ф. Скиннер выдвинул идею, получившую название программированного обучения [81]. Им предлагалось повысить эффективность управления усвоением учебного материала, построив его как последовательную программу подачи порций информации и контроля их усвоения. Это направление начало активно развиваться в США, а потом и в других странах [76]. Автоматизация программированного обучения началась с использования обучающих и контролирующих устройств различного типа в 60-х-70-х годах. А в 80—е годы с появлением и распространением персональных компьютеров началось по—настоящему массовое использование обучающих программ. Таким образом, задача создания автоматизированных систем, призванных обучать без помощи человека, имеет более чем тридцатилетнюю историю.
На сегодняшний день создано огромное количество различных программ учебного назначения по многим предметам, однако, существенного влияния на учебный процесс это не оказывает. Упор в большинстве применяемых компьютерных программ делается на наглядность, которая с помощью компьютера реализуется чрезвычайно эффективно. Но зачастую обучение этим и ограничивается, и такие программы являются, по сути дела, информационными или демонстрационными. Конечно, электронные учебно-методические пособия и средства обучения (иллюстрирован-
ные методические пособия, "Рабочие тетради", "Альбомы", "Виртуальные экскурсии" и др.) могут сыграть и играют весьма значительную роль в совершенствовании процесса обучения. Аудио-визуальное представление информации позволяет существенно расширить возможности преподавания, создает новую коммуникативную среду в отношениях учителя и ученика. При этом охватываются все традиционные формы и выявляются новые возможности и направления: дистанционное обучение (очно-заочное); обучение определенных социальных групп населения (инвалиды, реабилитационные программы и т.п.). Но демонстрационная программа не обеспечивает достаточной эффективности образования. Для обеспечения эффективности учебного процесса автоматизированный учебно-методический комплекс (электронный учебник) должен принципиально отличаться от текстовых учебников и задачников. Одно из таких отличий - возможность обеспечения интерактивности учебника и диалога с обучаемым.
Конечно, ни сегодня, ни в обозримом будущем, ни одна учебная программа не сможет заменить хорошего учителя и традиционный метод обучения и диалог. Но мнение, что учитель, в принципе, может прекрасно обходиться и без привлечения компьютерных средств [25], добиваясь при этом высокой эффективности обучения, ошибочно. Повышение эффективности обучения при использовании качественных обучающих систем было подтверждено рядом исследований [8,32,93], где выделяются следующие позитивные факторы: индивидуализация обучения [112], интенсификация обучения, использование выразительных средств вычислительной техники, таких как наглядность, наличие средств моделирования объектов и процессов и т.п. [14,82], возможность контроля степени усвоения знаний.
Кроме повышения эффективности обучения, внедрение обучающих систем разгружает преподавателя от ряда трудоемких и часто повторяющихся операций по представлению учебной информации и контролю зна-
ний; способствует разработке объективных методов контроля знаний; облегчает накопление учебно - методического опыта. Для этого обучающие программы должны работать вместе с учителем и учитель должен выступать в роли эксперта и передавать компьютеру свои знания, а дальше основную по времени работу должна выполнять программа. Построенная таким образом обучающая система будет представлять собой экспертную систему (ЭС) и являться интеллектуальной в отличие от популярных сегодня интерактивных программ-тестов, которые могут лишь частично моделировать работу учителя но проверке знаний обучаемого [61].
Несмотря на наличие интерактивиости, "директивный характер" таких обучающих программ-тестов с заранее заданным сценарием и обязательным контролем в заранее определенных местах является недостатком, лишающим обучаемого инициативы и накладывающим свои ограничения на ученика. Одним из таких ограничений является выбор ответа только из списка предложенных, Например, в обучающей системе по математике это дает возможность обратной проверки, что нежелательно. Следовательно, ученику следует позволить вводить ответ в произвольной форме (аналогично ответу в тетради), что требует более совершенных программ сопоставления и классификации ответов [66]. При этом,форма ответа (сообщения) пользователя должна быть адаптивна. То есть при вводе ответа ученик должен пользоваться той формой записи, к которой он привык в школе. Адаптивные системы с приспособлением визуальной части системы позволяют легче усвоить изучаемый материал. Еще одно свойство, вкладываемое в адаптивные системы - способность к пополнению базы лингвистических и проблемно - ориентированных знаний в рабочем режиме [62]. Система, обладающая данной возможностью, обеспечивает динамически меняющийся диалог, что положительно отражается на качестве обучения.
Требование адаптивности системы граничит с требованием индивидуально го подхода к ученику, подразумевающим создание каждому ученику индивидуального варианта задания, так как в случае одинаковых задач возникает проблема "списывания". То есть при решении задачи на своем компьютере сильным учеником аналогичное решение будет у всего класса (поскольку обучающая система дает подсказки, советы и сообщает о правильности результата сразу же после ответа на вопрос). Следовательно, при массовом применении электронных учебников в реальном учебном процессе возникает проблема составления индивидуальных заданий для контрольных работ, при этом разные варианты заданий должны быть приблизительно одинакового уровня сложности. Решением данной проблемы может являться метод автоматической генерации заданий, позволяющий сгенерировать личный электронный учебник (персональный задачник).
Такой индивидуальный (диверсифицированный) подход к ученику, предполагающий создание индивидуального варианта задания, реализуется при помощи специализированных систем генерации заданий и собственных программ генерации в развитых системах компьютерной алгебры (Maple, MathCad, MatLab [20,21]). Однако системы компьютерной алгебры во-первых, являются дорогостоящими и закрытыми системами, а во-вторых не ориентированы на интерактивное обучение вследствие отсутствия проверки ответов пользователя и оценивания знаний. В свою очередь, специализированные генераторы не являются существенно интеллектуальными, исключают непосредственное участие преподавателя в составлении вариантов и не дают возможность генерации произвольной задачи.
Учитывая перечисленные недостатки систем, существующие обучающие системы не имеют должного широкого распространения. Состояние современных обучающих систем таково, что на сегодняшний день, как пра-
вило, программы генерации задач и контроля знаний не интегрированы; промышленные обучающие системы не имеют изменяемой базы знаний и исключают влияние преподавателя па процесс обучения, отсутствует конструктивный диалог с обучаемым в процессе тренинга. Обучающие системы, осуществляющие контроль знаний, как правило, представляют собой программы-тесты, в которых присутствует элемент угадывания и существует возможность обратной проверки; не существует широко распространенных систем генерации заданий.
Для устранения указанных недостатков обучающая система должна иметь возможность генерации произвольной интерактивной задачи и обеспечить контроль знаний, основанный на ответе пользователя в произвольной адаптивной форме (в терминах предметной области). Проверка таких ответов обучаемого, считающаяся раньше прерогативой человека, является сегодня задачей систем искусственного интеллекта (ИИ).
При создании таких систем ИИ существует проблема выбора языка программирования. Часто используются языки логического программирования (Prolog). На данных языках легко описываются базы знаний и производится логический вывод. Однако эти языки имеют ряд недостатков: во-первых, они не ориентированы на обучение и определенную предметную область; во-вторых, в данных языках затруднительна реализация интерфейса системы. При этом средства интеграции языков искусственного интеллекта с индустриальными языками и средами (Builder C++, Visual С, Delphi, Java) пока довольно слабые. Поэтому возникает задача разработки специализированного языка ИИ, интегрированного с индустриальным языком и япляющегося языком представления знаний. Данный язык позволит создать существенно интеллектуальную обучающую систему, ориентированную как на диалог с учеником, так и па диалог с преподавателем.
Таким образом, стоит актуальная и практически значимая задача создания полноценной интеллектуальной обучающей системы, обладающей интерактивностью, адаптивностью, индивидуальностью и позволяющей компьютеризировать важнейшие этапы учебного процесса: формирование заданий и контроль знаний. Соответственно этой задаче формулируется цель диссертационной работы - разработка модели интерактивной интеллектуальной обучающей системы по математике, создание языка представлении знаний для данной системы, реализация и внедрение в конкретные обучающие системы инструментальных средств вычисления, сопоставления и преобразования формул, обеспечивающих генерацию задач и интеллектуальный контроль знаний обучаемого.
Для достижения цели были поставлены и решены следующие задачи:
Исследование методов компьютерной алгебры, включая методы представления данных; исследование интеллектуальных систем, фреймового и продукционного представления знаний, прямого и обратного вывода, декларативных языков (Lisp, Prolog, язык нормальных алгоритмов Маркова, РЕФАЛ) с целью применения в обучающей системе по математике.
Разработка архитектуры интеллектуальной обучающей системы, сочетающей в себе инструментарий эксперта для генерации задач и инструментарий ученика для контроля знаний.
Создание специализированного языка представления знаний и соответствующей машины вывода, осуществляющей унификацию (сопоставление с образцом) над деревьями математических выражений.
Реализация алгоритмов визуализации, вычисления, сопоставления и преобразования формул с применением методов компьютерной алгебры и рекурсивею-логического программирования.
Реализация алгоритмов генерации задач на основе прямого логического вывода и создание типовых запросов (скриптов на интерпретируемом языке Java Script) для автоматической генерации задач (обеспечивающих выборку различных и равноценных вариантов) с автоматизированным решением некоторых подзадач.
Создание методом автоматической генерации базы задач, используемой в интерактивных электронных учебниках ив печатных изданиях (для автоматизированного получения соответствующих Т^К-документов необходима реализация алгоритма конвертациии формул в ТЁХ-формат).
Научная новизна работы состоит в следующем:
Разработана оригинальная модель интеллектуальной обучающей системы, основанной на декларативных знаниях и осуществляющей генерацию заданий и контроль знаний учащегося.
Предложен, реализован и внедрен в конкретные интеллектуальные обучающие системы новый декларативный язык древовидных структур Т-РЕФАЛ (Tree-Refal), основанный на семантике РЕФАЛа и учитывающий специфику предметной области (математики).
Впервые алгоритмы компьютерной алгебры интегрированы с методами искусственного интеллекта и развитыми способами отождествления на деревьях в Т-РЕФАЛе (упрощение формул при генерации задач, алгоритмы преобразования формул в решателе, алгоритмы сопоставления формул при проверке знаний).
Реализованы оригинальные инструментальные средства генерации интерактивных задач по математике и проверки знаний на основе методов искусственного интеллекта (продукционно-фреймового представления знаний, прямого и обратного логического вывода).
Практическая значимость Реализованы необходимые функции визуализации и преобразования (popмул, а также функции контроля математических знаний учеников. Данные функции включены в динамически присоединяемую библиотеку ((ill), используемую в электронных мультимедийных учебных пособиях [53-60], изданных на CD-ROM и внедренных в ряде школ, на подготовительных курсах и для дистанционного обучения. Соавторами данных изданий являются Станченко СВ., Прилуц-кий CO., Зайцев В,Е., Крылов С.С, Тимохин В.В., Шестаков П.С, а также математики-методисты Высоцкий И. Р. и Шестаков С А. Диссертантом реализованы, алгоритмы символьной математики (визуализация, аналитические преобразования, вычисление, сопоставление формул), использующиеся в данных обучающих системах.
Реализованные алгоритмы визуализации формул также были использованы для подготовки телеуроков по физике, химии, алгебре, геометрии для телевизионного канала "Телешкола" в системе спутникового телевидения НТВ Плюс, в 2000 г. и на телеканале "Школьник ТВ", выходящем в эфир с 2002 г.
Инструментарий генерации задач успешно применяется для создания вариантов для компьютерного обучения и для автоматизированной подготовки макетов книг (методическое обеспечение экзаменационных работ в школах: 3 книги и 11 рабочих тетрадей [96-109]). Сборник задач, полученный при помощи данного инструментария, допущен Министерством образования РФ в качестве учебного пособия для учащихся 11-х классов. По таким образом сгенерированным заданиям в 2002/2003 уч.г. проводилась государственная (итоговая) аттестация по алгебре и началам анализа в общеобразовательных учреждениях города Москвы (письмо Министерства образования РФ от 24.12.2002 № 13-52-90/14, см.Приложение5).
Апробация работы. Результаты работы докладывались на IX и XI
международных школах-семинарах "Новые информационные технологии"
(Судак, 2001, где по итогам конкурса получен грант фонда содействия развитию малых форм предприятий в научно-технической сфере, Судак, 2003), были представлены на международной научной конференции XXVII "Гагаринские чтения" (Москва, 2001), обсуждались на международной научно-практической Интернет-конференции "Информационные технологии в науке и образовании" (Шахты, 2001), докладывались на X международной конференции "Математика. Компьютер. Образование" (Пущино,2003), на международной научно-технической конференции IEEE AIS'03 (Дивноморское,2003), на объединенном семинаре ВЦ РАН, МГУ и ОИЯИ по компьютерной алгебре под руководством проф. Абрамова С.А. (Москва, 2004), на семинаре кафедры математической теории интеллектуальных систем механико-математического факультета МГУ под
руководством проф. Подколзина А.С. (Москва, 2004).
Публикации. Основные результаты диссертации опубликованы в печатных работах [43-52], и реализованы в виде электронных мультимедиа учебников на CD-ROM [53-60]. Электронный учебник "Алгебра 7-11" [53] включен в "Перечень электронных изданий учебного назначения" для поставки в сельские школы по Федеральной программе развития образования (приказ Министра образования РФ № 2677 от 11.07.2001), учебник "Математика абитуриенту" [54] имеет гриф Министерства образования РФ, учебники серии "Все задачи школьной математики" [56-59] - победители конкурса Министерства РФ по делам печати, телерадиовещания и средств
массовых коммуникаций "Книга года"-2003 в номинации Мультимедиа.
Структура и объем работы. Диссертация состоит из введения, 4-х
глав, заключения, списка литературы и 5-ти приложений, включая электронное приложение на CD-ROM. Общий объем работы - 168 страниц, в том числе основной текст - 108 страниц, 33 рисунка, список литературы из 120 наименований.
Декларативный и процедурный подходы к построению ИОС
Представление знаний - одно из ключевых направлений в искусственном интеллекте. В рамках этого направления решается задача создания языка общения специалиста с компьютером и задачи, связанные с формализацией и представлением знаний в памяти интеллектуальной системы (ИС). Для различных предметных областей существуют десятки моделей (или языков) представления знаний. Большинство из них может быть сведено к следующим классам [16]: 1) продукционные модели; 2) фреймовые модели; 3) семантические сети; 4) формальные логические модели. Концептуальные знания в математике- это в основном равносильности, формулы и тождества. Например, равносильность \g(x) — у-&х — 1CF — знание экспоненцирования, формула а2 — знание о преобразовании разности квадратов в произведение, тождество arcsin(-) = - — знание табличных тригонометрических углов. Эти знания можно представлять в виде А — В, где левая часть формулы (Л) - предложение-образец, а правая — результирующая формула. На этих знаниях, представленных своего рода продукциями, осуществляется вывод формул, заключающийся в сопоставлении преобразуемой формулы с Л и, в случае успешного сопоставления, преобразовании данной формулы в формулу, соответствующую правой (В).
Чаще всего вывод на такой продукционной базе знаний бывает прямой (от данных к поиску цели) или обратный (от цели для ее подтверждения - к данным). Прямой вывод используется при преобразованиях выражений в операционной части системы, а обратный - для доказательства обнаруженной ошибки пользователя в контролирующей части системы.
Фреймовая модель представления знаний с наследованием свойств часто используется для решения задач классификации. В разрабатываемой обучающей системе такая модель применена для классификации ошибок обучаемого (в контролирующей части системы). Так, разработанная контролирующая система имеет продукционно-фреймовое представление знаний.
Помимо классификации СИИ по моделям представления знаний существует классификация обучающих систем по использующимся знаниям: декларативным и процедурным.
Соответственно с делением информации на декларативную (овеществленную в данных) и процедурную (воплощенную в выполняемых в ходе решения задачи программах) [84], японскими учеными было предложено классифицировать интеллектуальные обучающие системы на основе характера используемых в них знаний: декларативных или процедурных [117]. В своих разработках они уделяют большое внимание первому классу ИОС (основанных на декларативных знаниях), потому как такие системы носят более интеллектуальный характер и являются экспертными системами в обучении в явном виде. Учитывая преимущества декларативного подхода к построению ИОС, для контроля знаний и преобразования формул выбрана декларативная модель. Знания преобразований формул и классификации ошибок в такой модели, представляют собой декларации (сентенции), в отличие от описания алгоритмов, записываемого во многих системах компьютерной алгебры (Maple [65]) при процедурном подходе. В данном случае декларативные знания являются наиболее приближенными к языку предметной области. Процедурная информация используется, в основном, для ввода в систему функциональных знаний и применяется при генерации заданий.
Таким образом, в диссертационной работе предлагается модель ИОС разделенная на два основных блока: обучающая система Оля контроля знаний, содержащая декларативные знания и направленная на диалог с конечным пользователем - обучаемым и инструментарий экспертпа, содержащий процедурные знания и играющий роль генератора заданий и подсистемы приобретения знаний.
Предлагаемый подход, включающий в базу знаний ОС для контроля знаний только концептуальные (декларативные) знания, обладает большей общностью по сравнению с существующими интеллектуальными обучающими системами, где БЗ и каталог ошибок содержат процедурные или поведенческие знания и зависит от хода решения задачи. В случае присутствия в БЗ поведенческих знаний реакция системы на ответ пользователя зависит от хода решения задачи, при этом определении предполагается только один верный вариант поведения системы. Однако, это не всегда так, поскольку поведенческие знания системы не обязательно полностью определены. Например, в них может быть представлена процедура преобразования алгебраических уравнений, при которой действия могут выполняться в различном порядке и все же приводить к приемлемому решению [5].
Каталог ошибок при декларативном подходе представляет собой модель обучаемого. Анализ существующих систем обучения позволяет сделать следующий вывод: большинство из существующих обучающих систем tie содержит модели обучаемого [69,82]. Те же системы, в состав которых входит эта модель, построены, в основном, на основании процедурных знаний и жестко запрограммированных алгоритмов и наборов параметров (ЭКСТЕРН, РЕПЕТИТОР, КАДИС и др.).
Процедурные знания в предлагаемой модели используются в инструментарии эксперта-методиста для создания (генерации) задач. Учитывая, что при генерации задач требуются различные преобразования (упрощения) формул и необходимо знание последовательности их применения, обучающая система должна содержать подсистему аналитических преобразований, реализующую основные алгоритмы компьютерной алгебры и способная решать некоторые типы задач. Знания этих алгоритмов или правил преобразования объектов содержатся в базе поведенческих знаний. Эти знания используются генератором интерактивных заданий при порождении задач.
Сопоставление с образцом на деревьях математических выражений
Синтаксическое отождествление достаточно часто используется в экспертно-обучающих системах при обработке символьной информации. Наиболее естественно применение языков с синтаксическим отождествлением в программах, ведущих диалог на естественном языке, лингвистических программах (переводчики), а также в программах перевода с одного языка программирования на другой (программах-трансляторах [88]). К интеллектуальным обучающим системам по математике, основанным на символьных вычислениях, также применимы алгоритмы синтаксического отождествления.
В неформализованном виде синтаксическое отождествление имеет место, например, в записи закона коммутативности сложения в виде a + b — b + а. Это равенство, содержащее переменные а и 6, называется "образцом" и изображает бесконечное множество равенств ("объектов"): 0 + 0 = 0 + 0; 13 + 25 = 25 + 13; если вместо а и b поставить некоторые числа. Задача синтаксического отождествления обратная: не конкретизировать переменные в некотором образце, а распознать релевантность объектного равенства данному образцу. Такая процедура поиска но образцу наиболее подходит для классификации формул при нахождении возможных преобразований математических выражений и при классификации ошибок пользователя.
Одним из языков, применяющих алгоритмы синтаксического отождествления, является сентенциальный (декларативный) язык нормальных алгоритмов А.А. Маркова (AM), использующийся для преобразования строк. Программа на языке AM представляет собой последовательность формул подстановки (преобразований) а=4 /3, где а. и (3 - некоторые строки. При этом для применения того или иного правила происходит при успешном синтаксическом отождествлении левой части формулы подстановки (а) и исходного преобразуемого выражения.
Теперь рассмотрим соответствующее синтаксическому отождествлению в РЕФАЛЕ введенное автором понятие сопоставления с образцом на деревьях в Т-РЕФАЛЕ.
Почти все языки, происходящие из AM (Comit, SNOBOL), предназначены для обработки строк, т.е. линейных структур. При оптимизации алгоритмов сопоставления строки приобрели явно выраженную синтаксическую структуру. Это привело к появлению таких языков как AMBIT и РЕФАЛ, где обрабатываемые выражения можно представить деревом. В диссертационной работе при синтаксическом отождествлении или сопоставлении с образцом предлагается использовать объекты и образцы, представленные деревьями математических (или арифметических) выражений, а не деревьями общего вида (где структуру задают скобки), использующимися в языке РЕФАЛ (рис. 2.5.).
А Фактически, тем самым предложен новый вид отождествления -отождествление формул, представляющий собой отождествление их дере-ньев [45]. В логике первого порядка для сопоставления с образцом или унификации в настоящее время также используются различные представления термов. Наиболее известными являются алгоритмами сопоставления являются алгоритмы, предложенные Робинсоном, Мартелли и Монтана-ри, Юэ, Корбином и Бидуа. Классический алгоритм Робинсона требует экспоненциальных затрат времени [95]. Им было показано, что для создания более эффективных процедур унификации необходимо использование специальных структур для представления термов. Юэ и Корбин используют графовое представление термов, и временная сложность их составляет 0(п2). Алгоритм Мартелли и Монтанари использует табличное представление. Его сложность составляет 0(п + logm) (п - число термов, т - число различных переменных в термах) [3]. Предлагаемое в диссертационной работе представление образца и объекта в виде специальных структур - деревьев математических выражений также дает достаточно эффективный алгоритм сопоставления формул.
Учитывая грамматику формул, описанную в п. 2.1.1 дерево мате-\татического выражения представляет собой бинарное дерево, соответствующее некоторой правильной математической формуле и построенное по следующим законам: 1) узлами дерева являются переменные, константы, операции; 2) переменные и константы (действительные числа) - терминальные элементы; 3) операции - нетерминальные элементы арности 1 (модуль, синус и т.п) или 2 (+,-, ) соответствующие унарным и бинарным операциям в математике. Операнды (слагаемые, сомножители) есть дочерние деревья операций. Представления сопоставляемых объекта и образца в виде деревьев математических выражений дозволяет не только оптимизировать алгоритм сопоставления, но и учитывать специфику предметной области - математики. Используя данное представление, при сопоставлении с образцом можно рассматривать несколько объектных выражений, получаемых из данного при помощи закона коммутативности и ассоциативности (рис. 2.6.). Такое сопоставление на деревьях проходит успешно для формул с различным символьным представлением, и соответствует эквивалентности деревьев, определяемой следующими правилами: 1) терминальные элементы или листья (константы, переменные) эквивалентны, если они совпадают; 2) деревья /(щ,,.., ип) и р(г»і,... ,vn), ( где /-математическая операция; щ, Vi - операнды) эквивалентны, если / и д - совпадают и а) если /- некоммутативная операция, щ и ы эквивалентны для каждого г; б) если /- коммутативная операция (+, ) щ,...}ип и vi,...,vn эквива лентны как мультимножества. Мультимножество величин щ,...,ип, эквивалентно мультимножеству 1 ,...,1 , если каждый щ эквивалентен некоторому Vj и, наоборот, каждому Vj эквивалентен некоторый элемент щ.
Унификация математических ошибок в Т-РЕФАЛ
Чтобы сделать дальнейшие модификации РЕФАЛа практически используемыми, в частности, для приложений компьютерной алгебры, потребовались дополнительные усилия.. С. Н. Флоренцев, С. А. Романенко, Анд. В. Климов и другие были авторами первых эффективных РЕФАЛ-комииляторов. С середины восьмидесятых годов и до настоящего времени РЕФАЛ успешно применяется в исследованиях, связанных с суперкомпиляцией и частичными вычислениями [86].
К настоящему времени существует несколько диалектов языка РЕФАЛ, среди которых наиболее динамично развиваются РЕФАЛ-5 [90] и РЕФАЛ Плюс. Разработаны методы эффективной реализации языка; созданы системы программирования для различных программно-аппаратных платформ. Несмотря па это, РЕФАЛ крайне редко применяется в индустриальном программировании (под индустриальным программированием понимается изготовление программных продуктов для конечного пользователя). При этом РЕФАЛ нельзя назвать неизвестным языком: многие профессиональные программисты знакомы с этим языком. РЕФАЛ реализован на всех основных типах ЭВМ и используется как для автоматизации построения трансляторов и аналитических преобразований, так и в качестве инструментальной среды для реализации языков представления знаний [16]. Однако трудность интеграции РЕФАЛа с другими языками (в частности, с объектно-ориентированными) являлась причиной слабой востребованности этого языка. На сегодняшний день уже реализованы достаточно мощные средства интеграции языка РЕФАЛ с процедурными языками: например, система РЕФАЛ-Java.
Рассмотрим синтаксис и семантику базисного РЕФАЛ А. Данный язык предназначен для обработки символьной информации. Он является одномерным знаковым языком, т.е. его объекты — это некоторые последовательности знаков. Все знаки РЕФАЛа делятся на собственные знаки и объектные знаки. Следующие знаки являются собственными знаками: =, s, t, е, (,), , . Все остальные знаки являются объектными. Знаки ( и ) называются структурными скобками, и — коикретизационными скобками. Минимальной семантической единицей является символ - объектный знак. Другой элементарной единицей является переменная, которая представляет собой последовательность из указателя типа (одного из знаков з, tt е), точки и любого идентификатора или числа. Примеры переменных: еЛ s.2 t.3. Первый знак - указатель типа переменной, числа 1, 2, 3 — индексы неременных. Различие между указателями типа состоит в множествах допустимых значений или в интерпретации переменных (функция типа I: N — V, где N - множество обозначений переменных, V - множество их допустимых значений [34]). Значением s-иеременной может служить только один символ. Значением t-переменной может быть любой терм (либо символ, либо выражение в структурных скобках), значением е-переменной может быть любое выражение.
Из символов, переменных и скобок строятся более сложные объекты - выражения. Выражением в РЕФАЛЕ называется любая (может быть пустая) последовательность символов, переменных и скобок, которая правильно построена относительно конкретизациейных и структурных скобок. Например: F(5, G(3) ) . Частным случаем выражения является терм. Он представляет собой либо символ, либо переменную, либо выражение, заключенное в скобки. Например: si, F, (G(3)). Выражения, не содержащие конкретизационных скобок, называются типовыми, не содержащие переменных и конкретизационных скобок - объектными.
Основной операцией в языке РЕФАЛ является операция синтаксического отождествления или сопоставление с образцом. Для заданных объектного выражения Е и образца L будем обозначать операцию сопоставления Е с L через Е: L , где двоеточие - специальный знак РЕФАЛа, знак сопоставления. В данном случае Е распознается как частный случай L, т.е. образец можно рассматривать как множество объектных выражений, которые могут быть получены в результате придания допустимых значений всем переменным. Так, образец А е.1 представляет множество всех объектных выражений, начинающихся с символа А. Всем вхождениям одной и той же переменной следует придавать одно и то же значение. Образец s.l е.2 s.l можно рассматривать как множество всех объектных выражений, которые начинаются и заканчиваются одним и тем же символом и состоят, по крайней мере, из двух символов. Выражения-образцы выполняют также еще одну функцию: они описывают декомпозицию объектных выражений, в ходе которой переменные образца отождествляются с некоторыми частями объектного выражения, то есть принимают некоторые значения.
Формально операция сопоставления определяется следующим образом [90]: Если существует подстановка S для переменных в L такая, что применение S к L приводит к Е, тогда сопоставление, или распознавание, является успешным. Переменные в L принимают значения, предписываемые подстановкой S. При этом значения переменных должны удовлетворять следующим требованиям: - значением s-переменной может быть только символ, t-переменной - только терм, Значением е-переменной может быть произвольное выражение, в том числе и пустое; - все вхождения одной и той же переменной должны принимать одинаковое значение.
В случае отсутствие подстановки S сопоставление считается неудавшимся. Если имеется несколько способов присваивания значений свободным переменным в образце, при которых сопоставление может быть успешно, то выбирается такой способ, при котором самая левая е-переменная принимает наиболее короткое значение. Если это не приводит к однозначности, подобный выбор делается для следующей (самой левой) е-перемешюй, и т.д. То есть, для того, чтобы обеспечить однозначный результат сопоставления, используется следующее соглашение о том, что сопоставление осуществляется слева направо (рис. 2,7.) и выбирается первое успешное сопоставление EcL.
Упрощение формул с помощью Т-РЕФАЛ-предложений
Наиболее распространенный метод оценивания обучаемого — стандартизованный контроль знаний [78]. Сущность такого контроля состоит в том, что обучаемому предлагается выборка специальных заданий и по ответам на нее выносится суждение о его знаниях. Стандартизованный контроль знаний в АО С выполняется с помощью тестов. В общем случае, тест - это набор вопросов и правильных ответов к ним (эталонов), Действия пользователя при таком подходе чаще всего заключаются в выборе правильного значения (правильных ответов) из предложенного списка. При этом для большинства тестов вводится сильное ограничение - двухбалльная система оценки ответа: ответ считается либо абсолютно правильным, либо совсем неправильным. Это ограничение не соответствует реальному положению, когда правильность ответа определяет преподаватель, который подходит к оценке ответа дифференцированно. Поэтому целесообразно включить в систему контроля знаний возможность анализа произвольного ответа тестируемого с определением степени правильности ответа, т.е. степени его соответствия эталону.
Другой метод контроля знаний основывается на оценке действий обучаемого [2]. Этот метод применяется в экспертно - обучающих системах, основанных на знаниях. Знания о предметной области и правила оценки действий обучаемого позволяют системе в ходе диалога с обучаемым определять уровень его знаний без задания контрольных вопросов. С помощью этого метода можно на высоком уровне моделировать взаимодействие преподавателя с обучаемым. Этому методу соответствует менее распространенный способ построения диалога, основанный на контекстно-свободном ответе пользователя. Примерами систем с таким диалогом является программа APRIL, решающая арифметические задачи в словесной формулировке [62], система AutoTutor, которая делает попытку понять обычный студенческий язык [67] и ряд других. В системах основанных на контроле знаний при помощи оценки действий обучаемого появляется возможность разнообразить диапазон вопросов и ответов, внести эмоциональную окраску в диалог "компьютер-человек", в отличие от жестко спроектированного диалога получаемого при применении стандартизованного метода контроля знаний. Однако, несмотря на явное преимущество систем с интеллектуальным диалогом, сегодня основную долю рынка занимают стандартизованные системы-тесты.
Учитывая основные недостатки тестовой модели (возможность случайного угадывания тестируемым правильных ответов, пассивная роль пользователя при выборе ответа из списка предложенных, отсутствие градации правильности ответа, ограниченный диалог), реализованный в диссертационной работе инструментарий для контроля знаний по математике основывается на оценке произвольного ответа обучаемого. Оценка правильности ответа носит градуированный характер, так как производится при помощи модели ошибок.
Опытные учителя и преподаватели знают, как важно иметь представления не только о том, что обучаемые знают и умеют, но и о том, как обучаемые ошибаются и, главное, как они могут ошибаться [5]. В настоящее время ошибки обучаемых превратились в предмет серьезных исследований, и во многом это связано с разработкой интеллектуальных обучающих систем. В середине 70-х годов исследователи, занимающиеся моделированием обучаемого, обратили внимание на процедурные ошибки, которые совершались обучаемыми разных поколений, и которые в явном виде можно было использовать при разработке систем. Под процедурной ошибкой понимается правильное исполнение неправильной процедуры, это ошибка в поведенческих знаниях. Процедурную ошибку стали называть словом "баг" ("bug" — ошибка в программе или устройстве). Изучение таких ошибок привело к появлению термина "модель ошибок" и дало начало долговременному проекту BUGGY — "описательной теории ошибок, представимых посредством перечисления ошибок, доступных наблюдению". Система BUGGY была разработана в 1975 году Дж. Брауном (J. Brown) и Р. Варто ном (R. Burton) [113]. Они начали с изучения протоколов действий обучаемых при выполнении алгебраических операций, данные из которых позволяли судить о выполнении каждого процедурного умения в отдельности. В результате была разработана диагностическая модель, отражающая наличие или отсутствие у обучаемого умений, необходимых для решения задач. Модель использовала ошибочные варианты отдельных умений для воспроизведения поведения обучаемого. При этом авторы сделали попытку перечислить возможные процедурные ошибки при решении задач.
Таким образом, создается "каталог ошибок", или "библиотека ошибок", что означает множество ошибок, заранее описанных разработчиками системы. По сути дела, такой каталог и есть модель ошибок. Примером еще одной системы, построенной на процедурных ошибках, представляющих собой модель обучаемого, являются системы, реализованные на основе расширенного логического программирования (Prolax [30]). Рассмотренные ошибки (баги) являются несоответствиями на поведенческом уровне. Недостатки подхода, использующего такие ошибки, отмечены в п. 1.4.1.
В диссертационной работе для контроля знаний выбран несколько другой подход. Предлагается рассматривать не процедурные, а так называемые "декларативные" ошибки. То есть рассматривается не ход решения задачи, а полученные конечный (при зачете) или промежуточные результаты (при тренинге). "Каталог ошибок" содержит возможные декларативные ошибки при решении задач. Оценивание ошибки может зависеть от типа задачи или проверяемой интерактивной формулы. Это отражено во фреймовой структуре "каталога ошибок". Рассмотрим более подробно содержание и структуру каталога ошибок в реализованных обучающих системах.
