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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Доклады на спецсеминарах)
(Доклады на спецсеминарах)
Строка 36: Строка 36:
 
|-
 
|-
 
|colspan="3"|'''[[Сложность решения дискретных задач]]'''
 
|colspan="3"|'''[[Сложность решения дискретных задач]]'''
{{announce Seminar| 2 марта 2018 г.
+
{{announce Seminar| 30 марта 2018 г.
| Раскраски в три цвета планарных графов без треугольников.
+
| Достаточное условие для поиска без возврата. Доклад по статье: Freuder E.C. A sufficient condition for backtrack-free search // J. of the ACM. 1982.
В докладе будет показано, что если граф без треугольников является планарным, то задача его раскраски в три цвета решается полиномиальным алгоритмом. Доклад по статье: Grunbaum B. Grotzsch’s theorem on 3-coloring.
+
| Лобанов А. (318 гр.)
| Жорина А.А. (518/1 гр.)
+
 
|}}
 
|}}
 
   
 
   

Версия 15:27, 28 марта 2018

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

Дискретная математика и математическая кибернетика
Дискретные функции и сложность алгоритмов
Дискретный анализ
Теория управляющих систем и математические модели СБИС
23 марта Доклад по статье Редькина Н.П. «К вопросу о длине диагностических тестов для схем» (Матем. заметки, 2017, том 102, выпуск 4, с. 624–627). Курбацкая В.К.
16 марта Доклад по препринту Попкова К.А. «Полные проверяющие тесты длины два для схем при произвольных константных неисправностях элементов», Препринт № 104 за 2017 г. ИПМ им. М.В. Келдыша РАН, М.: ИПМ им. М.В. Келдыша РАН, 2017, 16 с. Мальцев А.Н.
2 марта 2018 г. Доклад по статье Ложкина С.А., Власова Н.В. "О сложности мультиплексорной функции в классе пи-схем". Хзмолян Д.Э.


Сложность решения дискретных задач
30 марта 2018 г. Достаточное условие для поиска без возврата. Доклад по статье: Freuder E.C. A sufficient condition for backtrack-free search // J. of the ACM. 1982. Лобанов А. (318 гр.)


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


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

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

М. Аббас