Краткий конспект курса высшей алгебры

Числа
Натуральные числа. Принцип математической индукции. Свойства операций сложения и умножения натуральных чисел. Кольцо целых чисел. Поля рациональных и вещественных (действительных) чисел. Аксиомы поля. Поле комплексных чисел: определение; свойства мнимой единицы, вещественной и мнимой частей комплексного числа, сопряженного комплексного числа, модуля и аргумента комплексного числа. Умножение комплексных чисел в тригонометрической форме. Формулы Муавра для решения уравнения xn = a в поле комплексных чисел.

Векторные пространства
Векторное пространство строк, его свойства. Аксиомы абстрактного векторного пространства. Линейная комбинация и оболочка набора векторов, тривиальная и нетривиальная линейные комбинации, линейная зависимость векторов и линейная выразимость наборов векторов, эквивалентные наборы: связи между этими понятиями. Элементарные преобразования наборов. База и ранг наборов векторов и оболочек. Конечномерное векторное пространство: база, координатная строка, связь с пространством строк. Подпространство: включение базы подпространства в базу пространства, сумма и пересечение подпространств, связь между их размерностями. Прямая сумма подпространств. Внешняя прямая сумма пространств. Фактор-пространство. Матрица набора векторов. Элементарные преобразования матриц. Алгоритм Гаусса приведения матрицы к ступенчатому виду. Линейное отображение (оператор): определение; образ, ядро, ранг и дефект, связь между ними. Сложение, умножение линейных отображений и умножение отображения на скаляр: свойства этих операций. Матрица линейного отображения, операции над матрицами. Строчный ранг и дефект матрицы.

Матрицы и определители.
Сложение и умножение матриц. Кольцо квадратных матриц над полем: проверка аксиом, разложение матрицы в произведение элементарных и диагональной матриц. Определитель, его поведение при простейших преобразованиях строк. Определитель произведения матриц. Транспонирование матриц. Определитель транспонированной матрицы. Разложение определителя по произвольной строке и произвольному столбцу. Обратная матрица: существование, вычисление. Матрица перехода от одной базы векторного пространства к другой, ее невырожденность. Изменение координат при изменении базы. Ранг матрицы: теорема о ранге. Ранг суммы и произведения матриц.

Системы линейных уравнений
Система линейных уравнений над полем. Решение системы. Векторная и матричная форма записи системы. Матрица и расширенная матрицы системы. Системы линейных уравнений с обратимой матрицей. Эквивалентность систем линейных уравнений. Метод Гаусса. Критерий совместности системы. Общее решение системы, число свободных неизвестных. Фундаментальный набор решений однородной системы. Связь между общими решениями однородной и неоднородной систем. Системы линейных уравнений с точки зрения линейных отображений. Теоремы Фредгольма.

Полиномы
Полиномы над кольцом. Кольцо полиномов. Деление с остатком. Делители полинома. Наибольший общий делитель двух полиномов: существование и вычисление (алгоритм Евклида). Взаимно простые полиномы. Неразложимые полиномы, разложение полинома в произведение неразложимых. Корни и значения. Теорема Безу. Производная. Кратные корни. Формула Тейлора. Интерполяционные полиномы Лагранжа и Лагранжа — Сильвестра. Существование корня полинома в расширении поля. Разложение полинома в произведение линейных множителей. Формулы Виета. Полиномы от нескольких неизвестных. Симметрические полиномы, их выражение через основные симметрические полиномы. Алгебраическая замкнутость поля комплексных чисел. Неразложимые полиномы над полями комплексных и вещественных чисел. Связь между разложимостью полиномов над полем рациональных чисел и над кольцом целых чисел. Алгоритмическая разрешимость вопроса о разложимости полинома над Z. Признак неразложимости полинома над Z (признак Эйзенштейна).

