Системы компьютерной алгебры

Компьютерная алгебра

1. Системы компьютерной алгебры

Краткая история символьных вычислений

Краткая история символьных вычислений

История математики до компьютерной эры содержит много примеров трудоемких вычислений.
Некоторые вычисления сводились к сложным и громоздким преобразованиям формул,
другие вычисления использовали небольшие формулы, но требовали выполнения операций с большим количеством цифр в числах.
Великий Леонард Эйлер (1707 – 1783) был непревзойдённым мастером формальных выкладок и преобразований, в его трудах многие математические формулы и символика получили современный вид (например, ему принадлежат обозначения для е и π).
Наглядными примерами мастерства Эйлера служат его вычисление суммы обратных квадратов и получение необычайной формулы, связывающей суммы делителей натуральных чисел [[1], стр. 39–43, 11–122].
[1] Пойа Д. Математика и правдоподобные вычисления. – М.: «Наука», 1975. – 464 с.

Краткая история символьных вычислений

В 19 веке очень много вычислений было проделано в астрономии.
Например, французский математик Урбен Леверье проводил расчет орбиты Нептуна. Расчет был основан на аналитических вычислениях возмущенной орбиты Урана. И этот расчет собственно и привел к открытию Нептуна.

Краткая история символьных вычислений

Впечатляющие вычисления с карандашом и бумагой проделал французский астроном Чарльз-Евгений Делоне для вычисления орбиты Луны.
Он вывел около 40000 формул. На их вывод потребовалось 10 лет и еще 10 лет ушло на проверку формул. Окончательная формула занимала 128 страниц его книги с результатами работы.
Проверка его аналитических преобразований было проведена двумя американскими математиками с помощью компьютера в 70-е годы 20 века. Компьютеру потребовалось двое суток работы.

Краткая история символьных вычислений

Большие усилия тратили математики на определение числа π, вручную вычисляя большое количество цифр.
Так, например, наилучший результат к концу XIX века был получен англичанином Вильямом Шенксом.
Он потратил 15 лет для того, чтобы вычислить 707 цифр, хотя из-за ошибки только первые 527 были верными. Он использовал формулу Мэчина (Johm Machin, 1680 – 1751) .
Ошибку Шенкса обнаружил в 1944 году Фергюсон; он считал по формуле, подобной формуле Мэчина на настольном механическом калькуляторе.

                                          ,

Краткая история символьных вычислений (near)

Э́дгар А́ллан По (1809 -1849) — американский писатель, поэт, является представителем американского романтизма. Наибольшую известность получил за свои «мрачные» рассказы. Создатель формы современного детектива.

Ворон
…
And the silken, sad, uncertain rustling of each purple curtain Thrilled me - filled me with fantastic terrors never felt before; So that now, to still the beating of my heart, I stood repeating "Tis some visiter entreating entrance at my chamber door - Some late visiter entreating entrance at my chamber door; - This it is and nothing more."
…
Шелковый тревожный шорох в пурпурных портьерах, шторах Полонил, наполнил смутным ужасом меня всего, И, чтоб сердцу легче стало, встав, я повторил устало: "Это гость лишь запоздалый у порога моего, Гость какой-то запоздалый у порога моего, Гость - и больше ничего".
…
Перевод Ю. Зенкевича

Краткая история символьных вычислений (near)

Mike Keith (born 1955) is an American mathematician, software engineer, and author of works of constrained writing

Poe, E. Near a Raven
Midnights so dreary, tired and weary.      Silently pondering volumes extolling all by-now obsolete lore.  During my rather long nap - the weirdest tap!      An ominous vibrating sound disturbing my chamber's antedoor.          "This", I whispered quietly, "I ignore".
Perfectly, the intellect remembers: the ghostly fires, a glittering ember.      Inflamed by lightning's outbursts, windows cast penumbras upon this floor.  Sorrowful, as one mistreated, unhappy thoughts I heeded:      That inimitable lesson in elegance - Lenore -          Is delighting, exciting...nevermore.
Ominously, curtains parted (my serenity outsmarted),      And fear overcame my being - the fear of "forevermore".  Fearful foreboding abided, selfish sentiment confided,      As I said, "Methinks mysterious traveler knocks afore.          A man is visiting, of age threescore”.
………………………………………………………
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282…
Всего 740 цифр

Краткая история символьных вычислений

В начале 50-х годов стали появляться первые программы, производящие частично аналитические вычисления.
В 1951 году с помощью компьютера EDSAC 1 было открыто наибольшее известное простое число – 180(2^127 – 1)^2 + 1 =
5210644015679228794060694325390955853335898483908056458352183851018372555735221 (79 цифр)

По состоянию на 29 августа 2014 года, наибольшее известное простое число равняется 



и содержит 17 425 170 десятичных цифр. Найдено 25 января 2013 года математиком Кертисом Купером, участником проекта распределенных вычислений GIMPS (Great Internet Mersenne Prime Search); это 48-е простое число Мерсенна. Простое число длиной в пять романов «Война и мир».

                                          ,

