Алгоритмические вопросы алгебры

Бакалавриат 2024/2025

Статус: Курс обязательный (Прикладная математика и информатика)

Кто читает: Департамент больших данных и информационного поиска

Когда читается: 4-й курс, 3 модуль

Охват аудитории: для своего кампуса

Преподаватели: Таламбуца Алексей Леонидович

Язык: русский

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Курс посвящён классическим алгоритмическим вопросам алгебры и дискретной математики, которые активно изучались, начиная с 1940-х годов, после того, как был сформулирован тезис Чёрча-Тьюринга, давший точное определение эффективно вычислимым функциям. Именно тогда стало возможным доказывать невозможность построения алгоритма для решения некоторой общей проблемы. Содержание курса будут составлять последовательно излагаемые известные результаты, в основном полученные во второй половине 20 века по алгоритмической разрешимости в алгебре и дискретной математике. При этом для некоторых задач будет доказана алгоритмическая неразрешимость, а для других, с виду довольно близких, будет устанавливаться разрешимость. В частности, будут рассматриваться проблема равенства в полугруппах, проблема вырождения произведения матриц, проблемы равенства, сопряжённости и проблемы вхождения для групп и полугрупп, а также проблемы однозначности декодирования для кодов и L-кодов.

Цель освоения дисциплины

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

Планируемые результаты обучения

Знание кодов и L-кодов, нестандартных систем счисления, алгоритма Хонкалы.
Знание алгоритмических проблем в алгебре

Содержание учебной дисциплины

Алгоритмические проблемы в алгебре, гипотеза Эйлера, теорема ДПРМ (без доказательства). Проблема Коллатца. Язык программирования FRACTRAN.
Коды и L-коды, нестандартные системы счисления, алгоритм Хонкалы.
Теорема Сардинаса-Паттерсона о разрешимости обратимости кодирования. Свободный моноид и проблема вхождения.
Проблема соответствия Поста (ПСП). Неразрешимость ПСП.
Теорема Патерсона о неразрешимости проблемы выражения нулевой матрицы.
Проблема порождения свободного подмоноида, её неразрешимость для целочисленных матриц (теорема Кларнера-Бирже-Саттерфилда).
Полугруппы и группы, заданные определяющими соотношениями. Свободная группа.
Теорема Маркова-Поста. Теорема Новикова (без доказательства).
Проблема равенства и сопряжённости в свободной группе. Финитная аппроксимируемость.
Проблема вхождения в подгруппу свободной группы. Фолдинги и алгоритм Столлингса. Теоремы Маканина (без доказательства).

Элементы контроля

Домашнее задание 1
Содержит 5 задач по темам первых 4 лекций и семинаров.
Домашнее задание 2
Содержит 5 задач по темам лекций и семинаров №6-8.
Контрольная работа
Содержит 4 задач. Задачи 1-3 и 3-4 относятся к тем же типам, что и задачи домашних заданий № 1 и № 2, соответственно.
Экзамен
Экзамен проводится в устной форме, предполагается проведение в аудитории. Студент получает билет, который включает в себя два вопроса из программы экзамена – один вопрос по материалу лекций 1-6 и один вопрос по материалу лекций 7-10. Во время подготовки можно использовать любые печатные материалы, но запрещается использовать электронные средства коммуникации. После ответа студенту могут быть заданы дополнительные вопросы по программе курса, а также предложены задачи на понимание теоретического материала. Такие задачи не требуют проведения обширных вычислений.

Промежуточная аттестация

2024/2025 3rd module
Итог = Округление(0.3 * ДЗ + 0.3 * КР + 0.4 * Э), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен.

Список литературы

Авторы

Кононова Елизавета Дмитриевна

Программа дисциплины