WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«RIGHTUSECHECKER. DESCRIPTION OF THE ALGORITHM Vasenina D. Perm State National Research University, Department of Computer Science Perm, Russia ...»

RIGHTUSECHECKER. ОПИСАНИЕ АЛГОРИТМА

Васенина Д.А.

Пермский государственный национальный исследовательский университет,

кафедра математического обеспечения вычислительных систем

Пермь, Россия

RIGHTUSECHECKER. DESCRIPTION OF THE ALGORITHM

Vasenina D.

Perm State National Research University, Department of Computer Science

Perm, Russia

Введение

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

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

–  –  –

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

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

Для условий – присутствующие в нем выражения и соответствующие знаки сравнения, порядок выражений не важен.

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

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

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

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

– среднее количество элементов в альтернативах, O – количество операторов в студенческой программе.

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

–  –  –

Итак, в главной программе эталона всего 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

–  –  –

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

–  –  –

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

Boolean CMPR_all(V) – функция сопоставления всех позиций. V – стартовая вершина.

Функция равна true, если вершина привязалась и false в противном случае.

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

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

P V p Boolean CMPR_all( ) begin current := V;

bad := false;

repeat bad := not(CMPR(current));

V : V V p & (current,V ) E p

current :=

until bad || current == null;

return not(bad);

end;

–  –  –

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

Научный руководитель:

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



Похожие работы:

«Российская академия наук Сибирское отделение Институт вычислительных технологий УТВЕРЖДАЮ Директор ИВТ СО РАН академик Ю. И. Шокин 1 сентября 2009 года «Подготовка цифровых батиметрических данных на регулярной сетке для Дальневосточных акваторий России» В...»

«Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра электронной техники и технологии В. Л. Ланин МОДЕЛИРОВАНИЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ СБОРКИ И МОНТАЖА ЭЛЕКТРОННЫХ МОДУЛЕЙ Методическое пособие для п...»

«Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники»МОДЕЛИРОВАНИЕ, КОМПЬЮТЕРНОЕ ПРОЕКТИРОВАНИЕ И ТЕХНОЛОГ...»

«Российская академия сельскохозяйственных наук ГОСУДАРСТВЕННОЕ НАУЧНОЕ УЧРЕЖДЕНИЕ ВСЕРОССИЙСКИЙ ИНСТИТУТ АГРАРНЫХ ПРОБЛЕМ И ИНФОРМАТИКИ ИМЕНИ А.А. НИКОНОВА (ГНУ ВИАПИ РОССЕЛЬХОЗАКАДЕМИИ) УДК № госрегистрации Инв. № УТВЕРЖДАЮ Директор ВИАПИ им. А.А. Никонова С.О. Сиптиц «_» 2012 г. ОТЧЕТ О НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ З...»

«УДК 519.6 ЗАДАЧА ШТЕЙНЕРА ДЛЯ АЦИКЛИЧЕСКОГО ГРАФА Ильченко А. В. Таврический национальный университет им. В.И. Вернадского факультет математики и информатики пр-т Вернадского, 4, г. Симферополь, 95007, Украина Abstract The Steiner problem for graph without cycles is considered in t...»

«Сравнение пространственной структуры домена альфа-глобиновых генов в трех типах клеток G.gallus Александра Галицына1, Екатерина Храмеева2,3, Сергей Ульянов4 Московский Государственный Университет, Факультет Биоинженерии и Биоинформатики, Ленинские Горы, д.1, стр.73, Москва 119991, Россия agalit...»

«Министерство образования Республики Беларусь Учреждение образования «БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ» УТВЕРЖДАЮ Проректор по учебной и воспитательной работе _С.К. Дик «30» _05 2016 г. ПРОГРАММА вступительного экзамена в магистратуру по специальности I –...»

«Министерство общего и профессионального образования Ростовской области Государственное бюджетное профессиональное образовательное учреждение Ростовской области «Ростовский-на-Дону государственный колледж связи и информатики» (ГБПОУ РО «РКСИ») УТВЕРЖДАЮ Дир...»

«МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОСТОВСКОЙ ОБЛАСТИ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ РОСТОВСКОЙ ОБЛАСТИ «РОСТОВСКИЙ-НА-ДОНУ КОЛЛЕДЖ СВЯЗИ И ИНФОРМАТИКИ»...»





















 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

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