Краткая история символьных вычислений

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

В 1953 было показано, как алгоритмы в теории групп могут быть реализованы на компьютере.

                                          ,

Что такое компьютерная алгебра?

Что такое компьютерная алгебра?

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

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

Что такое компьютерная алгебра?

В чем основные отличия символьных вычислений от численных и почему возник термин "компьютерная алгебра" ?

Когда мы говорим о вычислительных методах, то считаем, что все вычисления выполняются в поле вещественных или комплексных чисел. В действительности же всякая программа для ЭВМ имеет дело только с конечным набором рациональных чисел, поскольку только такие числа представляются в компьютере.
Для записи целого числа отводится обычно 16 или 32 двоичных символа (бита), для вещественного — 32 или 64 бита. Это множество не замкнуто относительно арифметических операций, что может выражаться в различных переполнениях, например, при умножении достаточно больших чисел или при делении на маленькое число.

Что такое компьютерная алгебра?

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

Что такое компьютерная алгебра?

Набор объектов, применяемых в символьных вычислениях, весьма разнообразен, в частности, в них используется значительно большее множество рациональных чисел.
Это множество все равно остается конечным, но ограничения на допустимые размеры числа (количество знаков в его записи) связаны обычно с размерами оперативной памяти ЭВМ, что позволяет пользоваться практически любыми рациональными числами, операции над которыми выполняются за приемлемое время.
При этом компьютерные операции над рациональными числами совпадают с соответствующими операциями в поле рациональных чисел.
Таким образом, снимается одна из основных проблем вычислительных методов — оценка погрешности вычислений.

Что такое компьютерная алгебра?

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

Что такое компьютерная алгебра?

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

Системы компьютерной алгебры

Системы компьютерной алгебры можно условно разделить на системы общего назначения и специализированные. К системам общего назначения относятся MACSYMA, REDUCE, MATEMATICA, MAPLE и другие системы.

Macsyma является системой компьютерной алгебры, которая первоначально разрабатывалась с 1968 по 1982 (первая распространяемая версия появилась в 1978 году) в Массачусетском технологическом институте как научный проект MAC (Mathematics and Computation), а затем стала продаваться как коммерческий продукт Maxima (компания Symbolics, последняя версия 2.4, 1999 г).
Это была первая общего назначения символическая система математики и одна из самых ранних систем, основанная на математических знаниях; многие его идеи были позже восприняты Mathematica, Maple и другими системами. Macsyma была реализована на МасLisp.

Системы компьютерной алгебры

$2,275 (Commercial), $2,155 (Government), $1245(Academic), $239 (Personal Edition), $99 (Student), $79 (Student, 12-Month term)

Maple начала разрабатываться в 1980 сотрудниками Symbolic Computation Group в Университете Waterloo (первая распространяемая версия в 1984 году). С 1988 года система продается компанией Maplesoft (версия 17, 2013).
Фундамент Maple составляет небольшое ядро, написанное на C. Это ядро в свою очередь обеспечивает функционирование языка Maple. Функциональность системы основана на различных библиотеках. Различные алгоритмы Maple используют численные данные в разных форматах. Символические выражения хранятся в памяти как направленные ациклические графы. Стандартный интерфейс и вычислительный интерфейс реализованы на Java.

Системы компьютерной алгебры

В конце прошлого века получила широкое распространение и сейчас быстро развивается система Mathematica. Ее успех в значительной степени объясняется ее широкими графическими возможностями, а также электронной документацией, которую можно рассматривать как электронную библиотеку, посвященную различным разделам математики и информатики.
$2,495 (Professional), $1095 (Education), $140 (Student), $69.95 (Student annual license)  $295 (Personal)

Системы компьютерной алгебры

Системы компьютерной алгебры в СССР.
Автоаналитик (Сибиряков Г. В., Арайс Е. А., Шутенков А. В., Гельфман Б. Ш., Зюзьков В. М.)

Система Mathematica

www.wolfram.com

Сайт рускоязычной поддержки: http://wolframmathematica.ru/

Система Mathematica

www.wolfram.com

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

Система была задумана Стивеном Вольфрамом (физик, математик и программист) и в дальнейшем разработана в компании Wolfram Research (Шампейн, штат Иллинойс, США). Начало разработки – 1986 г.; первая версия – 1988 г.; последняя 10-я версия – 9 июля 2014 г.

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

Система Mathematica Возможности и особенности

Библиотека традиционных и специальных математических функций.
Инструменты для работы с матрицами и данными, включая поддержку разреженных массивов.
Поддержка комплексных чисел, рациональны и вещественных чисел произвольной точности, интервальной арифметики и символьных вычислений.
Поддержка 2D и 3D-данных и функций визуализации и анимации.
Решение систем уравнений, диофантовых уравнений, обыкновенных дифференциальных уравнений, уравнений в частных производных, дифференциальных алгебраических уравнений, дифференциальных уравнений с задержкой аргумента, стохастических дифференциальных уравнений и рекуррентныx соотношений.
Численные и символические инструменты для классического и дискретного анализа.
Библиотеки многомерной статистики, включая интерполяцию и аппроксимацию данных, проверку гипотез, и расчеты вероятности и математического ожидания для более 100 различных распределений.

