Магистратура мехмата

Весенний семестр

Дистанционное обучение

Предлагается для дистанционных лекций и семинаров использовать Zoom.
Время встречи (Meeting): среда в 11:00, продолжительность 1 час 45 минут.
Meeting ID: 284 274 0990
В браузере нужно войти на страничку https://zoom.us/
в меню выбрать Join и указать Meeting ID. Браузер предложит установить приложение Zoom, после чего можно будет присоединиться к встрече. Zoom работает на любом компьютере или смартфоне.

Можно сразу войти на страничку встречи:
https://us02web.zoom.us/j/2842740990


Лекция 25 марта 2020: Нити и объекты синхронизации

Лекция 1 апреля 2020: не состоится ввиду объявленных каникул до 5 апреля.

Лекция 8 апреля 2020: Графика на языке Python

Лекция 15 апреля 2020:

Лекция 22 апреля 2020: SageMath, построение кубического сплайна.
Видео.

Лекция 6 мая 2020: Базисы Грёбнера в кольцах многочленов от нескольких переменных.
Видео, презентация.

Семинар 13 мая 2020: решения задач на базисы Грёбнера в кольцах многочленов, сплайны и др.
Видео.


Журнал группы магистратуры 1 курса, 2019-20 уч. год.

По каждой теме нужно решить одну задачу. Номер задачи равен номеру студента в журнале по модулю n, где n — число задач по данной теме. Решения задач присылайте мне на электронную почту в виде файла, присоединенного к письму (*.py для программ на языке Python3, *.sage для программ на языке sage). Адрес моей электронной почты:
vladimir_borisen (собака) mail.ru

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

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

Кодирование с открытым ключом и элементы теории чисел

Содержание лекции:

Презентация: теория чисел в криптографии

Список задач

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

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

Список задач

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

1.3. Параллельное программирование на языке Python: нити и объекты синхронизации

Презентация: Нити и объекты синхронизации

Примеры программ

  • Простейший пример на использование нитей и мьютекса — жеребьевка: headsTails.py. Программа использует модуль threading.

    Запускаются две однотипные нити (объект Thread), первая 10 раз печатает слово "Heads", вторая "Tails", в промежутках между печатями каждая нить засыпает на случайное время в интервале от 0.1 до 1 секунды. Выигрывает та нить, которая напечатает свое слово последней. Для предотвращения каши на печати нити для доступа к консоли используют мьютех (в языке Python он называется Lock), захват мьютекса производится методом acquire(), освобождение — release(). Ожидание завершения нити выполняется с помощью метода join() объекта типа Thread.

Задачи

  1. Вычислить определенный интеграл от заданной функции, разбив отрезок интегрирования на n частей (n небольшое!) и запустив для каждой части отдельную нить.
  2. Перемножить две квадратные n*n-матрицы, запустив k*k нитей, где k делит n. Нить с индексами (s,t) вычисляет минор матрицы-произведения в строках s*m+1, ..., s*m+m и столбцах t*m+1, ..., t*m+m, где m = n/k. (Результирующая матрица разбивается на клетки размера m = n/k, каждая нить вычисляет одну клетку.)
  3. Привести матрицу к ступенчатому виду методом Гаусса, используя параллельную работу со строками матрицы при обнулении очередного столбца.

1.4. Графика и оконное программирование на языке Python

Для графики мы используем модуль tkinter, представляющий собой наиболее простой оконный интерфейс. Мы также используем небольшой модуль R2Graph.py, в котором реализованы классы R2Vector и R2Point, с помощью которых удобно решать разные геометрические задачи на плоскости.

Подробный текст лекции: Графика на языке Python

Примеры программ

  • Нариcовать треугольник по кликам мыши, а также три его биссектрисы и вписанную окружность: triangle.py
  • Та же программа "Треугольник", но с возможностью перетаскивания его вершин мышью, при этом картинка меняется в реальном времени: triangle2.py
  • Часы: clock.py

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

  1. Нарисовать треугольник и точку Ферма-Торичелли (точка, минимизирующая сумму расстояний до вершин треугольника), изобразив процесс ее построения.
  2. Нарисовать треугольник, три внешне вписанных окружности и точку Нагеля.
  3. Нарисовать треугольник и точку Лемуана, которая построена как точка, изогонально сопряженная к точке пересечения медиан.
  4. Нарисовать кривую Безье порядка n по заданному массиву точек размера n+1.

1.5. Сетевые приложения на языке Python, интерфейс сокетов

Примеры программ

  • Скачать страницу из Internet по протоколу HTTP: httpGet.py
  • Пара простейших программ, использующих протокол UDP и групповое широковещание (multicast): программа udpSnd.py раз в секунду посылает дейтаграму по широковещательному адресу (224.1.1.22, 1234), которая содержит текущее время в текстовом формате. Программа udpRecv.py принимает эти дейтаграмы и распечатывает их на консоли.

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

Пример программы на Sage: построить кубический многочлен по узлам интерполяции x0, x1, в которых заданы значения ролинома y0, y1 и значения его производной dy0, dy1. Требуется вычислить коэффициенты полинома в виде выражений от заданных значений, а также нарисовать график полинома. График для конкретных значений рисуется с помощью функции

drawPolynom(x_0, y_0, x_1, y_1, dy_0, dy_1, xmin=-8, xmax=8, ymin=-6, ymax=6)
Файл с программой: CubInt.sage
Пример ее работы:
drawPolynom(-3, 0, 4, 1, 2, 0)

2.1. Графика в SageMath

Список задач

В задачах надо написать функцию (в смысле Python'а) с именем splineC1 или splineC2, на вход которой передается список пар. Каждая пара содержит координаты (xi, yi) i-го узла интерполяции, при этом координаты x идут в строго возрастающем порядке. Функция должна построить кубический C1 или С2-сплайн (с непрерывными только первыми производными или как первыми, так и вторыми производными). Пример использования функции:

    s = splineC1([(-7,-4), (-5,-1), (-3,-2), (-1,2),
                 (1,3), (3,1), (5,3), (7,-1)])
    show(s, aspect_ratio=1)
(этот C1-сплайн показан на первой картинке ниже).

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

  1. Построить C1-сплайн.
  2. Построить C2-сплайн.

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

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


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

Презентация к лекции по коммутативной алгебре

Требуется решить одну задачу из списка: номер 1 для студентов с нечетным номером по журналу, номер 2 с четным. Надо реализовать функцию на языке Sage, которая возвращает значение True или False. Набор многочленов передается функции как список.

Список задач

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