Перейти к полному списку специальных курсов кафедры

Спецкурс "Введение в алгоритмическую алгебру"

Годовой спецкурс для студентов 1-5 курсов.

Обновленная программа спецкурса:

1-й семестр.

'Введение в алгоритмическую алгебру. Часть 1'

1. Начальные сведения по теории алгоритмов и теории конечных автоматов.

Слова в алфавите. Словарные функции, детерминированные и ограниченно-детерминированные словарные функции. Конечные автоматы. Диаграмма Мура конечного автомата. Примеры конечных автоматов. Теорема о совпадении класса ограниченно-детерминированных функций с классом автоматных функций. Отображения отрезка [0,1] в себя, задаваемые конечными автоматами.

Машины Тьюринга и частично-рекурсивные функции как варианты формализации понятия алгоритма (вычислимой функции). Нумерация слов алфавита натуральными числами. Понятия n-местной частичной функции. Исходные (базисные) примитивно-рекурсивные функции. Операторы композиции, примитивной рекурсии. Понятие n-местной примитивно-рекурсивной функции (ПРФ). Оператор минимизации. Понятия n-местной частично-рекурсивной функции (ЧРФ), n-местной общерекурсивной функции (ОРФ). Изображение n-местных частично-рекурсивных функций в операторном виде (в виде операторного терма). Простейшие примеры. Изображение операций сложения, умножения, возведения в степень, взятия факториала в операторном виде. Доказательство невозможности универсальной (n+1)-местной примитивно-рекурсивной функции для класса всех n-местных примитивно-рекурсивных функций. Быстрорастущие общерекурсивные функции, диагональная функция Аккермана как пример общерекурсивной функции, не являющейся примитивно-рекурсивной функцией. Протокол успешно завершенного применения n-местной частично-рекурсивной функции к входному n-членному набору натуральных чисел. Нумерация (кодирование) конструктивных объектов словами алфавита, натуральными числами (геделева нумерация). Нумерация (кодирование) натуральными числами протоколов (успешно завершенных) вычислений. Теорема о существовании универсальной (n+1)-местной частично-рекурсивной функции для класса всех n-местных частично-рекурсивных функций (эскиз доказательства). Теорема о невозможности общерекурсивного продолжения универсальной (n+1)-местной частично-рекурсивной функции для класса всех n-местных частично-рекурсивных функций.

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

2. Уравнения в словах в свободном моноиде.

Результат Г. С. Маканина о существовании алгоритма, распознающего разрешимость систем уравнений в словах в свободном моноиде. (Доказательство для случая уравнений в словах с одной неизвестной). Лемма Нильсена о кодировании слов двухбуквенного алфавита унимодулярными матрицами второго порядка с неотрицательными целыми элементами, сведение систем уравнений в словах в двухбуквенном алфавите к соответствующей системе алгебраических уравнений в целых числах с целыми коэффициентами.

3. Метод устранения кванторов. Алгоритмическая разрешимость теорий некоторых классов алгебраических систем.

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

3.2. Теорема Тарского об устранимости кванторов в элементарной теории поля действительных чисел (с усовершенствованным доказательством). Примеры применения теоремы Тарского: 1) Разрешающий алгоритм для элементарной теории поля действительных чисел. 2) Алгоритм, решающий проблемы аналитической геометрии n-мерных евклидовых пространств (n = 1, 2, 3,:), формализуемые в элементарной теории поля действительных чисел. 3) Алгоритм, решающий задачи с параметрами в элементарной математике, формализуемые в теории поля действительных чисел. 4) Алгоритм, решающий задачи оптимизации с 'целевым' функционалом и 'ресурсными' ограничениями, выразимыми в теории поля действительных чисел.

3.3. Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с кванторами второго порядка по всевозможным подмножествам (без доказательства). Примеры применения теоремы Рабина к построению разрешающих алгоритмов: 1) Разрешающий алгоритм Пресбургера для элементарной теории сложения натуральных чисел. 2) Разрешающий алгоритм для элементарной теории класса всех булевых алгебр. 3) Разрешающий алгоритм для монадической теории второго порядка канторового дисконтинуума с кванторами второго порядка по замкнутым подмножествам. 4) Разрешающий алгоритм Ю. Л. Ершова для элементарной теории класса всех булевых алгебр с выделенным простым идеалом (ультрафильтром). 5) Разрешающий алгоритм для элементарной теории класса всех булевых алгебр с выделенной последовательностью идеалов.

3.4. Поле p-адических чисел. Теорема Ю. Л. Ершова о разрешимости элементарной теории поля p-адических чисел (без доказательства).

4. Некоторые результаты о невозможности алгоритмов в алгебре. (Обсуждение результатов, доказательства некоторых утверждений).

