пятница

Задание точечных решёток в евклидовом пространстве. Решётки и квадратичные формы. Реперы.
Свойства решёток. Леммы Блихфельдта и Минковского.
Подрешётки и центрировки, сечения и проекции решёток.
Минимальные векторы решётки и задача плотнейшей решётчатой упаковки шаров.

Кодирование, криптография, стеганография. Исторический очерк развития.
Введение в теорию кодирования. Алфавитное кодирование. Префиксные коды. Теорема Маркова. Неравенство МакМиллана.
Коды с минимальной избыточностью (коды Хаффмана).
Самокорректирующиеся коды (коды Хэмминга). Геометрические приложения.
Математическая модель шифра замены. Классификация шифров замены.
Шифры перестановки. Элементы анализа.
Анализ шифра Виженера: нахождение длины ключа с использованием индекса совпадения; нахождение ключа с использованием взаимного индекса совпадения.
Статистические характеристики открытых текстов. Пример вскрытия шифра простой замены.
Блочные шифры. Стандарты шифрования данных. Режимы использования блочных шифров.
Введение в теорию сложности вычислений. Скорость роста функций. Сложностные классы. Труднорешаемые задачи и их применение в криптографии.
Шифрование с открытым ключом: принципы и примеры протоколов.
Задача о рюкзаке и рюкзачные системы.
Задача дискретного логарифмирования. Алгоритм Сильвера-Полига-Хеллмана, индексный алгоритм.
Проверка чисел на простоту. Вероятностные тесты на простоту. Тест Соловея-Штрассена. Тест Миллера-Рабина.
Факторизация больших составных чисел. Алгоритм Полларда. Факторизация Ферма. Алгоритм факторных баз.
Эллиптические кривые и их применение в криптографии. Обобщение известных криптосистем на эллиптические кривые.
Совершенные шифры. Латинские квадраты и их свойства. Построение параметрических классов латинских квадратов.
Клеточные автоматы и их использование в криптографии.
Системы шифрования, основанные на сложностных задачах комбинаторной теории групп.

Вариационные принципы динамики упругого тела.
Полудискретный метод Галеркина.
Методы прямого интегрирования уравнений динамики.
Метод спектральных элементов.
Метод собственных функций (Метод нормальных форм колебаний).
Алгебраическая проблема собственных значений.

Ветвящиеся процессы Гальтона-Ватсона. Ветвящиеся процесс в изменяющейся среде. Производящие функции и вероятность невырождения.
Надкритические ветвящиеся процессы в случайной среде. Естественный мартингал.
Случайное блуждание с нулевым средним. Теорема о положительности. Общая конструкция P+-меры.
Критический ветвящийся процесс в случайной среде. Асимптотика вероятности невырождения.
Классификация докритических ветвящихся процессов. Предельные теоремы для докритического случая.

Теоремы сходимости для мартингалов.
Неравенства для мартингалов.
Теоремы об остановленном мартингале.
Стационарные в широком смысле последовательности. Теоремы Герглотца и Бохнера-Хинчина.
Спектральное представление стационарного в широком смысле процесса.
Безграничная делимость. Представление Леви-Хинчина.

Критические точки гладких функций и топология многообразий. Функции Морса. Категория Люстерника-Шнирельмана.
Элементы теории групп Ли. Приложения к физике.
Симплектическая геометрия на поверхностях.
Топология гамильтоновых динамических систем. Торы и теорема Лиувилля.
Симплектическая топология и интегрирование уравнений.

Логарифмические верхние оценки коммуникационной сложности функций MED и CIS.
Вероятностный протокол с логарифмической и константной коммуникацией для предиката равенства.
Связь детерминированной сложности с разбиением на одноцветные прямоугольники.
Методы доказательства нижних оценок для разбиений и покрытий прямоугольниками.
Теорема о квадратичной верхней оценке детерминированной сложности через недетерминированную
Теорема Разборова о квадратичном разрыве между недетерминированной и детерминированной сложностями.
Вероятностный протокол логарифмической сложности для GT
Сравнение вероятностных сложностей с общими и приватными битами (теорема Ньюмана).
Безошибочная вероятностная сложность предиката DISJ (теорема Хостада-Вигдерсона).
Пестрота. Линейная нижняя оценка вероятностной сложности предиката IP.
Информационная сложность протоколов, теорема о прямой сумме
Коммуникационная сложность отношений. Связь между формулами в базисе И, ИЛИ, НЕ и коммуникационной сложностью (Карчмер-Вигдерсон).
Отношение FORK и нижняя оценка глубины коммуникационного протокола для него. Сверх-логарифмическая нижняя оценка глубины монотонных формул для булевой функции
Применение коммуникационной сложности для оценки размера схем из пороговых элементов
Применение коммуникационной сложности для оценки высоты деревьев решений
Экспоненциальная нижняя оценка веса пороговых элементов для схем глубины 2, вычисляющих предикат IP.