IV Международная студенческая научная конференция Студенческий научный форум - 2012

 Введение

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

Программа RightUseChecker

Обзор аналогов

Для обоснования необходимости разработки и применимости RightUseChecker были проанализированы существующие системы тестирования: TSystem (доступна на сайте http://www.olympiads.ru/), Contester (доступна на сайте http://www.contester.ru/) а также другие он-лайн системы.

Помимо этого, были рассмотрены несколько автоматизированных обучающих систем, как, например, система EduCad.

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

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

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

Условие №1 (учебное): Вводится число А. Вывести 1, если оно больше 0 и -1, если меньше.

Условие №2 (олимпиадное): Вводится целое число А в диапазоне от -100 до 100. Вывести 1, если оно больше 0 и -1, если меньше и 0, если оно равно нулю.

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

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

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

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

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

Язык эталонов

Эталонная программа пишется на Паскале, с добавлением некоторых спецсимволов. Внутри каждого блока допускаются альтернативные варианты. Блок состоит из позиций, каждая позиция может иметь несколько альтернатив, внутри альтернативы может быть несколько элементов. Позиция, которая имеет несколько альтернатив (или вариант), должна начинаться со служебного символа !p и заканчиваться символом !!p. Внутри такого блока не может быть обязательных элементов, не принадлежащих какой-либо альтернативе, они все выносятся за ее пределы. Альтернатива начинается символом !a  и заканчивается символом !!a.  Те элементы, которые присутствуют в любом случае, вне зависимости от варианта, называются обязательными и не заключаются в рамки позиций или альтернатив.

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

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

Формальное описание грамматики

Введем обозначения:

G - грамматика языка эталонов;

A - алфавит языка эталонов;

R - правила языка эталонов;

A_пас - алфавит языка Паскаль;

A_мета - мета алфавит;

R_пас - правила языка паскаль;

R_мета - метаправила;

SF - множество начальных и конечных символов языка Паскаль;

 

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

 

Алфавит и правила языка Паскаль являются общеизвестными, и здесь мы их приводить не будем. Рассмотрим поподробнее алфавит и правила мета уровня.

Описание мета-алфавита

Мета-алфавит:

<алфавит> :: = <цифры> | <метасимволы> | <буквы>

<буквы> :: = A | B | ...| Z | a | b | ...| z | А | Б | ... | Я | а | б | ... | я

<цифры> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<метасимволы> ::= !p | !!p | !a | !!a | def | endef | define | _if | $ | #

Метаправила языка

Приведем описание метаправил языка в виде диаграмм Вирта:Алгоритм работы

Опишем основной алгоритм работы приложения.

Общий алгоритм сопоставления:

Цикл по всем позициям главной программы эталона

{

              Сопоставление позиции

              Если позиция не привязалась

{

Программа не сопоставлена

Выводим накопленный список ошибок

Выходим из цикла

}

}

Если все позиции привязались

{

Программа сопоставлена

}

 

Сопоставление позиции:

Цикл по всем альтернативам позиции, которые могут быть в одном слое с уже привязавшимися ранее альтернативами

{

              Цикл по всем элементам альтернативы

              {

                          Сопоставление элемента

Если элемент не привязался, то

                          {

                                      Альтернатива не привязалась

                                      Выходим из цикла

                          }

              }

Если все привязались

{

Альтернатива привязалась

Выходим из цикла

}

}

Если привязалась хоть одна альтернатива

{

Позиция привязалась

}

Иначе

{

              Позиция не привязалась

}

 

Сопоставление элемента:

Поиск в студенческой программе элемента, подходящего по типу и атрибутам^*

Если элемент найден

{

              Если у элемента есть вложенные позиции

{

                          Цикл по всем вложенным позициям

{

                                      Сопоставление позиции

                                      Если позиция не привязалась

{

Элемент не привязался

Добавляем текст ошибки в список

Выходим из цикла

}

}

Если все позиции привязались

{

Элемент привязался

}

}

Иначе

{

                          Элемент привязался

}

}

Иначе

{

              Элемент не привязался

}

 

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

• Для оператора присваивания - тип переменной и выражение
• Для оператора for - границы
• Для операторов while и repeat - условие
• Для оператора case - тип переменной, списки меток
• Для оператора if - условие, наличие else
• Для вызовов стандартных процедур - имя и параметры
• Для вызовов своих процедур - операторы процедуры и параметры
• Для выражений - список присутствующих в выражении переменных и констант, а также знаки операций.
• Для условий - присутствующие в нем выражения и соответствующие знаки сравнения, порядок выражений не важен.

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

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

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

В самом пессимистичном варианте, сложность алгоритма будет порядка P*A*E*O, где P - количество позиций в эталоне, A - количество альтернатив в каждом эталоне (среднее), E - среднее количество элементов в альтернативах, O - количество операторов в студенческой программе.

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

 

Пример работы

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

Эталон:

var n, sum, a: integer;

      i: integer;

begin

  !p

    !a <1>

      sum := 0;

    !!a # нет обнуления #

    !a <2>

      read(a);

      sum := a;

    !!a # нет идентификации #

  !!p  

  !p

    !a <1>   

      for i:=1 to n do begin

        read(a); # забыли считать #

        sum := sum + a;

      end;

    !!a

    !a

      for i:=2 to n do begin

        read(a); # забыли считать #

        sum := sum + a;

      end;

    !!a

  !!p

  write(sum);

end.

Студенческая программа:

var n, sum, a: integer;

      i: integer;

begin

  for i:=1 to n do begin

    read(a);

    sum := sum + a;

  end;

  write(sum);

end.

Итак, в главной программе эталона всего 3 позиции. Начинаем с первой.

1. Берем первый элемент первой альтернативы первой позиции, т.е. оператор sum:=0;
2. Начинаем искать сопоставимый элемент в студенческой программе, начиная с самого начала. Сопоставимые операторы совпадают как минимум по типу самого оператора, но ни оператор for, ни оператор write не подходят, следовательно, этот элемент не привязался, и альтернатива не привязалась. Сохраняем ошибку «нет обнуления»
3. Берем первый элемент второй альтернативы первой позиции, т.е. оператор read(a);
4. Начинаем искать опять же с самого начала. Но сопоставимых элементов снова нет. Т.е. элемент не привязался, альтернатива не привязалась. Запоминаем ошибку «нет идентификации»
5. Обе альтернативы первой позиции не привязались, следовательно, первая позиция не привязалась, и не привязалась вся программа.
6. Так как программа не сопоставилась, то выдаем все сохраненные ошибки, т.е. в окне ошибок будут сообщения «нет обнуления» и «нет идентификации».

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

Студенческая программа (второй вариант):

var n, mySum, myA: integer;

      i: integer;

begin

  read(myA);

  mySum := myA;

  for i:=2 to n do begin

    read(myA);

    mySum := mySum + myA;

  end;

  write(mySum);

end.

Начинаем так же:

1. Берем первый элемент первой альтернативы первой позиции, т.е. sum:=0;
2. Он не привязывается, поэтому альтернатива не привязывается. Сохраняем ошибку «нет обнуления»
3. Берем первый элемент второй альтернативы первой позиции. Находим в студенческой программе оператор read(myA); и делаем вывод, что этот элемент привязался.
4. Берем второй элемент второй альтернативы первой позиции. Он тоже привязывается, т.к. есть оператор mySum:=myA; Значит вторая альтернатива привязалась, т.е. первая позиция тоже привязалась.
5. Порядок внутри альтернативы нам не важен, но позиции идут строго друг за другом, значит надо знать с какого элемента студенческой программы можно привязывать следующие позиции. Максимальный номер привязавшегося элемента из данной позиции - это 1, т.к. оператор read(myA) имеет номер 0, а оператор myS:=myA имеет номер 1.
6. Берем первую альтернативу второй позиции. Но она совместима только со слоем «1», а наша привязавшаяся альтернатива принадлежала слою «2», т.е. ее мы рассматривать не можем.
7. Берем вторую альтернативу второй позиции. Здесь с совместимостью все нормально. Берем ее первый элемент, находим в студенческой программе, (начиная со 2го элемента) оператор for. Границы сопоставимы, теперь следует сопоставить вложенные операторы.
8. Берем первый вложенный оператор - read(a). Область поиска теперь только вложенные операторы найденного оператора for. Находим в ней оператор read(myA).
9. Берем второй вложенный оператор - sum:=sum+a; Для него находим mySum:=mySum+myA; Таким образом, оператор for полностью привязался, т.е. привязалась вторая альтернатива. Вторая позиция привязалась.
10. Берем последнюю, третью позицию. У нее всего одна альтернатива, т.к. она обязательная. Поиск осуществляем начиная с 3 элемента. Находим оператор write(mySum). Таким образом, третья позиция привязалась.
11. Все позиции программы-эталона привязались, значит, программы сопоставимы и список ошибок не выдается.

Обратим внимание, что  имена идентификаторов роли не играют.

Реализация

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

Модель представления эталона

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

Более подробно такая сеть представлена на рис.1Приведем формальное определение этой модели.

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

Множество вершин включает в себя объединение множеств вершин-элементов , вершин-альтернатив   и вершин-позиций :

.

Множество ребер включает в себя ребра-связи («следует за») между позициями , ребра-связи («следует за») между альтернативами , ребра-связи («следует за») между элементами  и ребра-связи от позиции к альтернативе, от альтернативы к элементу или от элемента к позиции, означающие отношение «включает» - :

Пусть Boolean CMPR - функция сопоставления вершины. Она равна true, если вершина привязалась и false в противном случае.

Boolean CMPR_all(V) - функция сопоставления всех позиций. V - стартовая вершина. Функция равна true, если вершина привязалась и false в противном случае.

Boolean attr(V) - функция сопоставления атрибутов. Она равна true, если атрибуты совпадают и false в противном случае.

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

Boolean CMPR_all( )

begin

  current := V;

  bad := false;

  repeat

    bad := not(CMPR(current));

    current := 

  until bad || current == null;

  return not(bad);

end;

Boolean CMPR( )

begin

  current := ;

  good := false;

  repeat

    good := (CMPR(current));

    current := 

  until good || current = null;

  return good;

end;

Boolean CMPR( )

begin

  current := ;

  bad := false;

  repeat

    bad := not(CMPR(current));

    current := 

  until bad || current == null;

  return not(bad);

end;

Boolean CMPR( )

begin

    return (Attr( ) && CMPR_all( );

end;

 

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

Научный руководитель:
кандидат физико-математических наук, доцент кафедры МОВС М.А. Плаксин

Код для цитирования: Скопировать