Язык описания алгоритмов начертательной геометрии adgl

Вид материала

Документы

Содержание Концепция языка Грамматика языка описания алгоритмов начертательной геометрии Alg  inputs steps Step_foreach  Step_break  Пример описания алгоритма

Подобный материал:

• Наименование и краткое содержание лекций № лек. Тема лекции, краткое содержание Количество, 72.86kb.
• Краткий курс лекций, 182.24kb.
• Программа-минимум кандидатского экзамена по специальности 05. 01. 01 «Инженерная геометрия, 92.15kb.
• Программа-минимум кандидатского экзамена по специальности 05. 01. 01 «Инженерная геометрия, 88.49kb.
• Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
• Введение Предмет "Программирование", 19.2kb.
• Основы алгоритмизации, 754.96kb.
• Программа по дополнительному образованию «элементы начертательной геометрии», 136.57kb.
• Вопросы курсовой работе по «Начертательной геометрии. Инженерной графике», 26.28kb.
• 1 Алгоритмизация и программирование Алгоритмы, виды алгоритмов, описания алгоритмов., 172.44kb.

Язык описания алгоритмов начертательной геометрии ADGL.

Бобровских А.С.

Введение

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

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

Концепция языка

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

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

При описании алгоритма в рамках концепции предлагаемого языка алгоритм представляется как последовательность входных данных и шагов алгоритма.

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

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

Грамматика языка описания алгоритмов начертательной геометрии

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

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

1. Step_action – выполнение команды;
   
2. Step_for – исполнение цикла со счетчиком;
   
3. Step_foreach – операции над элементами множества в цикле;
   
4. Step_if – условный оператор.
   

Рассмотрим граммитику языка ADGL:


ALG  INPUTS STEPS

INPUTS  INPUTS INPUT

INPUT  Statement;

STEPS  STEPS STEP_RETURN STEPS | STEPS STEP | STEP

STEP  STEP_ACTION | STEP_FOR | STEP_FORECH | STEP_IF

STEP_ ACTION  { Statement; }

STEP_FOR  For_Statement { STEPS_FOR }

STEP_FOREACH  Set_Statement { STEPS_FOR }

STEP_IF  if (Condition){ STEPS } else { STEPS } |

if (Condition){ STEPS }

STEPS_FOR  STEPS | STEPS STEP_BREAK STEPS |

STEPS STEP_CONTINUE STEPS |

STEPS STEP_RETURN STEPS

STEP_BREAK  Break_Condition;

STEP_CONTINUE  Continue_Condition;

STEP_RETURN  Return_Condition;


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

ALG

Описание алгоритма задается элементом ALG. Он содержит в себе объявления входных данных и шагов алгоритма. У данного элемента задаются свойства:

Name – для задания имени алгоритма, по которому к нему можно будет обращаться как к имени шага STEP_ACTION, который будет рассмотрен ниже, и, таким образом, использовать в других алгоритмах;

Description – необязательное свойство, в котором указывается описание алгоритма в целом.

Оба параметра являются строковыми.

INPUT

Элемент INPUT представляет собой описание входного параметра алгоритма. Для данного элемента необходимо задать свойства:

Name – имя параметра, по которому к нему будет осуществляться доступ в пределах алгоритма.

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

Description – описание параметра. Данное свойство является необязательным.

STEP_ACTION

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

Данный элемент, как и другие типы шагов имеет следующие свойства­:

Name – имя функции или алгоритма ALG, с параметрами, соответствующими данной функции или алгоритму.

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

STEP_FOR

Элемент STEP_FOR задает цикл, в рамках которого с данными осуществляются однотипные операции.

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

Start – задает начало цикла. В блоке Start могут быть описаны начальные значения нескольких элементов. Это могут быть как числовые параметры, например, начальный угол наклона прямой, так и параметры, являющиеся объектами, как в случае задания начальной точки какого-либо действия. Блок является обязательным

End – задает крайние значения цикла. Данный блок аналогичен блоку Start, за исключением того, что он необязателен. В случае совместного использования блоков Count и Step данный блок не используется.

Count – блок, задающий количество повторений тела цикла. Данный блок является обязательным, за исключением указания блоков Start, End и Step, и использования лишь одной изменяющейся переменной в цикле.

