Алгоритмическая алгебра
Название спецкурса на английском языке
Algorithmic algebra
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Элементы теории рекурсивных функций и алгоритмов.
Частично рекурсивные функции как вариант формализации понятия алгоритма. Примитивно рекурсивные и общерекурсивные функции.
Перечислимые, разрешимые, примитивно рекурсивные предикаты, отношения,
множества.
Теорема Аккермана (о диагональной одноместной «быстрорастущей» общерекурсивной функции, не являющейся примитивно рекурсивной функцией).
Теоремы об устранимости кванторов в элементарных теориях (в теориях 1-го порядка) некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теоремы об устранимости кванторов в монадических теориях 2-го порядка некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования (без доказательства). Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования.
Применения теорем о разрешимости монадических теорий 2-го порядка к доказательству разрешимости некоторых теорий 1-го порядка.
Частично рекурсивные функции как вариант формализации понятия алгоритма. Примитивно рекурсивные и общерекурсивные функции.
Перечислимые, разрешимые, примитивно рекурсивные предикаты, отношения,
множества.
Теорема Аккермана (о диагональной одноместной «быстрорастущей» общерекурсивной функции, не являющейся примитивно рекурсивной функцией).
Теоремы об устранимости кванторов в элементарных теориях (в теориях 1-го порядка) некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теоремы об устранимости кванторов в монадических теориях 2-го порядка некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования (без доказательства). Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования.
Применения теорем о разрешимости монадических теорий 2-го порядка к доказательству разрешимости некоторых теорий 1-го порядка.
Список источников
Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965
Панкратьев Е.В. Элементы компьютерной алгебры – М.: Интернет-университет информационных технологий
Рабин М. Разрешимые теории. Справочная книга по математической логике. Часть 3 Теория рекурсии. – Москва: Наука, 1982
Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980
Панкратьев Е.В. Элементы компьютерной алгебры – М.: Интернет-университет информационных технологий
Рабин М. Разрешимые теории. Справочная книга по математической логике. Часть 3 Теория рекурсии. – Москва: Наука, 1982
Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980
Дополнительная информация
UPD: Спецкурс с осени переносится на весну
В курсе освещаются следующие вопросы:
1) начальные сведения по теории алгоритмов и теории конечных автоматов,
2) уравнения в словах в свободном моноиде,
3) метод устранения кванторов,
4) алгоритмическая разрешимость теорий некоторых классов алгебраических систем.
Нужные для понимания спецкурса сведения по математической логике и алгебре будут кратко напоминаться по ходу лекций.
День недели
четверг
Время
16:45-18:20
Аудитория
1604
Дата первого занятия
Аудитория первого занятия
1604
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.