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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Расписание докладов)
 
(не показаны 74 промежуточных версий 1 участника)
Строка 1: Строка 1:
 
[[image:seminar1.jpg|thumb|right|Участники семинара (декабрь 2013 г.)]]
 
[[image:seminar1.jpg|thumb|right|Участники семинара (декабрь 2013 г.)]]
  
−
Спецсеминар для студентов и аспирантов кафедры математической кибернетики. В 2017-2018 уч.г. семинар проходит по пятницам с 16-20 до 17-55 в аудитории 505.
+
Спецсеминар для студентов кафедры математической кибернетики.  
 +
 
 +
В весеннем семестре 2021-2022 уч.г. семинар проходит удаленно.
  
 
==Руководители==
 
==Руководители==
 
[[Селезнева_Светлана_Николаевна|Селезнева Светлана Николаевна]]
 
[[Селезнева_Светлана_Николаевна|Селезнева Светлана Николаевна]]
−
 
−
[[Бухман_Антон_Владимирович|Бухман Антон Владимирович]]
 
  
 
== Тематика семинара ==
 
== Тематика семинара ==
  
−
На семинаре изучается алгоритмическая сложность распознавания свойств дискретных функций.
+
Дискретные структуры, алгоритмы на дискретных структурах и их сложность (дискретные функции и графы, их свойства; алгоритмы распознавания свойств дискретных функций и графов и их сложность).
−
Быстрые алгоритмы обеспечивают эффективность вычислений, а алгоритмическая сложность задачи показывает возможности ее эффективного решения.  
+
  
−
На семинаре также изучаются вид, свойства и сложность некоторых представлений дискретных функций. Различные представления дискретных функций и их свойства применяются, например, при построении быстрых алгоритмов, при представлении данных в компьютерах, при проектировании интегральных схем.
+
== Расписание докладов ==
  
−
При решении перечисленных задач часто возникают графы, комбинаторные множества, поэтому на семинаре также уделяется внимание изучению этих дискретных структур.
+
'''Весенний семестр 2020-2021 учебного года'''
  
−
[[Media:2-2015-selezn.pdf|Информация для студентов 2-го курса]]
+
Участники семинара: Лобанов Алексей (618/1 гр.), Макеев Владислав (518/1 гр.), Светиков Илья (518/1 гр.), Фэн Цзэпэн (518/1 гр.), Романов Андрей (518/1 гр.), Мартынов Петр (418 гр.), Мироненко Андрей (418 гр.), Савельев Александр (418 гр.), Акиндинов Никита (318 гр.), Бубнов Егор (318 гр.), Молдахметова Индира (318 гр.), Селевенко Роман (318 гр.), Королев Федор (318 гр.).
  
−
== Расписание докладов ==
+
 
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 5 марта 2021 г.
 +
| '''Расшифровка трехзначных монотонных функций'''. В докладе рассматривается оптимальный алгоритм расшифровки трехзначных монотонных функций. Доклад по статье: Алексеев В.Б. О расшифровке некоторых классов монотонных многозначных функций. Журнал вычислительной математики и математической физики.1976. Т. 16, N 1. С. 189-198.
 +
| Лю Юнцин (аспирантка 2 г.о.)
 +
|-
 +
|}
 +
 
 +
 
 +
'''Осенний семестр 2020-2021 учебного года'''
 +
 
 +
Участники семинара: Лебедев Марк (618/1 гр.), Лобанов Алексей (618/1 гр.), Макеев Владислав (518/1 гр.), Светиков Илья (518/1 гр.), Фэн Цзэпэн (518/1 гр.), Романов Андрей (518/1 гр.), Мартынов Петр (418 гр.), Мироненко Андрей (418 гр.), Савельев Александр (418 гр.), Акиндинов Никита (318 гр.), Бубнов Егор (318 гр.), Молдахметова Индира (318 гр.), Селевенко Роман (318 гр.), Королев Федор (318 гр.).
 +
 
 +
 
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 18 декабря 2020 г.
 +
| Отчет по преддипломной практике.
 +
| Лебедев Марк (618/1 гр.), Лобанов Алексей (618/1 гр.), Мартынов Петр (418 гр.), Мироненко Андрей (418 гр.), Савельев Александр (418 гр.)
 +
|-
 +
|-
 +
| 11 декабря 2020 г.
 +
