Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
§ 3. Постановка задачи в геометрической форме ? . 307
§ 4. Сокращенная д. п. ф..........................312
§ 5. Тупиковость на основе геометрических представлений. Методы построения тупиковых д. н. ф. . . 316
§ 6. Некоторые однозначно получаемые д. н. ф. . 324
§ 7. Понятие локального алгоритма.................331
Глава 2. Синтез схем из функциональных элементов . , 336
§ 1. Понятие схемы из функциональных элементов . 336
§ 2. Проблема синтеза схем из Ф. Э......................345
§ 3. Элементарные методы синтеза.........................351
§ 4. Нижняя оценка для Ь{п)..............................355
| 5. Оптимальный по порядку метод синтеза схем из
Ф. Э. (метод Шеннона)................................357
§ 6. Асимптотически наилучшип метод синтеза схем из
Ф. Э. (метод Лупанова) ........ 361
§ 7. Синтез сумматора....................................364
§ 8. Синтез схем из Ф. Э,, реализующих симметрические
функции..............................................366
Список литературы............................................370
Предметный указатель.........................................373
Указатель обозначений ..................................... 381
ПРЕДИСЛОВИЕ
Дискретная математика — часть математики, которая зародилась в глубокой древности. Как говорит само заглавие, главной ее спецификой является дискретность, т. е. антипод непрерывности. В широком смысле дискретная математика включает в себя и такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика и ряд разделов, которые наиболее интенсивно стали развиваться в середине этого века в связи с внедрением ЭВМ. Научно-технический прогресс поставил проблему изучения сложных управляющих систем. В узком смысле дискретная математика ограничивается только этими новыми разделами. Именно так это понимается и в данной книге. К упомянутым новым разделам мы относим: теорию функциональных систем; теорию графов и сетей; теорию кодирования; комбинаторный анализ; целочисленное программирование и т. п.
Дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования. Книга содержит материал, соответствующий двум типам программ курса «Дискретная математика»: стандартной программе для факультетов прикладной математики и кибернетики большинства университетов и программе соответствующего курса, читаемого в МГУ. Эти программы не ставят целью дать большое количество материала фактического и имеющего спрос в данное время. Чрезмерная детализация и привязывание программы к специальным фактам опасны тем, что лет через 10—15 (а это как раз время активной деятельности обучаемых сейчас студентов) появятся новые факты, а старые частично утратят свою значимость. Ввиду этого главная задача курса — это обучение методам и мышлению, характерным для дискретной математики. Материал, вошедший в эту книгу, знакомит читателя с узловыми задачами из нескольких раз-
ПРЕДИСЛОВИЕ
7
делов дискретной математики и ее приложений. Он подобран таким образом, чтобы сократить число необходимых понятий до минимума и, с другой стороны, дать небольшое количество (10—15) серьезных теорем с непохожими доказательствами, а также познакомить с применениями понятия алгоритма, владение которым особенно важно для специалистов в области прикладной математики.
В основу данной книги положен курс, который впервые был прочитан автором на механико-математическом факультете МГУ в 1964 г.
Книга состоит из пяти частей.
I часть. Функциональные системы с операциями.
II 'часть. Комбинаторный анализ.
III часть. Графы и сети.
IV часть. Теория кодирования.
V часть. Некоторые приложения к кибернетике.
Таким образом, содержание книги охватывает почти все основные разделы дискретной математики. При ее написании автору пришлось усовершенствовать целый ряд доказательств, в ряде случаев дать новые доказательства, которые публикуются здесь впервые.
Изложение многих вопросов из перечисленных разделов не всегда ведется па абстрактной основе: здесь широко используется геометрический язык и содержательные интерпретации. Это позволяет сочетать в построениях наглядность и известную строгость. Надо иметь в виду, что в математических статьях существуют две крайности: пренебрежение строгостью изложения и доведение строгости до абсурда. Обе указанные тенденции одинаково опасны. Строгость изложения должна соответствовать рассматриваемой задаче (и уровню аудитории), подобно тому как в приближенных вычислениях число значащих цифр получаемых результатов должно соответствовать точности исходных данных. Слишком «большой» занас строгости в этом смысле подобен вычислениям со значительным числом дополнительных разрядов.
Данная книга рассчитана на студентов, аспирантов и научных сотрудников.
При пользовапии материалом, изложенным в книге, надо иметь в виду, что содержание частей I, III, IV соответствует программе курса «Введение в дискретную математику» для студентов МГУ. Для изучения дискретной
8
ПРЕДИСЛОВИЕ
математики по типовой программе факультетов прикладной математики университетов части I, III, IV следует брать в сокращенном варианте, но к ним добавляется часть V. Эти сокращения состоят примерно в следующем: исключается гл. 2 (часть I), кроме § 1; в гл. 3 (часть I) опускается материал до канонических уравнений; в гл. 4 (часть I) исключается последний параграф; в гл. 2 (часть III) опускается теорема о числе сетей. Некоторый вспомогательный материал можно найти в части II.
