Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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