Линейные преобразования векторных пространств
Определение линейного преобразования. Матрица линейного преобразования. Координаты образа. Связь между алгеброй линейных преобразований и алгеброй матриц. Связь между матрицами линейного преобразования в разных базах. Подобие матриц. Образ, ядро, ранг и дефект линейного преобразования. Невырожденные преобразования. Инвариантное подпространство и ограничение линейного преобразования на инвариантном подпространстве. Собственные векторы, собственные значения, характеристические корни. Значения полинома от матрицы и от линейного преобразования. Теорема Гамильтона — Кели.

Жорданова база для линейного преобразования
Ядерные и корневые разложения пространства. Нильпотентное преобразование: ниль-слой, жорданов набор, жорданова таблица и ее элементарные преобразования, существование жордановой базы, жорданова матрица, связь числа ее жордановых клеток и их размерностей с рангами степеней нильпотентного пробразования. Жорданова база для произвольного преобразования. Матричная форма теоремы Жордана.

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

Линейные преобразования евклидовых и унитарных пространств
Скалярное произведение. Евклидовы и унитарные пространства: ортогональные наборы векторов, процесс ортогонализации, существование ортонормированной базы, скалярное произведение в ортонормированной базе. Ортогональное дополнение к подпространству, его свойства. Сопряженное линейное преобразование, сопряженная матрица и их свойства. Нормальные преобразования и матрицы: свойства собственных векторов, канонический вид матрицы нормального преобразования. Ортогональные и унитарные преобразования. Канонический вид их матриц. Унитарность матрицы перехода от одной ортонормированной базы к другой. Самосопряженные преобразования и эрмитовы матрицы, свойство их характеристических корней, канонический вид. Неотрицательные преобразования, существование неотрицательного квадратного корня из неотрицательного преобразования. Сингулярные числа. Полярное разложение линейных преобразований и матриц.

Квадратичные формы
Матрица квадратичной формы, ее изменение при линейной замене переменных. Алгоритм Лагранжа приведения квадратичной формы к диагональному виду. Приведение вещественной квадратичной формы к главным осям. Закон инерции вещественной квадратичной формы. Положительно определенные квадратичные формы: определение, критерий положительной определенности в терминах значений и главных определителей. Одновременная диагонализация двух форм.

Подстановки
Группа подстановок. Циклы, независимые циклы, разложение подстановки в произведение независимых циклов. Декремент подстановки. Четность подстановки. Разложение подстановки в произведение транспозиций, связь с четностью подстановки. Знак подстановки, его мультипликативность. Явная формула для определителя матрицы.

Парадоксы теории множеств

Парадоксами теории множеств называют
рассуждения, демонстрирующие противоречивость наивной теории множеств, такие как
парадокс Бурали-Форти (1897)
парадокс Кантора (1899)
парадокс Рассела (1905)
рассуждения, результат которых интуитивно кажется ложным или «парадоксальным», но которые, тем не менее, являются следствием аксиом формальной теории множеств, включая:
предложенный Б. Расселом «парадокс Тристрама Шенди», демонстрирующий нарушение принципа «часть меньше целого» для бесконечных множеств,
нетривиальные следствия аксиомы выбора:
парадокс Банаха — Тарского,
парадокс Хаусдорфа;
особое место занимает парадокс Сколема, представляющий собой ошибочное рассуждение, которое может быть допущено неспециалистом при применении теоремы Лёвенгейма — Сколема к аксиоматической теории множеств.

Аксиоматика теории множеств

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

Система аксиом Цермело—Френкеля (ZF) является стандартной системой аксиом для теории множеств. Эта и подобные ей системы аксиом любопытны потому, что любая математическая теория может быть «переведена» на язык теории множеств таким образом, что теоремы этой теории станут теоремами о множествах, доказуемыми из аксиом ZF (любой объект можно считать множеством, соответственно и переформулировать утверждение не представляет собой проблему[источник не указан 316 дней]).

К этой системе аксиом часто добавляют аксиому выбора, и называют системой Цермело — Френкеля с аксиомой выбора (ZFC).

