URSS.ru Магазин научной книги
Обложка Деза Е.И., Модель Д.Л. Основы дискретной математики: Теория графов. Комбинаторика. Рекуррентные соотношения. Производящие функции Обложка Деза Е.И., Модель Д.Л. Основы дискретной математики: Теория графов. Комбинаторика. Рекуррентные соотношения. Производящие функции
Id: 312168
579 р.

ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ:
Теория графов. Комбинаторика. Рекуррентные соотношения. Производящие функции. Изд. 4, доп.

Основы дискретной математики: Теория графов. Комбинаторика. Рекуррентные соотношения. Производящие функции URSS. 2024. 252 с. ISBN 978-5-9519-4728-4.
Типографская бумага

Аннотация

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


Содержание
top
Введение6
Глава 1. Графы и их применения9
1.1. Основные понятия11
1.2. Степени вершин графа13
1.3. Операции над графами16
1.3.1. Взятие подграфа16
1.3.2. Взятие дополнения17
1.3.3. Уничтожение ребра18
1.3.4. Уничтожение вершины18
1.4. Полный граф и пустой граф19
1.5. Путь, цикл20
1.6. Связный граф22
1.7. Деревья25
1.8. Регулярные графы29
1.9. Двудольные графы30
1.10. Графы и матрицы32
1.10.1. Матрица смежности32
1.10.2. Матрица принадлежности35
1.10.3. Матрица расстояний36
1.10.4. Матрица достижимости38
1.11. Плоские графы39
1.11.1. Основные понятия39
1.11.2. Вершины, ребра и грани плоского графа. Формула Эйлера40
1.11.3. Графы К5 и К3,343
1.11.4. Теорема Понтрягина—Куратовского43
1.11.5. Раскраска плоских графов44
1.12. Эйлеровы графы48
1.13. Гамильтоновы графы50
Глава 2. Комбинаторика и рекуррентные соотношения55
2.1. Основные комбинаторные соединения58
2.2. Рекуррентные соотношения63
2.3. Решение рекуррентных соотношений69
2.4. Деление многочленов и рекуррентные соотношения75
2.5. Производящие функции78
2.6. Рекуррентные соотношения и конечные суммы86
2.6.1. Сумма первых п натуральных чисел86
2.6.2. Сумма п первых членов арифметической прогрессии87
2.6.3. Сумма п первых членов геометрической прогрессии88
2.6.4. Сумма первых п квадратов натуральных чисел89
2.6.5. Сумма первых п кубов натуральных чисел90
2.6.6. Сумма первых п чисел Фибоначчи92
2.7. Некоторые методы суммирования95
2.7.1. Простейший способ суммирования95
2.7.2. Преобразование Абеля (суммирование по частям)95
2.8. Асимптотические методы суммирования99
2.8.1. Суммирование и производящие функции99
2.8.2. Асимптотические формулы100
Глава 3. Задачи105
3.1. Элементы теории графов106
3.1.1. Определение графа. Граф как бинарное отношение106
3.1.2. Степени вершин графа108
3.1.3. Операции над графами111
3.1.4. Изоморфные графы117
3.1.5. Классические графы. Путь, цикл, связный граф121
3.1.6. Деревья123
3.1.7. Регулярные графы128
3.1.8. Двудольные графы129
3.1.9. Графы и матрицы131
3.1.10. Плоские графы134
3.1.11. Эйлеровы и Гамильтоновы графы140
3.2. Комбинаторика146
3.2.1. Комбинаторные соединения. Правило сложения и умножения146
3.2.2. Размещения с ограничениями153
3.2.3. Разбиение на группы157
3.2.4. Решение неопределенных уравнений161
3.2.5. Метод включений и исключений167
3.2.6. Бином Ньютона и полиномиальная теорема173
3.2.7. Основные комбинаторные тождества175
3.3. Рекуррентные соотношения178
3.3.1. Числа Фибоначчи179
3.3.2. Треугольник Паскаля182
3.3.3. Решение рекуррентных соотношений188
3.3.4. Конечные суммы191
3.4. Контрольные работы200
3.4.1. Контрольная работа по теме «Графы»200
3.4.2. Лабораторная работа по комбинаторике203
3.4.3. Контрольная работа по теме «Комбинаторика»212
3.4.4. Контрольная работа по теме «Рекуррентные соотношения»215
Литература218
Дополнение к четвертому изданию219
Глава 4. Специальные числа219
4.1. Многоугольные числа219
4.2. Центральные многоугольные числа225
4.3. Пространственные фигурные числа228
4.4. Числа Каталана231
Задачи к главе 4242
4.1. Специальные числа242
4.2. Контрольные работы248