| Обсуждение литературы и курсовых и выпускных работ с научными руководителями. 
 +
|-
 +
| 13, 20, 27 ноября, 4 декабря 2020 г.
 +
| Обсуждение литературы и курсовых и выпускных работ с научными руководителями. 
 +
|
 +
|-
 +
| 6 ноября 2020 г.
 +
| Доклады с обзором литературы по теме выпускных работ. 
 +
| Мартынов Петр (418 гр.), Мироненко Андрей (418 гр.), Савельев Александр (418 гр.)
 +
|-
 +
| 30 октября 2020 г.
 +
| Доклады с обзором литературы по теме выпускных и курсовых работ.
 +
| Лебедев Марк (618/1 гр.), Лобанов Алексей (618/1 гр.), Романов Андрей (518/1 гр.)
 +
|-
 +
| 2, 9, 16, 23 октября 2020 г.
 +
| Обсуждение литературы и курсовых и выпускных работ с научными руководителями.
 +
|
 +
|-
 +
| 25 сентября 2020 г.
 +
| Организационное собрание
 +
|
 +
|-
 +
|}
 +
 
 +
 
 +
'''Весенний семестр 2019-2020 учебного года'''
 +
 
 +
Участники семинара: Лебедев Марк (618/1 гр.), Мазуренко Анастасия (618/1 гр.), Лобанов Алексей (518/1 гр.), Шурыгин Дмитрий (518/1 гр.), Романов Андрей (418 гр.), Мартынов Петр (318 гр.), Мироненко Андрей (318 гр.), Савельев Александр (318 гр.).
 +
 
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 15 мая 2020 г.
 +
| Представление курсовых работ участников семинара.
 +
| Лобанов А. (518/1 гр.), Шурыгин Д. (518/1 гр.), Мартынов П. (318 гр.), Мироненко А. (318 гр.), Савельев А. (318 гр.)
 +
|-
 +
| 24 апреля 2020 г.
 +
| Представление выпускных работ участников семинара.
 +
| Мазуренко А. (618/1 гр.), Романов А. (418 гр.)
 +
|-
 +
| 17 апреля 2020 г.
 +
| '''Проверка периодичности функций алгебры логики'''.
 +
| Савельев Александр (318 гр.)
 +
|-
 +
| 10 апреля 2020 г.
 +
| '''Пять видов минимальных замкнутых классов в k-значной логике'''.
 +
| Лобанов Алексей (518/1 гр.)
 +
|-
 +
| 3 апреля 2020 г.
 +
| '''Алгоритм минимизации псевдополиномиальных форм функций алгебры логики'''.
 +
| Шурыгин Дмитрий (518/1 гр.)
 +
|-
 +
| 27 марта 2020 г.
 +
| Тема уточняется
 +
| Яшунский А.Н. (ИПМ РАН)
 +
|-
 +
| 20 марта 2020 г.
 +
| '''Замкнутые классы в k-значной логике, содержащие все функции одной переменной'''.
 +
| Мартыненко Петр (318 гр.)
 +
|-
 +
| 13 марта 2020 г.
 +
| '''Применение SAT-решателей для минимизации полиномиальных форм функций алгебры логики'''.
 +
| Романов Андрей (418 гр.)
 +
|-
 +
| 6 марта 2020 г.
 +
| '''Некоторые вопросы синтеза параллельных схем'''.
 +
| Сергеев И.С. (ФГУП "Квант")
 +
|-
 +
| 28 февраля 2020 г.
 +
| Организационное собрание
 +
|
 +
|-
 +
|}
 +
 
 +
 
 +
'''Осенний семестр 2019-2020 учебного года'''
 +
 
 +
Участники семинара: Лебедев Марк (618/1 гр.), Мазуренко Анастасия (618/1 гр.), Лобанов Алексей (518/1 гр.), Шурыгин Дмитрий (518/1 гр.), Борсова Зурета (418 гр.), Романов Андрей (418 гр.), Мартынов Петр (318 гр.), Мироненко Андрей (318 гр.), Савельев Александр (318 гр.).
 +
 
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 6 декабря 2019 г.
 +
