В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40




Скачать 154.59 Kb.
НазваниеВ. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40
Дата публикации12.04.2013
Размер154.59 Kb.
ТипДокументы
uchebilka.ru > Математика > Документы

Інструментальні засоби і середовища програмування

УДК 681.3

об одном подходе к Проектированию АЛГЕБРАИЧЕСКИХ типов данных

В.С. Песчаненко

Институт кибернетики им. В.М. Глушкова НАН Украины,

03680,Киев, проспект Академика Глушкова, 40

vladim@ksu.ks.ua

Робота присвячена методам вирішення проблем які виникли при проектуванні алгебраїчних типів даних шкільної системи комп’ютерної алгебри Терм. Описана ієрархія алгебраїчних типів даних цієї системи, розглянуті основні методи проектуванні та реалізації алгебраїчних обчислень, які ґрунтуються на використанні технологій символьних перетворень.
The article is dedicated to the methods for solving the problems, aroused during design of school computer algebra system TerM algebraic data type. The algebraic data type hierarchy of the present system is described in the article; also the basic methods of design and realization of the algebraic computing, based on the usage of symbolic conversion technologies, are examined.

Введение


Существующие коммерческие системы компьютерной алгебры (Derive, Mathematica, Maple, MathCad и др.) в основном решают проблему поддержки профессиональной математической деятельности. Отметим, что использование таких систем в учебных целях в школе ограничено. Среди нескольких причин выделим главную: они ориентированы на получение ответа математической задачи, а не на получение хода ее решения, что является главной целью ученика. Поэтому системы компьютерной алгебры учебного назначения (системы школьной компьютерной алгебры) должны поддерживать ход решения математической задачи. Эта поддержка заключается либо в генерации шага решения задачи в соответствии с командой пользователя, либо в проверке математической правильности шага решения, если он выполнен пользователем.
^

Математическая деятельность пользователя заключается в следующем:


  • построении математических объектов;

  • распознавании свойств математических объектов;

  • преобразованиях математических объектов.

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

  • математические объекты определены в предметной области в виде мате­ма­ти­ческих конструкций;

  • свойства математических объектов описаны аксиоматически;

  • преобразования объектов определены в виде списка допустимых (элементарных) преобразований.

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

  • распознает некоторое свойство математического объекта, определенного в решаемой задаче;

  • преобразует этот объект.

Таким образом, процесс решения задачи – последовательность вида

,
T1 T2 Ti Tn





S1 S2 . . . Si Si+1 . . . Sn
где Si – математические объекты, Ti – их элементарные преобразования.

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

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

Еще одна принципиальная отличительная особенность ТерМ заключается в том, что в системе реализован полный набор учебных объектов, что позволяет эффективно организовать учебный процесс. Это – дидактические материалы (математический учебник, задачник, справочник, тетрадь) и математические инструменты (среда решения (задач) решатель и графики). Общая объектная модель системы ТерМ показана на рис. 1.

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

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

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

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

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

Постановка задачи


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

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

Проектирование иерархии алгебраических типов ТерМ осуществлялось в терминах частично-упорядоченных многосортных алгебраических систем [2].

Многосортные алгебры


Под многосортной алгеброй (МСА) ^ Т будем понимать многоосновную алгебраическую систему A(A1,..,Ak) с главным носителем А, носителями алгебр аргументов Σ, сигнатурой предикатов П, сигнатурой констант Е (выделенных элементов носителя).
. (1)

Алгебры аргументов, в свою очередь, определяются как многосортные. Например, на рис. 2 показан фрагмент структуры многоосновности. Стрелочки, проведенные на нем из А1,…,Ак в А означают, что сигнатура МСА А определяется через сигнатуры А1,…,Ак.

Мы описываем структуру МСА в терминах наследования алгебр, расширения алгебр и морфизмов алгебр.

Алгебраэлемент иерархии МСА описываются сигнатурой, носителем, алгоритмами реализации операций сигнатуры и набором аксиом.

Проектирование осуществляется в 2 этапа: прототипирования, анализ свойств прототипа и реализации окончательной версии.

Прототипирование заключается в построении МСА в терминах наследования, расширения, морфизмов и реализации построенной иерархии на языке АПЛАН в системе алгебраического программирования АПС [3].

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

