|
Литература\Комбинаторика для программистов. Оглавление
Комбинаторика для программистов
В. Липский
Оглавление
0.1 Предисловие редактора перевода
0.2 От автора
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 Задачи
© JlC, 2005
|
