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

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

Трехмерная графика и аналитическая геометрия

Классы для поддержки двумерной и трехмемрной графики

Для вычислений на плоскости R2 используются классы R2Vector (вектор на плоскости с вещественными координатами) и R2Point (точка на плоскости). В пакете "R2Graph.zip" реализованы все основные операции на плоскости

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

Тема 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.

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

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

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

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

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

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

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

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

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

Параллельное программирование на языке 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. Привести матрицу к ступенчатому виду методом Гаусса, используя параллельную работу со строками матрицы при обнулении очередного столбца.