Общая информация

Список сотрудников

Дудаков Сергей Михайлович
Дудаков Сергей Михайлович
Декан факультета ПМиК, заведующий кафедрой информатики

доктор физико-математических наук, доцент

Образование:

Тверской госуниверситет

E-mail:

sergeydudakov@yandex.ru

WWW:

pmkinfo.tversu.ru/pers/dudakov/index.php

Сфера научных интересов

  • логическое программирование;
  • вычислительная и алгоритмическая сложность;
  • теория баз данных;
  • теория языков первого порядка.

Основные результаты:

  • [1] Исследование сложности параллельности для Хорновского фрагмента линейной логики. Выделены классы Хорновских секвенций и установлена сложность задач распознавания принадлежности к этим классам и сложность задач доказуемости для секвенций из этих классов.
  • [2] Исследование соотношений между вычислительной сложностью и алгоритмической сложностью множеств. Доказано, что NP-полные по Тьюрингу проблемы не могут иметь алгоритмическую сложность распознавания порядка k lg lg n для начальных отрезков длины n почти для всех n. Доказано, что EXP-полные проблемы имеют колмогоровскую сложность меньше n - poly(lg n) для начальных отрезков длины n для бесконечно многих n.
  • [3] Исследование сложности построения совершенной модели пропозициональной нормальной логической программы. Получен ответ на один из открытых вопросов в работах Айтера и Готтлоба. Построен класс сложности, для которого эта задача является полной.
  • [4-9] Исследование сложности обновления дедуктивных баз данных. Получены оценки сложности в различных случаях.
  • [10-21] Получен трансляционный результат для класса обогащений арифметики Пресбургера одноместными функциями, согласованными со сложением. Исследована выразительная сила языков первого порядка для конечных алгебраических систем, вложенных в случайный граф. Установлена связь между свойствами псевдоконечной однородности, изолированности и сводимости. Приведен пример разрешимого обогащения арифметики пресбургера без свойства коллапса к порядку. Показана возможность в ряде случаев эффективно транслировать расширенные формулы в ограниченные.
  • [22-27] Исследованы итеративные операторы, их определенность, разрешимость связанных с ними задач и их вычислительная сложность. Найдены необходимые и достаточные условия определенности IFP-операторов. Установлена связь определенности с категоричностью и сильной минимальностью теории. Установлена вычислительная сложность логики унарного транзитивного замыкания для функции следования.

