Механико-математический факультет МГУ им. М.В. Ломоносова
Кафедра Математической теории интеллектуальных систем (МаТИС)
Г.И. Сыркин читает полугодовой спецкурс
«Введение в алгоритмическую алгебру»
(для студентов 1-6 курса, магистрантов и аспирантов)
В 1-м семестре 2019-2020 учебного года
По четвергам с 16 час. 45 мин. в ауд. 465 ВМК, начиная с 26 сентября
Программа
(Некоторые разделы данной программы могут быть перенесены в полугодовой спецкурс
«Дополнительные главы алгоритмической алгебры», читаемый во 2-м семестре)
Некоторые сведения из теории рекурсивных функций.
1.1. Частично рекурсивные функции как вариант формализации понятия алгоритма. Основные примитивно рекурсивные функции и основные рекурсивные операторы (операторы композиции, примитивной рекурсии, минимизации). Операторные термы (с переменными по частичным многоместным функциям). Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции как значения соответствующих операторных термов без функциональных переменных. Частичные функции, рекурсивные относительно множества частичных функций. Примеры представления примитивно рекурсивными операторными термами конкретных функций (функции сложения и функции умножения двух натуральных чисел, функции взятия факториала натурального числа). Некоторые важные операторы, выразимые через основные примитивно рекурсивные функции и основные рекурсивные операторы.
1.2. Теорема Р. Робинсон о совпадении класса всех одноместных примитивно-рекурсивных функций с классом одноместных функций, порождаемых функцией следования s и функцией взятия квадратичного остатка q с помощью операторов сложения, композиции и итерирования функций (без доказательства). Двуместная «быстрорастущая» функция Аккермана и её определение с помощью оператора рекурсии 2-ой ступени (оператора рекурсии по лексико-графически упорядоченному множеству пар натуральных чисел). Диагональная одноместная функция Аккермана как пример одноместной «быстрорастущей» общерекурсивной функции, не являющейся примитивно рекурсивной функцией, теорема Аккермана.
Алгоритмическая разрешимость теорий некоторых классов алгебраических систем. Метод устранения кванторов.
2.1. Арифметика Пресбургера (арифметика сложения натуральных чисел без умножения), арифметика сложения целых чисел с отношением порядка (без умножения). Взаимная интерпретируемость арифметики сложения целых чисел с отношением порядка и арифметики сложения натуральных чисел. Расширение исходной сигнатуры арифметики сложения целых чисел с отношением порядка с помощью добавления счётного множества символов двуместных отношений сравнения по всевозможным натуральным модулям. Теорема Пресбургера об устранимости кванторов в арифметике сложения целых чисел в расширенной сигнатуре. Теорема Пресбургера о разрешимости теории сложения натуральных чисел. [Нижняя оценка (двойная экспонента) сложности разрешающего алгоритма]. Примеры применения теоремы Пресбургера, алгоритм решения задачи целочисленного линейного программирования.
2.2. Теорема Тарского об устранимости кванторов в элементарной теории поля действительных чисел (с доказательством). Алгебраические и полуалгебраические множества в n-мерном пространстве. Связь навешивания квантора существования по переменной и проектирования множества в n-мерном пространстве вдоль координатной прямой, соответствующей квантифицированной переменной.
Примеры применения теоремы Тарского: 1) Разрешающий алгоритм для элементарной теории поля действительных чисел. 2) Алгоритм, решающий проблемы аналитической геометрии n-мерных евклидовых пространств (n = 1, 2, 3,…), формализуемые в элементарной теории поля действительных чисел. 3) Алгоритм, решающий конкурсные задачи с параметрами в элементарной математике, формализуемые в теории поля действительных чисел (на примерах). 4) Алгоритм, решающий задачи оптимизации с «целевым» функционалом и «ресурсными» ограничениями, выразимыми в теории поля действительных чисел.
2.3. Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования и с кванторами второго порядка по всевозможным подмножествам (без доказательства).
Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования и с кванторами второго порядка по всевозможным конечным подмножествам (без доказательства). Интерпретация элементарной теории (теории первого порядка) сложения натуральных чисел в слабой монадической теории второго порядка натуральных чисел с одной функцией следования s и с кванторами второго порядка по всевозможным конечным подмножествам. Следствие о разрешимости элементарной теории сложения натуральных чисел.
2.4.* Примеры применения теоремы Рабина к построению разрешающих алгоритмов: 1) Разрешающий алгоритм Пресбургера для элементарной теории сложения натуральных чисел. 2) Разрешающий алгоритм для элементарной теории класса всех булевых алгебр. 3) Разрешающий алгоритм для монадической теории второго порядка канторового дисконтинуума с кванторами второго порядка по замкнутым подмножествам. 4) Разрешающий алгоритм Ю. Л. Ершова для элементарной теории класса всех булевых алгебр с выделенным простым идеалом (ультрафильтром). 5) Разрешающий алгоритм для элементарной теории класса всех булевых алгебр с выделенной последовательностью идеалов.
2.5.* Поле p-адических чисел. Теорема Ершова Ю.Л. (и, независимо – Акса Дж., Кочена С.) о разрешимости элементарной теории поля p-адических чисел (без доказательства).
Литература
1. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.
2. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – Москва: Мир, 1972.
3. Панкратьев Е.В. Элементы компьютерной алгебры /М.: Интернет-университет информационных технологий; www.intuit.ru – БИНОМ. Лаборатория знаний, www.lbz.ru, 2007. – 247 с.: ил. – (Серия «Основы информатики и математики»).
4. Дэвенпорт Д., Сирэ И.,Турнье Э. Компьютерная алгебра. – Москва: Мир, 1991.
5. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Языки и исчисления. М.: МЦНМО, 2008.
6. Рабин. М. Разрешимые теории. – Справочная книга по математической логике. Часть 3. – Москва: Наука, 1982.
7. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980.
8. Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Вычислимые функции. 2-е изд., исправленное. М.:МЦНМО, 2002.
9. Лавров И. А.,Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов.— М.: Физматлит, 2004.
Примечание
В программу спецкурса могут быть внесены изменения с учётом уровня подготовки и интересов слушателей. Нужные для понимания спецкурса сведения по математической логике и алгебре будут кратко напоминаться по ходу лекций. Доказательства некоторых теорем могут быть предложены слушателям для самостоятельного изучения с последующим обсуждением на спецкурсе или вне рамок спецкурса.
Информация о данном спецкурсе размещена на сайте кафедры МаТИС: https://www.intsys.msu.ru/study/courses/