Дискретная математика и программирование в Wolfram Mathematica
Дискретная математика — это необходимый базис для карьеры прикладного математика и программиста, и в то же время один из предметов, вызывающих у студентов наибольшие трудности.
Это учебное пособие познакомит вас с главными понятиями и методами дискретной математики, а также даст основы программирования в математической компьютерной среде Mathematica. В доступной форме изложен теоретический материал разделов: комбинаторика и перечислительная комбинаторика; структуры данных — двоичные кучи и двоичные деревья поиска — и основные алгоритмы на них; алгоритмы сортировки и сравнение их трудоемкости; сравнения по модулю, операции в кольцах вычетов и современные методы шифрования; графы и деревья. Приведены решения задач, иллюстрирующих вводимые понятия, а также даны задачи и упражнения для самостоятельной работы.
На двенадцати «уроках программирования» приведены реальные программные коды, реализующие все введенные ранее алгоритмы. Кроме того, на этих уроках показано, каким образом Mathematica поможет при решении различных задач дискретной математики. Книга будет полезна студентам и преподавателям вузов, а также всем, кто желает научиться программировать, используя Wolfram Mathematica.
Рекомендовано в качестве учебного пособия для студентов направлений подготовки 01.03.02 "Прикладная математика и информатика", 01.03.04 "Прикладная математика", а также для студентов других направлений, изучающих дисциплину "Дискретная математика".
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
I. Работа с системой Mathematica
Действие 1. Первое знакомство с Mathematica
и Wolfram Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Картина 1. Две составные части Mathematica: оболочка и ядро . . . . . . . . . 12
1.1. Начнём, пожалуй . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
1.2. Как задавать вопросы Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3. Что делать, если всё в жизни пошло не так . . . . . . . . . . . . . . . . . . . . . . 16
Картина 2. Общие правила синтаксиса в Wolfram Mathematica . . . . . . . . . . 17
2.1. Встроенные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
2.2. Шесть видов скобок в Wolfram Language . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3. Разделители (запятая и точка с запятой) и полезные мелочи . . . . 19
Картина 3. Вычисления с большими числами, преобразования
выражений, действия с функциями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1. Очень большой калькулятор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2. Константы в Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3. Формы записи функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
3.4. Преобразование выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5. Решение уравнений и правила замены . . . . . . . . . . . . . . . . . . . . . . . . . . . .27
3.6. Графика в Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.7. Создание списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Действие 2. Введение в основы программирования
в Wolfram Language для начинающих . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Картина 4. Основные идеи построения Wolfram Language . . . . . . . . . . . . . . . 35
4.1. Все объекты в Mathematica являются выражениями . . . . . . . . . . . . . .35
4.2. Списки как выражения и выражения как списки . . . . . . . . . . . . . . . . . .40
4.3. Операции присваивания и правила замены . . . . . . . . . . . . . . . . . . . . . . . 47
4.4. Шаблоны: первое знакомство . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5. Шаблоны с условиями, с ограничениями
и альтернативные шаблоны . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.6. Шаблоны и подстановка правила замены:
Replace, ReplaceAll и ReplaceRepeated . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.7. Шаблоны для произвольного числа аргументов . . . . . . . . . . . . . . . . . . 61
Действие 3. Стили программирования в Wolfram Language . . . . . . . . 66
Картина 5. Процедурное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
5.1. Условные операторы: If, Which, Switch . . . . . . . . . . . . . . . . . . . . . . . . . .67
5.2. Операторы цикла: For, While, Do, Table . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3. Управление процессом: команды Break, Continue и Return . . . . . .78
5.4. Локализация переменных и подпрограммы: With, Module
и Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Картина 6. Функциональное программирование . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.1. Анонимные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2. Функции высшего порядка: Apply и Map . . . . . . . . . . . . . . . . . . . . . . . . . .86
6.3. Функции MapIndexed, MapThread и Thread . . . . . . . . . . . . . . . . . . . . . . .90
6.4. Операторы NestList, FixedPointList и FoldList . . . . . . . . . . . . . . .92
6.5. Функции выбора: Position, Cases, Select и Pick . . . . . . . . . . . . . . . 95
6.6. Команды разделения и сборки: Gather, Split, Partition
и Flatten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
Картина 7. Программирование, основанное на применении
шаблонов и правил замены . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.1. Первые примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
II. Дискретная математика и уроки с Mathematica
Введение
Урок 1. Примеры программных кодов в Mathematica . . . . . . . . . . . . . . . . . . . .112
§ 1. Рассуждения по индукции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Урок 2. Рекуррентно заданные последовательности . . . . . . . . . . . . . . . . . . . . . 133
§ 2. Суммирования — первые примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Урок 3. Суммирования и разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .151
Глава 1. Комбинаторика
§ 3. Число элементов множества. Формула «включений-исключений» . . .161
§ 4. Счётные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
§ 5. Отображения и их типы. Образы и прообразы . . . . . . . . . . . . . . . . . . . . . . 169
§ 6. Перестановки, размещения, сочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Урок 4. Комбинаторные вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
§ 7. Производящие функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .194
Урок 5. Производящие функции и задача «о размене» . . . . . . . . . . . . . . . . . 203
§ 8. Элементы «перечислительной комбинаторики» . . . . . . . . . . . . . . . . . . . . . 216
Урок 6. Перечисление подмножеств и перестановок . . . . . . . . . . . . . . . . . . . . . 222
Глава 2. Структуры данных и алгоритмы
§ 9. Двоичные кучи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Урок 7. Реализация алгоритмов на двоичных кучах . . . . . . . . . . . . . . . . . . . . .245
§ 10. Алгоритмы сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
Уроки 8 и 9. Реализация алгоритмов сортировки
и сравнение их трудоёмкости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
§ 11. Алгоритм Евклида и его следствия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Урок 10. Числа простые и составные.
Реализация алгоритма Евклида и его обобщений . . . . . . . . . . . . . . . . . . . 289
§ 12. Сравнения по модулю.
Малая теорема Ферма и теорема Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
§ 13. Шифрование с открытым ключом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
Урок 11. Вычисления в кольцах вычетов.
Шифрование по алгоритму RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
§ 14. Кольца, поля, группы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Глава 3. Графы и деревья
§ 15. Графы: первая задача и первые понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
§ 16. Связные графы. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
§ 17. Некоторые теоремы теории графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
§ 18. Теорема Холла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .346
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
Изучаем Python, том 1, 5-е издание3 280 ₽
Java. Полное руководство, 10-е издание4 430 ₽
Анализ ценных бумаг. 3-е издание5 690 ₽