|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Линейная комбинаторикаучебный курс
- Автор: Ирматов А.А.
- Год создания: 2008
- Организация: МГУ имени М.В. Ломоносова
- Описание: Аннотация курса: В курсе изучаются свойства пучков гиперплоскостей вероятностно-комбинаторными и алгебро-топологическими методами, даются верхние и нижние оценки числа пороговых функций, разбирается доказательство Tao-Vũ о числе вырожденных ±1-матриц. Изучаются спектральные свойства пороговых функций; проблема параметров Чжоу; РАС-обучающие алгоритмы для класса пороговых функций Тематическое содержание курса Тема 1 Нижние оценки Yajima-Ibaraki и Muroga-Toda числа пороговых функций. Верхняя оценка числа пороговых функций. Тема 2 Верхняя оценка для максимального веса пороговой функции. Пример J.Håstad пороговой функции с экспоненциальным минимальным весом. Тема 3 Свойства Анти-Адамаровых (Anti-Hadamard) матриц. Построение пороговых функций Håstad'а для размерностей, отличных от степени 2. Тема 4 Верхняя оценка для норм матриц, обратных к (0,1) или (-1,+1)-матрицам. Оценка минимально возможного расстояния от заданной вершины (0,1)-куба до гиперплоскости, порожденной вершинами этого куба и не содержащей заданную вершину. Тема 5 Граничные точки пороговых функций. Определяющая выборка и определяющее число для гипотезы из заданного класса. Оценки для определяющего числа гипотезы из класса пороговых функций. Тема 6 Терема Sperner’a. Лемма Littlewood-Offord’а. Теорема A.Odlyzko о подпространствах, порожденных ±1-векторами. Тема 7 Теорема A.Odlyzko о подпространствах, порожденных ±1-векторами. Нижняя оценка А.А.Ирматова числа пороговых функций. Асимптотика логарифма числа пороговых функций K-значной логики. функций. Асимптотика логарифма числа пороговых функций K-значной логики. Тема 8 Теорема Komlós'a о числе вырожденных (0,1)-матрицах. Тема 9 Комбинаторная размерность и комбинаторный Грассманиан. Теорема Freiman'a. Тема 10 Теорема Freiman'a. Тема 11 Структурная теорема о строении исключительных подпространств комбинаторного Грассманиана. Теорема Tao-Vũ о числе вырожденных ±1-матриц. Тема 12 Теорема Tao-Vũ о числе вырожденных ±1-матриц- окончание Тема 13 Частично-упорядоченное множество пучка гиперплоскостей. Функция Мёбиуса и характеристический полином пучка гиперплоскостей. Теорема о поперечном сечении (The Cross-Cut Theorem). Теорема Уитни о характеристическом полиноме пучка гиперплоскостей. Тема 14 Функция Мёбиуса геометрической решетки. Теорема Т.Заславского (1975). Тема 15 Алгебро-топологическое описание функции Мёбиуса пучка гиперплоскостей. Тема 16 Алгебро-топологическое описание функции Мёбиуса пучка гиперплоскостей- продолжение. Тема 17 Гармонический анализ на булевом кубе. Тема 18 Тест BLR (M. Blum, Luby, and Rubinfeld) на e-близость булевой функции к линейной. Тест J.Håstad'а на e-близость булевой функции к “диктатор-функции” (f(x)=xi). Тема 19 Влияние переменной и ее интерпретация для функций со значениями ±1. Оценка влияния функции Maj(x) Тема 20 Теорема FKN (Friedgut, Kalai and Naor) о близости булевой функции к 1-хунте. Тема 21 Теорема KKL (Kahn-Kalai-Linial). Тема 22 Теорема Friedgut. Тема 23 Приложения теоремы KKL Тема 24 Спектральные свойства пороговых функций. Тема 25 Шумоустойчивость и обучаемость класса линейных пороговых функций. Теорема Переса Тема 26 Проблема параметров Чжоу (Chow). Тема 27 Проблема параметров Чжоу (Chow)- продолжение. Тема 28 PAC-обучающий алгоритм для класса пороговых функций. Тема 29 PAC-обучающий алгоритм для класса пороговых функций- продолжение. Тема 30 Теорема Berry-Essen'a Тема 31 Приближение пороговой функции пороговой функцией с малым весом (n3/22Õ(1/e^2/3)) Тема 32 Приближение пороговой функции пороговой функцией с малым весом (n3/22Õ(1/e^2/3))- продолжение.
- Добавил в систему: Ирматов Анвар Адхамович
Преподавание курса
- 14 февраля 2023 - 19 декабря 2023 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 15 февраля 2022 - 20 декабря 2022 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 9 февраля 2021 - 14 декабря 2021 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 11 февраля 2020 - 15 декабря 2020 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 12 февраля 2019 - 17 декабря 2019 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 13 февраля 2018 - 18 декабря 2018 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 7 февраля 2017 - 19 декабря 2017 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 9 февраля 2016 - 20 декабря 2016 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 10 февраля 2015 - 15 декабря 2015 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.
- 11 февраля 2014 - 16 декабря 2014 Ирматов Анвар Адхамович
- МГУ имени М.В. Ломоносова, Механико-математический факультет, Отделение математики, Кафедра математической теории интеллектуальных систем
- факультативная, лекции, 68 часов
- Автор: Ирматов А.А.