Введение
top

Дискретная математика – часть математической науки, которая зародилась в глубокой древности. Как говорит само название, главной ее спецификой является дискретность, то есть антипод непрерывности.

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

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

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

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

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

В целом можно считать, что дискретная математика – область математики, занимающаяся изучением дискретныхструктур, которые возникают как в пределах самой математики, так и в ее приложениях. К числу таких структур могут быть отнесены конечные группы, конечные графы, а также некоторые математические модели преобразования информации, конечные автоматы, машины Тьюринга и т.д. Это примеры структур конечного (финитного) характера. Раздел дискретной математики, изучающий их, называется конечной математикой. Помимо указанных конечных структур, дискретная математика изучает некоторые алгебраические системы, бесконечные графы, вычислительные схемы определенного вида, клеточные автоматы и т.д. В качестве синонима иногда употребляется термин дискретный анализ.

Таким образом, к ведению дискретной математики могут быть отнесены такие разделы, как:

  • наивная теория множеств;
  • математическая логика;
  • математическая кибернетика;
  • теория функциональных систем;
  • общая алгебра;
  • комбинаторика;
  • теория графов;
  • машинная арифметика;
  • теория алгоритмов;
  • теория игр;
  • теория кодирования;
  • теория конечных автоматов;
  • теория формальных грамматик;
  • вычислительная геометрия;
  • теория булевых функций;
  • логическое программирование;
  • функциональное программирование;
  • Булева алгебра;
  • комбинаторная логика;
  • математическая лингвистика;
  • теория искусственного интеллекта.

Конечно, охватить все эти разделы в рамках одной книги невозможно, и сегодня имеется много учебников и учебных пособий, в которых освешены те или иные избранные вопросы дискретной математики (см, например,). Целью нашей книги явилось детальное рассмотрение тех вопросов, которые входят в программу курсов Дискретная математика и Основы дискретной математики для студентов математических факультетов педвузов. Помимо доказательства необходимых теоретических утверждений, наше учебное пособие содержит большое число разнообразных задач, решение которых может не только помочь студентам глубже понять теорию, но и сподвигнуть их на самостоятельные исследования в этой активно развивающейся области метематической науки.


Об авторах
top
photoДеза Елена Ивановна
Доктор педагогических наук (2012), кандидат физико-математических наук (1993). В 1983 г. окончила математический факультет Московского государственного педагогического института имени В. И. Ленина (МГПИ), в 1992 г. — аспирантуру по кафедре теории чисел МГПИ (ныне — Московский педагогический государственный университет, МПГУ), в 2010 г. — докторантуру по кафедре теоретической информатики и дискретной математики МПГУ. С 1988 г. — преподаватель кафедры теории чисел математического факультета МПГУ, с 2006 г. — профессор кафедры теоретической информатики и дискретной математики математического факультета МПГУ. Область научных интересов: теория чисел, дискретная математика, дидактика высшей школы. Автор нескольких монографий, более 10 учебных и учебно-методических пособий, более 150 научных публикаций.
photoМодель Дмитрий Лазаревич
В 2003 г. с отличием окончил математический факультет МПГУ. Победитель программы «Урбан Лидер» 2023 г. для руководителей среднего звена Правительства Москвы. В настоящее время — старший преподаватель кафедры теории чисел; является соискателем ученой степени кандидата наук на кафедре теории и методики преподавания математики. Область научных интересов: дискретная математика, методы принятия решений, профильное образование школьников, развитие образовательных систем. Автор более 20 научно-методических публикаций.