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

л

московским государственный университет

имени М.В. ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики Кафедра алгоритмических языков

На правах рукописи удк 519.6

ГРУЗДЕВА Надеада Валерьевна

ПРОБЛЕМНО-ОРИЕНТИРОВАННЫЕ ЗНАНИЯ В СИСТЕМЕ ОБУЧЕНИЯ ФУНКЦИОНАЛЬНОМУ ПРОГРАММИРОВАНИЮ

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Диссертация

па соискание ученой степени кандидата физико-математических наук

Научный руководитель кандидат физико-математических наук доцент Большакова Елена Игоревна

Москва - 1998

Оглавление

Введение.................................................... 3

Глава 1. Компьютерные системы обучения программированию.......11

Глава 2. Представление знаний о классах задач и вариантах программ .25

2.1 Классификация типичных задач........................25

2.2 Спецификации задач и шаблоны программ...............33

2.3 Процедуры анализа и синтеза программ..................38

Глава 3. Процедуры проверки правильности рефал-программ........43

3.1 Проверка правильности решений задач первого класса.....43

3.2 Проверка правильности решений задач второго класса.....49

3.3 Вспомогательные процедуры...........................56

3.3.1 Установление соответствия

нетерминал -> тип рефал-переменной..........56

3.3.2 Эквивалентные трансформации БНФ ...........59

3.3.3 Построение левой части рефал-правила

по альтернативе БНФ........................62

3.3.4 Построение правой части рефал-правила

по альтернативе БНФ........................65

3.3.5 Разбиение образцов на группы................70

Глава 4. Экспериментальная система обучения языку Рефал.........75

4.1 Основные функции и структура системы.................75

4.2 Учебник языка Рефал.................................78

4.3 Библиотека спецификаций задач и шаблонов программ.....82

4.4 Модуль проверки правильности рефал-программ..........85

4.5 Модуль трассировки рефал-программ....................89

Заключение..................................................93

Литература...................................................95

Приложение 1. Синтаксис языка Рефал-2.........................99

Приложение 2. Шаблоны рефал-программ........................103

Введение

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

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

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

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

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

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

Распространение персональных ЭВМ и успехи в области искусственного интеллекта (ИИ) оказали революционное влияние на исследования в области применения ЭВМ в обучении. На смену традиционным компьютерным обучающим системам приходят учебные системы нового поколения - интеллектуальные обучающие системы (ИОС) [3, 12]. Создание ИОС стало результатом применения методов и средств ИИ в области автоматизированного обучения.

Первые попытки создания ИОС относятся к началу 70-х годов и вызваны разочарованием ряда разработчиков обучающих систем в традиционной технологии программированного обучения, а именно, в слабой адаптивности традиционных КОС к конкретному обучаемому. С помощью этой технологии невозможно создать КОС, которые выполняли бы функции контроля и помощи в процессе практической работы обучаемого с учетом его индивидуальных характеристик. В течение 70-х и 80-х годов был разработан ряд экспериментальных ИОС [1, 2, 5, 25-28, 3032], которые продемонстрировали плодотворность нового подхода и стимулировали дальнейшие исследования [4, 6, 8-11, 29, 33-37].

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

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

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

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

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

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

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

Что касается обучения программированию, то актуальность применения методов ИИ в этой области обусловлена спецификой изучаемого предмета:

• составление программ - это задача, сопоставимая по сложности, например, с доказательством теорем;

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

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

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

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

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

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

Очевидно, что одной из основных проблем разработки интеллектуальных систем обучения программированию является проблема проверки правильности программ, написанных обучаемым в процессе решения задач. Методы формального доказательства правильности программ [13, 23 ,38] трудно реализуемы и малопригодны для использования в КОС.

В существующих системах обучения программированию [1, 2, 5, 25-28, 30-32] проверка правильности программы понимается как установление ее соответствия (эквивалентности) одной из известных системе эталонных программ, являющихся решениями соответствующей задачи. Сложность проверки правильности программ связана с тем, что даже для несложных задач число различных решений одной и той же задачи (вариантов программ) достаточно велико. Причем эта вариативность резко увеличивается с ростом сложности задач.

В области автоматизированного обучения программированию наименее изученным является обучение функциональным языкам, к которым относятся Лисп [17, 24], Рефал [16, 19, 20, 41], Плэнер [18]. Большинство разработанных к настоящему времени систем предназначалось для обучения языку Лисп, из них известны лишь три

ИОС- система Lisp Tutor [1, 27], система ELM-ART [30] и отечественная система ЛУЧ [2].

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

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

Исторически первая система обучения функциональному программированию - Lisp Tutor - относится к системам поддержки процесса решения задач. Lisp Tutor осуществляет пошаговое управление и контроль хода решения обучаемым простой лисп-задачи (например, программирование функции APPEND), и в ней не возникает проблема проверки правильности законченной программы. В отличие от Lisp-Tutor системы ЛУЧ и ELM-ART обладают возможностью анализа различных законченных программ - решений одной задачи. Система ЛУЧ проверяла правильность программы путем тестирования на некотором наборе тестов. В системе ELM-ART проверка правильности программы обучаемого проводится путем сопоставления с эталонными программами-

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

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

Данная диссертационная работа посвящена исследованию и разработке методов проверки правильности функциональных программ для КОС и организации необходимых для этого проблемно-ориентированных знаний. Исследование проводилось для функционального языка программирования Рефал.

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

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

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

Данная диссертационная работа состоит из введения и четырех

глав.

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

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

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

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

Глава I. Компьютерные системы обучения программированию

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

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