2. В.Липский - Комбинаторика для программистов - Книги по программированию - Программирование - Каталог файлов

2. В.Липский - Комбинаторика для программистов

Язык:русский | Формат:pdf | Размер:1,3Мб | Страниц:200

1 Введение в комбинаторику
1.1 Основные понятия
1.2 Функции и размещения
1.3 Перестановки: разложение на циклы, знак перестановки
1.4 Генерирование перестановок
1.5 Подмножества множества, множества с повторениями,
1.6 k-элементные подмножества, биномиальные коэффициенты
1.7 Генерирование k-элементных подмножеств
1.8 Разбиения множества
1.9 Числа Стирлинга второго и первого рода
1.10 Генерирование разбиений множества
1.11 Разбиения чисел
1.12 Производящие функции
1.13 Принцип включения и исключения
1.14 Задачи
2 Алгоритмы на графах
2.1 Машинное представление графов
2.2 Поиск в глубину в графе
2.3 Поиск в ширину в графе
2.4 Стягивающие деревь я(каркасы)
2.5 Отыскание фундаментального множества циклов в графе
2.6 Нахождение компонент двусвязности
2.7 Эйлеровы пути
2.8 Алгоритмы с возвратом (back-tracking)
2.9 Задачи
3 Нахождение кратчайших путей в графе
3.1 Началь ные понятия
3.2 Кратчайшие пути от фиксированной вершины
3.3 Случай неотрицательных весов — алгоритм Дейкстры
3.4 Пути в бесконтурном орграфе
3.5 Кратчайшие пути между всеми парами вершин, транззамыкани
3.6 Задачи
4 Потоки в сетях и родственные задачи
4.1 Максимальный поток в сети
4.2 Алгоритм построения максимального потока
4.3 Найбольшие паросочетания в двудольных графах
4.4 Системы различных представителей
4.5 Разложение на цепи
4.6 Задачи
5 Матроиды
5.1 Жадный алгоритм решения оптимизационных задач
5.2 Матроиды и их основные свойства
5.3 Теорема Рамо-Эдмондса
5.4 Матричные матроиды
5.5 Графовые матроиды
5.6 Матроиды трансверсалей
5.7 Задачи