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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Расписание докладов)
(не показаны 44 промежуточных версий 1 участника)
Строка 1: Строка 1:
Спецсеминар для студентов и аспирантов кафедры математической кибернетики. Проходит по пятницам с 16:20 до 17:55.
+
[[image:seminar1.jpg|thumb|right|Участники семинара (декабрь 2013 г.)]]
ауд. 504
+
  
== Тематика семинара ==
+
Спецсеминар для студентов и аспирантов кафедры математической кибернетики. В 2017-2018 уч.г. семинар проходит по пятницам с 16-20 до 17-55 в аудитории 505.
Алгоритмическая сложность задач распознавания свойств дискретных функций, сложность вычисления дискретных функций, сложность полиномиальных представлений дискретных функций, построение и анализ эффективности алгоритмов для решения дискретных задач.
+
  
 
==Руководители==
 
==Руководители==
 
[[Селезнева_Светлана_Николаевна|Селезнева Светлана Николаевна]]
 
[[Селезнева_Светлана_Николаевна|Селезнева Светлана Николаевна]]
 +
 +
[[Бухман_Антон_Владимирович|Бухман Антон Владимирович]]
 +
 +
== Тематика семинара ==
 +
 +
Вычислительная сложность; быстрые алгоритмы; труднорешаемые задачи; дискретные функции; графы.
  
 
== Расписание докладов ==
 
== Расписание докладов ==
  
=== Осенний семестр 2014-2015 учебного года ===
+
'''Осенний семестр 2017-2018 учебного года'''
  
Слушатели семинара: Барбачакова Светлана (518 гр.), Ким Игорь (518 гр.), Плаксина Анна (518 гр.), Хрулев Егор (518 гр.), Гордеев Михаил (418 гр.). В осеннем семестре 2014-2015 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].
+
Слушатели семинара: Мельник Марина (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%"
Строка 18: Строка 22:
 
! Доклад
 
! Доклад
 
! Докладчик
 
! Докладчик
 +
|-
 +
| 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 г.
 +
| 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 учебного года заседания семинара проходят совместно с семинарами [[Дискретные функции и сложность алгоритмов]] и [[Дискретный анализ]].
 +
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 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 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].
 +
 +
{| class="wide" width="100%"
 +
! Дата
 +
! Доклад
 +
! Докладчик
 +
|-
 +
| 28 ноября 2014 г.
 +
|
 +
| Хрулев Егор, 518 гр.
 +
|-
 +
| 31 октября 2014 г.
 +
| О сложности функций k-значной логики в классе поляризованных полиномиальных форм.
 +
Доклад по статье С.Н. Селезневой, "Дискретная математика", 2002.
 +
| Гордеев Михаил, 418 гр.
 
|-
 
|-
 
| 10 октября 2014 г.
 
| 10 октября 2014 г.
Строка 26: Строка 105:
 
|}
 
|}
  
=== Весенний семестр 2013-2014 учебного года ===
+
'''Весенний семестр 2013-2014 учебного года'''
  
 
В весеннем семестре 2013-2014 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].
 
В весеннем семестре 2013-2014 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].
Строка 52: Строка 131:
 
|}
 
|}
  
=== Осенний семестр 2013-2014 учебного года ===
+
'''Осенний семестр 2013-2014 учебного года'''
 
+
[[Image: seminar1.jpg| Заседание семинара]]
+
 
+
Участники семинара (декабрь 2013 г.)
+
  
 
В осеннем семестре 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) и получении экспериментальных результатов. Цели исследований:

Версия 11:34, 20 ноября 2017

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

Спецсеминар для студентов и аспирантов кафедры математической кибернетики. В 2017-2018 уч.г. семинар проходит по пятницам с 16-20 до 17-55 в аудитории 505.

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

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

Бухман Антон Владимирович

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

Вычислительная сложность; быстрые алгоритмы; труднорешаемые задачи; дискретные функции; графы.

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

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

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

Дата Доклад Докладчик
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 Текст программы, Результаты