XIX Белоусов А.И., Ткачев СБ. Дискретная математика (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска)

Математика в техническом университете Выпуск Х1Х Серил удостпоена Премии Правитпельстпва Российской Федерации в областпи науки и тпехники за 2003 вод Комплекс учебников из 21 выпуска Под редакцией В.С. Зарубина и А.П. Крищенко 1. Введение в анализ П. Дифференциальное исчисление функций одного переменного П1. Аналитическая геометрия 1У. Линейная алгебра Ч.

Дифференциальное исчисление функций многих переменных Ч1. Интегральное исчисление функций одного переменного 'ЧП. Кратные и криволинейные интегралы. Элементы теории поля 'ЧП1. Дифференциальные уравнения 1Х. Ряды Х. Теория функций комплексного переменного Х1. Интегральные преобразования и операционное исчисление ХП. Дифференциальные уравнения математической физики ХП1. Приближенные методы математической физики Х1У. Методы оптимизации ХЪ'. Вариационное исчисление и оптимальное управление ХУ1. Теория вероятностей ХУП. Математическая статистика ХУП1. Случайные процессы Х1Х.

Дискретная математика ХХ. Исследование операций ХХ1. Математическое моделирование в технике УДК 512.5+519.1(075.8) ББК 22.174 Б43 Рецемзеигяьк чл.-корр. РАН Ю.Н. Павловский, проф. А.К. Платонов Б43 Белоусов А.И., усачев С.Б. Дискретнаи математика: Учеб. длл вузов / Под ред.

В.С. Зарубина, А.П. Крищенко.— 3-е изд., стереотип. — Мз Изд-во МГТУ им. Н.Э. Баумана, 2004. -744 с. (Сер. Математика в техническом университете; Вып. Х1Х). 18ВН 5-7038-1769-2 (Вып. Х1Х) БВН 5-7038-1270-4 В деватнадцатом выпуске серии „Математика в техническом университете" изжвкены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классическке понятия теории булевых функций, а также основы теории формальных языков, куда включены теории кояечных автоматов, регулярных языков, контекстно-свободных языков и магезинвых автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам.

Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана. Для студентов технических университетов. Может быть полезен преподавателям, аспирантам к инженерам. Ил. 200. Табл.2Т. Библиогр. бб назв. УЛК 512.5+519.ЦОТ5.6) ВВК 22.174 © А.И. Белоусов, С.Б. Ткачев, 2001 © Московский государственный технический университет им. Н.Э. Баумана, 2001 БВг1 5-7038-1769-2 (Вып. Х1Х) 19ВМ 5-7038-1270-4 © Издательство МГТУ им. Н.Э. Баумана, 2001 К 175-летаю МГТУ пм. Н.Э.

Баумана ПРЕДИСЛОВИЕ Предлагаемая читателю книга является девятнадцатым выпуском комплекса учебников „Математика в техническом университете". Она содержит систематическое изложение курса дискретной математики. Развитие классической („ непрерывной" ) математики было обусловлено прежде всего решением задач естествознания, главным образом физики. „Дискретная" же математика развивалась в свюи с изучением законов и правил человеческого мышления, что н обусловило ее применение в тех областях техники, которые так или иначе связаны с моделированием мышления, и в первую очередь в вычислительной технике и программировании.

Мышление реализует себя прежде всего в языке. Поэтому разумно считать, что ядро дискретной математики образует именно математическая теория языков, точнее, область этой теории, называемая теорией формальных юыков. Слово „формальный" подчеркивает, что в этой теории изучаются в основном искусственные языки, специально созданные для каких-то целей: юыки программирования, языки математики и т.п. Теория формальных языков является базой теории кодирования, „криптологии", изучвющей методы защиты информации, теории алгоритмов и в определенном смысле математической логики.

