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