Эта система аксиом записана на языке логики первого порядка, и содержит бесконечное количество аксиом. Существуют и другие, конечные системы. Например, система NBG (von Neumann — Bernays — Godel) наряду с множествами рассматривает так называемые классы объектов. NBG равносильна ZF в том смысле, что любая теорема о множествах (то есть не упоминающая о классах), доказуемая в одной системе, также доказуема и в другой.

Классы сложности

В рамках классической теории осуществляется классификация задач по классам сложности (P-сложные, NP-сложные, экспоненциально сложные и др.). К классу P относятся задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга), а к классу NP — задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими. Работу такой машины можно представить как разветвляющийся на каждой неоднозначности процесс: задача считается решённой, если хотя бы одна ветвь процесса пришла к ответу. Другое определение класса NP: к классу NP относятся задачи, решение которых с помощью дополнительной информации полиномиальной длины, данной нам свыше, мы можем проверить за полиномиальное время. В частности, к классу NP относятся все задачи, решение которых можно проверить за полиномиальное время. Класс P содержится в классе NP. Классическим примером NP-задачи является задача о коммивояжёре.

Поскольку класс P содержится в классе NP, принадлежность той или иной задачи к классу NP зачастую отражает наше текущее представление о способах решения данной задачи и носит неокончательный характер. В общем случае нет оснований полагать, что для той или иной NP-задачи не может быть найдено P-решение. Вопрос о возможной эквивалентности классов P и NP (то есть о возможности нахождения P-решения для любой NP-задачи) считается многими одним из основных вопросов современной теории сложности алгоритмов. Ответ на этот вопрос не найден до сих пор. Сама постановка вопроса об эквивалентности классов P и NP возможна благодаря введению понятия NP-полных задач. NP-полные задачи составляют подмножество NP-задач и отличаются тем свойством, что все NP-задачи могут быть тем или иным способом сведены к ним. Из этого следует, что если для NP-полной задачи будет найдено P-решение, то P-решение будет найдено для всех задач класса NP. Примером NP-полной задачи является задача о конъюнктивной форме

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

Современное состояние теории алгоритмов

В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям.
Классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности (P, NP и др.).
Теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. Асимптотический анализ позволяет оценить рост потребности алгоритма в ресурсах (например, времени выполнения) с увеличением объема входных данных.
Теория практического анализа вычислительных алгоритмов решает задачи получения явных функции трудоёмкости, интервального анализа функций, поиска практических критериев качества алгоритмов, разработки методики выбора рациональных алгоритмов.

Возникновение теории алгоритмов

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

Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое А. А. Марковым понятие нормального алгоритма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.

Следует отметить также немалый вклад в теорию алгоритмов, сделанный Д. Кнутом, A. Ахо и Дж. Ульманом. Одной из лучших работ на эту тему является книга «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза И. Лейзерсона, Рональда Л. Ривеста, Клиффорда Штайна.

Теория графов

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V?V.

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

Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.

Исторический очерк

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

Впервые, насколько можно судить по дошедшим до нас древним сочинениям, развитая алгебраическая система появляется в «Арифметике» Диофанта (IV век). Вряд ли можно сомневаться, что у него были предшественники, как они имелись у Евклида, Архимеда и других, однако мы ничего не знаем ни о людях, ни о трудах, на которые мог опираться этот замечательный алгебраист. Да и последователей у него не было до XV века. Впрочем, в Европе с переводом «Арифметики» познакомились только в XVI веке, и методы Диофанта оказали огромное влияние на Виета и Ферма.

Основная проблематика «Арифметики» — нахождение рациональных решений неопределённых уравнений (многочленов произвольной степени) с рациональными коэффициентами. У Диофанта используется буквенная символика, правда, по-прежнему только для неизвестных. Во введении к «Арифметике» Диофант принимает следующие обозначения: неизвестную он называет «числом» и обозначает буквой ?, квадрат неизвестной — символом ?? и т. д. Особые символы обозначали отрицательные степени, знак равенства и даже, похоже, отрицательные числа (есть даже правило знаков: минус на минус даёт плюс). Всё прочее выражается словесно. Сформулированы многие привычные нам правила алгебры: смена знака при переносе в другую часть уравнения, сокращение общих членов и др.

