Сложность решения дискретных задач
Спецсеминар для студентов и аспирантов кафедры математической кибернетики. В 2018-2019 уч.г. семинар проходит по пятницам с 16-20 до 17-55 в аудитории 503.
Руководители
Тематика семинара
Вычислительная сложность; быстрые алгоритмы; труднорешаемые задачи; дискретные функции; графы.
Расписание докладов
Весенний семестр 2018-2019 учебного года
Заседания семинара проходят совместно с семинаром Теория дискретных функций механико-математического факультета МГУ, руководители: Жук Дмитрий Николаевич, Галатенко Алексей Владимирович
Участники семинара: Жорина Александра (618/1 гр.), Сакович Марк (518/1 гр.), Мазуренко Анастасия (518/1 гр.), Шурыгин Дмитрий (418 гр.), Лобанов Алексей (418 гр.), Мартынов Петр (318 гр.), Романов Андрей (318 гр.), Борсова Зурета (318 гр.). В весеннем семестре 2018-2019 учебного года заседания семинара проходят по пятницам с 16-20 до 17-55 в ауд. 503.
| Дата | Доклад | Докладчик |
|---|---|---|
| 29 марта 2019 г.
О сложности проверки полиномиальной полноты конечных квазигрупп. Доклад по статье: Галатенко А.В., Панкратьев А.Е. // Дискретная математика. 2018. Т. 30, вып. 4. С. 3-11. |
Галатенко А.В. (МГУ имени М.В. Ломоносова, мех-мах ф-т) | |
| 15 марта 2019 г. | Сложность решения систем уравнений в полиномиально полной алгебре. В докладе доказывается NP-полнота задачи о совместности системы уравнений над полиномиально полной алгеброй. Доклад по статье: Horvath G., Nehaniv C.L., Szabo C. An assertion concerning functionally complete algebras and NP-completeness // Theoretical Computer Science. 2008. V. 407. P. 591-595. | Сакович Марк (618/1 гр.) |
| 1 марта 2019 г. | Оптимальный алгоритм для k-согласованности системы предикатов. В докладе рассматривается оптимальный алгоритм приведения произвольной системы предикатов к k-согласованной с сохранением множества решений. Доклад по статье: Cooper M.C. An optimal k-consistency algorithm // Artificial Intelligence. 1989. V. 41. P. 89-95. | Лобанов Алексей (418 гр.) |
| 22 февраля 2019 г. | Организационное заседание |
Осенний семестр 2018-2019 учебного года
Участники семинара: Жорина Александра (618/1 гр.), Сакович Марк (518/1 гр.), Мазуренко Анастасия (518/1 гр.), Шурыгин Дмитрий (418 гр.), Лобанов Алексей (418 гр.), Мартынов Петр (318 гр.), Романов Андрей (318 гр.), Борсова Зурета (318 гр.). В осеннем семестре 2018-2019 учебного года заседания семинара проходят по пятницам с 16-20 до 17-55 в ауд. 503.
| Дата | Доклад | Докладчик |
|---|---|---|
| 23 ноября 2018 г. | Сложность расшифровки монотонной функции. Доклад посвящен задаче расшифровки монотонных функций. Рассматривается оптимальный алгоритм расшифровки монотонных функций, построенный на основе разбиения единичного n-мерного куба на цепи Анселя. | Лю Юнцин (магистратура, 2-й курс) |
| 16 ноября 2018 г. | О существовании в графах m реберно непересекающихся остовных деревьев. В докладе доказывается необходимое и достаточное условие существования в связном графе m реберно непересекающихся остовных деревьев. Подграф H графа G называется его остовным деревом, если H содержит все вершины графа G и является деревом. | Мазуренко Анастасия (518/1 гр.) |
| 9 ноября 2018 г. | Сложность расшифровки счетчика делимости на m. В докладе рассматривается задача расшифровки функций, которые называются счетчиками делимости на m. Эти функции равны единице в том случае, когда в единицу обращается кратное m число их существенных переменных. В остальных случаях эти функции равны нулю. Предлагается асимптотически оптимальный алгоритм расшифровки функций из этого класса. | Сакович Марк (518/1 гр.) |
| 19 октября 2018 г. | Сложность систем функций над конечным полем нечетной характеристики в классе поляризованных полиномов. В докладе рассматриваются представления функций над конечным полем поляризованными полиномами, т.е. такими полиномами, в которых каждая переменная может быть смещена на определенную величину. Доказывается, что можно найти систему, содержащую всего две функции, сложность которой в классе поляризованных полиномов равна максимально возможной. Доклад по статье: Селезнева С.Н., Гордеев М.М. Сложность систем функций над конечным полем в классе поляризованных полиномиальных форм // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2017. № 4. С. 41-46. | Шурыгин Дмитрий (418 гр.) |
| 12 октября 2018 г. | Расшифровка слабо положительных дизъюнкций. В докладе рассматривается задача расшифровки функций алгебры логики, зависящих от n переменных, которые можно представить в виде элементарной дизъюнкции с ровно одной переменной с отрицанием. При расшифровке можно задавать вопросы о значении расшифровываемой функции на произвольном наборе значений ее переменных и получать правильные ответы. Функция считается расшифрованной, если восстановлены ее значения на всех возможных наборах значений ее переменных. Находятся верхняя и нижняя оценки наименьшего числа вопросов, которые требуется задать, чтобы расшифровать любую функцию от n переменных из рассматриваемого множества. | Жорина Александра (618/1 гр.) |
| 5 октября 2018 г. | Организационное заседание |
Весенний семестр 2017-2018 учебного года
Участники семинара: Мельник Марина (618/1 гр.), Астахова Анастасия (618/1 гр.), Жорина Александра (518/1 гр.), Сакович Марк (418 гр.), Мазуренко Анастасия (418 гр.), Соломатова Мария (418 гр.), Шурыгин Дмитрий (318 гр.), Лобанов Алексей (318 гр.), Самойлов Сергей (341 гр.). В весеннем семестре 2017-2018 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ по пятницам с 16-20 до 17-55 в ауд. 503.
| Дата | Доклад | Докладчик |
|---|---|---|
| 20 апреля 2018 г. | Представление выпускных работ студентов 418 группы. Презентации работ Мазуренко Анастасии, Саковича Марка, Соломатовой Марии. | Мазуренко Анастасия (418 гр.), Сакович Марк (418 гр.), Соломатова Мария (418 гр.) |
| 13 апреля 2018 г. | Представление выпускных работ студентов 618/1 группы. Презентации работ Астаховой Анастасии, Вершинина Александра, Мельник Марины. | Астахова Анастасия (618/1 гр.), Вершинин Александр (618/1 гр.), Мельник Марина (618/1 гр.), |
| 6 апреля 2018 г. | Попарная согласованность систем ограничений. Доклад по статье: Janssen P., Jegou P., Nouguier B., Vilarem M.C. A filtering process for general constraint satisfaction problems: achieving pairwise-consistency using an associated binary representations. 1989. | Шурыгин Дмитрий (318 гр.) |
| 30 марта 2018 г. | Достаточное условие для поиска без возврата. В докладе предлагается достаточное условие, при котором решение задачи выполнимости системы ограничений можно найти поиском без возврата. Доклад по статье: Freuder E.C. A sufficient condition for backtrack-free search // J. of the ACM. 1982. V. 29, N 1. P. 24-32. | Лобанов Алексей (318 гр.) |
| 16 марта 2018 г. | Верхние оценки сложности функций над непростыми конечными полями в классе поляризованных полиномов. Доклад по статье Казимирова А.С., Реймерова С.Ю. // Известия Иркутского государственного университета. Серия: Математика. 2017. № 17. С. 378–385. | Самойлов Сергей (341 гр.) |
| 2 марта 2018 г. | Раскраски в три цвета графов без треугольников: если граф без треугольников является планарным, то эта задача решается полиномиальным алгоритмом. Доклад по статье: Grunbaum B. Grotzsch’s theorem on 3-coloring. | Жорина Александра (518/1 гр.) |
Осенний семестр 2017-2018 учебного года
Участники семинара: Мельник Марина (618/1 гр.), Астахова Анастасия (618/1 гр.), Жорина Александра (518/1 гр.), Сакович Марк (418 гр.), Мазуренко Анастасия (418 гр.), Соломатова Мария (418 гр.), Шурыгин Дмитрий (318 гр.), Лобанов Алексей (318 гр.), Самойлов Сергей (341 гр.). В осеннем семестре 2017-2018 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ по пятницам с 16-20 до 17-55 в ауд. 505.
| Дата | Доклад | Докладчик |
|---|---|---|
| 8 декабря 2017 г. | Раскраски в три цвета графов без треугольников: NP-полнота задачи раскраски в 3 цвета графов без треугольников; если граф без треугольников является планарным, то эта задача решается полиномиальным алгоритмом. Доклад по статьям: Maffray F., Preissmann M. On the NP-completeness of the k-colorability problem for triangle-free graphs // Discrete Mathematics. 1996. V. 162. P. 313-317; Grunbaum B. Grotzsch’s theorem on 3-coloring. | Жорина Александра (518/1 гр.) |
| 1 декабря 2017 г. | Применение кодов восстановления LRC для хранения данных в Яндексе | Мазуров А.А. (Яндекс) |
| 22 ноября (среда) 2017 г. | Упаковки и покрытия путей в графах и кёниговы графы аннотация доклада | Мокеев Д.Б. (ННГУ) |
| 17 ноября 2017 г. | Полиномиальность задачи о раскраске в 3 цвета графа без порожденных простых цепей с 6 вершинами (продолжение доклада). Доклад по статье: Randerath B., Schiermeyer I. 3-Colorability \in P for P_6-free graphs // Discrete Applied Mathematics. 2004. V. 136. P. 299-313. | Астахова Анастасия, 618/1 гр. |
| 10 октября 2017 г. | Толщина полного графа. Доклад по статье: Алексеев В.Б., Гончаков В.С. Толщина произвольного полного графа // Матем. сб. 1976. Т. 101(143), вып. 2(10). | Алексеев В.Б. |
| 27 октября 2017 г. | Полиномиальность задачи о раскраске в 3 цвета графа без порожденных простых цепей с 6 вершинами. Доклад по статье: Randerath B., Schiermeyer I. 3-Colorability \in P for P_6-free graphs // Discrete Applied Mathematics. 2004. V. 136. P. 299-313. | Астахова Анастасия, 618/1 гр. |
| 13 октября 2017 г. | NP-полнота некоторых задач о раскраске графов без заданных порожденных подграфов: о раскраске в 4 цвета графа без порожденных простых цепей с 8 вершинами; о предраскраскраске в 4 цвета графа без порожденных простых цепей с 7 вершинами. Доклад по статье: Broesma H., Golovach P.A., Paulusma D., Song J. Updating the complexity status of coloring graphs without a fixed induced linear forest // Theoretacal Computer Science. 2012. V. 441. P. 9-19. | Сакович Марк, 418 гр. |
| 6 октября 2017 г. | NP-полнота некоторых задач о раскраске графов: о раскраске графа в 3 цвета; о раскраске в 3 цвета графа со степенями вершин, не более 4; о раскраске в 3 цвета планарного графа. | Мельник Марина, 618/1 гр. |
Весенний семестр 2016-2017 учебного года
Участники семинара: Гордеев Михаил (618/1 гр.), Мельник Марина (518/1 гр.), Астахова Анастасия (518/1 гр.), Кизилов Роман (518/1 гр.), Жорина Александра (418 гр.), Мотырева Елена (318 гр.), Сакович Марк (318 гр.), Соломатова Мария (318 гр.). В весеннем семестре 2016-2017 учебного года заседания семинара проходят совместно с семинарами Дискретные функции и сложность алгоритмов и Дискретный анализ.
| Дата | Доклад | Докладчик |
|---|---|---|
| 31 марта 2017 г. | NP-полнота некоторых задач о раскраске графов: о раскрашиваемости графа в 3 цвета; о раскрашиваемости в 3 цвета графа со степенями вершин, не более 4; о раскрашиваемости в 3 цвета планарного графа. | Мельник Марина, 518/1 гр. |
| 3 марта 2017 г. | О сложности нахождения веса функции по ее полиному Жегалкина | Жорина Александра, 418 гр. |
Осенний семестр 2016-2017 учебного года
Участники семинара: Гордеев Михаил (618/1 гр.), Мельник Марина (518/1 гр.), Астахова Анастасия (518/1 гр.), Кизилов Роман (518/1 гр.), Жорина Александра (418 гр.), Мотырева Елена (318 гр.), Сакович Марк (318 гр.), Соломатова Мария (318 гр.). В осеннем семестре 2016-2017 учебного года заседания семинара проходят совместно с семинарами Дискретные функции и сложность алгоритмов и Дискретный анализ.
Весенний семестр 2015-2016 учебного года
Участники семинара: Гордеев Михаил (518/1 гр.), Мельник Марина (418 гр.), Жорина Александра (318 гр.). В весеннем семестре 2015-2016 учебного года заседания семинара проходят совместно с семинарами Дискретные функции и сложность алгоритмов и Дискретный анализ.
Осенний семестр 2015-2016 учебного года
Участники семинара: Гордеев Михаил (518/1 гр.), Мельник Марина (418 гр.), Жорина Александра (318 гр.). В осеннем семестре 2015-2016 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ.
Осенний семестр 2014-2015 учебного года
Участники семинара: Ким Игорь (518 гр.), Плаксина Анна (518 гр.), Хрулев Егор (518 гр.), Гордеев Михаил (418 гр.), Мельник Марина (318 гр.). В осеннем семестре 2014-2015 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ.
| Дата | Доклад | Докладчик |
|---|---|---|
| 28 ноября 2014 г. | Хрулев Егор, 518 гр. | |
| 31 октября 2014 г. | О сложности функций k-значной логики в классе поляризованных полиномиальных форм.
Доклад по статье С.Н. Селезневой, "Дискретная математика", 2002. |
Гордеев Михаил, 418 гр. |
| 10 октября 2014 г. | О сложности функций алгебры логики в классе поляризованных полиномиальных форм.
Доклад по статье Н.А. Перязева, "Алгебра и логика", 1995, т. 34, N 3. |
Ким Игорь, 518 гр. |
Весенний семестр 2013-2014 учебного года
В весеннем семестре 2013-2014 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ.
| Дата | Доклад | Докладчик |
|---|---|---|
| 28 марта 2014 г. | Хрулев Егор (418 гр.) | |
| 21 марта 2014 г. | О длине булевых функций в классе полиномиальных форм с аффинными множителями в слагаемых. Доклад по статье Селезневой С.Н. | Гордеев Михаил (318 гр.) |
| 14 марта 2014 г. | О мультипликативной сложности квадратичных булевых функций. Доклад по статье Mirwald R., Schnorr C.P. The multiplicative complexity of quadratic boolean forms // Theoretical Computer Science. 102. 1992. P. 307-328. | Плаксина Анна (418 гр.) |
| 21 февраля 2014 г. | Организационное заседание семинара |
Осенний семестр 2013-2014 учебного года
В осеннем семестре 2013-2014 учебного года участники семинара выполняют практическое задание. Оно состоит в написании программы построения больших простых чисел по алгоритмам из работы Садовник Е.В. Проверка на простоту некоторых чисел вида 2kp^m-1 // Дискретная математика, 2006, т. 18, вып. 1, с. 146-155 (http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=38&option_lang=rus) и получении экспериментальных результатов. Цели исследований:
1. Изучить быстрые алгоритмы построения больших простых чисел.
2. Написать программу с использованием библиотеки для работы с большими числами.
3. Исследовать, насколько эффективно (с точки зрения времени работы) алгоритм, имеющий хорошую теоретическую оценку временной сложности, работает на практике.
4. Получить экспериментальные результаты - простые числа с десятками тысяч десятичных знаков.
Выход на суперкомпьютеры не предполагается, студенты пользуются персональными компьютерами.
| Студент | Вид чисел | Результаты |
|---|---|---|
| Красиков Антон, 518 группа | N = 2 * k * 7^m - 1 | Текст программы, Результат №1, Результат №2 |
| Плаксина Анна, 418 группа | N = 2 * 3^m - 1 | Текст программы и результаты |
| Хрулев Егор, 418 группа | N = 2 * k * 3^m - 1 | Текст программы, Результаты |
| Гордеев Михаил, 318 группа | N = 2 * 7^m - 1 | Текст программы, Результаты |
