Предполагается знание алгебры в объеме 2-го курса мехмата и знакомство с гильбертовыми пространствами.
Целевая аудитория
1-2 курс
3-6 курс, магистранты
Подразделение
[Кафедра теории функций и функционального анализа]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Описание унитарных представлений группы SL(2,R).
Связь унитарных представлений группы SL(2,R) и соотношений для гипергеометрических функций.
Представления группы SL(2,R) и классические ортогональные многочлены.
Список источников
Н. Я. Виленкин. Специальные функции и теория представлений групп. М.: Наука, 1965.
Дополнительная информация
Цель спецкурса - рассказать об унитарных представлениях группы SL(2,R) (группы вещественных матриц порядка 2 с определителем 1) и об их применениях к теории специальных функций. Фактически, разные естественные вопросы о представлениях приводят к ответам, где появляются гипергеометрические функции разного уровня (функции Бесселя $_0F_1$, вырожденные гипергеометрические функции $_1F_1$, функции Гаусса $_2F_1$ и более сложные функции, $_3F_2$, $_4F_3$), при этом представления позволяют получать различные тождества для этих функций. Естественным образом возникают также различные системы ортогональных многочленов, от многочленов Эрмита и Лагерра до многочленов Рак'а и Вильсона.
Предварительных познаний по представлениям (за пределами алгебры 2 курса) и специальным функциям не предполагается. Предполагается знакомство с гильбертовыми пространствами.
День недели
понедельник
Время
18:30-20:05
Аудитория
468
Дата первого занятия
Аудитория первого занятия
468
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Представление натуральных чисел в виде суммы двух квадратов.
Уравнение Пелля.
Классы эквивалентности бинарных квадратичных форм.
Группа целочисленных автоморфизмов бинарной формы с целыми коэффициентами.
Теория приведения бинарных квадратичных форм.
Представление натуральных чисел бинарными квадратными формами.
Список источников
Бухштаб А. А. Теория чисел. М.: Просвещение, 1966.
Бугаенко В. О. Уравнение Пелля. М.: МЦНМО, 2001.
Венков Б. А. Элементарная теория чисел. М.-Л.: ОНТИ, 1937.
Касселс Дж. В. С. Введение в геометрию чисел. М.: Мир, 1965.
Дирихле П. Г. Л. Лекции по теории чисел. М.-Л.: ОНТИ, 1936.
Конвей Дж. Квадратичные формы, данные нам в ощущениях. М.: МЦНМО, 2008.
Selected problems of the analysis of Boolean functions
Авторы курса
Таранников Юрий Валерьевич
Пререквизиты
Базовые знания математического анализа, линейной и высшей алгебры.
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Преобразование Уолша булевой функции и его свойства.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Нисана-Сегеди о максимальном числе существенных переменных и ее усиления.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Список источников
O’Donnell R. Analysis of boolean functions. Cambridge University Press, 2014.
Wegener I., The complexity of boolean functions, Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1987.
Carlet C. Boolean functions for cryptography and coding theory. Cambridge University Press, 2021.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., Szegedy M. On the degree of boolean functions as real polynomials, Computational Complexity 4 (1994), p. 301-313.
Chiarelli J., Hatami P., Saks M., An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function, Combinatorica 40 (2020), p. 237-244.
Wellens J., Relationships between the number of inputs and other complexity measures of boolean functions, arXiv:2005.00566v2, 2022.
Huang H. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, arXiv:1907.00847v2, 2019.
Nisan N., CREW PRAMs and decision trees, SIAM J. Comput. 20 (6) (1991), p. 999 -1007.
Rubinstein D., Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), p. 297-299.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
Блок-дизайны и t-дизайны.
Конечные геометрии.
Матрицы Адамара.
Латинские квадраты.
Трансверсальные дизайны.
Ортогональные массивы.
Связь с линейными кодами.
Разностные множества.
Корреляционно-иммунные и бент-функции.
Вист-турниры.
Список источников
Таранников Ю. В. Комбинаторные свойства дискретных структур и приложения к
криптологии. М.: МЦНМО, 2011.
Hedayat A. S., Sloane N. J. A., Stufken , J. Orthogonal arrays. Theory and applications. Springer-Verlag, 1999.
Handbook of Combinatorial Designs. 2nd Edition by Colbourn C. J., Dinitz J. H (Eds). Chapman and Hall/CRC, 2007.
Базовые знания математического анализа, линейной и высшей алгебры.
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Год
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Преобразование Уолша булевой функции и его свойства.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Нисана-Сегеди о максимальном числе существенных переменных и ее усиления.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Деревья решений.
Приложения анализа булевых функций в теории сложности.
Нелинейность булевых функций.
Корреляционно-иммунные и устойчивые булевы функции.
Приложения анализа булевых функций в криптологии.
Список источников
O’Donnell R. Analysis of boolean functions. Cambridge University Press, 2014.
Wegener I., The complexity of boolean functions, Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1987.
Carlet C. Boolean functions for cryptography and coding theory. Cambridge University Press, 2021.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., Szegedy M. On the degree of boolean functions as real polynomials, Computational Complexity 4 (1994), p. 301-313.
Chiarelli J., Hatami P., Saks M., An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function, Combinatorica 40 (2020), p. 237-244.
Wellens J., Relationships between the number of inputs and other complexity measures of boolean functions, arXiv:2005.00566v2, 2022.
Huang H. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, arXiv:1907.00847v2, 2019.
Nisan N., CREW PRAMs and decision trees, SIAM J. Comput. 20 (6) (1991), p. 999 -1007.
Rubinstein D., Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), p. 297-299.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
Базовые знания математического анализа, линейной и высшей алгебры.
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Полгода (осень)
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Преобразование Уолша булевой функции и его свойства.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Нисана-Сегеди о максимальном числе существенных переменных и ее усиления.
Сложностные характеристики булевой функции и их взаимосвязь.
Список источников
O’Donnell R. Analysis of boolean functions. Cambridge University Press, 2014.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., Szegedy M. On the degree of boolean functions as real polynomials, Computational Complexity 4 (1994), p. 301-313.
Chiarelli J., Hatami P., Saks M., An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function, Combinatorica 40 (2020), p. 237-244.
Wellens J., Relationships between the number of inputs and other complexity measures of boolean functions, arXiv:2005.00566v2, 2022.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
Дополнительная информация
До особого указания спецкурс читается по субботам с 15:00 в ауд. 433.
Элементы теории рекурсивных функций и алгоритмов.
Частично рекурсивные функции как вариант формализации понятия алгоритма. Примитивно рекурсивные и общерекурсивные функции.
Перечислимые, разрешимые, примитивно рекурсивные предикаты, отношения,
множества.
Теорема Аккермана (о диагональной одноместной «быстрорастущей» общерекурсивной функции, не являющейся примитивно рекурсивной функцией).
Теоремы об устранимости кванторов в элементарных теориях (в теориях 1-го порядка) некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теоремы об устранимости кванторов в монадических теориях 2-го порядка некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования (без доказательства). Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования.
Применения теорем о разрешимости монадических теорий 2-го порядка к доказательству разрешимости некоторых теорий 1-го порядка.
Список источников
Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965
Панкратьев Е.В. Элементы компьютерной алгебры – М.: Интернет-университет информационных технологий
Рабин М. Разрешимые теории. Справочная книга по математической логике. Часть 3 Теория рекурсии. – Москва: Наука, 1982
Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980
Дополнительная информация
В курсе освещаются следующие вопросы: 1) начальные сведения по теории алгоритмов и теории конечных автоматов, 2) уравнения в словах в свободном моноиде, 3) метод устранения кванторов, 4) алгоритмическая разрешимость теорий некоторых классов алгебраических систем.
Нужные для понимания спецкурса сведения по математической логике и алгебре будут кратко напоминаться по ходу лекций.
День недели
четверг
Время
16:45-18:20
Аудитория
468
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
