Часть II. МАТЕМАТИЧЕСКИЕ ОСНОВАНИЯ И ОСНОВНЫЕ АЛГОРИТМЫ

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

В гл. 2 мы рассматриваем основные свойства целых чисел и алгоритмы для работы с ними, в гл. 3 то же самое делается для полиномов. Материал существен для понимания ч. III настоящей книги.

Глава 2. Целые числа

Старейшая область математики — теория чисел, изучение свойств целых (положительных) чисел — оказывается весьма полезной в современном исследовании алгоритмов. Многие известные задачи теории чисел при рассмотрении с алгоритмической точки зрения превращаются в глубокие и притягательные открытые проблемы, причем нерешенной является не проблема вычисления, а проблема быстрейшего вычисления. Кроме того, целые числа очень часто встречаются в различных областях математики, и, изучая алгебру, мы снова сталкиваемся с понятиями, значение которых впервые было замечено в связи с целыми числами; те же понятия позднее оказались полезными в гораздо более общих ситуациях. В этой главе рассматриваются те свойства целых чисел и те алгоритмы, которые нам понадобятся в дальнейшем.

2.1. Основные понятия

Материал этого раздела, без сомнения, знаком читателю. Изложение будет достаточно неформальным (Sims, 1984).

2.1.1. Множества

Алгебраическая система — это множество объектов вместе с набором операций, позволяющих комбинировать эти объекты. Изучаемые нами объекты и операции над ними можно эффективно описывать на языке теории множеств; см. п. 1 раздела «Исторические замечания и литература».

Мы мажем рассматривать множество просто как набор некоторых специфических элементов. Если А — множество их — его элемент, то мы будем писать и читать это как принадлежит А» или — элемент из А»; читается как не принадлежит А». Множество А является подмножеством множества В, или А содержится в В (мы пишем А С В), если каждый элемент из А является элементом из В; другими словами,

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

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

Для часто встречающихся числовых множеств имеются специальные обозначения. Натуральные числа образуют множество целые числа — множество , а рациональные числа составляют множество . Через мы будем обозначать вещественные числа; комплексные числа образуют множество , где Мы имеем цепочку включений совокупности ненулевых элементов соответствующих множеств обозначаются через . Вещественные числа разделяются на положительные, отрицательные и нуль; обозначают совокупности положительных элементов соответствующих множеств.

Над множествами можно выполнять некоторые операции и получать новые множества. Обгединение множеств А и В — это множество или Объединение состоит из элементов, принадлежащих либо А, либо В, либо обоим этим множествам. Пересечение множество Пересечение состоит из общих элементов множеств Разностью называется множество . Декартово (или прямое) произведение — множество — названо так в честь французского математика Р. Декарта (1596-1650). Элементами этого произведения являются пары Наконец, имея множество А, мы можем образовать множество всех его подмножеств Отметим, что А и 0 всегда принадлежат

Множество I называется множеством индексов для семейства множеств если для каждого задано множество -

из семейства F. Если I — множество из элементов, мы часто будем обозначать семейство из различных множеств через . Как и в случае двух множеств, можно рассматривать объединение и пересечение семейства множеств, для некоторого для всех». Для семейства из множеств декартово произведение определяется как

Элементами произведения являются строки длины . Если -кратное произведение обозначается кратко через

Определение 2.1.1. Разбиением множества S называется множество его подмножеств, такое, что:

b. Если , то либо либо

Каждый элемент множества S принадлежит некоторому элементу множества

Иначе говоря, разбиение множества S — это семейство его непустых подмножеств, таких, что каждый элемент из S принадлежит в точности одному подмножеству из этого семейства. Элементы разбиения называются блоками. Например, { {1,2,3}, {4,5,6} } — разбиение множества {1,2,3,4,5,6} на два блока. Подмножество R множества S называется множеством представителей для разбиения если R содержит по одному элементу из каждого блока .

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

Предложение 2.1.2. Для множеств А, В, С выполняется равенство

Доказательство. Докажем половину утверждения, а именно включение . Пусть . Тогда или . Если , то . Если , то . В любом случае принадлежит объединению . Доказательство обратного включения оставим читателю в качестве упражнения.