Тип: курс по выбору кафедры

Лектор: Ирматов Анвар Адхамович

Для: для студентов 5 курса

Время: вт 18.30 - 20.05

Начиная с: 16.09.2025

Аудитория: 12-25

Применение методов линейной алгебры в комбинаторике.
Элементы вероятностного подхода к комбинаторным проблемам.
Сложность обучения и размерность Вапника-Червоненкеса.
Пороговые функции и их свойства. Разложение Фурье дискретных функций и параметры Чжоу.
Верхние и нижние оценки числа пороговых функций. Лемма Littlewood-Offord (1938) в
формулировке Erdős (1945). Верхняя оценка J.Komlós (1977) для числа вырожденных +-1-матриц.
Теорема Odlyzko (1988) о подпространствах, порожденных ±1-векторами. Нижняя оценка
А.А.Ирматова (1993) числа пороговых функций. Асимптотика логарифма числа пороговых функций K-значной логики.

Спецкурс посвящен изучению комбинаторных свойств линейных объектов, возникающих в дискретной математике и математической кибернетики таких как, пороговые функции, конфигурации гиперплоскостей, случайные матрицы и других методами линейной алгебры, комбинаторной топологии и вероятности. Предполагается изложить последние достижения в оценке числа пороговых функций и числа вырожденных +-1 -матриц, полученные рядом авторов, за последние 80 лет.

Материалы:

[1] L.Babai, P.Frankl. Linear Algebra Methods in Combinatorics. Version 2.1. 2020
[2] Н.Алон, Дж.Спенсер. Вероятностный метод. Москва. Бином. Лаборатория знаний. 2007
[3] P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. Volume 51, Number 12 (1945), 898-902
[4] A. M. Odlyzko. On subspaces spanned by random selections of ±1 vectors, J. Combinatorial Theory A, 47 (1988), pp. 124-133
[5] А.А. Ирматов. О числе пороговых функций, Дискрет. матем., 1993, том 5, выпуск 3, страницы 40–43
[6] А. А. Ирматов, Ж. Д. Ковиянич. Об асимптотике логарифма числа пороговых функций K-значной логики, Дискрет. матем., 1998, том 10, выпуск 3, страницы 35–56.