Шаблон:Current Seminars — различия между версиями
Материал из Кафедра математической кибернетики
(→Доклады на спецсеминарах) |
(→Доклады на спецсеминарах) |
||
| Строка 32: | Строка 32: | ||
|- | |- | ||
|colspan="3"|'''[[Сложность решения дискретных задач]]''' | |colspan="3"|'''[[Сложность решения дискретных задач]]''' | ||
| + | {{announce Seminar| 27 октября 2017 г. | ||
| + | | Полиномиальность задачи о раскраске в 3 цвета графа без порожденных простых цепей с 6 вершинами. | ||
| + | | Астахова А., 618/1 гр. | ||
| + | |}} | ||
{{announce Seminar| 13 октября 2017 г. | {{announce Seminar| 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. | | 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. | ||
Версия 14:16, 21 октября 2017
Доклады на спецсеминарах
| Дискретная математика и математическая кибернетика | ||
| Дискретные функции и сложность алгоритмов | ||
| Дискретный анализ | ||
| 20 октября 2017 г. | О максимальной длине цепи в единичном n-мерном кубе. По статье Евдокимова А.А. | Вершинин А., 618/1 гр.
|
| Теория управляющих систем и математические модели СБИС и Некоторые вопросы теории управляющих систем | ||
| 20 октября 2017 г. | О динамической активности схем из функциональных элементов. | Шуплецов М.С. |
| 27 октября 2017 г. | Доклад по статье "Dynamic Programming Algorithms for Large-Scale Equivalence Checking and Functional Correction". Аннотация доклада | Автайкина Мария
|
| Сложность решения дискретных задач | ||
| 27 октября 2017 г. | Полиномиальность задачи о раскраске в 3 цвета графа без порожденных простых цепей с 6 вершинами. | Астахова А., 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. | Сакович М., 418 гр.
|
| Теоретические проблемы программирования | ||
| 19 октября 2017 г. (четверг, ауд. 614) | Horn fragments of temporal logics & complex event processing.
We discuss the use of various temporal knowledge representation formalisms for ontology-mediated query answering over temporal data. In particular, we consider ontology and query languages based on the linear temporal logic LTL, the multi-dimensional Halpern-Shoham interval temporal logic HS, as well as the metric temporal logic MTL. Our main focus is on the data complexity of answering temporal ontology-mediated queries and their rewritability into standard first-order and datalog queries. |
M.V. Zakharyaschev
|
