https://mk.cs.msu.ru/api.php?action=feedcontributions&feedformat=atom&user=SavitskiyIVКафедра математической кибернетики - Вклад участника [ru]2026-06-04T15:28:34ZВклад участникаMediaWiki 1.22.5//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:MV_exam_info.pdfФайл:MV exam info.pdf2026-06-04T08:22:20Z<p>SavitskiyIV: SavitskiyIV загружена новая версия «Файл:MV exam info.pdf»</p>
<hr />
<div></div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-06-04T07:49:35Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, ассистент кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками (RC-машинам) — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
RC-машины машины всесторонне исследуются: доказывается их универсальность, определяются сложностные классы, анализируются алгоритмические проблемы, а также возможности упрощения и модификации машин без изменения вычислительных возможностей. Исследуемые машины и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, RC-машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором (CS-машин).<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br>''Аннотация''. В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-06-02T18:21:39Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками (RC-машинам) — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
RC-машины машины всесторонне исследуются: доказывается их универсальность, определяются сложностные классы, анализируются алгоритмические проблемы, а также возможности упрощения и модификации машин без изменения вычислительных возможностей. Исследуемые машины и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, RC-машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором (CS-машин).<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br>''Аннотация''. В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-06-02T18:20:57Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками (RC-машинам) — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
RC-машины машины всесторонне исследуются: доказывается их универсальность, определяются их сложностные классы, анализируются их алгоритмические проблемы, а также возможности упрощения и модификации машин. Исследуемые машины и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, RC-машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором (CS-машин).<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br>''Аннотация''. В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:FS_exam_info.pdfФайл:FS exam info.pdf2026-06-02T08:25:00Z<p>SavitskiyIV: SavitskiyIV загружена новая версия «Файл:FS exam info.pdf»</p>
<hr />
<div>Программа курса и информация о зачёте и экзамене по курсу «Функциональные системы».</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8BФункциональные системы2026-06-02T08:17:53Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]<br />
[[Категория:Магистерская программа Дискретные управляющие системы и их приложения]]<br />
<br />
Курс для студентов магистратуры кафедры МК, читается в осеннем семестре:<br />
* 1-й курс программы «Дискретные структуры и алгоритмы» — 2 часа лекций и 1 час семинаров в неделю, отчётность экзамен. <br />
* 2-й курс программы «Дискретные управляющие системы» — 2 часа лекций в неделю, отчётность зачёт.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
В курсе излагаются классические результаты о замкнутости и полноте для булевых функций и функций k-значной логики. Он углубляет сведения, полученные из курса [[Дискретная математика (1-й курс)]].<br />
<br />
В первой, основной части курса даётся полное описание всех замкнутых классов булевых функций. Во второй части доказывается ряд теорем о полноте для функций k-значной логики. В третьей части курса приводится описание всех предполных классов функций k-значной логики (без доказательств).<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:FS_exam_info.pdf|'''Программа курса и порядок проведения экзамена / зачёта''']]<br />
<br />
[[Media:Функциональные_системы_лекции.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
[[Media:PostDiagram.pdf|'''Диаграмма Поста''']] (распечатку разрешено использовать на экзамене и зачёте)<br />
<br />
===Литература===<br />
<br />
# [[Media:Функциональные_системы_лекции.pdf|Савицкий И.В. Презентации к лекциям. 2025.]] (в файле присутствует электронное оглавление)<br />
# [[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012. 47 с.]]<br />
# Марченков С.С. Избранные главы дискретной математики. М.: Физматлит, 2023. 192 с.<br />
# [[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015. 136 с.]]<br />
<br />
===Дополнительная литература===<br />
<br />
# Марченков С.С. Основы теории булевых функций. М.: Физматлит, 2014. 135 с.<br />
# Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 103 с.<br />
# Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2003. 384 с.<br />
# Фрейвалд Р.В. Функциональная полнота для не всюду определенных функций алгебры логики // Дискретный анализ. 1966. № 8. С. 55–68.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8BФункциональные системы2026-06-02T08:17:44Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]<br />
[[Категория:Магистерская программа Дискретные управляющие системы и их приложения]]<br />
<br />
Курс для студентов магистратуры кафедры МК, читается в осеннем семестре:<br />
* 1-й курс программы «Дискретные структуры и алгоритмы» — 2 часа лекций и 1 час семинаров в неделю, отчётность экзамен. <br />
* 2-й курс программы «Дискретные управляющие системы» — 2 часа лекций в неделю, отчётность зачёт.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
В курсе излагаются классические результаты о замкнутости и полноте для булевых функций и функций k-значной логики. Он углубляет сведения, полученные из курса [[Дискретная математика (1-й курс)]].<br />
<br />
В первой, основной части курса даётся полное описание всех замкнутых классов булевых функций. Во второй части доказывается ряд теорем о полноте для функций k-значной логики. В третьей части курса приводится описание всех предполных классов функций k-значной логики (без доказательств).<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:FS_exam_info.pdf|'''Программа курса и порядок проведения экзамена/зачёта''']]<br />
<br />
[[Media:Функциональные_системы_лекции.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
[[Media:PostDiagram.pdf|'''Диаграмма Поста''']] (распечатку разрешено использовать на экзамене и зачёте)<br />
<br />
===Литература===<br />
<br />
# [[Media:Функциональные_системы_лекции.pdf|Савицкий И.В. Презентации к лекциям. 2025.]] (в файле присутствует электронное оглавление)<br />
# [[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012. 47 с.]]<br />
# Марченков С.С. Избранные главы дискретной математики. М.: Физматлит, 2023. 192 с.<br />
# [[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015. 136 с.]]<br />
<br />
===Дополнительная литература===<br />
<br />
# Марченков С.С. Основы теории булевых функций. М.: Физматлит, 2014. 135 с.<br />
# Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 103 с.<br />
# Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2003. 384 с.<br />
# Фрейвалд Р.В. Функциональная полнота для не всюду определенных функций алгебры логики // Дискретный анализ. 1966. № 8. С. 55–68.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%94%D0%93%D0%94%D0%9C%D0%B8%D0%9A_%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D0%B8_1-12_%D0%9F%D1%80%D0%B5%D0%B7%D0%B5%D0%BD%D1%82%D0%B0%D1%86%D0%B8%D1%8F.pdfФайл:ДГДМиК Лекции 1-12 Презентация.pdf2026-06-01T19:37:13Z<p>SavitskiyIV: SavitskiyIV загружена новая версия «Файл:ДГДМиК Лекции 1-12 Презентация.pdf»</p>
<hr />
<div></div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T14:22:28Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br>''Аннотация''. В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T14:21:40Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br>''Аннотация'': В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T14:21:17Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T14:01:15Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет получить чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T14:00:48Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет построить чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T13:58:50Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором).<br />
<br />
Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T13:58:33Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены двум малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Класс AC<sup>0</sup> задаётся альтернирующими схемами константной глубины и известен также как FO (может быть задан формулами логики предикатов первого порядка). Класс TC<sup>0</sup> задаётся пороговыми схемами константной глубины и известен также как FOM (может быть задан формулами логики предикатов первого порядка с мажоритарным квантором). Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T11:05:11Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор некоторых наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T10:44:10Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''[https://infra-e.ru/products/978-5-9729-2057-0 Машины в теории вычислимых функций]''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T09:00:26Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [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]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-31T09:00:09Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* Профили в системах: [https://istina.msu.ru/profile/Sav/ ИСТИНА] [https://www.elibrary.ru/author_profile.asp?authorid=981480 РИНЦ] [https://mathnet.ru/rus/person/124716 Math-Net.ru] [ORCID https://orcid.org/0000-0003-3433-8096] [https://researchgate.net/profile/Igor-Savitskii ResearchGate] [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8BФункциональные системы2026-05-30T19:41:00Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]<br />
[[Категория:Магистерская программа Дискретные управляющие системы и их приложения]]<br />
<br />
Курс для студентов магистратуры кафедры МК, читается в осеннем семестре:<br />
* 1-й курс программы «Дискретные структуры и алгоритмы» — 2 часа лекций и 1 час семинаров в неделю, отчётность экзамен. <br />
* 2-й курс программы «Дискретные управляющие системы» — 2 часа лекций в неделю, отчётность зачёт.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
В курсе излагаются классические результаты о замкнутости и полноте для булевых функций и функций k-значной логики. Он углубляет сведения, полученные из курса [[Дискретная математика (1-й курс)]].<br />
<br />
В первой, основной части курса даётся полное описание всех замкнутых классов булевых функций. Во второй части доказывается ряд теорем о полноте для функций k-значной логики. В третьей части курса приводится описание всех предполных классов функций k-значной логики (без доказательств).<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:FS_exam_info.pdf|'''Программа курса и порядок проведения экзамена''']]<br />
<br />
[[Media:Функциональные_системы_лекции.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
[[Media:PostDiagram.pdf|'''Диаграмма Поста''']] (распечатку разрешено использовать на экзамене и зачёте)<br />
<br />
===Литература===<br />
<br />
# [[Media:Функциональные_системы_лекции.pdf|Савицкий И.В. Презентации к лекциям. 2025.]] (в файле присутствует электронное оглавление)<br />
# [[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012. 47 с.]]<br />
# Марченков С.С. Избранные главы дискретной математики. М.: Физматлит, 2023. 192 с.<br />
# [[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015. 136 с.]]<br />
<br />
===Дополнительная литература===<br />
<br />
# Марченков С.С. Основы теории булевых функций. М.: Физматлит, 2014. 135 с.<br />
# Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 103 с.<br />
# Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2003. 384 с.<br />
# Фрейвалд Р.В. Функциональная полнота для не всюду определенных функций алгебры логики // Дискретный анализ. 1966. № 8. С. 55–68.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:FS_exam_info.pdfФайл:FS exam info.pdf2026-05-30T19:40:39Z<p>SavitskiyIV: Программа курса и информация о зачёте и экзамене по курсу «Функциональные системы».</p>
<hr />
<div>Программа курса и информация о зачёте и экзамене по курсу «Функциональные системы».</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T19:09:44Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Указанные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T19:08:17Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T19:04:50Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Обратимые вычисления ===<br />
<br />
Введён новый тип абстрактного вычислительного устройства с автоматически меняющимися счётчиками, задающий обратимые вычисления. Доказана универсальность данного устройства для обратимых вычислений.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1917 Обратимые счетчико-сумматорные машины]'' // Дискретная математика. 2026. Т. 38, № 2. С. 67–83.<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''[https://kpfu.ru/dis_card?p_id=3248 Сложность вычислений на регистровых машинах со счётчиками]''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''[https://www.libnauka.ru/item.php?doi=10.7868/S0869565217280052 Регистровые машины со счётчиками]'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T18:27:24Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы абстрактной (теоретической) математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T16:48:12Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Изучение сложностных классов рекурсивных функций относится к теоретический математике. Результаты этой области редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данной научной области возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T16:38:56Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии даются определения и характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T16:36:21Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Публикации ==<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T16:34:14Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br><br>В пособии характеризуются вычислительные возможности ряда абстрактных вычислительных устройств: как широко известных (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, двуленточные нестирающие машины Тьюринга), так и более специальных (стековые регистровые машины, регистровые машины со счётчиками, счётчиковые машины с сумматором).<br />
<br />
== Публикации ==<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T16:25:59Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br />
<br />
== Публикации ==<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (задаётся альтернирующими схемами константной глубины) и TC<sup>0</sup> (задаётся пороговыми схемами константной глубины) — малым сложностным классам, характеризующим параллельные вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T16:25:01Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br />
<br />
== Публикации ==<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> (альтернирующие схемы константной глубины) и TC<sup>0</sup> (от: пороговые схемы константной глубины) — малым сложностным классам, характеризующим вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T16:12:45Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br />
<br />
== Публикации ==<br />
<br />
=== Малые классы параллельно реализуемых рекурсивных функций ===<br />
<br />
Публикации посвящены классам AC<sup>0</sup> и TC<sup>0</sup> — малым сложностным классам, характеризующим вычисления на полиномиальном от длины входа количестве процессоров с константным временем работы. Составлен обзор наиболее важных результатов по данным классам. Показано, что операция ограниченной префиксной конкатенации позволяет задать чисто словарное индуктивное определение класса TC<sup>0</sup>.<br />
<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T16:05:59Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]<br />
<br />
== Учебные пособия ==<br />
<br />
# Марченков С. С., Савицкий И. В. ''Машины в теории вычислимых функций''. М., Вологда: Инфра-Инженерия, 2024. 104 с.<br />
<br />
== Публикации ==<br />
<br />
=== Классы параллельно реализуемых рекурсивных функций ===<br />
<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=50071408 О совпадении сложностных классов BPC и TC<sup>0</sup>]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 4. С. 36–45.<br />
# Савицкий И. В., Марченков С. С. ''[https://library.keldysh.ru/mvk.asp?id=2023-52 Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации]'' // Математические вопросы кибернетики. Вып. 21. М.: ФИЗМАТЛИТ, 2023. С. 52–110.<br />
<br />
=== Машины с автоматически меняющимися счётчиками ===<br />
<br />
Цикл публикаций посвящён регистровым машинам со счётчиками — абстрактному вычислительному устройству счётчикового типа, программа которого может изменять лишь один регистр, а все остальные изменяются автоматически.<br />
<br />
Данные машины всесторонне исследуются и применяются для получения новых базисов по суперпозиции в известных сложностных классах. Кроме того, исследуемые машины применяются для определения вычислительных возможностей другого вычислительного устройства подобного типа — счётчиковых машин с сумматором.<br />
<br />
Результаты данных работ легли в основу кандидатской диссертации:<br />
<br />
Савицкий И. В. ''Сложность вычислений на регистровых машинах со счётчиками''. Дисс. ... канд. физ.-мат. наук: 01.01.09. М.: МГУ, 2021. 143 с.<br />
<br />
# Савицкий И. В. ''[https://www.mathnet.ru/rus/dm1408 Вычисления на регистровых машинах со счетчиками]'' // Дискретная математика. 2017. Т. 29, № 1. С. 95–113.<br />
# Савицкий И. В. ''Регистровые машины со счётчиками'' // Доклады Академии Наук. 2017. № 4. С. 387–388.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=38537754 Устранение неравенств в регистровых машинах со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2019. № 3. С. 45–51.<br />
# Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=43025591 Арифметизация регистровых машин со счетчиками]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 3. С. 30–42.<br />
# Марченков С. С., Савицкий И. В. ''[https://www.elibrary.ru/item.asp?id=32358207 Вычисления на счетчиковых машинах с сумматором]'' // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31–39.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:DM_KF_exam_info.pdfФайл:DM KF exam info.pdf2026-05-30T15:31:08Z<p>SavitskiyIV: SavitskiyIV загружена новая версия «Файл:DM KF exam info.pdf»</p>
<hr />
<div>Программа курса «Дискретная математика» для Казахстанского филиала МГУ</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-30T15:15:36Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://mathnet.ru/rus/person/124716 Профиль Math-Net.ru]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-29T17:06:24Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [https://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:SavitskiyIVУчастник:SavitskiyIV2026-05-29T17:01:55Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
{{DISPLAYTITLE:Савицкий Игорь Владимирович}}<br />
'''Савицкий Игорь Владимирович''' — кандидат физико-математических наук, младший научный сотрудник лаборатории ДУСП кафедры МК.<br />
<br />
* [http://istina.msu.ru/profile/Sav/ Профиль в системе ИСТИНА]<br />
* [https://researchgate.net/profile/Igor-Savitskii Профиль ResearchGate]<br />
* [https://scholar.google.ru/citations?user=kqTH780AAAAJ&hl=ru Профиль Google Scholar]<br />
<br />
== Области научных интересов ==<br />
<br />
* Теория алгоритмов и сложности вычислений<br />
* Классы рекурсивных функций, их машинные и индуктивные описания<br />
<br />
=== Разъяснение для студентов ===<br />
<br />
Теория алгоритмов и рекурсивных функций — это разделы теоретический математики. Результаты этих областей редко возможно напрямую использовать в прикладных задачах.<br />
<br />
В данных научных областях возможна работа с абстрактными вычислительными устройствами (вроде машин Тьюринга), построение сложных функций из простых с помощью различных типов рекурсии, а также использование других способов алгоритмического описания множеств (языков) и функций.<br />
<br />
Взаимодействие с этими математическими объектами и построение алгоритмов в подобных моделях могут быть отдалённо похожи на создание программ на очень специфических, сильно ограниченных языках программирования. Однако любые подобные задачи не предполагают разработки с использованием стандартных прикладных языков программирования.<br />
<br />
== Лекционные курсы ==<br />
<br />
* [[Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)]]<br />
* [[Модели вычислений]] (МК, 4-й курс)<br />
* [[Функциональные системы]] (МК, магистратура)<br />
* [[Дискретная математика (КФ)]] (Казахстанский филиал, 2 курс)<br />
<br />
== Спецсеминары ==<br />
<br />
* [[Дискретные функции и сложность алгоритмов]]</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9Модели вычислений2026-05-05T10:00:53Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
<br />
Курс для студентов бакалавриата кафедры МК, читается в весеннем семестре:<br />
* 4-й курс — 3 часа лекций и 1 час семинаров в неделю (всего 16 пар), отчётность — экзамен.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
Курс посвящён изучению ряда вычислительных моделей (как классических, так и более специальных), используемых в теории алгоритмов. Исследуются распознаваемые данными моделями языки и анализируется сложность задач анализа этих моделей.<br />
<br />
В первой части курса изучаются конечные автоматы-распознаватели и регулярные языки. Вторая часть курса посвящена машинам Тьюринга, рекурсивно перечислимым языкам и неразрешимым задачам. В третьей части рассматриваются формальные грамматики, контекстно-свободные языки и магазинные автоматы. В четвёртой части изучаются конечные автоматы-преобразователи, автоматы для распознавания языков из бесконечных слов, а также задание языков с помощью формул логики второго порядка специального вида.<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:MV_exam_info.pdf|'''Программа курса и порядок проведения экзамена''']]<br />
<br />
Презентации к лекциям см. ниже<br />
<br />
===Литература===<br />
<br />
# Захаров В.А. Презентации к лекциям (см. ниже)<br />
# Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. М.: Мир, 1978. 612 с.<br />
<br />
===Дополнительная литература===<br />
<br />
# Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2001. 768 с.<br />
# Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. М.: МЦНМО, 1999. 176 с.<br />
# Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983.<br />
# Льюис Ф., Розенкранц Д, Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, 1979. 656 с.<br />
# Матрос Д.Ш., Поднебесова Г.Б. Теория алгоритмов. М.: Бином, 2008. 200 с.<br />
# Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. М: Бином, 2006. 247 с. <br />
# Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.<br />
# Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002. 528 с.<br />
<br />
===Записи лекций===<br />
<br />
[https://www.youtube.com/playlist?list=PLhe7c-LCgl4IMdRB_wTdvu7t63FSE6cLn Видеозаписи лекций и семинаров 2025 года] ([[Савицкий Игорь Владимирович|И.В. Савицкий]]).<br />
<br />
[https://m.cs.msu.ru/index.php/s/N6FkcmFbxQkS8z9?path=%2FЗахаровВА%2FМодели%20вычислений Видеозаписи и презентации лекций 2022 года] ([[Захаров Владимир Анатольевич|В.А. Захаров]]).<br />
<br />
== Презентации к лекциям (В.А. Захаров) ==<br />
<br />
'''[[Media: Lecture_CM_1.pdf| Лекция 1.]]''' Формальные языки. Операции над языками.Разнообразие моделей вычислений. Конечные автоматы Рабина-Скотта. Автоматные языки. Упрощение конечных автоматов. Детерминированные конечные автоматы. Минимизация детерминированных конечных автоматов.<br />
<br />
'''[[Media: Lecture_CM_2.pdf| Лекция 2.]]''' Алгоритм преобразования конечного автомата к детерминированному виду. Замкнутость класса автоматных языков относительно операций над языками. Теорема о разрастании для автоматных языков.<br />
Примеры неавтоматных языков.<br />
<br />
'''[[Media: Lecture_3.pdf| Лекция 3.]]''' Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини о соответствии между регулярными выражениями и конечными автоматами. Задача проверки соответствия текста шаблону и теоретико-автоматный подход к ее решению. Задача поиска подстроки в строке. Алгоритм Ахо-Карасик. Двусторонние конечные автоматы. Теорема о соответствии между односторонними и двусторонними конечными автоматами.<br />
<br />
'''[[Media: Lecture_4.pdf| Лекция 4.]]''' Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки. Моделирование односторонних и многоленточных машин Тьюринга одноленточными машинами Тьюринга. Арифметические функции, вычислимые по Тьюрингу. Характеристические теоремы для рекурсивных и рекурсивно-перечислимых языки. Массовые алгоритмические проблемы и их связь с рекурсивными языками. Замкнутость классов рекурсивных и рекурсивно перечислимых языков относительно теоретико-множественных операций.<br />
<br />
'''[[Media: Lecture_5.pdf| Лекция 5.]]''' Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга. Сводимость алгоритмических проблем. Примеры алгоритмически неразрешимых проблем программирования. Функциональные (семантические) свойства программ. Теорема Райса.<br />
<br />
'''[[Media: Lecture_6.pdf| Лекция 6.]]''' Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста. Многоголовочные конечные автоматы. Алгоритмическая неразрешимость проблемы останова для многоголовочных конечных автоматов. Ассоциативные исчисления. Алгоритмическая неразрешимость проблемы достижимости для полусистем Туэ. Примеры алгоритмически неразрешимых проблем математики: проблема разрешимости диофантовых уравнений, проблема мозаики. Машины Минского. Универсальность модели вычислений машин Минского.<br />
<br />
'''[[Media: Lecture_7.pdf| Лекция 7.]]''' Формальные грамматики. Классификация формальных грамматик. Иерархия Хомского формальных языков. Неограниченные грамматики и рекурсивно перечислимые языки. Праволинейные грамматики. Совпадение класса автоматных языков и класса праволинейных языков. Контекстно-свободные грамматики. Устранение недостижимых и &epsilon;-правил. Нормальная форма Хомского контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.<br />
<br />
'''[[Media: Lecture_8.pdf| Лекция 8.]]''' Деревья синтаксического разбора. Теорема о разрастании для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными. Автоматы с магазинной памятью и их свойства. Взаимосвязь контекстно-свободных языков и автоматов с магазинной памятью. Детерминированные магазинные автоматы.<br />
<br />
'''[[Media: Lecture_9.pdf| Лекция 9.]]''' Свойства замкнутости контекстно-свободных языков. Алгоритмические проблемы для КС-языков. Неразрешимость проблемы эквивалентности для контекстно-свободных грамматик. Алгоритм Кока-Касами-Янгера синтаксического анализа контекстно-свободных языков. Детерминированные КС-языки и синтаксические анализаторы. LL(k)-грамматики. Контекстно-зависимые грамматики.<br />
<br />
'''[[Media: Lecture_10.pdf| Лекция 10.]]''' Конечные автоматы-преобразователи. Рациональные отношения и их свойства. Описание рациональных отношений регулярными выражениями. Свойства замкнутости класса рациональных отношений. Неразрешимость проблемы эквивалентности для недетерминированных автоматов-преобразователей. Разрешимость проблемы эквивалентности для детерминированных автоматов-преобразователей. <br />
<br />
'''[[Media: Lecture_11.pdf| Лекция 11.]]''' Реагирующие системы вычислений. Автоматы Бюхи. &omega;-регулярные языки. Свойства замкнутости класса &omega;-регулярных языков. Алгоритмические проблемы для автоматов Бюхи. Другие виды &omega;-автоматов: автоматы Рабина, автоматы Маллера. Взаимосвязь детерминированных и недетерминированных &omega;-автоматов. Применение &omega;-автоматов для верификации реагирующих систем.<br />
<br />
'''[[Media: Lecture_12.pdf| Лекция 12.]]''' Логический способ описания языков. Монадическая предикатов логика второго порядка S1S. Взаимосвязь логики S1S и &omega;-автоматов. Другие логики предикатов второго порядка.<br />
<br />
== Задачи к семинарам (В.А. Захаров) ==<br />
<br />
'''[[Media: Seminar_1.pdf| Семинар 1]]''' (после лекции 3). Построение конечных автоматов для заданных языков. Преобразование недетерминированных автоматов к детерминированным. Минимизация детерминированных автоматов. Распознавание автоматности языков, полученных при помощи теоретико-множественных и алгебраических операций над автоматными языками. Доказательство неавтоматности языков. Построение регулярных выражений для автоматных языков. Построение автоматов, соответствующих регулярным выражениям.<br />
<br />
'''[[Media: Seminar_2.pdf| Семинар 2]]''' (после лекции 6). Доказательство нерекурсивности и рекурсивной перечислимости языков. Использование метода сводимости для доказательства алгоритмической неразрешимости массовых проблем.<br />
<br />
'''[[Media: Seminar_3.pdf| Семинар 3]]''' (после лекции 9). Построение контекстно-свободных грамматик и магазинных автоматов. Приведение контекстно-свободных грамматик к нормальной форме Хомского. Применение алгоритма Кока-Касами-Янгера для проверки принадлежности заданного слова заданному контекстно-свободному языку. Применение теорем о разрастании для классификации языков.<br />
<br />
'''[[Media: Seminar_4.pdf| Семинар 4]]''' (после лекции 12). Построение конечных автоматов-преобразователей, распознающих заданные рациональные отношения. Построение автоматов Бюхи и формул логики S1S, задающих регулярные omega-языки.<br />
<br />
<!--<br />
<br />
== Задачи с решениями ==<br />
<br />
'''[[Media: Seminar_3-1.pdf| Задачи по теме Лекции 7.]]''' (с решениями)<br />
<br />
'''[[Media: Seminar_3-2.pdf| Задачи по теме Лекций 8 и 9.]]''' (с решениями)<br />
<br />
'''[[Media: Seminar_4-1.pdf| Задачи по теме Лекции 10.]]'''<br />
<br />
'''[[Media: Seminar_4-2.pdf| Задачи по теме Лекциям 11 и 12.]]'''<br />
<br />
--></div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_(%D0%9A%D0%A4)Дискретная математика (КФ)2026-05-05T10:00:39Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
<br />
Курс для студентов бакалавриата Казахстанского филиала МГУ, читается дистанционно в осеннем семестре:<br />
* 2-й курс ВМК — 2 часа лекций и 2 часа семинаров в неделю, отчётность — экзамен.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
Базовый курс по дискретной математике, в котором изучаются основы некоторых её традиционных разделов: теория булевых функций, теория графов, теория кодирования, теория автоматов и схем из функциональных элементов.<br />
<br />
В первой части курса изучаются булевы функции, их выразительные возможности и вопросы полноты их систем. Вторая часть посвящена основам теории графов; в ней излагаются основные свойства графов и деревьев, изучаются вопросы связности, планарности и раскрасок графов. В третьей части изучаются алфавитные кодирования, рассматриваются оптимальные коды и коды, исправляющие ошибки. В четвёртой части даются основы теории автоматов и схем из функциональных элементов; демонстрируется выражение схемами автоматных функций, а также некоторых арифметических функций.<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:DM_KF_exam_info.pdf|'''Программа курса''']] (вариант для КФ — 2 часа лекций в неделю)<br />
<br />
[[Media:ДМ_2h_Презентация.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
===Литература===<br />
<br />
# [[Media:ДМ_2h_Презентация.pdf|Савицкий И.В. Презентации к лекциям по дискретной математике для 2 часов в неделю. 2023.]] (в файле присутствует электронное оглавление)<br />
# [[Media:Алексеев_-_2004_-_Лекции_по_дискретной_математике.pdf|Алексеев В.Б. Лекции по дискретной математике. М.: ВМК МГУ, 2004. 74 с.]] <br />
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.<br />
<br />
===Дополнительная литература===<br />
<br />
# Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с.<br />
<br />
===Записи лекций===<br />
<br />
# [https://www.youtube.com/playlist?list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT Видеозаписи лекций 2023 года] ([[Алексеев Валерий Борисович |В.Б. Алексеев]], расширенный вариант курса на 3 ч в неделю).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B3%D0%BB%D0%B0%D0%B2%D1%8B_%D0%B4%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B9_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8_%D0%B8_%D0%BA%D0%B8%D0%B1%D0%B5%D1%80%D0%BD%D0%B5%D1%82%D0%B8%D0%BA%D0%B8_(2-%D0%B9_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA,_4_%D0%BA%D1%83%D1%80%D1%81)Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)2026-05-05T10:00:23Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
<br />
Курс для студентов бакалавриата, читается в осеннем семестре:<br />
* 4-й курс 2-й поток — 2 часа лекций, 1 час консультаций и 1 час семинаров в неделю, отчётность — экзамен.<br />
<br />
Лекторы: [[Ложкин Сергей Андреевич]], [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
Первая и вторая части курса посвящены классическим результатам теории алгоритмов.<br />
<br />
В первой части курса изучаются модели конечных автоматов-распознавателей и преобразователей, демонстрируются различные описания классов задаваемых ими множеств и функций. Во второй части рассматриваются машины Тьюринга и рекурсивные функции, устанавливается связь между вычислимыми и частично рекурсивными функциями, а также даются основные сведения о сложностных классах P и NP.<br />
<br />
Третья часть курса посвящена вопросам синтеза схем для реализации функций алгебры логики. Она дополняет сведения, полученные из курса [[Основы кибернетики (2-й поток, 3 курс)]]. В третьей части излагаются методы получения асимптотических оценок сложности для ряда специальных классов функций, а также методы получения нижних оценок сложности для некоторых «индивидуальных» функций.<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:Программа_ДГДМиК.pdf|'''Программа курса 2025-2026 уч. года''']]<br />
<br />
[[Media:Планы семинаров ДГДМиК.pdf|'''План семинарских занятий''']]<br />
<br />
[[Media:ДГДМиК_Лекции_1-12_Презентация.pdf|'''Презентации к лекциям 1–12''']] (первая и вторая части курса; в файле присутствует электронное оглавление)<br />
<br />
===Литература===<br />
<br />
# [[Media:ДГДМиК_Лекции_1-12_Презентация.pdf|Савицкий И.В. Презентации к лекциям по 1 и 2 частям курса. 2023.]] (в файле присутствует электронное оглавление)<br />
# [[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015. 136 с.]]<br />
# [[Media:Dgcyb-lect-190113.pdf|Ложкин С.А. Дополнительные главы кибернетики. МГУ, 2019.]]<br />
# [[Media:Лекции_ДГКТУС_2008.pdf|Ложкин С. А. Дополнительные главы кибернетики и теории управляющих систем. МГУ, 2008.]]<br />
# [[Media:Sapozhenko_alg.pdf|Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Изд-во МГУ, 2001.]]<br />
<br />
===Дополнительная литература===<br />
<br />
# Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2008. 384 с.<br />
# [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002.]]<br />
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. Физматлит, 2005. 416 с.<br />
# [[Media:ok-2.pdf|Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики», 2-е изд. М.: МАКС Пресс, 2011.]]<br />
<br />
===Записи лекций===<br />
<br />
# [https://www.youtube.com/playlist?list=PLhe7c-LCgl4K9ZH8d2xPfOhLGdqIXxZd1 Видеозаписи лекций 2023 года] ([[Ложкин Сергей Андреевич |С.А. Ложкин]], [[Савицкий Игорь Владимирович |И.В. Савицкий]]).<br />
# [https://www.youtube.com/playlist?list=PLOaW8o20mEgi_9DKM3zURWlvd7BF7MIXp Видеозаписи лекций 1-2 части курса 2020 года] ([[Марченков Сергей Серафимович |С.С. Марченков]]).<br />
# [https://m.cs.msu.ru/s/SzdHtfy8q67277g Видеозаписи и презентации лекций 3 части курса 2020 года] ([[Ложкин Сергей Андреевич |С.А. Ложкин]]).<br />
<br />
<!---<br />
==2025-2026 учебный год==<br />
<br />
===Экзамен===<br />
<br />
[[Media:DGDMiK_exam_info_2024.pdf|'''Вопросы к экзамену и порядок проведения''']]<br />
<br />
Экзамен проводится 24 января 2026 года.<br />
<br />
Обратите внимание! Личное присутствие студента обязательно даже в случае выставление оценки автоматом. Отсутствие студента будет приравнено к неявке, а на пересдачах предварительные оценки уже не будут учитываться.<br />
<br />
Для экзамена зарезервированы аудитории 503–505. В аудиториях 503 и 504 будет приниматься экзамен, в аудитории 505 проставляются автоматы. Аудитории 506, 507 и 524 использоваться не будут.<br />
<br />
Студенты из групп 411, 412, 413, 414, 415 сдают в аудитории 503.<br />
<br />
Студенты из групп 416, 417, 418, 491, 492 сдают в аудитории 504.<br />
<br />
Приходить следует к следующему времени (независимо от наличия автомата):<br />
<br />
Группы 411, 412, 415, 416 и 492 — к 9:00.<br />
<br />
Группы 413, 414, 417, 418 и 491 — к 10:30.<br />
<br />
Студентам, имеющим право на автомат и согласным с оценкой следует проходить с зачётками в аудиторию 505, где отдельный человек будет проставлять автоматы (лично передать зачётку и проследить за проставлением правильной оценки в рабочую ведомость).<br />
<br />
Студентам, которые будут сдавать экзамен в какой-либо форме, следует централизованно (внутри группы) собрать зачётки и отнести в аудиторию экзамена своей группы (503 или 504). После этого преподаватели будут вызывать студентов по одному.<br />
<br />
Студентам не со второго потока следует присоединиться к группе, с которой они посещали семинары.<br />
<br />
===Консультации и другие мероприятия 22 января 2026 года.===<br />
<br />
10:30, ауд. П-13. Написание пропущенной по уважительной причине контрольной.<br />
* Каждый студент может написать не более одной пропущенной контрольной.<br />
* Для допуска на написание пропущенной контрольной необходимо:<br />
# Заранее (до 18 января) записаться (сообщить И.В. Савицкому) с указанием номера контрольной (1, 2 или 3), которую студент будет писать.<br />
# Предъявить документ, подтверждающий уважительную причину отсутствия на контрольной с этим номером (справка по болезни). Можно предъявить фото документа заранее, либо принести оригинал, копию или фото на само мероприятие.<br />
<br />
12:05, ауд. П-13. Консультация по лекциям (С.А. Ложкин, И.В. Савицкий).<br />
<br />
13:40, ауд. П-13. Группы 413, 414, 416, 417: консультация по семинарам (Т.В. Андреева).<br />
<br />
13:40, ауд. 503. Группы 411, 419/2: консультация по семинарам (А.В. Бухман).<br />
<br />
13:40, ауд. 505. Группы 412, 419/1: консультация по семинарам (Б.В. Чокаев).<br />
<br />
13:40, ауд. 506. Группы 415, 418: консультация по семинарам (И.В. Савицкий).<br />
<br />
На семинарских консультациях студенты с других потоков присоединяются к группам, с которыми они посещали семинары.<br />
<br />
===Расписание лекций и консультаций===<br />
<br />
ПН 1 сентября — лекция<br><br />
ПТ 5 сентября — лекция<br />
<br />
ПН 8 сентября — лекция<br><br />
ПТ 12 сентября — нет занятия<br />
<br />
ПН 15 сентября — лекция<br><br />
ПТ 19 сентября — лекция<br />
<br />
ПН 22 сентября — лекция<br><br />
ПТ 26 сентября — нет занятия<br />
<br />
ПН 29 сентября — лекция<br><br />
ПТ 3 октября — лекция<br />
<br />
ПН 6 октября — лекция<br><br />
ПТ 10 октября — нет занятия<br />
<br />
ПН 13 октября — лекция<br><br />
ПТ 17 октября — консультация к КР по части 1<br />
<br />
ПН 20 октября — КР по части 1<br><br />
ПТ 24 октября — лекция<br />
<br />
ПН 27 октября — лекция<br><br />
ПТ 31 октября — нет занятия<br />
<br />
СБ 1 ноября — лекция (по расписанию понедельника)<br><br />
ПТ 7 ноября — лекция<br />
<br />
ПН 10 ноября — нет занятия<br><br />
ПТ 14 ноября — консультация к КР по части 2<br />
<br />
ПН 17 ноября — КР по части 2<br><br />
ПТ 21 ноября — лекция<br />
<br />
ПН 24 ноября — лекция<br><br />
ПТ 28 ноября — нет занятия<br />
<br />
ПН 1 декабря — нет занятия<br><br />
ПТ 5 декабря — лекция<br />
<br />
ПН 8 декабря — лекция<br><br />
ПТ 12 декабря — лекция (разбор задач семинара 8)<br />
<br />
ПН 15 декабря — лекция + консультация к КР по части 3<br><br />
ПТ 19 декабря — КР по части 3<br />
---></div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9Модели вычислений2026-05-05T09:58:04Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
<br />
Курс для студентов бакалавриата кафедры МК, читается в весеннем семестре:<br />
* 4-й курс — 3 часа лекций и 1 час семинаров в неделю (всего 16 пар), отчетность — экзамен.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
Курс посвящён изучению ряда вычислительных моделей (как классических, так и более специальных), используемых в теории алгоритмов. Исследуются распознаваемые данными моделями языки и анализируется сложность задач анализа этих моделей.<br />
<br />
В первой части курса изучаются конечные автоматы-распознаватели и регулярные языки. Вторая часть курса посвящена машинам Тьюринга, рекурсивно перечислимым языкам и неразрешимым задачам. В третьей части рассматриваются формальные грамматики, контекстно-свободные языки и магазинные автоматы. В четвёртой части изучаются конечные автоматы-преобразователи, автоматы для распознавания языков из бесконечных слов, а также задание языков с помощью формул логики второго порядка специального вида.<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:MV_exam_info.pdf|'''Программа курса и порядок проведения экзамена''']]<br />
<br />
Презентации к лекциям см. ниже<br />
<br />
===Литература===<br />
<br />
# Захаров В.А. Презентации к лекциям (см. ниже)<br />
# Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. М.: Мир, 1978. 612 с.<br />
<br />
===Дополнительная литература===<br />
<br />
# Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2001. 768 с.<br />
# Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. М.: МЦНМО, 1999. 176 с.<br />
# Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983.<br />
# Льюис Ф., Розенкранц Д, Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, 1979. 656 с.<br />
# Матрос Д.Ш., Поднебесова Г.Б. Теория алгоритмов. М.: Бином, 2008. 200 с.<br />
# Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. М: Бином, 2006. 247 с. <br />
# Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.<br />
# Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002. 528 с.<br />
<br />
===Записи лекций===<br />
<br />
[https://www.youtube.com/playlist?list=PLhe7c-LCgl4IMdRB_wTdvu7t63FSE6cLn Видеозаписи лекций и семинаров 2025 года] ([[Савицкий Игорь Владимирович|И.В. Савицкий]]).<br />
<br />
[https://m.cs.msu.ru/index.php/s/N6FkcmFbxQkS8z9?path=%2FЗахаровВА%2FМодели%20вычислений Видеозаписи и презентации лекций 2022 года] ([[Захаров Владимир Анатольевич|В.А. Захаров]]).<br />
<br />
== Презентации к лекциям (В.А. Захаров) ==<br />
<br />
'''[[Media: Lecture_CM_1.pdf| Лекция 1.]]''' Формальные языки. Операции над языками.Разнообразие моделей вычислений. Конечные автоматы Рабина-Скотта. Автоматные языки. Упрощение конечных автоматов. Детерминированные конечные автоматы. Минимизация детерминированных конечных автоматов.<br />
<br />
'''[[Media: Lecture_CM_2.pdf| Лекция 2.]]''' Алгоритм преобразования конечного автомата к детерминированному виду. Замкнутость класса автоматных языков относительно операций над языками. Теорема о разрастании для автоматных языков.<br />
Примеры неавтоматных языков.<br />
<br />
'''[[Media: Lecture_3.pdf| Лекция 3.]]''' Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини о соответствии между регулярными выражениями и конечными автоматами. Задача проверки соответствия текста шаблону и теоретико-автоматный подход к ее решению. Задача поиска подстроки в строке. Алгоритм Ахо-Карасик. Двусторонние конечные автоматы. Теорема о соответствии между односторонними и двусторонними конечными автоматами.<br />
<br />
'''[[Media: Lecture_4.pdf| Лекция 4.]]''' Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки. Моделирование односторонних и многоленточных машин Тьюринга одноленточными машинами Тьюринга. Арифметические функции, вычислимые по Тьюрингу. Характеристические теоремы для рекурсивных и рекурсивно-перечислимых языки. Массовые алгоритмические проблемы и их связь с рекурсивными языками. Замкнутость классов рекурсивных и рекурсивно перечислимых языков относительно теоретико-множественных операций.<br />
<br />
'''[[Media: Lecture_5.pdf| Лекция 5.]]''' Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга. Сводимость алгоритмических проблем. Примеры алгоритмически неразрешимых проблем программирования. Функциональные (семантические) свойства программ. Теорема Райса.<br />
<br />
'''[[Media: Lecture_6.pdf| Лекция 6.]]''' Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста. Многоголовочные конечные автоматы. Алгоритмическая неразрешимость проблемы останова для многоголовочных конечных автоматов. Ассоциативные исчисления. Алгоритмическая неразрешимость проблемы достижимости для полусистем Туэ. Примеры алгоритмически неразрешимых проблем математики: проблема разрешимости диофантовых уравнений, проблема мозаики. Машины Минского. Универсальность модели вычислений машин Минского.<br />
<br />
'''[[Media: Lecture_7.pdf| Лекция 7.]]''' Формальные грамматики. Классификация формальных грамматик. Иерархия Хомского формальных языков. Неограниченные грамматики и рекурсивно перечислимые языки. Праволинейные грамматики. Совпадение класса автоматных языков и класса праволинейных языков. Контекстно-свободные грамматики. Устранение недостижимых и &epsilon;-правил. Нормальная форма Хомского контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.<br />
<br />
'''[[Media: Lecture_8.pdf| Лекция 8.]]''' Деревья синтаксического разбора. Теорема о разрастании для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными. Автоматы с магазинной памятью и их свойства. Взаимосвязь контекстно-свободных языков и автоматов с магазинной памятью. Детерминированные магазинные автоматы.<br />
<br />
'''[[Media: Lecture_9.pdf| Лекция 9.]]''' Свойства замкнутости контекстно-свободных языков. Алгоритмические проблемы для КС-языков. Неразрешимость проблемы эквивалентности для контекстно-свободных грамматик. Алгоритм Кока-Касами-Янгера синтаксического анализа контекстно-свободных языков. Детерминированные КС-языки и синтаксические анализаторы. LL(k)-грамматики. Контекстно-зависимые грамматики.<br />
<br />
'''[[Media: Lecture_10.pdf| Лекция 10.]]''' Конечные автоматы-преобразователи. Рациональные отношения и их свойства. Описание рациональных отношений регулярными выражениями. Свойства замкнутости класса рациональных отношений. Неразрешимость проблемы эквивалентности для недетерминированных автоматов-преобразователей. Разрешимость проблемы эквивалентности для детерминированных автоматов-преобразователей. <br />
<br />
'''[[Media: Lecture_11.pdf| Лекция 11.]]''' Реагирующие системы вычислений. Автоматы Бюхи. &omega;-регулярные языки. Свойства замкнутости класса &omega;-регулярных языков. Алгоритмические проблемы для автоматов Бюхи. Другие виды &omega;-автоматов: автоматы Рабина, автоматы Маллера. Взаимосвязь детерминированных и недетерминированных &omega;-автоматов. Применение &omega;-автоматов для верификации реагирующих систем.<br />
<br />
'''[[Media: Lecture_12.pdf| Лекция 12.]]''' Логический способ описания языков. Монадическая предикатов логика второго порядка S1S. Взаимосвязь логики S1S и &omega;-автоматов. Другие логики предикатов второго порядка.<br />
<br />
== Задачи к семинарам (В.А. Захаров) ==<br />
<br />
'''[[Media: Seminar_1.pdf| Семинар 1]]''' (после лекции 3). Построение конечных автоматов для заданных языков. Преобразование недетерминированных автоматов к детерминированным. Минимизация детерминированных автоматов. Распознавание автоматности языков, полученных при помощи теоретико-множественных и алгебраических операций над автоматными языками. Доказательство неавтоматности языков. Построение регулярных выражений для автоматных языков. Построение автоматов, соответствующих регулярным выражениям.<br />
<br />
'''[[Media: Seminar_2.pdf| Семинар 2]]''' (после лекции 6). Доказательство нерекурсивности и рекурсивной перечислимости языков. Использование метода сводимости для доказательства алгоритмической неразрешимости массовых проблем.<br />
<br />
'''[[Media: Seminar_3.pdf| Семинар 3]]''' (после лекции 9). Построение контекстно-свободных грамматик и магазинных автоматов. Приведение контекстно-свободных грамматик к нормальной форме Хомского. Применение алгоритма Кока-Касами-Янгера для проверки принадлежности заданного слова заданному контекстно-свободному языку. Применение теорем о разрастании для классификации языков.<br />
<br />
'''[[Media: Seminar_4.pdf| Семинар 4]]''' (после лекции 12). Построение конечных автоматов-преобразователей, распознающих заданные рациональные отношения. Построение автоматов Бюхи и формул логики S1S, задающих регулярные omega-языки.<br />
<br />
<!--<br />
<br />
== Задачи с решениями ==<br />
<br />
'''[[Media: Seminar_3-1.pdf| Задачи по теме Лекции 7.]]''' (с решениями)<br />
<br />
'''[[Media: Seminar_3-2.pdf| Задачи по теме Лекций 8 и 9.]]''' (с решениями)<br />
<br />
'''[[Media: Seminar_4-1.pdf| Задачи по теме Лекции 10.]]'''<br />
<br />
'''[[Media: Seminar_4-2.pdf| Задачи по теме Лекциям 11 и 12.]]'''<br />
<br />
--></div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8BФункциональные системы2026-05-04T15:27:13Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]<br />
[[Категория:Магистерская программа Дискретные управляющие системы и их приложения]]<br />
<br />
Курс для студентов магистратуры кафедры МК, читается в осеннем семестре:<br />
* 1-й курс программы «Дискретные структуры и алгоритмы» — 2 часа лекций и 1 час семинаров в неделю, отчётность экзамен. <br />
* 2-й курс программы «Дискретные управляющие системы» — 2 часа лекций в неделю, отчётность зачёт.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
В курсе излагаются классические результаты о замкнутости и полноте для булевых функций и функций k-значной логики. Он углубляет сведения, полученные из курса [[Дискретная математика (1-й курс)]].<br />
<br />
В первой, основной части курса даётся полное описание всех замкнутых классов булевых функций. Во второй части доказывается ряд теорем о полноте для функций k-значной логики. В третьей части курса приводится описание всех предполных классов функций k-значной логики (без доказательств).<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:FS-curriculum.pdf|'''Вопросы к экзамену и зачёту''']]<br />
<br />
[[Media:Функциональные_системы_лекции.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
[[Media:PostDiagram.pdf|'''Диаграмма Поста''']] (распечатку разрешено использовать на экзамене и зачёте)<br />
<br />
===Литература===<br />
<br />
# [[Media:Функциональные_системы_лекции.pdf|Савицкий И.В. Презентации к лекциям. 2025.]] (в файле присутствует электронное оглавление)<br />
# [[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012. 47 с.]]<br />
# Марченков С.С. Избранные главы дискретной математики. М.: Физматлит, 2023. 192 с.<br />
# [[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015. 136 с.]]<br />
<br />
===Дополнительная литература===<br />
<br />
# Марченков С.С. Основы теории булевых функций. М.: Физматлит, 2014. 135 с.<br />
# Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 103 с.<br />
# Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2003. 384 с.<br />
# Фрейвалд Р.В. Функциональная полнота для не всюду определенных функций алгебры логики // Дискретный анализ. 1966. № 8. С. 55–68.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8BФункциональные системы2026-05-04T15:26:45Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]<br />
[[Категория:Магистерская программа Дискретные управляющие системы и их приложения]]<br />
<br />
Курс для студентов магистратуры кафедры МК, читается в осеннем семестре:<br />
* 1-й курс программы «Дискретные структуры и алгоритмы» — 2 часа лекций и 1 час семинаров в неделю, отчётность экзамен. <br />
* 2-й курс программы «Дискретные управляющие системы» — 2 часа лекций в неделю, отчётность зачёт.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
В курсе излагаются классические результаты о замкнутости и полноте для булевых функций и функций k-значной логики. Он углубляет сведения, полученные из курса [[Дискретная математика (1-й курс)]].<br />
<br />
В первой, основной части курса даётся полное описание всех замкнутых классов булевых функций. Во второй части доказывается ряд теорем о полноте для функций k-значной логики. В третьей части курса приводится описание всех предполных классов функций k-значной логики (без доказательств).<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:FS-curriculum.pdf|'''Вопросы к экзамену и зачёту''']]<br />
<br />
[[Media:Функциональные_системы_лекции.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
[[Media:PostDiagram.pdf|'''Диаграмма Поста''']] (распечатку разрешено использовать на зачёте / экзамене)<br />
<br />
===Литература===<br />
<br />
# [[Media:Функциональные_системы_лекции.pdf|Савицкий И.В. Презентации к лекциям. 2025.]] (в файле присутствует электронное оглавление)<br />
# [[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012. 47 с.]]<br />
# Марченков С.С. Избранные главы дискретной математики. М.: Физматлит, 2023. 192 с.<br />
# [[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015. 136 с.]]<br />
<br />
===Дополнительная литература===<br />
<br />
# Марченков С.С. Основы теории булевых функций. М.: Физматлит, 2014. 135 с.<br />
# Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 103 с.<br />
# Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2003. 384 с.<br />
# Фрейвалд Р.В. Функциональная полнота для не всюду определенных функций алгебры логики // Дискретный анализ. 1966. № 8. С. 55–68.</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:%D0%94%D0%9C_2h_%D0%9F%D1%80%D0%B5%D0%B7%D0%B5%D0%BD%D1%82%D0%B0%D1%86%D0%B8%D1%8F.pdfФайл:ДМ 2h Презентация.pdf2026-05-04T12:46:43Z<p>SavitskiyIV: SavitskiyIV загружена новая версия «Файл:ДМ 2h Презентация.pdf»</p>
<hr />
<div></div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_(%D0%9A%D0%A4)Дискретная математика (КФ)2026-05-01T09:19:42Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
<br />
Курс для студентов бакалавриата Казахстанского филиала МГУ, читается дистанционно в осеннем семестре:<br />
* 2-й курс ВМК — 2 часа лекций и 2 часа семинаров в неделю, отчетность — экзамен.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
Базовый курс по дискретной математике, в котором изучаются основы некоторых её традиционных разделов: теория булевых функций, теория графов, теория кодирования, теория автоматов и схем из функциональных элементов.<br />
<br />
В первой части курса изучаются булевы функции, их выразительные возможности и вопросы полноты их систем. Вторая часть посвящена основам теории графов; в ней излагаются основные свойства графов и деревьев, изучаются вопросы связности, планарности и раскрасок графов. В третьей части изучаются алфавитные кодирования, рассматриваются оптимальные коды и коды, исправляющие ошибки. В четвёртой части даются основы теории автоматов и схем из функциональных элементов; демонстрируется выражение схемами автоматных функций, а также некоторых арифметических функций.<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:DM_KF_exam_info.pdf|'''Программа курса''']] (вариант для КФ — 2 часа лекций в неделю)<br />
<br />
[[Media:ДМ_2h_Презентация.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
===Литература===<br />
<br />
# [[Media:ДМ_2h_Презентация.pdf|Савицкий И.В. Презентации к лекциям по дискретной математике для 2 часов в неделю. 2023.]] (в файле присутствует электронное оглавление)<br />
# [[Media:Алексеев_-_2004_-_Лекции_по_дискретной_математике.pdf|Алексеев В.Б. Лекции по дискретной математике. М.: ВМК МГУ, 2004. 74 с.]] <br />
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.<br />
<br />
===Дополнительная литература===<br />
<br />
# Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с.<br />
<br />
===Записи лекций===<br />
<br />
# [https://www.youtube.com/playlist?list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT Видеозаписи лекций 2023 года] ([[Алексеев Валерий Борисович |В.Б. Алексеев]], расширенный вариант курса на 3 ч в неделю).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_(%D0%9A%D0%A4)Дискретная математика (КФ)2026-05-01T09:19:23Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
<br />
Курс для студентов бакалавриата Казахстанского филиала МГУ, читается дистанционно в осеннем семестре:<br />
* 2-й курс ВМК — 2 часа лекций и 2 часа семинаров в неделю, отчетность — экзамен.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
Базовый курс по дискретной математике, в котором изучаются основы некоторых её традиционных разделов: теория булевых функций, теория графов, теория кодирования, теория автоматов и схем из функциональных элементов.<br />
<br />
В первой части курса изучаются булевы функции, их выразительные возможности и вопросы полноты их систем. Вторая часть посвящена основам теории графов; в ней излагаются основные свойства графов и деревьев, изучаются вопросы связности, планарности и раскрасок графов. В третьей части изучаются алфавитные кодирования, рассматриваются оптимальные коды и коды, исправляющие ошибки. В четвёртой части даются основы теории автоматов и схем из функциональных элементов; демонстрируется выражение схемами автоматных функций, а также некоторых арифметических функций.<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:DM_KF_exam_info.pdf|'''Программа курса''']] (вариант для КФ — 2 лекции в неделю)<br />
<br />
[[Media:ДМ_2h_Презентация.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
===Литература===<br />
<br />
# [[Media:ДМ_2h_Презентация.pdf|Савицкий И.В. Презентации к лекциям по дискретной математике для 2 часов в неделю. 2023.]] (в файле присутствует электронное оглавление)<br />
# [[Media:Алексеев_-_2004_-_Лекции_по_дискретной_математике.pdf|Алексеев В.Б. Лекции по дискретной математике. М.: ВМК МГУ, 2004. 74 с.]] <br />
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.<br />
<br />
===Дополнительная литература===<br />
<br />
# Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с.<br />
<br />
===Записи лекций===<br />
<br />
# [https://www.youtube.com/playlist?list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT Видеозаписи лекций 2023 года] ([[Алексеев Валерий Борисович |В.Б. Алексеев]], расширенный вариант курса на 3 ч в неделю).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:DM_KF_exam_info.pdfФайл:DM KF exam info.pdf2026-05-01T09:18:53Z<p>SavitskiyIV: SavitskiyIV загружена новая версия «Файл:DM KF exam info.pdf»</p>
<hr />
<div>Программа курса «Дискретная математика» для Казахстанского филиала МГУ</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:DM_KF_exam_info.pdfФайл:DM KF exam info.pdf2026-05-01T09:13:04Z<p>SavitskiyIV: SavitskiyIV загружена новая версия «Файл:DM KF exam info.pdf»</p>
<hr />
<div>Программа курса «Дискретная математика» для Казахстанского филиала МГУ</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_(%D0%9A%D0%A4)Дискретная математика (КФ)2026-05-01T09:12:00Z<p>SavitskiyIV: </p>
<hr />
<div>__NOTOC__<br />
<div style="max-width:940px"><br />
[[Категория:Лекционные курсы кафедры МК]]<br />
<br />
Курс для студентов бакалавриата Казахстанского филиала МГУ, читается дистанционно в осеннем семестре:<br />
* 2-й курс ВМК — 2 часа лекций и 2 часа семинаров в неделю, отчетность — экзамен.<br />
<br />
Лектор: [[Савицкий Игорь Владимирович]].<br />
<br />
==Аннотация==<br />
<br />
Базовый курс по дискретной математике, в котором изучаются основы некоторых её традиционных разделов: теория булевых функций, теория графов, теория кодирования, теория автоматов и схем из функциональных элементов.<br />
<br />
В первой части курса изучаются булевы функции, их выразительные возможности и вопросы полноты их систем. Вторая часть посвящена основам теории графов; в ней излагаются основные свойства графов и деревьев, изучаются вопросы связности, планарности и раскрасок графов. В третьей части изучаются алфавитные кодирования, рассматриваются оптимальные коды и коды, исправляющие ошибки. В четвёртой части даются основы теории автоматов и схем из функциональных элементов; демонстрируется выражение схемами автоматных функций, а также некоторых арифметических функций.<br />
<br />
==Материалы по курсу==<br />
<br />
===Программа и основные материалы===<br />
<br />
[[Media:DM_KF_exam_info.pdf|'''Программа курса''']]<br />
<br />
[[Media:ДМ_2h_Презентация.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)<br />
<br />
===Литература===<br />
<br />
# [[Media:ДМ_2h_Презентация.pdf|Савицкий И.В. Презентации к лекциям по дискретной математике для 2 часов в неделю. 2023.]] (в файле присутствует электронное оглавление)<br />
# [[Media:Алексеев_-_2004_-_Лекции_по_дискретной_математике.pdf|Алексеев В.Б. Лекции по дискретной математике. М.: ВМК МГУ, 2004. 74 с.]] <br />
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.<br />
<br />
===Дополнительная литература===<br />
<br />
# Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с.<br />
<br />
===Записи лекций===<br />
<br />
# [https://www.youtube.com/playlist?list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT Видеозаписи лекций 2023 года] ([[Алексеев Валерий Борисович |В.Б. Алексеев]], расширенный вариант курса на 3 ч в неделю).</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:DM_KF_exam_info.pdfФайл:DM KF exam info.pdf2026-05-01T09:11:44Z<p>SavitskiyIV: Программа курса «Дискретная математика» для Казахстанского филиала МГУ</p>
<hr />
<div>Программа курса «Дискретная математика» для Казахстанского филиала МГУ</div>SavitskiyIV//mk.cs.msu.ru/index.php/%D0%A4%D0%B0%D0%B9%D0%BB:MV_exam_info.pdfФайл:MV exam info.pdf2026-04-18T20:20:30Z<p>SavitskiyIV: SavitskiyIV загружена новая версия «Файл:MV exam info.pdf»</p>
<hr />
<div></div>SavitskiyIV