Д. КУК, Г. БЕЙЗ

КОМПЬЮТЕРНАЯ

МАТЕМАТИКА

Перевод с английского Г. М. КОБЕЛЬКОВА

МОСКВА «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ

ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

1990

ББК 22.18

К89

УДК 519.6

Кук Д., Бейз Г. Компьютерная математика: Пер. с англ.— М.: Наука, Гл. ред. физ.-мат. лит., 1990.— 384 с— ISBN 5-02-014216-6.

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

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

Табл. 28. Ил. 164.

Оглавление

ПРЕДИСЛОВИЕ 7

ВВЕДЕНИЕ 8

ГЛАВА 1. МНОЖЕСТВА 11

§ 1. Множества н их спецификация 11

§ 2. Простейшие операции над множествами 17

§ 3. Диаграммы Венна 24

§ 4. Подмножества и доказательства 27

§ 5. Произведения множеств 36

ГЛАВА 2. ОТНОШЕНИЯ 39

§ 1. Основные понятия 40

§ 2. Графические представления 44

§ 3. Свойства отношений 48

§ 4. Разбиения и отношения эквивалентности 50

§ 5. Отношения порядка 54

§ 6. Отношения на базах данных и структурах данных 57

§ 7. Составные отношения 65

§ 8. Замыкание отношений 68

ГЛАВА 3. Функции 71

§ 1. Функции и отображения 71

§ 2. Обратные функции и отображения 75

§ 3. Мощность множеств и счетность 76

§ 4. Некоторые специальные классы функций 86

§ 5. Аналитические свойства вещественных функций 95

§ 6. Операции 110

ГЛАВА 4. ОСНОВНЫЕ ПОНЯТИЯ АРИФМЕТИКИ 120

§ 1. «Малая» конечная арифметика 120

§ 2. «Большая» конечная арифметика 125

§ 3. Двоичная арифметика 131

§ 4. Логическая арифметика 137

ГЛАВА 5. АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ 141

§ 1. Алгебраические структуры и подструктуры 142

§ 2. Простейшие операционные структуры 145

§ 3. Кольца и поля 148

§ 4. Линейная алгебра 160

§ 5. Решетка и булевы алгебры 180

§ 6. Замкнутые полукольца 202

ГЛАВА 6. МАТРИЦЫ 205

§ 1. Матрицы и бинарные отношения на конечных множествах 205

§ 2. Матрицы над другими алгебраическими структурами 212

§ 3. Матрицы и векторные пространства 216

Глава 7. Теория графов 227

§ 1. Вводные понятия 227

§ 2. Маршруты, циклы и связанность. 236

§ 3. Планарные графы 241

§ 4. Структуры данных для представления графа 248

§ 5. Обход графа 252

§ 6. Ориентированные графы 257

ГЛАВА 8. ЯЗЫКИ И ГРАММАТИКИ 273

§ 1. Основные понятия 273

§ 2. Грамматики с фразовой структурой 281

§ 3. Контекстно-свободные языки 292

§ 4. Понятия грамматического разбора и грамматических модификаций 298

§ 5. Грамматики операторного предшествования 314

ГЛАВА 9. КОНЕЧНЫЕ АВТОМАТЫ 318

§ 1. Общие понятия 319

§ 2. Конечные автоматы 337

§ 3. Регулярная алгебра 349

ГЛАВА 10.КОМПЬЮТЕРНАЯ ГЕОМЕТРИЯ 358

§ 1. Системы координат для подмножеств R³ 360

§ 2. Преобразования 366

§ 3. Кривые и поверхности 387

Предисловие

