Коммуникационная сложность
теории вероятностей
Вероятностный протокол с логарифмической и константной коммуникацией для предиката равенства.
Связь детерминированной сложности с разбиением на одноцветные прямоугольники.
Методы доказательства нижних оценок для разбиений и покрытий прямоугольниками.
Теорема о квадратичной верхней оценке детерминированной сложности через недетерминированную
Теорема Разборова о квадратичном разрыве между недетерминированной и детерминированной сложностями.
Вероятностный протокол логарифмической сложности для GT
Сравнение вероятностных сложностей с общими и приватными битами (теорема Ньюмана).
Безошибочная вероятностная сложность предиката DISJ (теорема Хостада-Вигдерсона).
Пестрота. Линейная нижняя оценка вероятностной сложности предиката IP.
Информационная сложность протоколов, теорема о прямой сумме
Коммуникационная сложность отношений. Связь между формулами в базисе И, ИЛИ, НЕ и коммуникационной сложностью (Карчмер-Вигдерсон).
Отношение FORK и нижняя оценка глубины коммуникационного протокола для него. Сверх-логарифмическая нижняя оценка глубины монотонных формул для булевой функции
Применение коммуникационной сложности для оценки размера схем из пороговых элементов
Применение коммуникационной сложности для оценки высоты деревьев решений
Экспоненциальная нижняя оценка веса пороговых элементов для схем глубины 2, вычисляющих предикат IP.
E. Kushilevitz, N. Nisan. Communication Complexity. Cambridge UP. 1st edition 1997
Чат в Телеграм: https://t.me/+9G993a4ym640ZTVi
Современные методы обработки данных, II
Алгоритм построения синтении.
Алгоритм эволюции синтении.
В.А. Любецкий, К.Ю. Горбунов, Л.И. Рубанов. Построения и эволюции синтеничных структур. // 2026 год. Рукопись.
Дан набор буквенных последовательностей. Синтенией называется набор их коротких подпоследовательностей, которые подобны по взаиморасположению букв и по их гомологии (которая возникает из того, что каждая буква обозначает сложный объект, например, ген). Изложение не использует материал 1-го семестра (https://scs.math.msu.ru/ru/node/8581) и не требует предварительных знаний. Сейчас этот материал доступен в рукописи. Курс может сдаваться как «годовой» (объединение материала 1-го и 2-го семестров), так и как «полугодовой» (материал весеннего семестра). Эта тема нуждается в компьютерной программе, и широко востребована в мировой практике.
Метод резолюций
Теорема Эрбрана
Метод резолюций для логики высказываний
Алгоритм унификации
Метод резолюций для логики предикатов
Уточнения исчисления резолюций
Применения метода резолюций в математической логике
Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.
A.Leitsch. The Resolution Calculus. Springer, 1997.
В спецкурсе детально излагается так называемый метод резолюций, используемый при построении систем автоматического доказательства теорем.
Математическая логика, часть 2
Теоремы Геделя о неполноте.
Аксиоматическая теория множеств.
Теорема Цермело.
G. Boolos. The logic of provability. Cambridge University Press, 1993.
Спецкурс является обязательным для студентов 3 курса кафедры математической логики и теории алгоритмов.
Математическая логика, часть 1
Интуиционистская логика высказываний.
Логика предикатов.
Теорема Геделя о полноте.
В. Е. Плиско, В. Х. Хаханян. Интуиционистская логика. — М.: Изд-во при мех.-мат. ф-те МГУ, 2009.
Спецкурс является обязательным для студентов 3 курса кафедры математической логики и теории алгоритмов.
Математические методы анализа данных, II
Постановка задачи об оптимальной эволюции вдоль дерева (ациклической сети): даны данные в листьях дерева и ищутся данные в нелистовых вершинах. Один из подходов основан на марковской (или близкой к ней) эволюции.
Постановка задачи о классификации данного множества точек в многомерном вещественном пространстве (иными словами, столбцов неотрицательной числовой матрицы данных). Минимизируется функционал, который накладывает условие на искомую кластеризацию: для каждого её кластера, «близость» точек внутри него значимо больше, чем близость точек кластера к точкам вне кластера. Оставшаяся часть курса обсуждает эту задачу кластеризации.
Удаление скрытых параметров в данных. Преобразование данных, приводящее к минимальной зависимости дисперсии строки данной матрицы от среднего строки.
Выбор характерных для кластеризации строк матрицы.
Переход к оптимальным и наиболее информативным координатам исходных точек, т.е. к новым координатам столбцов.
Переход к графу: вершины – исходные точки, рёбра соединяют вершины, у которых окрестности вершин пересекаются, и рёбрам приписаны ранговые веса.
Максимизация функции модулярности, аргумент которой – переменная кластеризация вершин (=точек) графа.
Алгоритм такой максимизации.
Выбор индивидуальных признаков каждого кластера в оптимальной кластеризации.
Понижение размерности исходных данных (матрица типично имеет более 30 тысяч строк 50 тысяч столбцов; возможно понижение размерности пространства до значения 2).
Курс не предполагает предварительных знаний; в частности, знакомства с курсами лектора прошлого учебного года.
Страница спецкурса: http://logic.math.msu.ru/staff/lyubetsky/mmdp/.
Cлушатели должны зарегистрироваться по адресу gorbunov@iitp.ru, сообщив о себе: ФИО полностью, факультет, группу, свой email и мобильный.
Компьютерная обработка больших данных — универсальное направление исследований буквально во всех областях естественных и гуманитарных наук. В тоже время такая обработка опирается на методы современной математики, от алгоритмов до геометрии. Используемые здесь методы/алгоритмы в основном эвристические, интуитивно построенные, для которых почти неизвестны доказательства их правильности. Более того, обычно не существует даже математической постановки задачи, решаемой таким эвристическим алгоритмом; сама эта задача понимается интуитивно, на основе компьютерных экспериментов и опыта применения в данной прикладной области. Будет рассказан, так называемый, метод Seurat, широко применяемый в разных прикладных задачах и особенно в биоинформатике. Будут обсуждаться проблемы его обоснования, далёкие от математического решения. Будут предложены компьютерные вычислительные программистские математические задачи, как и реально прикладные, для курсовых и дипломных работ; для аспирантских тем. Никакие предварительные знания не предполагаются; все необходимые сообщаются на лекциях. После каждой лекции предполагается факультативный семинар и обсуждение задач.
Односторонние функции и их применения
Статистически и вычислительно неотличимые случайные величины. Свойства вычислительно неотличимых случайных величин. Полиномиально генерируемые и доступные последовательности случайных величин. Генераторы псевдослучайных чисел (ПСЧ). Слабая необратимость генераторов ПСЧ.
Понятие трудного бита для данной функции. Лемма о трудном бите (конкатенация значения функции и трудного бита неотличима от конкатенации значения функции и случайного бита).
Построение генератора ПСЧ, исходя из односторонней перестановки с трудным битом.
Теорема о вероятностном декодировании списком кода Адамара.
Теорема Левина-Гольдрайха о трудном бите для односторонних функций (доказательство по модулю теоремы о вероятностном декодировании списком кода Адамара).
Семейства псевдослучайных функций (ПСФ). Сильный и слабый варианты определения. Построение псевдослучайных функций исходя из генератора ПСЧ.
Односторонние перестановки с секретом (trapdoor permutations). Примеры. Трудный бит для необратимой перестановки с секретом.
Одноразовые схемы шифрования с закрытым ключом (СШЗК, симметричные схемы). Построение СШЗК на основе генератора ПСЧ.
Многоразовые схемы шифрования с закрытым ключом. Построение многоразовой СШЗК на основе семейства ПСФ и одноразовой СШЗК.
Схемы шифрования с открытым ключом (ШОК, асимметричные схемы). Конструкция ШОК на основе необратимой перестановки с секретом. Неинтерактивные протоколы привязки к биту (НПБ). Построение НПБ на основе односторонней перестановки.
Интерактивные алгоритмы. Интерактивные протоколы привязки к биту (ИПБ). Построение ИПБ на основе генератора ПСЧ. Протоколы бросания монетки. Построение таких протоколов на основе протокола привязки к биту.
М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко. Криптография в банковском деле. М.: МИФИ, 1997.
O. Goldreich. Foundations of cryptography. Basic tools. Cambridge Univ. Press. 2001. 400 p.
O. Goldreich. Foundations of cryptography. Basic applications. Cambridge Univ. Press. 2004
Коды с исправлением ошибок
Количество исправленных ошибок и стираний. Код Хэмминга [n-1,n,2].
Граница Хэмминга. Граница Гилберта.
Формула для объема шара Хэмминга. Функция Шеннона.
Линейные коды.
Граница Варшамова-Гилберта.
Коды Возенкрафта.
Коды Хэмминга.
Граница Синглтона. Коды Рида-Соломона.
Каскадные коды. Коды Форни. Коды Форни-Юстесена-Возенкрафта
Границы Плоткина и улучшение границы Синглтона.
Коды Адамара.
Код Рида — Маллера.
Коды БЧХ.
Декодирование списком с исправлением ошибок. Общие границы.
Декодирование списком и минимальное расстояние.
Декодирование списком с исправлением n-sqrt{n(n-d)} ошибок для кода Рида-Соломона.
Декодирование списка с (1-eps)/2 ошибками для кода Адамара
Теорема Голдрайха-Левина
Страничка курса в Телеграме https://t.me/+7w1cLI5fA9Q1ZmYy
Конструктивная логика
Теория алгоритмов
Конструктивные интерпретации логических и логико-математических языков
В.Е.Плиско, Лекции по конструктивной логике. М.: Луч, 2021.