| '''Алгоритм построения реберно непересекающихся остовных деревьев'''. В докладе рассматривается полиномиальный алгоритм, который для заданного графа G проверяет, найдутся ли в этом графе два реберно непересекающихся остовных дерева, и при положительном ответе выдает эти два дерева. Доклад по статье: Roskind J., Tarjan R.E. A note of finding minimum-cost edge-disjoint spanning trees // Mathematics of Operations Research. 1985. V. 10, N 4. P. 701-708.
 +
| Мазуренко Анастасия (618/1 гр.)
 +
|-
 +
| 22 и 29 ноября 2019 г.
 +
| '''Параметро-эффективная расшифровка функций алгебры логики'''. В докладе показывается, что расшифровать любую функцию алгебры логики n переменных, если заранее известно, что у нее не более k существенных переменных, можно с логарифмической сложностью относительно n. Доклад по статье: Damaschke P. Adaptive Versus Nonadaptive Attribute-Efficient Learning // Machine Learning. 2000. V. 41. P. 197–215.
 +
| Лебедев Марк (618/1 гр.)
 +
|-
 +
| 18 и 25 октября 2019 г.
 +
| '''Простой алгоритм для мальцевских ограничений'''. В докладе рассматривается полиномиальный алгоритм проверки выполнимости системы ограничений, удовлетворяющих некоторой мальцевской операции. Доклад по статье: Bulatov A., Dalmau V. A simple algorithm for Mal'tsev constraints // SIAM J. Computing. 2006. V. 36, N 1. P. 16-27.
 +
| Мартынов Петр (318 гр.)
 +
|-
 +
| 11 октября 2019 г.
 +
| Организационное собрание
 +
|
 +
|-
 +
|}
 +
 
 +
 
 +
'''Весенний семестр 2018-2019 учебного года'''
 +
 
 +
Заседания семинара проходят совместно с семинаром '''Теория дискретных функций''' механико-математического факультета МГУ, руководители: '''Жук Дмитрий Николаевич''', '''Галатенко Алексей Владимирович'''
 +
 
 +
Участники семинара: Жорина Александра (618/1 гр.), Сакович Марк (518/1 гр.), Мазуренко Анастасия (518/1 гр.), Шурыгин Дмитрий (418 гр.), Лобанов Алексей (418 гр.), Романов Андрей (318 гр.), Борсова Зурета (318 гр.). В весеннем семестре 2018-2019 учебного года заседания семинара проходят по пятницам с 16-20 до 17-55 в ауд. 503.
 +
 
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 17 мая 2019 г.
 +
| Представление курсовых работ участников семинара 3-го и 5-го курсов.
 +
| Мазуренко Анастасия (518/1 группа), Сакович Марк (518/1 группа), Борсова Зурета (318 группа)
 +
|-
 +
| 19 апреля 2019 г.
 +
| Представление выпускных работ участников семинара 4-го и 6-го курсов
 +
| Жорина Александра (618/1 группа), Лю Юнцин (М210 группа), Лобанов Алексей (418 группа), Шурыгин Дмитрий (418 группа)
 +
|-
 +
| 12 апреля 2019 г.
 +
| 
 +
| Романов Андрей (318 группа)
 +
|-
 +
| 5 апреля 2019 г.
 +
| '''О сложности проверки аффинности конечных квазигрупп'''. Доклад по статье: Галатенко А.В., Панкратьев А.Е. // Дискретная математика. 2018. Т. 30, вып. 4. С. 3-11.
 +
| Борсова Зурета (318 группа)
 +
|-
 +
| 29 марта 2019 г.
 +
| '''О сложности проверки полиномиальной полноты конечных квазигрупп'''. Доклад по статье: Галатенко А.В., Панкратьев А.Е. // Дискретная математика. 2018. Т. 30, вып. 4. С. 3-11.
 +
| Галатенко А.В. (МГУ имени М.В. Ломоносова, мех.-мат. ф-т)
 +
|-
 +
| 22 марта 2019 г.
 +
| '''Сложность решения систем уравнений над конечной группой'''. В докладе рассматривается  задача о совместности системы уравнений над конечной группой G. Показано, что эта задача - полиномиальна, если G - коммутативна, и эта задача - NP-полна, если G - некоммутативна.  Доклад по статье: Goldmann M. The complexity of solving equations over finite groups // Information and Computation. 2002. V. 178. P. 253-262. 
 +
| Мазуренко Анастасия (518/1 гр.)
 +
|-
 +
| 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. 
 +
