Федеральное агентство по образованию

Государственное образовательное учреждение
высшего профессионального образования
Иркутский государcтвенный университет

П Р О Г Р А М М А
вступительного экзамена в аспирантуру по специальности
01.01.06 “Математическая логика, алгебра и теория чисел”

                                                  УТВЕРЖДЕНА

                                     на заседании Ученого совета 
                                                 Института математики и экономики                                                                            
                                        (протокол № 2 от 22.10.2004 г.)
                                       
                                         Председатель Ученого совета 
                                                              _______________Срочко В.А. 

Иркутск – 2004
ПРОГРАММА-МИНИМУМ 
вступительного экзамена в аспирантуру по специальности
01.01.06 “Математическая логика, алгебра и теория чисел”
по физико-математическим наукам
Введение
В основу настоящей программы положены следующие дисциплины: математическая логика; алгебра; теория чисел.
Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по математике и механике при участии Математического института им. В.А. Стеклова РАН и Московского государственного университета им. М.В. Ломоносова.
1. Математическая логика и теория алгоритмов
Понятие алгоритма и его уточнения. Вычислимость по Тьюрингу, частично рекурсивные функции, рекурсивно перечислимые и рекурсивные множества. Тезис Чёрча.
Универсальные вычислимые функции. Существование перечислимого неразрешимого множества. Алгоритмические проблемы.
Построение полугруппы с неразрешимой проблемой распознавания равенства.
Классы P и NP. Полиномиальная сводимость и NP-полные задачи. Теорема об NP-полноте задачи ВЫПОЛНИМОСТЬ.
Логика высказываний. Представимость булевых функций формулами логики высказываний. Конъюнктивные и дизъюнктивные нормальные формы.
Исчисление высказываний. Полнота и непротиворечивость.
Логика предикатов. Приведение формул логики предикатов к предварённой нормальной форме.
Исчисление предикатов. Непротиворечивость. Теорема о дедукции.
* Полнота исчисления предикатов. Теорема Мальцева о компактности.
*Элементарные теории классов алгебраических систем. Категоричные в данной мощности теории. Теорема о полноте теории, не имеющей конечных моделей и категоричной в бесконечной мощности.
Разрешимые теории. Теория плотного линейного порядка.
Формальная арифметика. Теорема о представимости вычислимых функций в формальной арифметике (без доказательства).
*Теорема Гёделя о неполноте формальной арифметики. Теорема Тарского о невыразимости арифметической истинности в арифметике.
*Неразрешимость алгоритмической проблемы выводимости для арифметики и логики предикатов.
*Аксиоматическая теория множеств. Порядковые числа, принцип трансфинитной индукции. Аксиома выбора.
2. Алгебра
Теоремы Силова.
Простота группы An , n ? 5 и SO3.
Теорема о конечно порожденных модулях над евклидовым кольцом и ее следствия для групп и линейных операторов.
Свободные группы и определяющие соотношения.
Алгебраические расширения полей. Теорема о примитивном элементе. Поле разложения многочлена. Основная теорема теории Галуа.
Конечные поля, их подполя и автоморфизмы.
Радикал кольца. Структурная теорема о полупростых кольцах с условием минимальности.
Группа Брауэра. Теорема Фробениуса.
Нетеровы кольца и модули. Теорема Гильберта о базисе.
Алгебры Ли. Простые и разрешимые алгебры. Теорема Ли о разрешимых алгебрах. Теорема Биркгофа-Витта.
*Основы теории представлений. Теорема Машке. Одномерные представления. Соотношения ортогональности.
*Алгебраические системы. Свободные алгебры. Многообразие алгебр. Теорема Биркгофа.
*Решетки. Дедекиндовы решетки. Теорема Стоуна о булевых алгебрах.
3. Теория чисел
Квадратичный закон взаимности.
Первообразные корни и индексы.
Неравенства Чебышева для функции ?(x).
Дзета-функция Римана. Асимптотический закон распределения простых чисел.
Характеры и L-функции. Теорема Дирихле о простых числах в арифметической прогрессии.
Тригонометрические суммы. Модуль гауссовой суммы. Полные тригонометрические суммы и число решений сравнений.
*Критерий Вейля равномерного распределения. Теорема Вейля о последовательности значений многочлена.
Модулярная группа и модулярные функции. Теорема о строении алгебры модулярных форм.
Представление целых чисел унимодулярными квадратичными формами.
Приближение вещественных чисел рациональными дробями. Теорема Лиувилля о приближении алгебраических чисел рациональными дробями. Примеры трансцендентных чисел.
Трансцендентность чисел е и ?.
Основная литература
1.	Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
2.	Ершов Ю.Л., Палютин Е.А. Математическая логика. 2-е изд. М.: Наука, 1987.
3.	Мальцев А.И. Алгоритмы и рекурсивные функции. 2-е изд. М.: Наука, 1986.
4.	Мендельсон Э. Введение в математическую логику. 3-е изд. М.: Наука, 1984.
5.	Новиков П.С. Элементы математической логики. 2-е изд. М.: Наука, 1973.
6.	Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. М.: Наука, 1980.
7.	Ван дер Варден Б.Л. Алгебра. М.: Наука, 1976.
8.	Кострикин А.И. Введение в алгебру. Ч. 3. Основные структуры алгебры. М.: Физматлит, 2000.
9.	Винберг Э.Б. М. Курс алгебры. М.: Факториал Пресс, 2001.
10.	Скорняков Л.А. Элементы общей алгебры. М.: Наука, 1983.
11.	Мальцев А.И. Алгебраические системы. М.: Наука, 1970.
12.	Ленг С. Алгебра. М.: Мир, 1968.
13.	Джекобсон Н. Алгебры Ли. М.: Мир, 1964.
14.	Боревич З.И., Шафаревич И.Р. Теория чисел. М.: Наука, 1985.
15.	Виноградов И.М. Основы теории чисел. М.: Наука, 1981.
16.	Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в теорию чисел. М.: Изд-во МГУ, 1995.
17.	Карацуба А.А. Основы аналитической теории чисел. М.: Наука, 1983.
18.	Кейперс Л., Нидеррейтер Г. Равномерное распределение последовательностей. М.: Наука, 1985.
19.	Коробков Н.М. Тригонометрические суммы и их приложения. М.: Наука, 1989.
20.	Серр Ж.П. Курс арифметики. М.: Мир, 1972.
21.	Чандрасекхаран К. Введение в аналитическую теорию чисел. М.: Мир, 1974.