Step – шаг изменения переменной цикла. Числовой параметр. При отсутствии блока Count его использование обязательно.

Trace – траектория изменения параметра цикла. Используется в том случае, если изменяемый параметр – точка, и расположение следующей точки определяется какой либо линией, как прямой, так и кривой. Может принимать значения: 1) line – изменение параметра линейно. Это значение по умолчанию. 2) «имя_объекта» - один из объектов модели данных – некая кривая, либо прямая. Если данный параметр задан, то Start и End обязательно должны принадлежать данной линии.

STEP_FOREACH

Данный элемент задает цикл, в котором над множеством элементов производятся однотипные операции. Для описания множества элементов используется слово Set. У данного элемента также указывается свойство Name – имя множества.

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

STEP_IF

Условный оператор задается с помощью свойств:

Condition – условие оператора:

IFTrue – ветвь шагов, исполняемых при выполнении условия;

IFFalse – ветвь шагов, исполняемых при невыполнении условия.

Они соответственно обозначают условие, начало блока, выполняемого в случае его истинности, и начало блока, выполняемого, если условие неверно.

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

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

Выделим основные шаги и представим код программы реализующей данный алгоритм:

1. Нахождение опорных точек – точек пересечения проекции плоскости с проекцией конуса на фронтальной плоскости.
   
2. Проведение между точками A и B вспомогательных секущих плоскостей h – горизонтальных плоскостей, проецирующихся на фронтальной плоскости в виде отрезков.
   
3. Нахождение пересечения плоскости Д и вспомогательных плоскостей во фронтальной проекции.
   
4. Вычисление радиуса окружностей – проекций пересечения конуса и вспомогательной плоскости h в горизонтальной плоскости.
   
5. Проведение в горизонтальной проекции окружностей с вычисленными радиусами.
   
6. Проецирование точек пересечения, найденных на шаге 3) на горизонтальную плоскость для нахождения точек сечения. Точками сечения будут являться точки пересечения проекции и окружностей, полученных на шаге 5).
   
7. Повторение шагов 2) - 6).
   
8. Соединение полученных точек плавной кривой.
   

Представим код, реализующий данный алгоритм:

Algorithm

Name = ConeIntersection

Description = “алгоритм построения сечения конуса плоскостью”

Input

Name = Cone

Type = Cone (vertical. V: Height, Radius, Point; H: Center)

Description = “конус”

Input

Name = Plane

Type = Plane (fp. V: Point1, Point2)

Description = “плоскость”

Step_Action

Name = FindIntersection(Plane,Cone)

Step_For

Name = FindingOnePoint

Description = “цикл, в шаге которого находится одна искомая точка”

Start = LastStep.GetResult(1)

End = LastStep.GetResult(2)

Count = 10

Step_Action

Name = MakeLine(horizontal. V: Height)

Step_Action

Name = FindIntersection(LasStep, Plane)

Step_Action

Name = FindIntersection(Cone, Steps.StepNavigate(-2).GetResult)

Step_Action

Name = Measure(Steps.StepNavigate(-1).GetResult(1), Steps.StepNavigate(-1).GetResult(2))

Step_Action

Name = MakeCircle(H: Cone.H.Center, LastStep/2)

Step_Action

Name = MakeProjection(VH: Steps.StepNum(“2.2”))

Step_Action

Name = FindIntersection(Steps.StepNum(“2.5”), LastStep)

Step_Action

Name = MarkOutput(LastStep)

Step_For_End

Заключение

Предложенный язык описания алгоритмов начертательной геометрии и инженерной графики позволяет в достаточно простой форме реализовывать даже сложные алгоритмы.

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

Список литературы

Гордон В. О. Курс начертательной геометрии. М.: Государственное изд-во технико-теоретической литературы, 1957.

Казаков М. А., Столяр С. Е. Визуализаторы алгоритмов как элемент технологии преподавания дискретной математики и программирования / Международная научно-методическая конференция “Телематика-2000”. СПб.:СПбИТМО (ТУ) 2000, с. 189-191.

Шалыто А. А., Туккель Н. И. От тьюрингова программирования к автоматному // Мир ПК. 2002. №2, с. 144-149.