Записи с меткой «подпакете»

Улучшенное разложение на простые множители — FactorlntegerECM

Улучшенное разложение на простые множители — FactorlntegerECM
Алгоритм разложения чисел на простые множители, реализованный в ядре Mathematiica 3, способен за 3 часа (на рабочих станциях) разлагать числа, имеющие до 18 цифр. Улучшенный алгоритм в подпакете FactorlntegerECM позволяет увеличить максимальное число цифр до 40. Реализуется разложение следующей функцией:

  • FactorIntegerECM[n] — возвращает один из делителей числа п. Возможны опции FactorSize->q, CurveNumber->b и CurveCountLimit->c.

Примеры применения этой функции:
<<NumberTheory`FactorlntegerECM`
FactorIntegerECM[123456789]
34227
3*5*7*9
945
FactorlntegerECM[945]
189
Функции теории чисел — NumberTheory Functions
В подпакете NumberTheoryFunctions имеется ряд функций, относящихся к теории чисел:

  • SquareFreeQ[n] — дает True, если п не имеет квадратичного фактора, и False в ином случае;
  • NextPrime [n] — дает наименьшее простое число, превосходящее п;
  • ChineseRemainderTheorem[listl, Iist2.] — дает наименьшее неотрицательное целое г, такое что Mod [r, Iist2] ==list1;
  • SqrtMod [d, n] — дает квадратный корень из (d mod п) для нечетного n;
  • PrimitiveRoot [n] — дает примитивный корень п;
  • QuadraticRepresentation [d, n] — дает решение {х,у} для уравнения х 2 + (d у) 2 ==п для нечетного п и положительного d;
  • ClassList[d] — дает список неэквивалентных квадратичных форм дискриминанта d для отрицательного и свободного от квадратов целого d вида 4n+1;
  • ClassNumber [d] — дает список неэквивалентных квадратичных форм дискриминанта d;
  • SumOf Squares [d, n] — дает число представлений целого числа п в виде суммы d квадратов;
  • SumOf SquaresRepresentations [d, n] — дает список представлений целого числа п в виде суммы d квадратов, игнорируя порядок и знаки.

