Кук Д., Бейз Г. - Компьютерная математика

Д. КУК,1'. БЕЙБ КОМПЬЮТЕРНАЯ МАТЕМАТИКА Перевод с впглийского Г. М. КОБЕЛЬКОВА МОСКВА еИАРКАе ГЛАВНАЯ РЕДАКЦИЯ ФИЭИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 199 0 ББК 2218 К89 УДК 519.6 СОМРСТЕВ МАТНЕМАТ1СЯ В. У. СООКЕ АКВ Н. Е. ВЕ2 СашЬг!бне 11пжегвйу Ргеял СашЬП42е т.Окном кете аонк кнш носнньье 'мкьиобккн вупмиу 1602110000-056 К 033402з 90 20-90 18ВЫ 5-02-014216-6 саюьгюяе Пв!тегз!тг © Ргезз, гвве гг з «Натка». Фнзматлвт, перевод ва ртссння язмн, 1тто Кук Д,, Вейв Г, Компьютерняя математика: Пер. с аигл.— Мл Науке, Гл. ред.

физ;мат, лвт,, 1990.— 384 с.— 1ЗВМ 3-02-014216-6. На основе фундаментальных понятий матемвтикн, введенных в начале, матемвтически строго описывается ряд проблем и дается их решение. Иаложевпе, где вто возможно, носит строгий матемвтнческкн характер. Доказательства утверждений проводятся не конструктивном уровне. Деетсв большое количество примеров и унраязпепий, результвты которых, как правило, исподьвуются в дальнейшем. Для студентов, аспирантов п научных работников, аанимаюШихся вопросами компьютерной математики и ее приложениями.

Табл. 28. Ил. 164. ОГЛАВЛЕНИЕ Предисловие Введение 10 10 15 22 24 33 35 36 40 43 46 50 53 62 64 данных 68 68 72 73 83 91 105 О4 141 119 123 125 134 137 139 140 154 172 192 Глава $1. $2. $3. $4. $5. Глава $1. $2. $3. $4. $5. $6. $7. $8. Главе $1, $2. $3. $5, $6. Глава $1, $2. $3. $4. Глава $1, $2. $3. $4. $5.

$6. 1» 1. Мвожества Множества п их спецификация Простейшие операции кад множсстзамп Диаграммы Венва Подмножества и доказательства Произведения мвожеств 2, Отиошеиия Освоввые понятия Графические представлевия Свойства отношений Разбиения в отиошевия екзивалевтностп Отношения порядка Отношения па базах данных и структурах Составные отяошевия Замыкавие отношений 3.

Фупкцпи Фувкции и отображения Обратные функции и отображенпя Мощность множеств я счетвость . Некоторые специальные классы функций Авалитическяе свойства вещестеевных функций Операции 4. Освоввые поияткя арифметики «Малая» копечпая арпфметика «Большая» конечная арифмегпка Двоичная арпфметика . Логическая арифметика 5. Алгебраические структуры Алгебрапческпе структуры п подструктуры . Простейшие операциокные структуры Кольца и поля . Линейная алгебра Решетки и булевы алгебры Замкнутые полукольца 195 202 206 283 298 Главе $1.

$2. $3. Глава $1. $2. $3. $4. $5. $6. Глава $1. $2. $3. $4. $5. В. Матрицы ° ° Матрицы и бинарные отпошеввя па конечных мно- жествах Матрицы иад другими алгебраическими структура- Матрицы и векторвыа пространства 7. Теория графов Вводвые понятия Марпгруты, циклы и связвость Плеварвые графы, Структуры данных для представления графа Обход графа Ориентированные графы 8. Языки и грамматики Оснозпыа повятия Грамматики с фразевой структурой Коитекотио-свободвые языки Попятвя грамматического разбора и грамматиче- ских модификаций .

. . . . . . ° Грамматики операторного предшестзозавия , > 217 217 228 234 238 242 257 257 264 276 Г л а в в 9. Конечные автоматы $1. Общие понятия $2. Конечные автоматы $3. Регулярная алгебра Гл а за 10. Комкьютервая геометрия $1. Системы координат для подмножеств Кт $2. Преобразования $3. Кривые и позерхпости Ппедметпый указатель 302 302 320 344 345 350 370 ° 333 ПРЕДИСЛОВПЕ Вычисления являются точной наукой, и систематическое изучение всех аспектов, включая такно различные области, как разработка баз данных, проверка систем н создание математического обеспечения, с необходимостью вызывает использование математических моделей. С этой точки зрения многие учебные программы по вычислениям в университетах и институтах содержат специальные курсы, знакомящие студентов с соответствующими математическими структурами и методами.

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

Мы особенно хотим поблагодарить наших >кап — Крис и Карис-за постоянную поддержку и понимание в течение всего процесса написании книги. Особо благодаркм Крис Кук за многочисленные часы, которые она провела, помогая нам в соаданни проекта рукописи, Орнеллу Ларднер за аккуратно напечатанный окончательный вариант и Алана Бенсона, который прочитал всю работу и сделал много конструктивных предложений.

Ответственность эа все оставшиеся ошибки и неточности принадлежит исключительно нам. Д. Кук, Г. Бейа ЛаФбаро, 1982 ВВЕДЕНИЕ Книга в основном представляет собой курс лекций по компьютерной математике для университетов и институтов; однако она также может быть полезной для специалистов, работающих в этой области и желающих получить более глубокие знания предмета. Книга содержит материал из тех областей современной математики, которые имеют отношения к вычислениям, и, как следствие, обеспечивает читателя средством для сжатого и точного описания многих проблем компьютерной науки.

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

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

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

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

Фуввцвв з4вслевзы!! ввалив 5. Алгебрвичеенве структуры— ! е. м 10. Кемпьюсерввя геометрия з. языки 7. Теории графов 9. Теервв — + Коз!пвлязоры ввтомвтов -- —-- — ьДиагностика Фермвльвея теория ! ! ! !-ь Искусствеввый вычислений программ ивтеллект Терминология и обозначения обычно строго вводятся в соответствующем месте текста. Однако иногда в примерах мы используем термины, которые раньше не опре- 8 делялись. В таких случаях обычно следует руководствоваться интуицией, а не формальными сообрал|ениями. Так, в одном из случаев в гл.

1 используется термин «конечная машина», в то время как определение дано лишь в гл. 9. В т 5 гл. 3 некоторые свойства действительных чисел используются без доказательства. Например, мы используем неравенство треугольника !я+ у! < ~ !л! +! у!, где ! ° ! обозначает абсолютную величину числа, в некоторых докааательствах, относящихся к пределам. При желании читатель может опустить зги доказательства до прочтения из и. 3.4 гл.

5. Повсюду в книге символ г" будет означать конец определения, примера, доказательства н т. п., а символ ~ — обнаружение логической ошибки, т. е. противоречив. Также по причинам, которые станут ясными в т 5 гл. 1, мы обычно будем использовать для обозначения операции умноженил символ (а не Х), хотя, когда мы будем иметь дело с обычными числами, символ е иногда будет опускаться с целью упрощения записи в больших выражениях, ГЛАЗА МНОЖЕСТВА 5 Е Множества н их спецификация Как уже отмечалось во введении, нам хотелось бы построить математическую теорию достаточно строго, однако при этом возникают некоторые трудности с обоснованием.