Введение в прикладную комбинаторику

  

А. Кофман. Введение в прикладную комбинаторику. Под ред. Б.А. Севастьянова Изд-во «Наука» Гл. редакция физико-математической литературы. М., 1975 г.

В предлагаемой книге известного французского математика и педагога А. Кофмана излагаются основы прикладной комбинаторики. В ней рассматриваются математические вопросы, представляющие большой интерес для практических приложений, а именно: элементы теории перечисления, теории графов, оптимизации и некоторые другие. Наряду с доказательствами основных предложений приводится большое число практических рецептов и алгоритмов решения комбинаторных задач, позволяющих зачастую получить численный результат.

При написании книги автор стремился к тому, чтобы читатель, не обладающий предварительной подготовкой, получил дополнительный стимул к изучению этой области математики. Этому способствует большое количество примеров и иллюстративного материала. Простота и наглядность изложения делают ее доступной самому широкому кругу читателей.



Оглавление

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
ГЛАВА 1. ПЕРЕСЧЕТ. ПРИМЕНЕНИЕ ПРОИЗВОДЯЩИХ ФУНКЦИЙ
§ 2. Теоретико-множественное произведение. Понятие r-выборки
§ 3. Размещения. Сочетания
§ 4. Пересчет. Перечисление. Классификация. Оптимизация
§ 5. Производящие функции
§ 6. Сведения о конечноразностных операторах
§ 7. z-преобразование
§ 8. Применение производящей функции. Энумераторы и денумераторы сочетаний
§ 9. Денумераторы размещений
§ 10. Основные последовательности и формулы для пересчета
ГЛАВА II. РАЗВИТИЕ МЕТОДОВ ПЕРЕСЧЕТА
§ 12. Формула включения и исключения
§ 13. Использование общего метода решета в теории чисел
§ 14. Задача о встречах. Беспорядки и совпадения
§ 15. Перманент матрицы
§ 16. Группы подстановок. Перестановки. Транспозиции
§ 17. Денумераторы цикловых классов
§ 18. Классифицирование. Схема размещения элементов по ячейкам
§ 19. Урновые схемы
§ 20. Задача о супружеских парах, или задача Люка
§ 21. Перестановки с запретными положениями. Размещение по ячейкам
§ 22. Противоречивые перестановки
§ 23. Латинские прямоугольники
ГЛАВА III. СВОЙСТВА ГРАФОВ
§ 25. Граф. Определение
§ 26. Понятие пути
§ 27. Сильно связный граф. Разложение на максимальные сильно связные подграфы. Транзитивное замыкание и пересчет путей
§ 28. Порядковая функция графа без контуров
§ 29. Функция Гранди
§ 30. Внутренняя устойчивость. Внешняя устойчивость
§ 31. Ядра графа
§ 32. Основные понятия для неориентированных графов
§ 33. Хроматическое число. Хроматический класс
§ 34. Клика. Максимальная клика
§ 35. p-цветный граф. Граф с p отображениями. Неориентированный мультиграф, или неориентированный p-граф
§ 36. Плоские p-графы
§ 37. Подмножество сочленения
§ 38. Прадерево. Дерево
§ 39. Конечные структуры
ГЛАВА IV. ПЕРЕЧИСЛЕНИЕ
§ 41. Метод латинской композиции
§ 42. Перечисление путей
§ 43. Перечисление элементарных путей
§ 44. Перечисление элементарных контуров
§ 45. Перечисление последовательностей с повторением
§ 46. Перечисление факторов графа
§ 47. Перечисление рассечений
§ 48. Другие методы и задачи перечисления
ГЛАВА V. ОПТИМИЗАЦИЯ
§ 50. Числовая функция на графе
§ 51. Оптимизация пути в графе без контуров. Теоремы оптимальности
§ 52. Метод динамического программирования
§ 53. Последовательные графы
§ 54. Метод прогрессивных разделений и оценок (метод ветвления и ограничения)
§ 55. Нахождение хорошего решения эвристическим методом
§ 56. Применение методов Монте-Карло
§ 57. Понятие k-оптимальности
§ 58. Оптимизация на прадереве. Отыскание оптимального дерева, являющегося частичным графом
§ 59. Задачи о временном упорядочении
§ 60. Оптимизация потока в сети
§ 61. Простой граф. Покрытие. Паросочетание
§ 62. Задача о назначении
ПРИЛОЖЕНИЕ А. БИНАРНАЯ БУЛЕВА АЛГЕБРА. КОЛЬЦО КЛАССОВ ВЫЧЕТОВ ПО МОДУЛЮ n. ПОЛЯ ГАЛУА ХАРАКТЕРИСТИКИ p
А3. Кольцо классов вычетов по модулю n
А4. Поля Галуа
А5. Алгебра по модулю 2
ПРИЛОЖЕНИЕ Б. КОДИРОВАНИЕ. КОДЫ, ОБНАРУЖИВАЮЩИЕ ОШИБКИ
Б3. Коды, обнаруживающие и исправляющие ошибки
Б4. Аналогия между циклическими и линейными кодами
Б5. Коды сцепления
Б6. Декодирование перестановками
ЛИТЕРАТУРА
email@scask.ru