Наследование


Механизм наследования является одним из основных характерных меха­низмов для объектно-ориентированного проектирования программных систем. При проектировании алгебр данных использование этого механизма имеет свои отличительные особенности. На содержательном уровне свойство наследования (B наследует A) означает, что:

  1. сигнатура B наследует сигнатуру A; На B могут быть определены собственные элементы сигнатуры-операции, константы и отношения;

  2. на B могут быть доопределены правила вычислений (интерпретирующие правила) для каждого элемента сигнатуры A;

  3. на B могут быть выполняться некоторые дополнительные свойства (например: коммутативность, ассоциативность, идемпотентность, отсутствие делителей нуля и т.д).

Пусть , – две многосортные алгебры, в которых дополнительно к (1) описаны еще системы аксиом AXТ, AXQ. Будем говорить, что алгебра Q наследует алгебру T, если

A ◄ B, ΣT ◄ ΣQ, ΠT ◄ ΠQ, ΕT  ΕQ, AXT  AXQ. (2)

Обозначение ^ A ◄ B означает, например, что носитель B является уточнением носителя A в том смысле, что любой элемент B можно получить из некото­рого элемента A путем доопределения (уточнения) некоторых фрагментов его структуры. Аналогичный смысл имеют и другие обозначения в (2). Некоторая алгебра может наследовать свойства и нескольких алгебр. В этом случае наследуемые свойства должны быть совместимыми.

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

Примеры наследования:

  1. Абстрактная группа наследует свойства абстрактной полугруппы. В этом примере свойства полугруппы дополнены операцией a-1 и соот­вет­ствующей аксиомой.

  2. Абстрактное коммутативное кольцо наследует свойства абелевой группы (группы по сложению) и коммутативной полугруппы. Например, показано, множественное наследование. (рис. 3).

Стрелочки, проведенные из А1,…,Ак в А на рис. 3 означают a), б), в) (см. выше).

Расширения

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

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

Примером расширения может быть построение поля рациональных чисел ^ R как расширения кольца целых чисел Z:

  • элементами расширения называют конструкции вида a/b, где ,

; (3)

  • на множестве R определяют операции кольца Z(+,-,*). Например,

Reduce; (4)

  • расширяют сигнатуру R, дополняя её операциями (/,()-1). Например,

Reduce; (5)

  • осуществляют вложения кольца Z в R, определяя изоморфизм Z в R тождеством вложения

a/1=a (функция Reduce) (6)

На рис 4, например, стрелка из А1 в А2 означает, что в А2 является расширением А1 определенное с помощью конструкции и вложения.

Морфизмы

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

Подобные алгебры А и В называются изоморфными, если существует взаимнооднозначный морфизм: .

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

Алгебра А – рациональных чисел над полем целых чисел. Это означает, что элементы А имеют вид: .

Алгебра В – десятичных периодических дробей над полем целых чисел в сигнатуре обобщенной числовой функции PeriodNumeric. Это означает, что элементы В имеют вид: , где Whole – целая часть, PPeriod – число до периода, Period – число периода.

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

Поэтому должны быть описаны алгебры А и В, причем вычисления в В описываются в терминах изоморфизма следующим образом:

, (7)

. (8)