Научные публикации:

  1. Dudakov S.M. The Concurrency Complexity for the Horn Fragment of Linear Logic // Proc of the fourth Intern. Simp. LFCS'97. Springer, 1997, 78-87.
    Сложность параллельности для хорновского фрагмента линейной логики
    Как известно, проблема доказуемости в хорновском фрагменте линейной логики является NP-полной. В данной работе исследуются различные определения параллельности и устанавливается сложность доказуемости для соответствующих классов секвенций, а также сложность распознавания. Вводится понятие k-максимальной параллельности, сложность доказуемости для соответствующих классов является полиномиальной по времени. Доказана теорема об иерархии и установлена сложность распознавания k-максимальной параллельности.
  2. Dudakov S.M.On information content of hard sets // Proc. of intern. conf. on mathematical logic "Maltsev meeting" (extended abstarct). Novosibirsk, 1999, 79-80.
    Информационная сложность полных множеств
    Исследуется колмогоровская алгоритмическая сложность NP- и EXPTIME-полных проблем. Получены два основных результата. Первый - если P не равно NP, то полиномиально ограниченная колмогоровская сложность NP-трудных проблем не меньше чем klg(lg(n)). Второй - обобщение результатов Бука и Лютца на EXPTIME-трудные множества.
  3. Dudakov S.M. On the complexity of perfect models of logic programs // Fundamenta Informaticae, vol. 39(3), 1999 pp. 249-258.
    Сложность совершенных моделей логических программ
    В работе исследуются совершенные модели норамальных логических программ, устанавливается сложность распознавания PERF-совместности и PERF-следования. Описана структура совершенных моделей.
  4. Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Monotone Expansion of Updates in Logical Databases // Proc. of 5th International Conference LPNMR'99, Berlin, Springer-Verlag, 1999 pp. 132-146.
    To find a minimal real change after an update of a database with integrity constraints (IC) expressed by an extended logic program is proven to be a hard problem. We define a class of operators expanding the input updates correctly with respect to the IC. The particular monotone expansion operator we describe is incrementally computed in square time. It provides a practical optimization of the standard complete choice algorithm resolving the update problem.
  5. Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Maximal Expansions of Database Updates // Proc. of FoIKS'2000, LNCS, 1762, pp.72-87.
    Databases with integrity constraints (IC) are considered. For each DB update, i.e. a set of facts to add and of facts to delete, the IC implies its correct expansion: new facts to add and new facts to delete. Simultaneously, each expanded update induces a correct simplification of the IC. In the limit this sequence of expansions and simplifications converges to the maximal correct update expansion independent from the initial DB state. We show that such maximal expansion is computed in square time for partial databases, and that its computation is a coNP-complete problem in classical databases. However, it is also square time computable in classical DBs under ICs with some restrictions on the use of negation. Computing the real change of the initial DB state after accomplishing an update is a hard problem. The use of maximal update expansion in the place of initial update can substantially simplify computation of a new correct DB state.
  6. Dekhtyar M., Dikovsky A., Dudakov S. On Complexity of Updates Through Integrity Constraints, // Proc. of the First Int. Conf. on Computational Logic (CL 2000), LNAI, 1861 (2000), pp. 867-881.
    The computational complexity is explored of finding the minimal real change of a database after an update constrained by a logic program. Quite surprisingly, a polynomial time algorithm is discovered which solves this problem for ground IC in partial interpretations. Formulated in a "property" form, even under the premise of fixed database scheme, this problem turns out to be complete in the first three classes of polynomial hierarchies, depending on many factors: type of interpretation (total or partial), presence of variables, use of negation, arity of predicates, etc. If the database scheme may vary, the complexity grows exponentially. Meanwhile, we show that under strong restrictions to negative constraints the problem is solvable in polynomial time.
  7. Dudakov S.M. The logic program model updates complexity (deletion case). // Proceeding of intern. conf. "Logic and application" (extended abstract). Novosibirsk, 2000.
    Сложность обновлений моделей логических программ (удаления)
    We prove that the problem of update of deductive database can be simplified if only deletions are enabled and additional formula is an atom. We prove the problem is computable in polinomial time in propositional case and the problem is coNP-complete if a logical problem contains variables.
  8. Michael I. Dekhtyar, Alexander Ja. Dikovsky, Sergey Dudakov, Nicolas Spyratos: Maximal state independent approximations to minimal real change // Annals of Mathematics and Artificial Intelligence 33(2-4), 2001, pp. 157-204.
  9. С.М.Дудаков Сложность обновлений дедуктивных баз данных с фиксированным ограничением целостности // Вестник ТвГУ. Серия Прикладная математика, № 1, 2003.
    В работе доказано, что если рассматривается случай, когда ограничения целостности дедуктивной базы данных заданы плоской логической программой (с переменными) и фиксированы, то сложность задач обновления полиномиально эквивалентны сложности аналогичных задач, когда ограниченя не содержат переменных, но не зафиксированы.
  10. С.М.Дудаков Трансляционная теорема в предикатных обогащениях начального фрагмента нестандартных моделей арифметики Пресбургера // Сложные системы: обработка информации, моделирование и оптимизация, ТвГУ, Тверь, 2002
    Трансляционный результат (трансляционная теорема) означает, что если взять произвольную модель теории и внедрить в нее некоторую конечную систему, то любой локально генерический запрос к внедренной системе с использованием символов теории может быть переписан без этих символов. В данной работе доказано, что если взять нестандартную модель арифметики Пресбургера, обогатить ее произвольными предикатами, определенными на натуральных числах, то в теории полученной системы выполняется трансляционная теорема.
  11. С.М.Дудаков Трансляционный результат для расширений арифметики Пресбургера одноместной функцией, согласованной со сложением // Матем. заметки 2004, Т.76, вып. 3, С.362-371.
    Доказано, что если обогатить арифметику Пресбургера произвольной одноместной функцией, согласованной со сложением, например, экспонентой или факториалом, то в полученной теории выполняется трансляционная теорема.
  12. С.М.Дудаков Трансляционная теорема для теорий I-сводимых алгебраических систем // Известия РАН, сер. математическая 2004, Т.68, №5, С.67-90.
    Показано, что отсутствие независимой формулы в теории не является необходимым условием для I-сводимости её моделей даже для расширений арифметики Пресбургера. Доказано, что из I-сводимости малой алгебраической системы автоматически следует, что каждая формула эквивалентна в ней некоторой P-ограниченной формуле, следовательно, для теорий таких систем выполняется трансляционная теорема.
  13. С.М.Дудаков Выразительная сила языков запросов первого порядка для баз данных на неупорядоченном случайном графе // Вестник НовГУ, Серия технические науки, №34, 2005. С.51-57
    Исследуется вопрос, расширяется ли множество выразимых в логике первого порядка запросов, если элементы базы данных берутся из неупорядоченного случайного графа.
  14. С.М.Дудаков Разрешимая теория без трансляционной теоремы // Вестник ТвГУ. Серия Прикладная математика, № 6(12), 2005. С.23-26
    Предлагается пример теории, который опровергает гипотезу о том, что не существует разрешимых теорий без транансляционной теоремы.
  15. С.М.Дудаков, М.А.Тайцлин Трансляционный результат для языков запросов в теории баз данных // Успехи математических наук, №61:2(368), 2006, С.2-65
    В центре нашего внимания так называемые относительные свойства изолированности и псевдоконечной однородности и универсумы без независимой формулы. Для сводимых теорий мы доказываем теорему об ограниченности. Для сводимых и ограниченных теорий мы доказываем теорему об относительной изолированности и, как следствие, получаем для сводимых теорий трансляционную теорему. Мы также замечаем, что сводимость равносильна относительной изолированности. С другой стороны, мы приводим теоремы, которые показывают, что для эффективно сводимых теорий, в которых существует эффективная почти неразличимая последовательность, возможна эффективная трансляция локально генерических запросов, использующих, кроме упорядочения и имён хранящихся таблиц, также и отношения и операции универсума, в запросы, которые эти отношения и операции универсума уже не используют. Мы приводим также пример такого обогащения арифметики Пресбургера, что для этого обогащения трансляционная теорема не имеет места, но элементарная теория этого обогащения разрешима. Это дает отрицательный ответ на некоторые открытые вопросы.
  16. S.M.Dudakov Isolation and reducibility properties and the collapse result // Proc. of intern.conf. CSR-2006. LNCS 3967, Springer, 2006. С.171-177.
    Two methods are used usually for to establish the collapse result for theories. They use the isolation property and the reducibility property. Early it is shown that the reducibility implies the isolation. We prove that these methods are equivalent.
  17. С.М.Дудаков Трансляционная теорема и автоматные структуры // Вестник ТвГУ, серия Прикладная математика, №4(21), 2006. С.5--35.
    Предлагается пример запроса к базе данных, который является локально генерическим и может быть записан с использованием отношений автоматных систем, но не может быть записан ограниченной формулой. Тем самым опровергаются гипотезы о том, что в автоматных структурах соблюдается трансляционная теорема, о том, что не существует разрешимых обогащений теории дискретного линейного порядка без трансляционной теоремы, и что в каждом таком обогащении без трансляционной теоремы существует формула, способная выделить любое подмножество любого конечного множества. Это построение так же опровергает две более слабые гипотезы, утверждающие то же самое для расширений арифметики Пресбургера. Кроме того, далее мы строим теории, опровергающие одну из гипотез из работы Болдвина и Бенедикта.
  18. С.М.Дудаков Псевдоконечная однородность, изолированность и сводимость // Матем. заметки, Т.81, вып. 4, 2004, С.515-527.
    Ранее установлено (Дудаков С.М., Тайцлин М.А.), что из сводимости некоторых моделей теории следует второе свойство псевдоконечной однородности для этой теории. Здесь мы доказываем обратное: из любого (первого или второго) свойства псевдоконечной однородности теории следует сводимость некоторых ее моделей, и, следовательно, второе свойство изолированности. Это доказывает также эквивалентность вторых свойств изолированности и псевдоконечной однородности, что контрастирует с тем, что первое свойство псевдоконечной однородности является более общим, чем первое свойство изолированности (Белеградек О.В., Столбоушин А.П., Тайцлин М.А.).
  19. С.М.Дудаков Достаточные условия эффективной трансляции локально генерических запросов, // Фундаментальная и прикладная математика. 2009. Т. 15. № 5. С. 49-61.
    Данная работа является продолжением исследований по теории языков запросов первого порядка к базам данных. Ранее было установлено, что во многих разрешимых теориях имеет место трансляционная теорема: каждый локально генерический запрос эквивалентен некоторому ограниченному, но вопрос о возможности эффективного нахождения этого запроса почти не исследовался. Используя полученные автором ранее результаты, мы предлагаем метод эффективного нахождения этих запросов для широкого класса теорий, который включает арифметику Пресбургера и теорию действительных чисел.
  20. С.М.Дудаков МОНАДИЧЕСКИЕ СОСТОЯНИЯ НАД УПОРЯДОЧЕННЫМ УНИВЕРСАЛЬНЫМ СЛУЧАЙНЫМ ГРАФОМ И КОНЕЧНЫЕ АВТОМАТЫ // Известия Российской академии наук. Серия математическая. 2011. Т. 75. № 5. С. 47-64.
    В работе продолжено изучение выразительной силы языка логики предикатов для конечных алгебраических систем, вложенных в бесконечные, которое было начато в работах М.А.Тайцлина, М.Бенедикта, Л.Либкина и др. Изучено, какие свойства конечной монадической системы можно выразить с помощью формул, если вложить такую систему в линейно упорядоченный произвольным образом случайный граф. В работе используется представление Бюхи для связи монадических состояний и формальных языков. Показано, что если ограничиться рассмотрением только инвариантных в линейно упорядоченных случайных графах формул, то такие формулы соответствуют конечным автоматам. Продемонстрировано, что $=$-инвариантные формулы, выражающие собственные свойства вложенных систем, способны выразить только булеву комбинацию свойств вида "мощность пересечения одноместных предикатов принадлежит одной из конечного числа фиксированных конечных или бесконечных арифметических прогрессий."
  21. Dudakov S.M. SUFFICIENT CONDITIONS FOR EFFECTIVE TRANSLATION OF LOCALLY GENERIC QUERIES // Journal of Mathematical Sciences. 2011. Т. 172. № 5. С. 654-662.
  22. С.М.Дудаков О БЕЗОПАСНОСТИ РЕКУРСИВНЫХ ЗАПРОСОВ // Вестник Тверского государственного университета. Серия: Прикладная математика. 2012. № 4 (27). С. 71-80.
    В работе исследуется вопрос об определенности рекурсивных запросов на универсуме. В качестве модели рекурсивного запроса применяется оператор инфляционной фиксированной точки IFP. Исследованы основные свойства IFP-оператора и показано, что модели счетно-категоричных теорий являются безопасными.
  23. С.М.Дудаков О БЕЗОПАСНОСТИ IFP-ОПЕРАТОРОВ И РЕКУРСИВНЫХ ЗАПРОСОВ // Вестник Тверского государственного университета. Серия: Прикладная математика. 2013. № 2 (29). С. 5-13.
    В работе продолжается исследование об определенности рекурсивных запросов на универсуме. Ранее нами показано, что модели счетно-категоричных теорий безопасны. В данной работе мы показываем, что счетная категоричность необходимым условием не является, и предлагаем необходимые и достаточные условия безопасности IFP-оператора.
  24. С.М.Дудаков НЕРАЗРЕШИМОСТЬ ПРОБЛЕМЫ ОПРЕДЕЛЕННОСТИ БИНАРНЫХ IFP-ОПЕРАТОРОВ ДЛЯ ТЕОРИИ ОДНОГО СЛЕДОВАНИЯ // Вестник Тверского государственного университета. Серия: Прикладная математика. 2014. № 4. С. 7-15.
    В работе продолжается исследование определенности оператора инфляционной фиксированной точки. Показано, что проблема определенности бинарного IFP-оператора для теории следования алгоритмически неразрешима.
  25. С.М.Дудаков СИЛЬНАЯ МИНИМАЛЬНОСТЬ И IFP-БЕЗОПАСНОСТЬ // Вестник Тверского государственного университета. Серия: Прикладная математика. 2015. № 3. С. 25-32.
    В работе продолжено исследование IFP-безопасности теорий. Доказано, что среди полных конечно аксиоматизируемых сильно минимальных теорий IFP-безопасных нет.
  26. Dudakov S.M. ON INFLATIONARY FIX-POINT OPERATORS SAFETY // Lobachevskii Journal of Mathematics. 2015. Т. 36. № 4. С. 328-331.
    We continue to investigate a safety of recursive queries (inflationary fix-point operators) over infinite universes. In the previous paper we have proved that models of countable categorical theories are safe. In this paper we propose a necessary and sufficient condition for IFP-safety and obtain a solution of the problem for linear order theories.
  27. С.М.Дудаков О выразительной силе логики одноместного транзитивного замыкания для дискретного порядка // Вестник Тверского государственного университета. Серия: Прикладная математика. 2017. № 4. С.
    В работе показано, что в теории дискретного линейного порядка с одноместным оператором транзитивного замыкания с помощью формул длины n можно представить сложение, умножение и экспоненту для натуральных чисел вплоть до H2(n), где H2(n) - гиперэкспонента.

