Липский В. Комбинаторика для программистов ОНЛАЙН

Липский В. Комбинаторика для программистов. — М.: Мир, 1988. — 200 с.
Первая глава книги содержит изложение классических разделов комбинаторики (перестановки, разбиения множеств и чисел, биномиальные коэффициенты, производящие функции, и т.д.), а также многие — необязательно классические — алгоритмы генерирования упомянутых комбинаторных объектов. Во второй главе представлены основные методы, используемые при конструировании алгоритмов на графах, в особенности методы систематичного обхода графов. В двух следующих главах обсуждаются методы нахождения кратчайших путей в графах и задача отыскания максимального потока в сети. В последней главе рассматривается применение комбинаторного понятия матроида для решения некоторого класса оптимизационных задач. Книга предназначена для программистов, желающих расширить свои знания в области комбинаторных алгоритмов, а также пополнить свои практические знания теоретическими.

загрузка...
От читателя требуются элементарные сведения из математики, а также знакомство с языком программирования Паскаль.
Оглавление
0.1 Предисловие редактора перевода………………………………..2
0.2 От автора…………………………………………………………3
1 Введение в комбинаторику……………………………5
1.1 Основные понятия………………………………………………..5
1.2 Функции и размещения…………………………………………..10
1.3 Перестановки: разложение на циклы, знак перестановки……….13
1.4 Генерирование перестановок……………………………………..19
1.5 Подмножества множества, множества с повторениями…………….29
1.6 k-элементные подмножества, биномиальные коэффициенты ……………34
1.7 Генерирование k-элементных подмножеств ……………………..39
1.8 Разбиения множества…………………………………………….43
1.9 Числа Стирлинга второго и первого рода……………………….45
1.10 Генерирование разбиений множества…………………………….50
1.11 Разбиения чисел………………………………………………….54
1.12 Производящие функции…………………………………………58
1.13 Принцип включения и исключения………………………………66
1.14 Задачи …………………………………………………………..70
2 Алгоритмы на графах 79
2.1 Машинное представление графов………………………………..79
2.2 Поиск в глубину в графе…………………………………………83
2.3 Поиск в ширину в графе…………………………………………86
2.4 Стягивающие деревья (каркасы) ………………………………..89
2.5 Отыскание фундаментального множества циклов в графе …. 92
2.6 Нахождение компонент двусвязности…………………………….95
2.7 Эйлеровы пути……………………………………………………99
2.8 Алгоритмы с возвратом (back-tracking) …………………………102
2.9 Задачи …………………………………………………………..108
3 Нахождение кратчайших путей в графе 111
3.1 Начальные понятия………………………………………………112
3.2 Кратчайшие пути от фиксированной вершины………………….114
3.3 Случай неотрицательных весов — алгоритм Дейкстры …………116
3.4 Пути в бесконтурном орграфе……………………………………120
3.5 Кратчайшие пути между всеми парами вершин, транз.замыкание ………………………………123
3.6 Задачи …………………………………………………………..127
4 Потоки в сетях и родственные задачи 129
4.1 Максимальный поток в сети……………………………………..129
4.2 Алгоритм построения максимального потока……………………134
4.3 Наибольшие паросочетания в двудольных графах………………147
4.4 Системы различных представителей…………………………….156
4.5 Разложение на цепи………………………………………………164
4.6 Задачи …………………………………………………………..170
5 Матроиды 174
5.1 Жадный алгоритм решения оптимизационных задач…………..174
5.2 Матроиды и их основные свойства………………………………176
5.3 Теорема Рамо-Эдмондса…………………………………………181
5.4 Матричные матроиды…………………………………………….183
5.5 Графовые матроиды …………………………………………….186
5.6 Матроиды трансверсалей…………………………………………189
5.7 Задачи …………………………………………………………..192

Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам: