Романовский И. В. Дискретный анализ. - Невский Диалект; БХВ-Петербург, 2003. - 320 с.
Пособие написано по материалам вводного лекционного курса, который автор читает на математико-механическом факультете Санкт-Петербургского государственного университета студентам, специализирующимся по прикладной математике и информатике. Особое внимание уделяется связям между понятиями дискретного анализа, возникающими в разных разделах математики и современной информатики.В это издание включено много новых материалов, в связи с чем изменилась структура книги: появились новые главы и параграфы. Увеличено число упражнений. Текст дополнен алфавитным указателем и библиографическими рекомендациями.
Оглавление
Введение 5
1. Некоторые определения из теории множеств 8
1.1. Основные определения....................................................8
1.2. Прямое произведение......................................................9
1.3. Разбиения....................................................................И
2. Строки фиксированной длины 16
2.1. Векторы из нулей и единиц..............................................16
2.2. Перебор 0-1 векторов....................................................32
2.3. Перебор элементов прямого произведения множеств ................35
2.4. Перестановки................................................................36
2.5. Размещения и сочетания..................................................47
2.6. Бином Ньютона и его комбинаторные использования..............52
2.7. Числа Фибоначчи..........................................................55
3. Элементарная теория вероятностей 59
3.1. Основные определения....................................................59
3.2. Условные вероятности и формула Байеса..............................64
3.3. Случайные величины......................................................66
3.4. Математическое ожидание и дисперсия................................68
3.5. Схема Бернулли............................................................70
3.6. Функции распределения ..................................................71
3.7. Случайные числа ..........................................................74
3.8. Двоичный поиск и неравенство Крафта................................79
3.9. Энтропия и ее свойства ..................................................83
4. Строки переменной длины 87
4.1. Строки, списки, последовательности.................. 87
4.2. Операции над строками ......................... 88
4.3. Функции от строк............................. 92
4.4. Скользящие суммы............................ 96
4.5. Поиск образца в строке ......................... 97
4.6. Задача о максимальном совпадении двух строк...........104
4.7. Задача Кнута-Пласса о выключке абзаца ..............108
4.8. Слияние...................................109
4.9. Операции над множествами на прямой................111
4.10. Длинная арифметика...........................112
4.11. Кусочно-постоянные функции .....................113
5. Сжатие и защита информации 117
5.1. Введение ..................................117
5.2. Код Шеннона-Фано и алгоритм Хаффмена.............118
5.3. Сжатие текстов .............................122
5.4. Избыточное кодирование.........................131
5.5. Криптография ...............................135
6. Информационный поиск и организация информации 144
6.1. Зачем здесь этим заниматься?......................144
6.2. Простейшие механизмы — массивы, файлы и цепные списки . . 145
6.3. Простейшее действие организации — сортировка .........147
6.4. Простейшее ускорение поиска — дихотомия ............156
6.5. Информационные деревья........................158
6.6. Хеширование................................169
6.7. Приоритетные очереди..........................171
7. Предикаты и отношения 176
7.1. Определения................................176
7.2. Отношения порядка............................178
7.3. Отношения в базах данных .......................180
8. Теория графов 185
8.1. Определения................................185
8.2. Построение транзитивного замыкания фафа (отношения) .... 190
8.3. Связность. Компоненты связности и сильной связности......192
8.4. Деревья...................................198
8.5. Применения деревьев...........................206
8.6. Матрица инциденций и линейные системы..............208
8.7. Задача о кратчайшем пути и ее варианты...............214
8.8. Задачи о кратчайшем дереве путей ..................224
8.9. Сетевой график и критические пути..................228
8.10. Теория паросочетаний и ее применения................236
9. Экстремальные задачи 244
9.1. Какие задачи и методы нам уже встречались ............244
9.2. Бистохастические матрицы .......................246
9.3. Экстремальные задачи на множестве перестановок.........252
9.4. Методы улучшенного перебора.....................253
9.5. Приближенные методы оптимизации .................258
10. Процессы 263
10.1. Конечные автоматы............................264
10.2. Марковская цепь..............................270
10.3. Управляемые процессы..........................279
10.4. Вычислительные процессы........................286
11. Связи дискретного и непрерывного анализа 300
11.1. Введение. Конкретная математика...................300
11.2. Производящие функции .........................300
11.3. Асимптотика................................304
Приложение. Библиографические рекомендации 306
Библиография 311
Алфавитный указатель 315