Если f,g – элементы алгебры В, и * – одна из бинарных операций сигнатура В, то результат f*g вычисляется по формуле: f *( g =  -1((f) * (g)).

В более общем виде, если F – выражение над А, то его значение вычисляется как .

Двойная стрелка на рис. 5 из А1 в А2 означает, что реализованы , а стрелка из А2 в А3.
^

Алгебраические типы данных ТерМ


В результате проектирования алгебраических типов данных ТерМ получена следующая диаграмма наследования (рис. 6), морфизмов (рис. 7), расширений (рис. 8).

MultyRadical – алгебра данных (АД) с сигнатурой и носителем . MultyRadical – кольцо радикалов над полем ^ Coef.

Radical – АД с сигнатурой и носителем . Radicalполугруппа с одним образующим элементом.

Complex – алгебра данных (АД) с сигнатурой и носителем . Complex– поле над полем Coef.

Coef, RatPolynom, RatMultyPolynom – будут рассмотрены подробно на рис. 8.

Изоморфизм Rational и PeriodNum был описан выше. Их изоморфизм с Real – известен. MultyPolinom – описанный на рис.9.

RecPolynom – АД с сигнатурой и носителем .

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

Coef – АД с сигнатурой и носителем для которого могут быть определены такие операции. ^ Coef – поле. Эта АД используется для обозначения коэффициентов МСА.

Degree –АД с расширенной сигнатурой и носителем . Degree – полугруппа с одним образующим элементом над полем Coef.

LinMonom – АД с сигнатурой (деление и умножение на число) и носителем . LinMonom – одномерное векторное пространство над полем ^ Coef..

MultyDegree – АД с сигнатурой и носителем . MultyDegree – расширение Degree по операции умножения, т.е. полугруппа степеней многих переменных над полем Coef..

Monom – АД с сигнатурой и носителем . Monom – расширение Degree по операции умножения, т.е. полугруппа мономов с одним образующим элементом над полем Coef..

LineSpace – АД с сигнатурой (сложение и умножение на число) и носителем . LineSpace – расширение LinMonom по операции сложения, т.е. векторное пространство линейных комбинаций над полем Coef..

MultyMonom – АД с сигнатурой и носителем . MultyMonom – расширение MultyDegree по операции умножения, т.е. полугруппа мономов многих переменных над полем Coef.

Polynom – АД с сигнатурой и носителем . Polynom – расширение Monom по операции сложения, т.е. кольцо многочленов одной переменной над полем Coef.

Affspace – АД с сигнатурой (умножение и деление на число) и носителем . AffSpace – расширение LinSpace по операции сложения с числом, т.е. аффинное пространство линейных комбинаций со свободным членом над полем Coef.

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

RatPolynom – АД с сигнатурой и носителем .RatPolynom – расширение Polynom по операции деления, т.е. поле рациональных функций от одной переменной над полем Coef.

RatMultyPolynom – АД с сигнатурой и носителем . RatMultyPolynom – расширение MultyPolinom по операции деления, т.е. поле рациональных функций многих переменных над полем Coef.

Реализация многосортной алгебры, выполненная в соответствии с диаграммами (рис. 6, рис. 7, рис. 8) позволила полностью реализовать стандартные алгоритмы символьных вычислений в классической алгебре. Однако эта реализация имеет недостатки: во-первых, рекурсивный спуск при вычислениях «проходит» около 10 систем переписываний; во-вторых, в тех случаях, когда схемы расширений алгебр подобны, желательно использовать методы параметрического программирования, что не предусмотрено диаграммой расширений (рис. 8).

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

Отметим, что эти проблемы можно решить средствами инсерционного программи­рования [4] и перенести на нижний уровень только числовые алгебры. В данной версии, однако, использовалась техника параметрического программирования. После прототипирования и определения основных свойств нижнем уровне были реализованы алгебры данных, указанные на рис. 9.

Алгебры данных ^ Variable, Coef, Degree, MultyDegree – остались содержательно такими же, как и на рис. 7.

Factor – АД с сигнатурой и носителем . Factor – расширение Degree, MComponent по операции умножения, т.е. полугруппа над полем ^ Coef.

LinSpase – АД с расширенной сигнатурой (умножение и деление на число) и носителем . LinSpace – расширение Factor по операции сложения, т.е. кольцо над полем Coef.

AffSpace – АД с расширенной сигнатурой (умножение и деление на число) и носителем . AffSpace – расширение Component по операции сложения, т.е. кольцо со свободным членом над полем Coef

GLAlgebra – АД с сигнатурой и носителем . RatPolynom – расширение Polynom по операции деления, т.е. поле частных над полем Coef.

Используя конкретное значение правой части в определении носителя Factor, несложно установить гомоморфизм между соответствующими алгебрами рис. 8 и рис. 9.

Поле такой реализации для проверки оптимальности перепроектированной диаграммы расширений МСА ТерМ, был поставлен вычислительный эксперимент. Небольшая часть результатов представлена в таблице.

Таблица. Результаты вычислительного эксперимента МСА ТерМ




Пример

Время вычисления

Используемая память

Рис. 9



38 с

121 Мб

Рис. 10

3 с

4 Мб

Рис. 9

Время загрузки ядра сиcтемы

10 с

32 Мб

Рис. 10

2 с

1 Мб


Таким образом, реализация на нижнем уровне расширений МСА системы решила вышеописанные проблемы.

Заключение


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

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

Опыт и традиции разработки приложений с использованием APS накапливаются и используются в Институте кибернетики им. В.М. Глушкова НАН Украины, Херсонском государственном университете и в других научных заведениях.

Выражаю благодарность научным руководителям А.А. Летичевскому, М.С. Львову, за постоянный интерес, руководство в проектировании ТерМ, адаптации APS и ценные замечания по содержанию данной работы.





  1. Львов М.С. Терм VII – шкільна система комп’ютерної алгебри. Комп’ютер у школі та сім’ї. – 2004. – № 7. – С. 27–30.

  2. Математическая логика в програм-мировании: Сб. статей М34 1980-1988 / Пер. c англ. – М.: Мир, 1991. – 408 c.

  3. Kapitonova U., Letichevsky A., Volkov V., Lvov M. Tools for solving problems in the scope of algebraic programming. Lectures Notes in Computer Sciences. – 1995 –№ 958.. – PP. 31–46.

  4. Капитонова Ю.В., Летичевский А.А., Волков В.А.. Дедуктивные средства системы алгебраического программирования // Кибернетика и системный анализ, 2000, 1, C. 17–35.

  5. Volkov V., Kuprienko A., Lvov M. Applied Computer Support of Mathematical Training. Proc. of Internal Work Shop in Computer Algebra Applications, Kiev., 1993. – PP. 25–26.

  6. Lvov M. AIST: Applied Computer Algebra System. Proc. of ICCTE’93. Kiev. – pp. 25–26.

  7. Песчаненко В.С. Розширення стандартних модулів системи алгебраїчного програмування APS для використання у системах навчального призначення. Науковий часопис НПУ ім. МП Драгоманова Сер. № 2. Комп’ютерно-орієнтовні системи навчання –К.: НПУ ім. М.П. Драгоманова. 2005 – №3(10).




© В.М. Зінькович, Є.І. Моренцов, 2006

ISSN 1727-4907. Проблеми програмування. 2006. №2-3. Спеціальний випуск

Добавить документ в свой блог или на сайт

Похожие:

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconБ. Е. Панченко Институт кибернетики им. В. М. Глушкова нан украины,...
Институт кибернетики им. В. М. Глушкова нан украины, 03187, проспект Академика Глушкова, 40

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconА. А. Пантелеймонов Институт кибернетики им. В. М. Глушкова нан украины...
Рассматривается возможность расширения синтаксиса, зависимого от языка реализации интерпретатора. Описываются особенности реализации,...

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconН. И. Алишов Институт кибернетики им. В. М. Глушкова нан украины...
Теоретические основы и практические задачи оптимизации времени доставки информационных ресурсов в распределенных системах

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconД. И. Щетинин Институт кибернетики им. В. М. Глушкова нан украины...
В работе представлены наиболее распространенные виды параллельных реляционных субд. Определяются понятия времени выполнения запроса...

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconПаралельне програмування. Розподілені системи І мережі
Институт программных систем нан украины, проспект Академика Глушкова, 40, Киев, 03187

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconИнститут программных систем нан украины 03187, Киев, проспект Академика Глушкова, 40
Распараллеливание алгоритмов функционирования классификатора со случайными подпространствами

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconМодель мультиагентной системы для е-бизнеса и технология ее програмМной реализации
...

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconТехнология имитационного моделирования процессов жизнеобеспечения...
Институт программных систем нан украины, 03187, Киев-187, проспект Академика Глушкова, 40. тел.(044) 266-51-69

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconД. М. Рябко Физико-технический учебно-научный центр нану, кафедра...
Физико-технический учебно-научный центр нану, кафедра Института кибернетики им. В. М. Глушкова

В. С. Песчаненко Институт кибернетики им. В. М. Глушкова нан украины, 03680,Киев, проспект Академика Глушкова, 40 iconДорошенко Институт программных систем нан украины 03187, Киев, проспект Академика Глушкова, 40/5
Для демонстрации этого подхода разработан прототип системы моделирования. Рассматривается пример декларативного описания протокола...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<