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

Основные числовые системы
Система натуральных чисел
Кольцо целых чисел
Поле рациональных чисел
Система действительных чисел
Поле комплексных чисел

Аналитические преобразования
с помощью компьютера
Особенности аналитических вычислений на компьютерах :
имеется возможность проводить аналитические (и численные)
преобразования без погрешностей;
2) в результате не теряется исходная информация
о характере исследуемого процесса;
3) на этом этапе аналитических вычислений
неустойчивость процесса не проявляется;
4) в ряде случаев наблюдается быстрое разрастание результатов
промежуточных вычислений (то есть объем промежуточных данных
в процессе вычислений очень большой);
5) ввиду упомянутого разрастания результатов резко повышаются
требования к объему памяти и к быстродействию компьютера;
6) резко повышаются требования к предварительному изучению алгоритма:
к оценке его быстродействия,
необходимой памяти и к эффективному представлению результата;
7) имеется возможность производить генерацию программ,
использующих найденные формулы.

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

Эффективность алгоритмов
Качество (эффективность) алгоритма
обычно оценивают асимптотической
сложностью, то есть порядком роста сложности
как функции от числа входов N
при неограниченном росте N
без учета мультипликативных констант.
Пример. Если N входных переменных
обрабатываются за время cN2,
где с – некоторая константа, то
асимптотическая сложность
этого алгоритма есть О(N2) (порядка N2).

Характеристики алгоритмов

Характеристики алгоритмов после ускорения.

В зависимости от порядка сложности и вида результирующих данных алгоритмы компьютерной математики можно отнести к четырем уровням:
1) базовые алгоритмические операции. Считается, что их сложность О(1), хотя они отличаются по сложности битовых операций (например, умножение двух n-разрядных чисел с фиксированной точкой требует О(n2) битовых операций, а сложение О(n));
2) скалярные алгоритмы с вычислительной сложностью О(n). Этот уровень включает в себя вычисление скалярного произведения n-мерных векторов, вычисление значения полинома по схеме Горнера, численное интегрирование и дифференцирование;
3) векторные алгоритмы сложности О(n2) . Сюда включаются умножение матрицы на вектор для вычисления линейных преобразований, вычисления свертки векторов (полиномов) и т.д.;
4) алгоритмы сложности О(n3). Это – матричное произведение, вычисление собственных значений и векторов, обращение матриц, метод наименьших квадратов, решение задач математического программирования, нахождение путей в графе и т.д.

Алгебра
Алгеброй называется упорядоченная пара
, где
А - непустое множество,
V - множество операций на A.
назад

Моноид
Алгебра типа (2, 0), где
A - произвольная непустое множество;
* - ассоциативная бинарная операция на A;
е - нейтральный элемент относительно ,
называется моноидом.
назад

Таким образом, группа – это непустое множество с двумя операциями на нем, бинарной операцией * и унарной | , причем бинарная операция ассоциативна и обладает нейтральным элементом, а унарная – переход к симметрическому элементу относительно бинарной операции.
Алгебра G типа называется группой, если ее главные операции удовлетворяют условиям (аксиомам):
бинарная операция ассоциативна, т.е. ;
в G имеется нейтральный элемент относительно ? , т.е. ;
.
Группа
назад

Кольцо
Кольцом называется алгебра K =〈K,+,-,·,1 〉 типа (2,1,2,0) , главные операции которой удовлетворяют следующим условиям:
1. алгебра K =〈K,+,-〉 – есть абелева группа;
2. алгебра K =〈K,·,1 〉 – есть моноид;
3. умножение дистрибутивно относительно
сложения, т.е.
назад

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

I.
II.
III.
IV.
V.
VI.
Если и
а)
б)
тогда А=N
Система натуральных чисел
Системой натуральных чисел называется алгебра N = , состоящая из некоторого множества N, выделенных в N элементов 0 и 1, бинарных операцией + и ∙ (называемых сложением и умножением соответственно), удовлетворяющих следующим аксиомам:
назад

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

Поле рациональных чисел
Полем рациональных чисел называется поле частных кольца целых чисел. Элементы поля рациональных чисел называются рациональными числами. Обозначим это поле Q .
назад

Система действительных чисел
Системой действительных чисел называется полное архимедовски упорядоченное поле.
назад