В прикладном аспекте эта теория служит основой разработки математического обеспечения вычислительных машин. Доминирующим в современной теории формальных языков является алгебраический подход, в котором существенно используется аппарат, базирующийся на понятии алгебраической структуры полукольца. Этот аппарат во многом похож на аппарат линейной алгебры. Систематическое изложение теории ПРЕДИСЛОВИЕ формальных языков на базе теории полуколец и является одной из основных задач этой книги. Отметим, что в отечественной учебной литературе такой подход почти не получил отражения. Теория формальных языков существенно опирается и на теорию графов. Многие задачи теории языков (например, задача определения языка конечного или магазинного автомата) сводится к задаче о путях во взвешенных (размеченных) ориентированных графах, где множество меток имеет алгебраическую структуру полукольца. Изложение материала построено следующим образом.

Глава 1 посвящена множествам и отношениям. Здесь напоминаются основы теории множеств, изложенные в первом выпуске комплекта учебников, причем некоторые вопросы излагаются более детально. Основное содержание главы составляет теория отношений. Центральным результатом является теорема о неподвижной точке для индуктивных упорядоченных множеств, на базе которой строятся методы решения задач о путях в графах и алгебраические методы в теории формальных языков.

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

Особенностью изложения является определение булевой алгебры как частного случая полукольца. В главе 4 приведены некоторые результаты общей теории алгебраических систем. Глава 5 посвящена теории графов. Центральное место в главе занимает изложение алгебраического метода решения задач о путях в ориентированных графах, размеченных над полукольцами. Этот материал служит, с одной стороны, иллюстрацией применения алгебраической техники в решении графовых задач, а с другой — основой решения задач в теории формальных языков. Глава содержит также описание некоторых алгоритмов на графах: алгоритма „поиска в глубину" и „поиска в ширину", алгоритма Краскала для отыскания остовного дерева наименьшего веса, алгоритма топологической сортировки.

Коротко рассматриваются изоморфвзм графов, группы автоморфизмов графов и элементы цикломатики (анализа структуры циклов неориентированного графа). Глава 6 посвящена классическому разделу дискретной математики — булевым функциям — и включает вопросы минимизации булевых функций и теорему Поста о функциональной полноте. В главах 7 и 8 изложена теория формальных языков. Глава 7 содержит „линейную часть" этой теории — теорию конечных автоматов и регулярных языков, а глава 8 — теорию контекстно-свободных языков. Это важнейший класс языков, его теоретический анализ является основой многих информационных технологий, таких, в частности, как проектирование компиляторов или разработка лингвистического обеспечения баз данных. Фундаментальным является понятие магазинного автомата — распознавателя в классе контекстно-свободных языков.

Именно эта модель языка служит математической основой конкретных технологий разработки синтаксических анализаторов для языков программирования. В дополнениях к главе 8 приведены элементарные сведения о синтаксическом анализе контекстно-свободных языков и введение в математическую теорию семантики формапьных языков (в частности, языков программирования). Здесь мы пытаемся перекинуть „мостик" от чистой теории к практической технологии анализа контекстно-свободных языков, используемой прежде всего в компиляторах.

Этот материал призван проиллюстрировать связь между изложеной математической теорией и ее приложениями к разработке математического обеспечения компьютеров. В конце каждой главы помещены задачи для самостоятельного решения. Наиболее трудные задачи снабжены указаниями. В некоторых задачах содержатся и теоретические результаты, ПРЕДИСЛОВИЕ дополняющие основной текст. Часть задач придумана авторами, часть заимствована из других задачников и учебников. Дискретная математика — бурно развивающаяся область.

К сожалению, в этом учебнике мы не нашли возможности даже обзорно изложить некоторые результаты, развивающие классическую теорию графов (гиперграфы, сети Петри, потоковые диаграммы) и теорию языков (сверхъязыки, автоматы над структурами, отличными от слов, теорию алгоритмов как динамических систем, топологические методы в семантике). Мы рекомендуем интересующемуся читателю обстоятельно написанную „Наш1Ьоо1с о1 ТЬеогейса1 Сошри1ег Яс1епсе", а также последние выпуски периодического издания „ЬесМге поМв ш СошриФег Яс1епсе".