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

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

• Профиль в системе ИСТИНА
• Профиль Math-Net.ru
• Профиль ResearchGate
• Профиль Google Scholar

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

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

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

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

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

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

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

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

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

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

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

1. Марченков С. С., Савицкий И. В. Машины в теории вычислимых функций. М., Вологда: Инфра-Инженерия, 2024. 104 с.

Публикации

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

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

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

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

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

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

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

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.