Сложность решения дискретных задач

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
Участники семинара (декабрь 2013 г.)

Спецсеминар для студентов и аспирантов кафедры математической кибернетики. В 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 Текст программы, Результаты