| Сакович Марк (518/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.
 +
 
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 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.
 +
 
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 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 учебного года'''
 
'''Осенний семестр 2017-2018 учебного года'''
  
−
Слушатели семинара: Мельник Марина (618/1 гр.), Астахова Анастасия (618/1 гр.), Жорина Александра (518/1 гр.), Сакович Марк (418 гр.), Мазуренко Анастасия (418 гр.), Соломатова Мария (418 гр.), Шурыгин Дмитрий (318 гр.), Лобанов Алексей (318 гр.), Самойлов Сергей (341 гр.). В осеннем семестре 2017-2018 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]] по пятницам с 16-20 до 17-55 в ауд. 505.
+
Участники семинара: Мельник Марина (618/1 гр.), Астахова Анастасия (618/1 гр.), Жорина Александра (518/1 гр.), Сакович Марк (418 гр.), Мазуренко Анастасия (418 гр.), Соломатова Мария (418 гр.), Шурыгин Дмитрий (318 гр.), Лобанов Алексей (318 гр.), Самойлов Сергей (341 гр.). В осеннем семестре 2017-2018 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]] по пятницам с 16-20 до 17-55 в ауд. 505.
  
 
{| class="wide" width="100%"
 
{| class="wide" width="100%"
Строка 29: Строка 280:
 
! Доклад
 
! Доклад
 
! Докладчик
 
! Докладчик
 +
|-
 +
| 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 г.
 +
| Упаковки и покрытия путей в графах и кёниговы графы [[Media: mokeev-22-11-17.docx|аннотация доклада]]
 +
| Мокеев Д.Б. (ННГУ)
 +
|-
 +
| 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 г.
 
| 13 октября 2017 г.
−
| NP-полнота некоторых задач о раскраске графов без заданных порожденных подграфов: о раскраске в 4 цвета графа без порожденных цепей с 8 вершинами; о предраскраскраске в 4 цвета графа без порожденных цепей с 7 вершинами.
+
| 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 гр.
 
| Сакович Марк, 418 гр.
 
|-
 
|-
 
| 6 октября 2017 г.
 
| 6 октября 2017 г.
−
| NP-полнота некоторых задач о раскраске графов: о раскрашиваемости графа в 3 цвета; о раскрашиваемости в 3 цвета графа со степенями вершин, не более 4; о раскрашиваемости в 3 цвета планарного графа.
+
| NP-полнота некоторых задач о раскраске графов: о раскраске графа в 3 цвета; о раскраске в 3 цвета графа со степенями вершин, не более 4; о раскраске в 3 цвета планарного графа.
 
| Мельник Марина, 618/1 гр.
 
| Мельник Марина, 618/1 гр.
 
|-
 
|-
Строка 42: Строка 317:
 
'''Весенний семестр 2016-2017 учебного года'''
 
'''Весенний семестр 2016-2017 учебного года'''
  
−
Слушатели семинара: Гордеев Михаил (618/1 гр.), Мельник Марина (518/1 гр.), Астахова Анастасия (518/1 гр.), Кизилов Роман (518/1 гр.), Жорина Александра (418 гр.), Мотырева Елена (318 гр.), Сакович Марк (318 гр.), Соломатова Мария (318 гр.). В весеннем семестре 2016-2017 учебного года заседания семинара проходят совместно с семинарами [[Дискретные функции и сложность алгоритмов]] и [[Дискретный анализ]].
+
Участники семинара: Гордеев Михаил (618/1 гр.), Мельник Марина (518/1 гр.), Астахова Анастасия (518/1 гр.), Кизилов Роман (518/1 гр.), Жорина Александра (418 гр.), Мотырева Елена (318 гр.), Сакович Марк (318 гр.), Соломатова Мария (318 гр.). В весеннем семестре 2016-2017 учебного года заседания семинара проходят совместно с семинарами [[Дискретные функции и сложность алгоритмов]] и [[Дискретный анализ]].
  
 
{| class="wide" width="100%"
 
{| class="wide" width="100%"
Строка 61: Строка 336:
 
'''Осенний семестр 2016-2017 учебного года'''
 
'''Осенний семестр 2016-2017 учебного года'''
  
−
Слушатели семинара: Гордеев Михаил (618/1 гр.), Мельник Марина (518/1 гр.), Астахова Анастасия (518/1 гр.), Кизилов Роман (518/1 гр.), Жорина Александра (418 гр.), Мотырева Елена (318 гр.), Сакович Марк (318 гр.), Соломатова Мария (318 гр.). В осеннем семестре 2016-2017 учебного года заседания семинара проходят совместно с семинарами [[Дискретные функции и сложность алгоритмов]] и [[Дискретный анализ]].
+
Участники семинара: Гордеев Михаил (618/1 гр.), Мельник Марина (518/1 гр.), Астахова Анастасия (518/1 гр.), Кизилов Роман (518/1 гр.), Жорина Александра (418 гр.), Мотырева Елена (318 гр.), Сакович Марк (318 гр.), Соломатова Мария (318 гр.). В осеннем семестре 2016-2017 учебного года заседания семинара проходят совместно с семинарами [[Дискретные функции и сложность алгоритмов]] и [[Дискретный анализ]].
  
 
'''Весенний семестр 2015-2016 учебного года'''
 
'''Весенний семестр 2015-2016 учебного года'''
  
−
Слушатели семинара: Гордеев Михаил (518/1 гр.), Мельник Марина (418 гр.), Жорина Александра (318 гр.). В весеннем семестре 2015-2016 учебного года заседания семинара проходят совместно с семинарами [[Дискретные функции и сложность алгоритмов]] и [[Дискретный анализ]].
+
Участники семинара: Гордеев Михаил (518/1 гр.), Мельник Марина (418 гр.), Жорина Александра (318 гр.). В весеннем семестре 2015-2016 учебного года заседания семинара проходят совместно с семинарами [[Дискретные функции и сложность алгоритмов]] и [[Дискретный анализ]].
  
 
'''Осенний семестр 2015-2016 учебного года'''
 
'''Осенний семестр 2015-2016 учебного года'''
  
−
Слушатели семинара: Гордеев Михаил (518/1 гр.), Мельник Марина (418 гр.), Жорина Александра (318 гр.). В осеннем семестре 2015-2016 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].
+
Участники семинара: Гордеев Михаил (518/1 гр.), Мельник Марина (418 гр.), Жорина Александра (318 гр.). В осеннем семестре 2015-2016 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].
  
 
'''Осенний семестр 2014-2015 учебного года'''
 
'''Осенний семестр 2014-2015 учебного года'''
  
−
Слушатели семинара: Ким Игорь (518 гр.), Плаксина Анна (518 гр.), Хрулев Егор (518 гр.), Гордеев Михаил (418 гр.), Мельник Марина (318 гр.). В осеннем семестре 2014-2015 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].
+
Участники семинара: Ким Игорь (518 гр.), Плаксина Анна (518 гр.), Хрулев Егор (518 гр.), Гордеев Михаил (418 гр.), Мельник Марина (318 гр.). В осеннем семестре 2014-2015 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].
  
 
{| class="wide" width="100%"
 
{| class="wide" width="100%"
Строка 118: Строка 393:
 
|-
 
|-
 
| 21 февраля 2014 г.
 
| 21 февраля 2014 г.
−
| Организационное заседание семинара
+
| Организационное собрание
 
|
 
|
 
|}
 
|}
Строка 124: Строка 399:
 
'''Осенний семестр 2013-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) и получении экспериментальных результатов. Цели исследований:
+
В осеннем семестре 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. Изучить быстрые алгоритмы построения больших простых чисел.
 
