Савицкий Игорь Владимирович

Савицкий Игорь Владимирович — кандидат физико-математических наук, ассистент кафедры МК.

• Профили в системах: ИСТИНА РИНЦ Math-Net.ru ORCID ResearchGate Google Scholar

Области научных интересов

• Теория алгоритмов и сложности вычислений
• Классы рекурсивных функций, их машинные и индуктивные описания

Разъяснение для студентов

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

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

Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.

Лекционные курсы

• Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)
• Модели вычислений (МК, 4 курс)
• Функциональные системы (МК, магистратура)
• Дискретная математика (КФ) (Казахстанский филиал, 2 курс)

Ведение семинаров

• Дискретная математика (1-й поток) (1 курс, группа 102)
• Дискретная математика (3-й поток) (1 курс, группа иностранных студентов 120)
• Дискретная математика (CФ) (Филиал в Севастополе, 1 курс)

Спецсеминары

• Дискретные функции и сложность алгоритмов

Публикации

Обратимые вычисления

Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.

1. Савицкий И. В. Обратимые счетчико-сумматорные машины // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.

Малые классы параллельно реализуемых рекурсивных функций

Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC⁰ задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC⁰ задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).

Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC⁰.

1. Савицкий И. В., Марченков С. С. Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.
2. Савицкий И. В. О совпадении сложностных классов BPC и TC⁰ // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.

Машины с автоматически меняющимися счётчиками

Цикл публикаций посвящён регистровым машинам со счётчиками (RC-машинам) — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.

RC-машины машины всесторонне исследуются: доказывается их универсальность, определяются сложностные классы, анализируются алгоритмические проблемы, а также возможности упрощения и модификации машин без изменения вычислительных возможностей. Исследуемые машины и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, RC-машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором (CS-машин).

1. Савицкий И. В. Вычисления на регистровых машинах со счетчиками // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.
2. Савицкий И. В. Регистровые машины со счётчиками // Доклады Академии Наук. 2017. № 4. С. 387–388.
3. Савицкий И. В. Устранение неравенств в регистровых машинах со счетчиками // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.
4. Савицкий И. В. Арифметизация регистровых машин со счетчиками // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.
5. Марченков С. С., Савицкий И. В. Вычисления на счетчиковых машинах с сумматором // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.

Результаты данных работ легли в основу кандидатской диссертации:

Савицкий И. В. Сложность вычислений на регистровых машинах со счётчиками. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.

Учебные пособия

1. Марченков С. С., Савицкий И. В. Машины в теории вычислимых функций. М., Вологда: Инфра-Инженерия, 2024. 104 с.
   Аннотация. В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).