Элементы линейной комбинаторики
Название спецкурса на английском языке
Elements of linear combinatorics
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Применение методов линейной алгебры в комбинаторике.
Элементы вероятностного подхода к комбинаторным проблемам.
Сложность обучения и размерность Вапника-Червоненкеса.
Пороговые функции и их свойства. Разложение Фурье дискретных функций и параметры Чжоу.
Верхние и нижние оценки числа пороговых функций. Лемма Littlewood-Offord (1938) в
формулировке Erdős (1945). Верхняя оценка J.Komlós (1977) для числа вырожденных 1-матриц.
Теорема Odlyzko (1988) о подпространствах, порожденных ±1-векторами. Нижняя оценка
А.А.Ирматова (1993) числа пороговых функций. Асимптотика логарифма числа пороговых функций K-значной логики.
Элементы вероятностного подхода к комбинаторным проблемам.
Сложность обучения и размерность Вапника-Червоненкеса.
Пороговые функции и их свойства. Разложение Фурье дискретных функций и параметры Чжоу.
Верхние и нижние оценки числа пороговых функций. Лемма Littlewood-Offord (1938) в
формулировке Erdős (1945). Верхняя оценка J.Komlós (1977) для числа вырожденных 1-матриц.
Теорема Odlyzko (1988) о подпространствах, порожденных ±1-векторами. Нижняя оценка
А.А.Ирматова (1993) числа пороговых функций. Асимптотика логарифма числа пороговых функций K-значной логики.
Список источников
L.Babai, P.Frankl. Linear Algebra Methods in Combinatorics. Version 2.1. 2020
Н.Алон, Дж.Спенсер. Вероятностный метод. Москва. Бином. Лаборатория знаний. 2007
P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. Volume 51, Number 12 (1945), 898-902
A. M. Odlyzko. On subspaces spanned by random selections of ±1 vectors, J. Combinatorial Theory A, 47 (1988), pp. 124-133
А.А. Ирматов. О числе пороговых функций, Дискрет. матем., 1993, том 5, выпуск 3, страницы 40–43
А. А. Ирматов, Ж. Д. Ковиянич. Об асимптотике логарифма числа пороговых функций K-значной логики, Дискрет. матем., 1998, том 10, выпуск 3, страницы 35–56.
Н.Алон, Дж.Спенсер. Вероятностный метод. Москва. Бином. Лаборатория знаний. 2007
P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. Volume 51, Number 12 (1945), 898-902
A. M. Odlyzko. On subspaces spanned by random selections of ±1 vectors, J. Combinatorial Theory A, 47 (1988), pp. 124-133
А.А. Ирматов. О числе пороговых функций, Дискрет. матем., 1993, том 5, выпуск 3, страницы 40–43
А. А. Ирматов, Ж. Д. Ковиянич. Об асимптотике логарифма числа пороговых функций K-значной логики, Дискрет. матем., 1998, том 10, выпуск 3, страницы 35–56.
Дополнительная информация
Первое занятие - 16.09
Спецкурс посвящен изучению комбинаторных свойств линейных объектов, возникающих в дискретной математике и математической кибернетики таких как, пороговые функции, конфигурации гиперплоскостей, случайные матрицы и других методами линейной алгебры, комбинаторной топологии и вероятности. Предполагается изложить последние достижения в оценке числа пороговых функций и числа вырожденных +-1 -матриц, полученные рядом авторов, за последние 80 лет.
Спецкурс по выбору кафедры для студентов 5 курса
День недели
вторник
Время
18:30-20:05
Аудитория
1225
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.