Система Mathematica Возможности и особенности

Расчеты и моделирование случайных процессов и очередей.
Локальная и глобальная оптимизации с ограничениями и без них.
Язык программирования Wolfram поддерживает различные парадигмы: процедурное, функционально и объектно-ориентированное программирование. Ещё один стиль программирования, основанный на правилах преобразований, непосредственно присущ системе, поскольку именно он лежит в основе возможности выполнения алгебраических преобразований.
Инструментарий для создания пользовательского интерфейса для расчетов и приложений.
Инструменты для 2D и 3D-обработки изображений и морфологической обработки изображений, включая распознавание изображений.
Инструменты для визуализации и анализа графов
Инструменты для задач комбинаторики.
Инструменты для анализа текста, включая регулярные выражения и семантический анализ.

Система Mathematica Возможности и особенности

Инструменты для интеллектуального анализа данных, такие как кластерный анализ, выравнивания последовательностей и сопоставление с образцом.
Библиотека функций теории чисел.
Инструменты для финансовых расчетов.
Инструменты теория групп и тензоров.
Библиотеки для обработки сигналов, в том числе вейвлет-анализ звуков, изображений и данных.
Системы управления библиотеками.
Непрерывные и дискретные интегральные преобразования.
Фильтры импорта и экспорта данных, изображений, видео, звуков, и документов САПР, ГИС и биомедицинских форматов.

Система Mathematica Возможности и особенности

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

Система Mathematica Возможности и особенности

Техническая обработка текстов, включая редактирование формулы и автоматизированную генерация отчетов.
Инструменты для подключения к DLL. SQL, Java,. NET, C + +, Fortran, CUDA, OpenCL и http-систем.
Инструменты для параллельного программирования.
Использование как «свободной формы языкового ввода» (естественного языка пользовательского интерфейса) так и языка Wolfram при взаимодействии с Интернетом.

Система Mathematica Интерфейс

Интерфейс математики состоит из двух частей, ядра и интерфейсного процессора. Интерфейсный процессор – это и есть пользовательский интерфейс, включающий в себя окно редактирования, в которое мы вводим данные, строку меню, палитру инструментов, упрощающих ввод данных. Ядро программы непосредственно выполняет вычисления. Таким образом, типичный процесс взаимодействия пользователя с Mathematica состоит из следующих шагов:
ввод данных в окно редактирования (пользователь и интерфейсный процессор);
отправка введённых данных в ядро для выполнения вычислений (интерфейсный процессор);
выполнение вычислений и отправка обратно в интерфейсный процессор (ядро);
вывод результатов на экран в окно редактирования (интерфейсный процессор).

Система Mathematica Интерфейс

Интерфейсный процессор предоставляет графический интерфейс, который позволяет создавать и редактировать документы Mathematica (называемые notebooks).
Ноутбуки могут содержать программный код вместе с результатами работы, форматированный текст (полученный с помощью редактора Mathematica в виде готового сразу для типографской печати), таблицы, изображения, элементы графического интерфейса и звуки.
Все содержание и форматирование могут быть сгенерированы алгоритмически или интерактивно редактироваться.
Ноутбук может быть структурирован с использованием иерархии ячеек, что позволяет разбивать документ на секции, показывать и прятать различные виды информации.
Документы могут быть представлены в виде слайдов для презентаций. Ноутбуки и их содержание представлены в виде выражений Mathematica, которые могут быть созданы, изменены или проанализированы программы Mathematica.
Это позволяет совершать преобразования в другие форматы, например, TeX или XML.

Система Mathematica Выполнение

Кроме выполнения ноутбуков в среде Mathematica есть несколько способов выполнение приложения, написанного на Mathematica вне среды.
1. Mathematica-код может быть преобразован в код С или автоматически созданный модуль DLL.
2. Mathematica Player Pro является средой выполнения, в которой работают любые приложения Mathematica, но эта среда не позволяет редактировать или создавать код.
3. Бесплатная программа Wolfram CDF Player предусмотрена для запуска ноутбуков Mathematica, которые были сохранены в формате вычислимого документа (CDF). Он также может просматривать стандартные Mathematica файлы, но не запускать их.

Алгоритмы компьютерной алгебры

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

Алгоритмы компьютерной алгебры

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

Представление данных

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

Представление данных

В книге
Д. Кнут. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы
хорошо описано, как представлять числа неограниченной длины и как эффективно выполнять арифметические операции с ними.
Алгоритмы работы со списковыми структурами также хорошо изучены, см.
Д. Кнут. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы

Представление данных

Представление данных

Представление данных

Представление данных

Представление данных

Представление данных

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений

Задача упрощения выражений