Шаблон: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 Рациональные отношения эквивалентности
В данной статье рассматриваются рациональные отношения (конечные трансдукции), которые являются отношениями эквивалентности. После установления иерархии включений, изучаются сложность вычисления канонических функций и разрешимость некоторых задач принадлежности к классу. Рассматриваются следующие классы: рациональные отношения эквивалентности, ядра эквивалентности рациональных функций, детерминированные рациональные отношения эквивалентности, ядра эквивалентности субсеквенциальных функций, распознаваемые отношения эквивалентности, ограниченные по длине отношения эквивалентности и конечные отношения эквивалентности. |
М. Аббас
|