Вычисления являются точной наукой, и си­стематическое изучение всех аспектов, включая такие различные области, как разработка баз данных, проверка систем и создание матема­тического обеспечения, с необходимостью вы­зывает использование математических моделей. С этой точки зрения многие учебные програм­мы по вычислениям в университетах и инсти­тутах содержат специальные курсы, знакомя­щие студентов с соответствующими математи­ческими структурами и методами. Содержание этой книги является таким курсом и занимает примерно 100 лекционных часов; курс читался студентам факультета компьютерных наук Технологического университета в Лафбаро. Ма­териал книги соответствует первым двум го­дам обучения. Лекции первого года посещают все студенты. Курс лекций второго года явля­ется необязательным; он обеспечивает основу для курсов, читающихся на последнем году обучения. Содержание книги совершенствова­лось в течение ряда лет. В течение этого вре­мени мы ощущали помощь многих из окружа­ющих нас людей, включая многочисленных коллег (как в Лафбаро, так и в других ме­стах) и студентов, которые помогали при подготовке по проверке материала. Мы особенно хотим поблагодарить наших жен – Крис и Кэрис – за постоянную поддержку и понимание в течение всего процесса написания книги. Осо­бо благодарим Крис Кук за многочисленные часы, которые она провела, помогая нам в со­здании проекта рукописи, Орнеллу Ларднер за аккуратно напечатанный окончательный вари­ант и Алана Бенсона, который прочитал всю работу и сделал много конструктивных предло­жений. Ответственность за все оставшиеся ошибки и неточности принадлежит исключи­тельно нам.

Д. Кук, Г. Бейз

Лафбаро, 1982

Введение

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

Книга содержит материал из тех областей современ­ной математики, которые имеют отношения к вычисле­ниям, и, как следствие, обеспечивает читателя средством для сжатого и точного описания многих проблем компью­терной науки. Несмотря на нашу приверженность изла­гать материал, непосредственно относящийся к компью­терной науке, в книге сделана попытка дать его разумное и строгое представление, приемлемое с математической точки зрения. Изложение по возможности носит конструк­тивный характер. Везде, где возможно, в каждой новой теме используются понятия и термины из предыдущих тем; материал сопровождается многочисленными упраж­нениями и примерами. Следует подчеркнуть, что разбор примеров и решение упражнений являются составной ча­стью изучения предлагаемого материала.

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

Множества обсуждаются в гл. 1 и используются да­лее во всей книге. Главы 2, 3 и 5—7 образуют основу строгого обсуждения многих разделов компьютерной ма­тематики; материал этих глав выбран таким образом, что­бы его можно было широко использовать. В гл. 4 описы­вается математическая модель арифметической системы, используемой в цифровых компьютерах при работе с це­лыми числами. Главы 8—10 связывают математическую теорию из предыдущих глав с разделами компьютерной математики. В частности, здесь выделены такие области, как теория языков, теория автоматов и компьютерная геометрия. Эти темы отражают одновременно и интере­сы авторов, и их желание изложить важные разделы современной математики, представляющие общий инте­рес, а не только прикладной. Другие области, где может применяться излагаемый в книге материал, включают в себя базы данных, сети, программную проверку и чис­ленный анализ. Главы 8—10 являются исходными для дальнейшего изучения таких тем, как компиляция, си­стемы моделирования, теория вычислений, компьютерная графика, вычислительная геометрия и автоматическое проектирование. Логические внутренние связи между гла­вами и другими изучаемыми областями показаны на сле­дующей диаграмме:

Терминология и обозначения обычно строго вводятся в соответствующем месте текста. Однако иногда в при­мерах мы используем термины, которые раньше не опре­делились. В таких случаях обычно следует руководство­ваться интуицией, а не формальными соображениями. Так, в одном из случаев в гл. 1 используется термин «конечная машина», в то время как определение дано лишь в гл. 9. В § 5 гл. 3 некоторые свойства действи­тельных чисел используются без доказательства. Напри­мер, мы используем неравенство треугольника , где обозначает абсолютную величину числа, в некоторых доказательствах, относящихся к пре­делам. При желании читатель может опустить эти дока­зательства до прочтения из п. 3.4 гл. 5. Повсюду в книге символ // будет означать конец определения, примера, доказательства и т. п., а символ # — обнаружение логи­ческой ошибки, т. е. противоречие. Также по причинам, которые станут ясными в § 5 гл. 1, мы обычно будем ис­пользовать для обозначения операции умножения символ * (а не Х), хотя, когда мы будем иметь дело с обычными числами, символ * иногда будет опускаться с целью упрощения записи в больших выражениях.