Научно-методические публикации:

  1. С.М.Дудаков. Информатика. // Фонд контрольных заданий для квалификационной аттестации студентов факультета ПМиК ТвГУ по основам фундаментальных и компьютерных знаний: Учебно-методический сборник. Тверь: ТвГУ. 2002. (Рекомендовано УМО в качестве учебного пособия для студентов специальности "Прикладная математика и информатика")
  2. С.М.Дудаков. Математическое введение в информатику: Учебное пособие. Тверь: ТвГУ. 2003. - 240c. (Рекомендовано УМО в качестве учебного пособия для студентов специальности "Прикладная математика и информатика")
  3. С.М.Дудаков. Информатика. // Фонд контрольных заданий для квалификационной аттестации студентов факультета ПМиК ТвГУ по основам фундаментальных и компьютерных знаний: Учебно-методический сборник. Тверь: ТвГУ. 2007. (Рекомендовано УМО в качестве учебного пособия для студентов специальности "Прикладная математика и информатика")
  4. С.М.Дудаков. Языки программирования и методы трансляции. // Фонд контрольных заданий для квалификационной аттестации студентов факультета ПМиК ТвГУ по основам фундаментальных и компьютерных знаний: Учебно-методический сборник. Тверь: ТвГУ. 2007. (Рекомендовано УМО в качестве учебного пособия для студентов специальности "Прикладная математика и информатика")
  5. С.М.Дудаков. Основы теории моделей: Учебник. Тверь: ТвГУ. 2013. - 480c.
  6. Захарова И.В., Дудаков С.М., Язенин А.В. О РАЗРАБОТКЕ ПРИМЕРНОГО УЧЕБНОГО ПЛАНА ПО УГНС «КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ» В СООТВЕТСТВИИ С ПРОФЕССИОНАЛЬНЫМИ СТАНДАРТАМИ // Вестник Тверского государственного университета. Серия: Педагогика и психология. 2016. № 2. С. 84-100. 13
  7. Захарова И.В., Дудаков С.М., Язенин А.В. О РАЗРАБОТКЕ МАГИСТЕРСКОЙ ПРОГРАММЫ ПО УГНС «КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ» В СООТВЕТСТВИИ С ПРОФЕССИОНАЛЬНЫМИ СТАНДАРТАМИ // Вестник Тверского государственного университета. Серия: Педагогика и психология. 2016. № 3. С. 114-126.
  8. Захарова И.В., Дудаков С.М., Язенин А.В., Солдатенко И.С. О МЕТОДИЧЕСКИХ АСПЕКТАХ РАЗРАБОТКИ ПРИМЕРНЫХ ОБРАЗОВАТЕЛЬНЫХ ПРОГРАММ ВЫСШЕГО ОБРАЗОВАНИЯ // Образовательные технологии и общество. 2015. Т. 18. № 3. С. 330-354.

Читаемые курсы

  • Дискретная математика
  • Математическая логика и теория алгоритмов
  • Общая алгебра
  • Прикладная алгебра и теория чисел
  • История и методология математики и информатики

Ученики, имеющие ученую степень

  • Снятков Алексей Сергеевич, кандидат физико-математических наук, Ярославский государственный университет им.Демидова, 2012
  • Золотов Александр Сергеевич, кандидат физико-математических наук, Приволжский (Казанский) федеральный университет, 2017