1. Изучить быстрые алгоритмы построения больших простых чисел.

Текущая версия на 00:41, 3 апреля 2022

Участники семинара (декабрь 2013 г.)

Спецсеминар для студентов кафедры математической кибернетики.

В весеннем семестре 2021-2022 уч.г. семинар проходит удаленно.

Руководители

Селезнева Светлана Николаевна

Тематика семинара

Дискретные структуры, алгоритмы на дискретных структурах и их сложность (дискретные функции и графы, их свойства; алгоритмы распознавания свойств дискретных функций и графов и их сложность).

Расписание докладов

Весенний семестр 2020-2021 учебного года

Участники семинара: Лобанов Алексей (618/1 гр.), Макеев Владислав (518/1 гр.), Светиков Илья (518/1 гр.), Фэн Цзэпэн (518/1 гр.), Романов Андрей (518/1 гр.), Мартынов Петр (418 гр.), Мироненко Андрей (418 гр.), Савельев Александр (418 гр.), Акиндинов Никита (318 гр.), Бубнов Егор (318 гр.), Молдахметова Индира (318 гр.), Селевенко Роман (318 гр.), Королев Федор (318 гр.).


Дата Доклад Докладчик
5 марта 2021 г. Расшифровка трехзначных монотонных функций. В докладе рассматривается оптимальный алгоритм расшифровки трехзначных монотонных функций. Доклад по статье: Алексеев В.Б. О расшифровке некоторых классов монотонных многозначных функций. Журнал вычислительной математики и математической физики.1976. Т. 16, N 1. С. 189-198. Лю Юнцин (аспирантка 2 г.о.)


