Участник:SavitskiyIV — различия между версиями
| (не показаны 43 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
| + | __NOTOC__ | ||
| + | <div style="max-width:940px"> | ||
{{DISPLAYTITLE:Савицкий Игорь Владимирович}} | {{DISPLAYTITLE:Савицкий Игорь Владимирович}} | ||
| − | '''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, | + | '''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, ассистент кафедры МК. |
| − | * [ | + | * Профили в системах: [https://istina.msu.ru/profile/Sav/ ИСТИНА] [https://www.elibrary.ru/author_profile.asp?authorid=981480 РИНЦ] [https://mathnet.ru/rus/person/124716 Math-Net.ru] [https://orcid.org/0000-0003-3433-8096 ORCID] [https://researchgate.net/profile/Igor-Savitskii ResearchGate] [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Google Scholar] |
| − | == | + | == Области научных интересов == |
* Теория алгоритмов и сложности вычислений | * Теория алгоритмов и сложности вычислений | ||
| − | * Классы рекурсивных функций, их машинные и | + | * Классы рекурсивных функций, их машинные и индуктивные описания |
| + | |||
| + | === Разъяснение для студентов === | ||
| + | |||
| + | Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах. | ||
| + | |||
| + | В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций. | ||
| + | |||
| + | Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования. | ||
== Лекционные курсы == | == Лекционные курсы == | ||
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]] | * [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]] | ||
| − | * [[Модели вычислений]] | + | * [[Модели вычислений]] (МК, 4 курс) |
| + | * [[Функциональные системы]] (МК, магистратура) | ||
| + | * [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс) | ||
| + | |||
| + | == Ведение семинаров == | ||
| + | |||
| + | * [[Дискретная математика (1-й поток)]] (1 курс, группа 102) | ||
| + | * [[Дискретная математика (3-й поток)]] (1 курс, группа иностранных студентов 120) | ||
| + | * [https://distant.sev.msu.ru/course/view.php?id=2635 Дискретная математика (CФ)] (Филиал в Севастополе, 1 курс) | ||
| + | |||
| + | == Спецсеминары == | ||
| + | |||
| + | * [[Дискретные функции и сложность алгоритмов]] | ||
| + | |||
| + | == Публикации == | ||
| + | |||
| + | === Обратимые вычисления === | ||
| + | |||
| + | Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений. | ||
| + | |||
| + | # Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83. | ||
| + | |||
| + | === Малые классы параллельно реализуемых рекурсивных функций === | ||
| + | |||
| + | Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором). | ||
| + | |||
| + | Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC<sup>0</sup>. | ||
| + | |||
| + | # Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110. | ||
| + | # Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45. | ||
| + | |||
| + | === Машины с автоматически меняющимися счётчиками === | ||
| + | |||
| + | Цикл публикаций посвящён регистровым машинам со счётчиками (RC-машинам) — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически. | ||
| + | |||
| + | RC-машины машины всесторонне исследуются: доказывается их универсальность, определяются сложностные классы, анализируются алгоритмические проблемы, а также возможности упрощения и модификации машин без изменения вычислительных возможностей. Исследуемые машины и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, RC-машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором (CS-машин). | ||
| + | |||
| + | # Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113. | ||
| + | # Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388. | ||
| + | # Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51. | ||
| + | # Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42. | ||
| + | # Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39. | ||
| + | |||
| + | Результаты данных работ легли в основу кандидатской диссертации: | ||
| + | |||
| + | Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с. | ||
| + | |||
| + | == Учебные пособия == | ||
| + | |||
| + | # Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br>''Аннотация''. В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором). | ||
Текущая версия на 13:49, 14 июня 2026
Савицкий Игорь Владимирович — кандидат физико-математических наук, ассистент кафедры МК.
- Профили в системах: ИСТИНА РИНЦ Math-Net.ru ORCID ResearchGate Google Scholar
Области научных интересов
- Теория алгоритмов и сложности вычислений
- Классы рекурсивных функций, их машинные и индуктивные описания
Разъяснение для студентов
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.
Лекционные курсы
- Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)
- Модели вычислений (МК, 4 курс)
- Функциональные системы (МК, магистратура)
- Дискретная математика (КФ) (Казахстанский филиал, 2 курс)
Ведение семинаров
- Дискретная математика (1-й поток) (1 курс, группа 102)
- Дискретная математика (3-й поток) (1 курс, группа иностранных студентов 120)
- Дискретная математика (CФ) (Филиал в Севастополе, 1 курс)
Спецсеминары
Публикации
Обратимые вычисления
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.
- Савицкий И. В. Обратимые счетчико-сумматорные машины // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.
Малые классы параллельно реализуемых рекурсивных функций
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC0 задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC0 задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC0.
- Савицкий И. В., Марченков С. С. Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.
- Савицкий И. В. О совпадении сложностных классов BPC и TC0 // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.
Машины с автоматически меняющимися счётчиками
Цикл публикаций посвящён регистровым машинам со счётчиками (RC-машинам) — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.
RC-машины машины всесторонне исследуются: доказывается их универсальность, определяются сложностные классы, анализируются алгоритмические проблемы, а также возможности упрощения и модификации машин без изменения вычислительных возможностей. Исследуемые машины и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, RC-машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором (CS-машин).
- Савицкий И. В. Вычисления на регистровых машинах со счетчиками // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.
- Савицкий И. В. Регистровые машины со счётчиками // Доклады Академии Наук. 2017. № 4. С. 387–388.
- Савицкий И. В. Устранение неравенств в регистровых машинах со счетчиками // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.
- Савицкий И. В. Арифметизация регистровых машин со счетчиками // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.
- Марченков С. С., Савицкий И. В. Вычисления на счетчиковых машинах с сумматором // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.
Результаты данных работ легли в основу кандидатской диссертации:
Савицкий И. В. Сложность вычислений на регистровых машинах со счётчиками. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.
Учебные пособия
- Марченков С. С., Савицкий И. В. Машины в теории вычислимых функций. М., Вологда: Инфра-Инженерия, 2024. 104 с.
Аннотация. В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).
