Что такое CoCoA?

• CoCoA - это программа, выполняющая вычисления с числами и многочленами.
• Распространяется свободно.
• Работает во многих операционных системах.
• Используется многими специалистами, однако также может быть полезна для выполнения "элементарных" вычислений.

Какие вычисления можно производить с помощью CoCoA?

Очень большие целые числа Рациональные числа Многочлены Системы линейных уравнений

Неотрицательные целые решения Кто лжет? Раскраска географической карты Формула Герона

Очень большие целые числа

Наибольшее "машинное целое" число, доступное на 32-битном компьютере, равно 2^32-1, однако в CoCoA, благодаря мощной библиотеке GMP, можно вычислять значения, достигающие 2^300000: попробуйте!

2^32-1; 

4294967295

2^64-1; 

18446744073709551615

Рациональные числа

CoCoA работает очень точно с дробями: дроби никогда не округляются! Таким образом, 1/3 значительно отличается от 0.3333333333333

(1/3) * 3;

1

0.3333333333333 * 3;

9999999999999/10000000000000

Многочлены

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

(x-y)^2 * (x^4-4*z^4) / (x^2+2*z^2);

x^4 -2*x^3*y +x^2*y^2 -2*x^2*z^2 +4*x*y*z^2 -2*y^2*z^2

Factor(x^4 -2*x^3*y +x^2*y^2 -2*x^2*z^2 +4*x*y*z^2 -2*y^2*z^2);

record[
  RemainingFactor := 1,
  factors := [x^2 -2*z^2,  x -y],
  multiplicities := [1,  2]]
]

Системы линейных уравнений

CoCoA умеет решать системы линейных уравнений. Достаточно записать каждое уравнение f = c в виде многочлена f - c. CoCoA может также решать системы полиномиальных уравнений, однако эта, несколько более сложная задача будет рассмотрена позже. А пока решим систему

x-y+z	=2
3x-z	=-6
x+y	=1

System := ideal(x-y+z-2, 3*x-z+6, x+y-1);
ReducedGBasis(System);

[x +3/5,  y -8/5,  z -21/5]

Следовательно, ответ: (z=21/5, x=-3/5, y=8/5)

Неотрицательные целые решения

Найдем тройки неотрицательных целых чисел, являющиеся решениями следующей системы:

3x - 4y + 7z	=2
2x - 2y + 5z	=10

M := mat([[3, -4, 7, -2], [2, -2, 5, -10]]);
H := HilbertBasisKer(M);
L := [h In H | h[4] <= 1];
L;

[[0, 10, 6, 1], [6, 11, 4, 1], [12, 12, 2, 1], [18, 13, 0, 1]]

Данный результат означает, что существуют лишь четыре решения: (0, 10, 6), (6, 11, 4), (12, 12, 2), (18, 13, 0).

Кто лжет?

A говорит: "B лжет."
B говорит: "C лжет."
C говорит: "A и B лгут."
Кто из них лжет на самом деле?
Для ответа на данный вопрос закодируем логические значения ИСТИНА и ЛОЖЬ элементами 1 и 0 поля ZZ/(2) соответственно:

use ZZ/(2)[a,b,c];
I1 := ideal(a, b-1);
I2 := ideal(a-1, b);
A := intersect(I1, I2);
I3 := ideal(b, c-1);
I4 := ideal(b-1, c);
B := intersect(I3, I4);
I5 := ideal(a, b, c-1);
I6 := ideal(b-1, a, c);
I7 := ideal(b, a-1, c);
I8 := ideal(b-1, a-1, c);
C := IntersectList([I5, I6, I7, I8]);
ReducedGBasis(A + B + C);

[b +1,  a,  c]

Единственным решением является следующее: A и C лгут, в то время как B говорит правду.

Раскраска географической карты

Можно ли раскрасить страны на карте в три цвета, так что цвета любых двух соседних стран различны?

use P ::= ZZ/(3)[x[1..6]];
define F(X)  return X*(X-1)*(X+1);  enddefine;
VerticesEq := [ F(x[i]) | i in 1..6 ];
edges := [[1,2],[1,3],  [2,3],[2,4],[2,5],  [3,4],[3,6],
          [4,5],[4,6],  [5,6]];
EdgesEq := [ (F(x[edge[1]])-F(x[edge[2]]))/(x[edge[1]]-x[edge[2]])
                  |  edge in edges ];
I := ideal(VerticesEq) + ideal(EdgesEq) + ideal(x[1]-1, x[2]);
ReducedGBasis(I);

[x[2],  x[1] -1,  x[3] +1,  x[4] -1,  x[6],  x[5] +1]

Решение можно проинтерпретировать следующим образом: в данном случае, по существу, есть только один способ раскраски. Например, если занумеровать голубой, красный и зеленый цвета числами 0, 1 и -1, соответственно, получим

Формула Герона

Можно ли выразить площадь треугольника как функцию длин его сторон?

use QQ[x[1..2],y,a,b,c,s];
A := [x[1], 0];
B := [x[2], 0];
C := [ 0,   y];
Hp := ideal(a^2 - (x[2]^2+y^2),  b^2 - (x[1]^2+y^2),
            c   - (x[2]-x[1]),   2*s - c*y);
E := elim(x[1]..y, Hp);
f := monic(gens(E)[1]);
f;

a^4 -2*a^2*b^2 +b^4 -2*a^2*c^2 -2*b^2*c^2 +c^4 +16*s^2

factor(f - 16*s^2);

record[
  RemainingFactor := 1,
  factors := [a +b -c,  a -b +c,  a +b +c,  a -b -c],
  multiplicities := [1,  1,  1,  1]
]

Результат можно интерпретировать в виде следующего равенства: s^2=-(1/16)(a+b+c)(a+b-c)(a-b+c)(a-b-c). Это означает, что квадрат площади треугольника со сторонами a,b,c равен p(p-a)(p-b)(p-c), где p = 1/2(a+b+c) - полупериметр. Следовательно, ответ положительный.