Осенний семестр 2020-2021 учебного года

Участники семинара: Лебедев Марк (618/1 гр.), Лобанов Алексей (618/1 гр.), Макеев Владислав (518/1 гр.), Светиков Илья (518/1 гр.), Фэн Цзэпэн (518/1 гр.), Романов Андрей (518/1 гр.), Мартынов Петр (418 гр.), Мироненко Андрей (418 гр.), Савельев Александр (418 гр.), Акиндинов Никита (318 гр.), Бубнов Егор (318 гр.), Молдахметова Индира (318 гр.), Селевенко Роман (318 гр.), Королев Федор (318 гр.).


Дата Доклад Докладчик
18 декабря 2020 г. Отчет по преддипломной практике. Лебедев Марк (618/1 гр.), Лобанов Алексей (618/1 гр.), Мартынов Петр (418 гр.), Мироненко Андрей (418 гр.), Савельев Александр (418 гр.)
11 декабря 2020 г. Обсуждение литературы и курсовых и выпускных работ с научными руководителями.
13, 20, 27 ноября, 4 декабря 2020 г. Обсуждение литературы и курсовых и выпускных работ с научными руководителями.
6 ноября 2020 г. Доклады с обзором литературы по теме выпускных работ. Мартынов Петр (418 гр.), Мироненко Андрей (418 гр.), Савельев Александр (418 гр.)
30 октября 2020 г. Доклады с обзором литературы по теме выпускных и курсовых работ. Лебедев Марк (618/1 гр.), Лобанов Алексей (618/1 гр.), Романов Андрей (518/1 гр.)
2, 9, 16, 23 октября 2020 г. Обсуждение литературы и курсовых и выпускных работ с научными руководителями.
25 сентября 2020 г. Организационное собрание


Весенний семестр 2019-2020 учебного года

Участники семинара: Лебедев Марк (618/1 гр.), Мазуренко Анастасия (618/1 гр.), Лобанов Алексей (518/1 гр.), Шурыгин Дмитрий (518/1 гр.), Романов Андрей (418 гр.), Мартынов Петр (318 гр.), Мироненко Андрей (318 гр.), Савельев Александр (318 гр.).

Дата Доклад Докладчик
15 мая 2020 г. Представление курсовых работ участников семинара. Лобанов А. (518/1 гр.), Шурыгин Д. (518/1 гр.), Мартынов П. (318 гр.), Мироненко А. (318 гр.), Савельев А. (318 гр.)
24 апреля 2020 г. Представление выпускных работ участников семинара. Мазуренко А. (618/1 гр.), Романов А. (418 гр.)
17 апреля 2020 г. Проверка периодичности функций алгебры логики. Савельев Александр (318 гр.)
10 апреля 2020 г. Пять видов минимальных замкнутых классов в k-значной логике. Лобанов Алексей (518/1 гр.)
3 апреля 2020 г. Алгоритм минимизации псевдополиномиальных форм функций алгебры логики. Шурыгин Дмитрий (518/1 гр.)
27 марта 2020 г. Тема уточняется Яшунский А.Н. (ИПМ РАН)
20 марта 2020 г. Замкнутые классы в k-значной логике, содержащие все функции одной переменной. Мартыненко Петр (318 гр.)
13 марта 2020 г. Применение SAT-решателей для минимизации полиномиальных форм функций алгебры логики. Романов Андрей (418 гр.)
6 марта 2020 г. Некоторые вопросы синтеза параллельных схем. Сергеев И.С. (ФГУП "Квант")
28 февраля 2020 г. Организационное собрание


Осенний семестр 2019-2020 учебного года

