Романовский И.В. Дискретный анализ

4-е изд., испр. и доп. — СПб.: Невский Диалект, БХВ-Петербург, 2008. — 336 с.Пособие написано по материалам вводного лекционного курса, который автор читает на математико-механическом факультете Санкт-Петербургского государственного университета студентам, специализирующимся по прикладной математике и информатике. Особое внимание уделяется связям между понятиями дискретного анализа, возникающими в разных разделах математики и современной информатики.
В это издание включено много новых материалов, в связи с чем изменилась структура книги: появились новые главы и параграфы. Увеличено число упражнений. Текст дополнен алфавитным указателем и библиографическими рекомендациями.Введение
Некоторые определения из теории множеств
Основные определения
Прямое произведение
Разбиения
Строки фиксированной длины
Векторы из нулей и единиц
Перебор - векторов
Перебор элементов прямого произведения множеств
Перестановки
Размещения и сочетания
Бином Ньютона и его комбинаторные использования
Числа Фибоначчи
Элементарная теория вероятностей
Основные определения
Условные вероятности и формула Байеса
Случайные величины
Математическое ожидание и дисперсия
Схема Бернулли
Функции распределения
Случайные числа
Двоичный поиск и неравенство Крафта
Энтропия и ее свойства
Строки переменной длины
Строки, списки, последовательности
Операции над строками
Функции от строк
Скользящие суммы
Поиск образца в строке
Задача о максимальном совпадении двух строк
Задача Кнута—Пласса о выключке абзаца
Слияние
Операции над множествами на прямой
Длинная арифметика
Кусочно-постоянные функции
Сжатие и защита информации
Введение
Код Шеннона-Фано и алгоритм Хаффмена
Сжатие текстов
Избыточное кодирование
Криптография
Информационный поиск и организация информации
Зачем здесь этим заниматься?
Простейшие механизмы — массивы, файлы и цепные списки
Простейшее действие организации—сортировка
Простейшее ускорение поиска — дихотомия
Информационные деревья
Хеширование
Приоритетные очереди
Предикаты и отношения
Определения
Отношения порядка
Отношения в базах данных
Теория графов
Определения
Построение транзитивного замыкания графа (отношения)
Связность Компоненты связности и сильной связности
Деревья
Применения деревьев
Матрица инциденций и линейные системы
Задача о кратчайшем пути и ее варианты
Задачи о кратчайшем дереве путей
Сетевой график и критические пути
Теория паросочетаний и ее применения
Экстремальные задачи
Какие задачи и методы нам уже встречались
Бистохастические матрицы
Экстремальные задачи на множестве перестановок
Методы улучшенного перебора
Приближенные методы оптимизации
Процессы
Конечные автоматы
Марковская цепь
Управляемые процессы
Вычислительные процессы
Связи дискретного и непрерывного анализа
Введение Конкретная математика
Производящие функции
Асимптотика
Приложение
Библиографические рекомендации
Библиография
Алфавитный указатель