Результат Ю. В. Матиясевича о диофантовости перечислимых предикатов на множестве целых чисел и о невозможности алгоритма, распознающего разрешимость систем алгебраических уравнений в целых числах с целыми коэффициентами. (Отрицательное решение 10-ой проблемы Гильберта). Алгоритмическая неразрешимость комбинаторной проблемы Э. Поста. Теорема А. А. Маркова-Э. Поста о существовании полугруппы с конечным числом образующих, конечным числом определяющих соотношений и неразрешимым отношением равенства. Теорема П. С. Новикова о существовании группы с конечным числом образующих, конечным числом определяющих соотношений и неразрешимым отношением равенства.

2-й семестр.

'Введение в алгоритмическую алгебру. Часть 2'

1. Краткое напоминание некоторых понятий и фактов из теории колец.

Аксиомы кольца, главные операции кольца: операция сложения, операция взятия противоположного, операция 'взятия' нуля, операция умножения. Независимость левого и правого закона дистрибутивности. Дополнительные аксиомы: ассоциативность, коммутативность умножения, существование единицы, условие отсутствия делителей нуля. Аксиомы тела, поля. Понятие подкольца кольца. Примеры. Отношения эквивалентности в кольце, согласованные с главными операциями кольца (конгруэнции кольца). Разбиение кольца на классы эквивалентности по конгруэнции кольца, фактор-кольцо кольца по конгруэнции. Идеал кольца как класс нуля кольца для некоторой конгруэнции этого кольца). Теорема о гомоморфизмах колец..

Главные идеалы кольца. Кольцо целых чисел, его подкольца и его идеалы. Кольцо вычетов кольца целых чисел по модулю m (m -целое число). Поле вычетов по простому модулю p (p-простое число). Кольцо многочленов от одной переменной (от множества переменных) над заданным кольцом (коэффициентов). Кольцо квадратных матриц (порядка n) с элементами из заданного кольца.

Неприводимые многочлены от одной переменной с целыми коэффициентами. Лемма Гаусса (о содержании произведения многочленов с целыми коэффициентами). Теорема о равносильности неприводимости многочлена с целыми коэффициентами от одной переменной над Z и над Q. Критерий Эйзенштейна (достаточный признак Эйзенштейна) неприводимости многочлена от одной переменной с целыми коэффициентами и примеры его применения.

Интерполяционный многочлен Лагранжа, его существование и единственность.

2. Алгоритмы разложения на неприводимые множители многочлена от одной переменной с целыми коэффициентами, с коэффициентами из поля вычетов по простому модулю.

Алгоритм Кронекера разложения многочлена с целыми коэффициентами от одной переменной на неприводимые множители.

Неравенство Миньотта о верхней оценке для модулей коэффициентов делителей многочлена с целыми коэффициентами от одной переменной. Алгоритм Берлекэмпа разложения на неприводимые множители многочлена от одной переменной с коэффициентами из поля вычетов по простому модулю. Лемма Гензеля (о продолжении разложения). Алгоритм разложения на неприводимые множители многочлена от одной переменной с целыми коэффициентами.

3*. Базисы Гребнера (стандартные базисы) идеалов кольца многочленов от многих переменных.

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

Мономиальные упорядочения. Лемма об обрыве цепей убывающих мономов. Примеры мономиальных упорядочений: лексикографические упорядочения, градуированные лексикографические упорядочения, градуированные обратные лексикографические упорядочения.

Деление многочлена на систему многочленов с остатком. Трудности, возникающие при делении: неоднозначность, возникающая при вычислении остатка (зависимость остатка от порядка многочленов, необходимость делить младшие члены). Алгоритм деления. Доказательство завершаемости работы алгоритма. Достаточное условие принадлежности многочлена идеалу.

Мономиальные идеалы. Эквивалентные условия принадлежности многочлена мономиальному идеалу. Лемма Диксона.

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

Независимость остатка от деления на базис Гребнера от порядка элементов. Нормальная форма полинома по модулю базиса Гребнера. Критерий принадлежности элемента идеалу. S-полиномы. Критерий, позволяющий проверять, является ли система образующих идеала его базисом Гребнера.

Алгоритм Бухбергера. Минимальный базис Гребнера. Редуцированный базис Гребнера. Единственность редуцированного базиса Гребнера. Применение теории базисов Гребнера к решению полиномиальных уравнений и к задаче нахождения неявного представления аффинного многообразия.

Примечание.

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

В программу спецкурса могут быть внесены изменения с учетом уровня подготовки и интересов слушателей.

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

Информация о данном спецкурсе размещена на сайте кафедры МаТИС: http://www.intsys.msu.ru/

Наверх