Шаблон:Current Seminars — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Доклады на спецсеминарах)
(Доклады на спецсеминарах)
Строка 28: Строка 28:
 
|colspan="3"|'''[[Сложность решения дискретных задач]]'''
 
|colspan="3"|'''[[Сложность решения дискретных задач]]'''
 
{{announce Seminar| 8 декабря 2017 г.
 
{{announce Seminar| 8 декабря 2017 г.
| Раскраски в три цвета графов без треугольников. В докладе будет доказана NP-полнота задачи раскраски в 3 цвета графов без треугольников. Также будет показано, что если граф без треугольников является планарным,  то эта задача решается полиномиальным алгоритмом. Доклад по статьям: Maffray F., Preissmann M. On the NP-completeness of the k-colorability problem for triangle-free graphs; Grunbaum B. Grotzsch’s theorem on 3-coloring.
+
| Раскраски в три цвета графов без треугольников.  
 +
В докладе будет доказана NP-полнота задачи раскраски в 3 цвета графов без треугольников. Также будет показано, что если граф без треугольников является планарным,  то эта задача решается полиномиальным алгоритмом. Доклад по статьям: Maffray F., Preissmann M. On the NP-completeness of the k-colorability problem for triangle-free graphs; Grunbaum B. Grotzsch’s theorem on 3-coloring.
 
| Жорина А.А. (518 гр.)
 
| Жорина А.А. (518 гр.)
 
|}}
 
|}}

Версия 14:10, 6 декабря 2017

Доклады на спецсеминарах

Дискретная математика и математическая кибернетика
Дискретные функции и сложность алгоритмов
Дискретный анализ
Теория управляющих систем и математические модели СБИС
24 ноября 2017 г. Доклад «Иерархия памяти современного микропроцессора, принципы работы кэш-памяти и преподкачки данных.» Крюков Павел


Сложность решения дискретных задач
8 декабря 2017 г. Раскраски в три цвета графов без треугольников.

В докладе будет доказана NP-полнота задачи раскраски в 3 цвета графов без треугольников. Также будет показано, что если граф без треугольников является планарным, то эта задача решается полиномиальным алгоритмом. Доклад по статьям: Maffray F., Preissmann M. On the NP-completeness of the k-colorability problem for triangle-free graphs; Grunbaum B. Grotzsch’s theorem on 3-coloring.

Жорина А.А. (518 гр.)
1 декабря 2017 г. Применение кодов восстановления LRC для хранения данных в Яндексе Мазуров А.А. (Яндекс)


Теоретические проблемы программирования
1 декабря 2017 г.


Доклад по статье J. Howard Johnson Рациональные отношения эквивалентности

В данной статье рассматриваются рациональные отношения (конечные трансдукции), которые являются отношениями эквивалентности. После установления иерархии включений, изучаются сложность вычисления канонических функций и разрешимость некоторых задач принадлежности к классу. Рассматриваются следующие классы: рациональные отношения эквивалентности, ядра эквивалентности рациональных функций, детерминированные рациональные отношения эквивалентности, ядра эквивалентности субсеквенциальных функций, распознаваемые отношения эквивалентности, ограниченные по длине отношения эквивалентности и конечные отношения эквивалентности.  

М. Аббас