Участники семинара: Лебедев Марк (618/1 гр.), Мазуренко Анастасия (618/1 гр.), Лобанов Алексей (518/1 гр.), Шурыгин Дмитрий (518/1 гр.), Борсова Зурета (418 гр.), Романов Андрей (418 гр.), Мартынов Петр (318 гр.), Мироненко Андрей (318 гр.), Савельев Александр (318 гр.).

Дата Доклад Докладчик
6 декабря 2019 г. Алгоритм построения реберно непересекающихся остовных деревьев. В докладе рассматривается полиномиальный алгоритм, который для заданного графа G проверяет, найдутся ли в этом графе два реберно непересекающихся остовных дерева, и при положительном ответе выдает эти два дерева. Доклад по статье: Roskind J., Tarjan R.E. A note of finding minimum-cost edge-disjoint spanning trees // Mathematics of Operations Research. 1985. V. 10, N 4. P. 701-708. Мазуренко Анастасия (618/1 гр.)
22 и 29 ноября 2019 г. Параметро-эффективная расшифровка функций алгебры логики. В докладе показывается, что расшифровать любую функцию алгебры логики n переменных, если заранее известно, что у нее не более k существенных переменных, можно с логарифмической сложностью относительно n. Доклад по статье: Damaschke P. Adaptive Versus Nonadaptive Attribute-Efficient Learning // Machine Learning. 2000. V. 41. P. 197–215. Лебедев Марк (618/1 гр.)
18 и 25 октября 2019 г. Простой алгоритм для мальцевских ограничений. В докладе рассматривается полиномиальный алгоритм проверки выполнимости системы ограничений, удовлетворяющих некоторой мальцевской операции. Доклад по статье: Bulatov A., Dalmau V. A simple algorithm for Mal'tsev constraints // SIAM J. Computing. 2006. V. 36, N 1. P. 16-27. Мартынов Петр (318 гр.)
11 октября 2019 г. Организационное собрание


Весенний семестр 2018-2019 учебного года

Заседания семинара проходят совместно с семинаром Теория дискретных функций механико-математического факультета МГУ, руководители: Жук Дмитрий Николаевич, Галатенко Алексей Владимирович

Участники семинара: Жорина Александра (618/1 гр.), Сакович Марк (518/1 гр.), Мазуренко Анастасия (518/1 гр.), Шурыгин Дмитрий (418 гр.), Лобанов Алексей (418 гр.), Романов Андрей (318 гр.), Борсова Зурета (318 гр.). В весеннем семестре 2018-2019 учебного года заседания семинара проходят по пятницам с 16-20 до 17-55 в ауд. 503.

Дата Доклад Докладчик
17 мая 2019 г. Представление курсовых работ участников семинара 3-го и 5-го курсов. Мазуренко Анастасия (518/1 группа), Сакович Марк (518/1 группа), Борсова Зурета (318 группа)
19 апреля 2019 г. Представление выпускных работ участников семинара 4-го и 6-го курсов Жорина Александра (618/1 группа), Лю Юнцин (М210 группа), Лобанов Алексей (418 группа), Шурыгин Дмитрий (418 группа)
12 апреля 2019 г. Романов Андрей (318 группа)
5 апреля 2019 г. О сложности проверки аффинности конечных квазигрупп. Доклад по статье: Галатенко А.В., Панкратьев А.Е. // Дискретная математика. 2018. Т. 30, вып. 4. С. 3-11. Борсова Зурета (318 группа)
29 марта 2019 г. О сложности проверки полиномиальной полноты конечных квазигрупп. Доклад по статье: Галатенко А.В., Панкратьев А.Е. // Дискретная математика. 2018. Т. 30, вып. 4. С. 3-11. Галатенко А.В. (МГУ имени М.В. Ломоносова, мех.-мат. ф-т)
22 марта 2019 г. Сложность решения систем уравнений над конечной группой. В докладе рассматривается задача о совместности системы уравнений над конечной группой G. Показано, что эта задача - полиномиальна, если G - коммутативна, и эта задача - NP-полна, если G - некоммутативна. Доклад по статье: Goldmann M. The complexity of solving equations over finite groups // Information and Computation. 2002. V. 178. P. 253-262. Мазуренко Анастасия (518/1 гр.)
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. Сакович Марк (518/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 Текст программы, Результаты
Источник — «https://mk.cs.msu.ru/index.php?title=Сложность_решения_дискретных_задач&oldid=9066»