Индийские математики средневековья тоже далеко продвинулись в алгебре; их символика богаче, чем у Диофанта, хотя несколько громоздка (засорена словами).

В Европе, в книгах «Арифметика» и «О данных числах» Иордана Неморария (XIII век) усматриваются зачатки символической алгебры, до поры до времени не отделившейся от геометрии. У него, а также у Фибоначчи уже встречаются выражения вроде «a лошадей за f дней съедают e мер овса». Однако в общую концепцию изложения символизм у них ещё не включён.

Крупнейший алгебраист XV века Лука Пачоли вводит свой аналог алгебраической символики, ещё не слишком общий и не слишком удобный.

Концептуальную реформу и коренные улучшения алгебраического языка ввёл в конце XVI века Франсуа Виет, адвокат по профессии, математик по склонности души. Он чётко представлял себе конечную цель — разработку «нового исчисления», своего рода обобщённой арифметики. Виет обозначал буквами все коэффициенты (кстати, именно Виет придумал этот термин). Все задачи решаются в общем виде, и только потом приводится числовые примеры. Виет свободно применяет алгебраические преобразования, замену переменных и другие алгебраические приёмы.

Система Виета вызвала всеобщее восхищение. Она позволила описать законы арифметики и алгоритмы с немыслимыми ранее общностью и компактностью, облегчила и углубила исследование общих числовых законов. Однако символика Виета была непохожа на современную, местами громоздка, и учёные разных стран приступили к её совершенствованию.

Англичанин Томас Хэрриот в своём посмертно изданном (1631) труде уже очень близок к современной символике: он обозначает переменные строчными буквами, а не заглавными, как у Виета, использует знак равенства, а также придуманные им символы сравнения «>» и «<». Практически современный вид алгебраической символике придал Рене Декарт (середина XVII века, трактат «Геометрия»). Итогом и завершением этого процесса стала «Универсальная арифметика» Ньютона. Некоторые оставшиеся тонкости уточнил Эйлер.

Аксиоматическая теория множеств

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

После обнаружения антиномии Рассела часть математиков (например, Л. Э. Я. Брауэр и его школа) решила полностью отказаться от использования теоретико-множественных представлений. Другая же часть математиков, возглавленная Д. Гильбертом, предприняла ряд попыток строго обосновать ту часть теоретико-множественных представлений, которая казалась им наиболее ответственной за возникновение антиномий, на основе заведомо надёжной финитной математики. С этой целью были разработаны различные аксиоматизации теории множеств.

Особенностью аксиоматического подхода является отказ от лежащего в основе программы Кантора представления о действительном существовании множеств в некотором идеальном мире. В рамках аксиоматических теорий множества «существуют» исключительно формальным образом, и их «свойства» могут существенно зависеть от выбора аксиоматики. Этот факт всегда являлся мишенью для критики со стороны тех математиков, которые не соглашались (как на том настаивал Гильберт) признать математику лишённой всякого содержания игрой в символы. В частности, Н. Н. Лузин писал, что «мощность континуума, если только мыслить его как множество точек, есть единая некая реальность», место которой в ряду кардинальных чисел не может зависеть от того, признаётся ли в качестве аксиомы континуум-гипотеза, или же её отрицание.

В настоящее время наиболее распространённой аксиоматической теорией множеств является ZFC — теория Цермело — Френкеля с аксиомой выбора. Вопрос о непротиворечивости этой теории (а тем более — о существовании модели для неё) остаётся нерешённым.

Не всеми математикам аксиома выбора принимается безоговорочно. Так, например Эмиль Борель и Анри Лебег считают, что доказательства, полученные при помощи этой аксиомы, имеют другую познавательную ценность, чем доказательства, независимые от неё. Другие же математики, такие как Феликс Хаусдорф и Адольф Френкель, принимают аксиому выбора безоговорочно, признавая за ней ту же степень очевидности, что и за другими аксиомами Цермело — Френкеля.