Алгоритмические вопросы алгебры
Название спецкурса на английском языке
Algorithmic issues in algebra
Пререквизиты
От слушателей не требуется специальной подготовки, хотя желательно знакомство с основными понятиями алгебры — группы, кольца, гомоморфизма и т.п.
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Математический институт имени В. А. Стеклова РАН]
Семестр
Полгода (осень)
Семестр
Осень
Тип курса
Спецкурс по выбору студента
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2026/27
Список тем
Вычислимость и формализация понятия алгоритма: модели вычислений, машины Тьюринга, рекурсивные функции и множества, неразрешимость проблемы остановки.
Алгоритмические проблемы в математике. Примеры разрешимых и неразрешимых проблем.
Алгоритмические проблемы для полугрупп (моноидов). Неразрешимость проблемы равенства для конечно определённых полугрупп.
Алгоритмические проблемы для групп. Проблемы равенства, сопряженности, изоморфизма и вхождения в подгруппу. Неразрешимость проблемы равенства в конечно определённых группах. Неразрешимость большинства алгоритмических проблем для групп.
Разрешимые алгоритмические проблемы для групп. Проблемы равенства, сопряжённости и вхождения для свободной группы. Проблемы вхождения и изоморфизма для конечно порождённых абелевых групп.
Алгоритмические проблемы для коммутативных колец. Проблема корня и проблема вхождения в идеал. Базисы Грёбнера.
Алгоритмические проблемы в математике. Примеры разрешимых и неразрешимых проблем.
Алгоритмические проблемы для полугрупп (моноидов). Неразрешимость проблемы равенства для конечно определённых полугрупп.
Алгоритмические проблемы для групп. Проблемы равенства, сопряженности, изоморфизма и вхождения в подгруппу. Неразрешимость проблемы равенства в конечно определённых группах. Неразрешимость большинства алгоритмических проблем для групп.
Разрешимые алгоритмические проблемы для групп. Проблемы равенства, сопряжённости и вхождения для свободной группы. Проблемы вхождения и изоморфизма для конечно порождённых абелевых групп.
Алгоритмические проблемы для коммутативных колец. Проблема корня и проблема вхождения в идеал. Базисы Грёбнера.
Список источников
В. С. Атабекян, Л. Д. Беклемишев, В. С. Губа, И. Г. Лысёнок, А. А. Разборов, А. Л. Семенов, “Вопросы алгебры и математической логики. Научное наследие С. И. Адяна”, УМН, 76:1(457) (2021), 3–30
Дополнительная информация
Страница спецкурса: https://www.mathnet.ru/conf2804
Цель курса — ознакомление с классическими разрешимыми и неразрешимыми алгоритмическими проблемами алгебры. Предполагается вводная часть, в которой будут рассмотрены различные вычислительные модели, приводящие к формализации понятий алгоритма и вычислимой функции. Будет доказана неразрешимость ряда алгоритмических проблем, в частности, неразрешимость проблемы равенства в конечно определенных полугруппах. С другой стороны, будут приведены примеры разрешимых проблем с описанием соответствующих алгоритмов, например, проблемы равенства и изоморфизма для конечно порожденных абелевых групп.
День недели
понедельник
Время
18:30-20:05
Аудитория
Внешняя площадка
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.