Практикум по алгебре

Мехмат, 3-й курс

Тема 1. Язык программирования Python

1.1. Элементы теории чисел

Список задач

  1. Реализовать вероятностный тест простоты Миллера-Рабина.
  2. Реализовать алгоритм для Китайской теоремы об остатках.
  3. Факторизовать целое число с помощью ρ-алгоритма Полларда.
  4. Факторизовать целое число с помощью p-1-алгоритма Полларда.
  5. Вычислить квадратный корень из x в поле Zp (p — простое число), т.е. найти r такое, что r2x (mod p).
  6. * Факторизовать целое число с помощью алгоритма Ленстра на эллиптических кривых.

1.2. Классы в языке Python

Список задач

  1. Реализовать класс Polynomial, представляющий многочлен произвольной степени с коэффициентами в поле рациональных чисел. Должны быть реализованы операции сложения, умножения, деления с остатком, вычисление наибольшего общего делителя многочленов, производной многочлена, а также вычисление многочлена с теми же корнями, свободного от кратных корней, т.е. частного от деления многочлена f на gcd(f, f').
  2. Та же задача, но для многочленов над полем Zp.
  3. Реализовать класс "Элементы поля GFp2", где p — простое число.
  4. Реализовать класс "Матрицы порядка m×n над полем рациональных чисел". Должны быть реализованы операции над матрицами, приведение матрицы к ступенчатому виду, вычисление ранга и определителя матрицы и решение линейной системы.
  5. Та же задача, но для матриц над полем Zp.

Тема 2. SageMath — система компьютерной математики

2.1. Задачи по геометрии

Решения всех задач должны быть оформлены как функции на языке Sage (аналогичны функциям в языке Python). Например, в задаче "Нарисовать треугольник, вписанную окружность и точку Жергона" решение оформляется в виде функции, на вход которой подаются 3 точки и которая возвращает графический объект.

Список задач

  1. Нарисовать треугольник, вписанную окружность и точку Жергона.
  2. Нарисовать треугольник, три внешне вписанных окружности и точку Нагеля.
  3. Нарисовать треугольник и точку Лемуана, которая построена как точка, изогонально сопряженная к точке пересечения медиан.
  4. Нарисовать кривую Безье порядка n по заданному массиву массиву точек размера n+1.

2.2. Коммутативная алгебра и базисы Гребнера

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


а также пособие по математическому практикуму для группы алгебры

Список задач

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