Примеры применения данных функций приведены ниже:
<<NumberTheory`NumberTheoryFunctions`
SquareFreeQ[2*3*5*7]
True SquareFreeQ[50]
False
NextPrime[1000000]
1000003
ChineseRemainderTheorem[{0, 1, 2}, {4, 9,
244
ChineseRemainderTheorem[Range[16], Prime[Range[16]]]
20037783573808880093
SqrtMod[3, 11]
5
SqrtMod[2, 10^64 +57]
876504467496681643735926111996
54610040103361197677707490912
2865
PrimitiveRoot[7]
3
QuadraticRepresentation[l, 13]
{3,. 2}
ClassList[-19]
{{1, 1, 5}}
ClassNumber[-10099]
25
SumOfSquaresRepresentations[3, 100]

{{0, 0, 10}, (0, 6, 8}}

Решение линейных уравнений с трехдиагональной матрицей — Tridiagonal

Решение линейных уравнений с трехдиагональной матрицей —Tridiagonal
При решении линейных уравнений часто встречаются матрицы особой формы — трехдиагональные. Подпакет Tridiagonal имеет функцию для решения линейных уравнений с такой матрицей:

  • TridiagonalSolve [a,b, с, г] — решение системы линейных уравнений с трехдиагональной матрицей m. х==г (диагонали представлены векторами а, b и с, вектор свободных членов — г).

Пример применения данной функции:
<<LinearAlgebra` Tridiagonal`
{а, b, с} = {{1, 2, 3}, {4, 5, б, 7}, {10, 9, 8}}
{{1, 2, 3}, {4, 5, 6, 7}, {10, 9, 8}}
m = Table[Switch[ j-i, -1, a[[j]], 0, b[[jj], 1, c[[j-l]], _, 0], {i, 4}, {j, 4}]//MatrixForm
TridiagonalSolve[a, b, c, {8, 3, 4, 5}
С учетом представленных функций и функций ядра набор матричных средств системы Mathematica является одним из наиболее полных. В области решения задач в численном виде он несколько уступает лишь специализированной матричной системе MATLAB 5.0/5.3.
Расширение в теории чисел
 
Мы уже описывали уникальные возможности систем Mathematica 3/4 в области обработки чисел и численных вычислений. Эти возможности существенно расширяет пакет NumberTheory, содержащий функции, реализующие алгоритмы теории чисел. Данный раздел посвящен знакомству с этим пакетом. далее…

Геометрические расчеты — пакет Geometry

Геометрические расчеты — пакет Geometry
 
В этом разделе описан пакет Geometry, содержащий ряд функций, полезных при выполнении геометрических расчетов. В основном это функции, относящиеся к построению регулярных полигонов на плоскости и полиэдров в пространстве. Кроме того, в пакете есть функции, задающие вращение фигур на плоскости и в пространстве.
Характеристики регулярных полигонов и полиэдров — Polytopes
Подпакет Polytopes содержит ряд функций для регулярных полигонов (многоугольников):

  • NumberOfVertices [р] — число вершин углов полигона;
  • NumberOfEdges [p] — число сторон полигона;
  • NumberOf Faces [p] — число граней полигона;
  • Vertices [р] — список координат вершин углов полигона;
  • Area [р] — площадь полигона при длине каждой стороны, равной 1;
  • InscribeciRadius [р]— радиус вписанной в полигон окружности;
  • CircumscribedRadius [р] — радиус описывающей полигон окружности.

В этих функциях наименование полигона р может быть следующим (в скобках дано число сторон):
Digon (2)
Triangle (3)
Square (4)
Pentagon (5)
Hexagon (6)
Heptagon (7)
Octagon (8)
Nonagon (9)
Decagon (10,)
Undecagon (11)
Dodecagon (12)
На0 показаны примеры применения некоторых из этих функций и построение крупными точками вершин полигона — Пентагона (пятиугольника).
Для объемных фигур — полиэдров — имеются следующие функции:

  • NumberOfVertices [р] — число вершин углов полиэдра;
  • NumberOfEdges [р] — число сторон полиэдра;
  • NumberOf Faces [р] — число граней полиэдра;
  • Vertices [p] — список координат вершин углов полиэдра;
  • Area [p] — площадь полиэдра при длине каждой стороны, равной 1;
  • InscribedRadius [р] — радиус вписанной в полиэдр окружности;
  • CircumscribedRadius [р] — радиус окружности, описывающей полиэдр;
  • Volume [p] — объем полиэдра;
  • Dual[p] — дуальный полиэдр;
  • Schlafli[p] — символ полиэдра.

Здесь наименование полиэдра может быть следующим:
Tetrahedron (4)
Cube (6)
Octahedron (8)
Didecahedron (12)
Icosahedron (20)
Примеры применения функций полиэдров представлены ниже:
Volume[Octahedron]
(Корень из 2) /3
Vertices [Octahedron]
{{0, 0, 1.41421}, {1.41421, 0, 0}, {0, 1.41421, 0},
{0, 0, -1.41421}, {-1.41421, 0, 0}, {0, -1.41421, 0}}
Dual [Octahedron]
Cube
InscribedRadius [Octahedron]
1/(Корень из 6)
GircumscribedRadius [Octahedron]
1/(Корень из 2)
 
Вращение фигур на плоскости и в пространстве — Rotations
Для задания поворота плоских фигур на заданный угол в подпакете Rotations заданы следующие функции:

  • RotationMatrix2D[theta] — дает матрицу для поворота на угол theta в двух измерениях;
  • Rotate2D [vec, theta] — поворачивает вектор vec по часовой стрелке на угол theta;
  • Rotate2D[vec,theta,{x,y}] — поворачивает вектор vec по часовой стрелке на угол theta относительно точки с координатами {х, у}.

Рисунок иллюстрирует работу с этими функциями.
Аналогичные функции существуют и для поворота трехмерных фигур:

  • RotationMatrix3D [psi, theta,phi] — дает матрицу поворота на заданные углы в трехмерном пространстве;
  • Rotate3D [vec, psi, theta, phi] — поворачивает вектор vec на заданные углы в трехмерном пространстве;
  • Rotate3D [vec, psi, theta, phi,{x,y,z}]— поворачивает вектор vec на заданные углы в трехмерном пространстве относительно точки с координатами {х,у, z}.

Приведем пример вычисления матрицы трехмерного поворота:
RotationMatrix3D[Pi, Pi/2, Pi/6]

{{-(Корень из 3)/2,0,1/2 }},{1/2,0,(Корень из 3)/2},{ 0,1,0,}}

Дискретные перестановки — Permutations

Дискретные перестановки — Permutations
В подпакете Permutations определен ряд функций дискретных перестановок:

  • RandomPermutation [n] — случайные перестановки из n элементов;
  • Ordering [list] — дает перестановки в установленном списком list порядке;
  • ToCycles [perm] — дает циклическую декомпозицию для списка list;
  • FromCycles [ {cicl, cic2,…}] — возвращает перестановки из циклических декомпозиций cic1, cic2, …;
  • PermutationQ [list] — возвращает True, если список list представляет перестановки, и False в ином случае.

Работа функций поясняется следующими примерами:
<<DiscreteMath`Permutations`
RandomPermutation[16]
{16, 12, 11, 5, 3, 4, 9, 14, 2, 8, 15, I, 13, 7, 10, 6}
ToCycles[%]
{{16, 6, 4, 5, 3, 11, 15, 10, 8, 14, 7, 9, 2, 12, 1}, {13}}
FromCycles[%]
{16, 12, 11, 5, 3, 4, 9, 14, 2, 8, 15, 1, 13, 7, 10, 6}
Ordering[%]
{12, 9, 5, 6, 4, 16, 14, 10, 7, 15, 3, 2, 13, 8, 11, 1}
 
Решение рекуррентных разностных уравнений — RSolve
Для решения рекуррентных разностных уравнений в подпакет RSolve введены следующие функции:

  • RSolve [eqn, a [n] , n] — решает рекуррентное уравнение для а [n];
  • RSolve [eqn, a, n] — решает рекуррентное уравнение для функции а;
  • RSolvet {eqnl, eqn2,…}, {al, a2,…},n] — решает систему рекуррентных уравнений, представленных списками.

Ниже представлены примеры применения данных функций:
<<DiscreteMath` RSolve`
RSolve[a[n+l] == 2 a[n], a[n], n]
{{a[n] -> 2nC[l]}}
RSolve[a[n] == a[n-l] + a[n-2], a[0] == a[l] == 1, a[n], n]
RSolve[ a[0] == a[l] == 2,
(n+1) (n+2) a[n+2]- 2 (n+1) a[n+l]- 3 a[n] == 0, a[n], n]
 
Деревья—Tree
Подпакет Tree содержит функции создания и применения древовидных структур, именуемых деревьями. Вот эти функции:

  • MakeTree [list] — создает дерево по информации, представленной в списке list;
  • TreeFind [tree, x] — возвращает позицию наименьшего элемента, превосходящего х в списке list, представляющем дерево.

Действие этих функций поясняют следующие примеры:
<<DiscreteMath` Tree`
MakeTree[{el, e2, е3, е4}]
{{e2, 2), {{el, 1}, {}, {}}, {{e3, 3}, {}, {{e4, 4}, {}, {}}}}
tree = MakeTree[{8.5, 1.2, 9.1, 3.4, 5., 7.6 ,6.4}]
{{6.4, 4}, {{3.4, 2}, {{1.2, 1}, {}, {}}, {{5., 3}, {}, {}}},
{{8.5, 6}, {{7.6, 5}, {}, {}}, {{9.1, 7}, {},{}}}}
TreeFind[tree, 1.2]
1 . .
TreeFind[tree, 1]
0
Для визуализации деревьев служат следующие функции:

  • TreePlot [tree] — строит график дерева tree;
  • ExprPlot [expr] — строит график, представляющий ехрг в виде дерева.

Примеры построения графиков деревьев представлены на8. Верхнп; график построен по данным дерева tree, определенного в приведенных выи: примерах, а нижний — по данным случайного дерева.

Построение графиков деревьев по выражению ехрг с помощью функции ExprPlot демонстрирует9.

Графы и их функции

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

Представление графов

AddEdge

AddVertex

Breadth’FirstTraversal

ChangeEdges

ChangeVertices

CircularVertices

CompleteQ

Contract

DeleteEdge

DeieteVertex

DepthFirstTr aversal

Diameter

DilateVertices

Distribution

Eccentricity

Edges

EmptyQ

FromAd j acencyLists

FromOrderedPairs

FromUnorderedPairs

GraphCenter

GraphComplement

InduceSubgraph

M

MakeSimple

MakeUndirected

Normal! zeVerticesPointsAndLines

Pseudograph

RadialEmbedding

Radius

RankGraph

RankedEmbedding

ReadGraph

RemoveSelf Loops

RootedEmbedding

RotateVertices

ShakeGraph

ShowGraph

ShowLabe 1 edGr aph

SimpleQ

Spectrum

SpringErrbedding

ToAdjacencyLists

ToOrderedPairs

ToUnorderedPairs

TranslateVertices

UndirectedQ

UnweightedQ

Vertices

WriteGraph

Одной из самых важных функций этой группы является функция ShowGraph (показать граф). Она обеспечивает визуальное представление графа, заданного аргументом функции. Покажем работу избранных функций этой группы на нескольких примерах.
На показано построение полного графа и его таблицы. далее…

Пакет дискретной математики DiscreteMath

Пакет дискретной математики DiscreteMath
 
Пакет DiscreteMath задает набор функций дискретной математики. Это прежде всего функции комбинаторики и работы с графами (более 230 функций). Мы вынуждены рассмотреть их только выборочно.
Комбинаторика и ее функции — Combinatorica и CombinatorialFunctions
Несколько функций комбинаторики (Factorial, Factorial2, Binomial, Multinomial, Pochhammer и Fibonacci) могут использоваться без загрузки пакетов расширения. Рисунок демонстрирует работу подпакета Combinatorial-Functions (функции комбинаторики). Определения функций этого пакета есть в справочной базе данных.
Подпакет Combinatorica задает определение ряда функций комбинаторики и теории графов. Ниже представлены имена функций комбинаторики.

далее…