Математика

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

год издания — 1975, кол-во страниц — 480, тираж — 18000, язык — русский, тип обложки — твёрд. 7Б тканев., масса книги — 550 гр., издательство — Физматлит

КНИГА СНЯТА С ПРОДАЖИ

Сохранность книги — хорошая

INTRODUCTION
A
LA COBINATORIQUE
EN VUE DES APPLICATIONS
PAR
A. KAUFMANN

DUNOD
PARIS
1968

Пер. с фр. В. П. Мякишева и В. Е. Тараканова

Формат 60x90 1/16

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

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

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

В процессе перевода и редактирования было выявлено и исправлено значительное количество ошибок и неточностей оригинала, особенно большим изменениям подверглись главы IV и V.

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Севастьянов Б. А.

Предисловие редактора перевода	6

Список основных обозначений	7

Г л а в а I. Пересчёт. Применение производящих функций	9

§ 1. Введение	9
§ 2. Теоретико-множественное произведение. Понятие r-выборки	9
§ 3. Размещения. Сочетания	10
§ 4. Пересчёт. Перечисление. Классификация. Оптимизация	16
§ 5. Производящие функции	18
§ 6. Сведения о конечноразностных операторах	20
§ 7. z-преобразование	24
§ 8. Применение производящей функции. Энумераторы и денумераторы
сочетаний	37
§ 9. Денумераторы размещений	44
§ 10. Основные последовательности и формулы для пересчёта	47

Г л а в а II. Развитие методов пересчёта	60

§ 11. Введение	60
§ 12. Формула включения и исключения	60
§ 13. Использование общего метода решета в теории чисел	70
§ 14. Задача о встречах. Беспорядки и совпадения	73
§ 15. Перманент матрицы	78
§ 16. Группы подстановок. Перестановки. Транспозиции	87
§ 17. Денумераторы цикловых классов	97
§ 18. Классифицирование. Схема размещения элементов по ячейкам	114
§ 19. Урновые схемы	125
§ 20. Задача о супружеских парах, или задача Люка	127
§ 21. Перестановки с запретными положениями. Размещение по ячейкам	133
§ 22. Противоречивые перестановки	145
§ 23. Латинские прямоугольники	151

Г л а в а III. Свойства графов	154

§ 24. Введение	154
§ 25. Граф. Определение	155
§ 26. Понятие пути	161
§ 27. Сильно связный граф. Разложение на максимальные сильно связные
подграфы. Транзитивное замыкание и пересчёт путей	164
§ 28. Порядковая функция графа без контуров	172
§ 29. Функция Гранди	177
§ 30. Внутренняя устойчивость. Внешняя устойчивость	180
§ 31. Ядра графа	186
§ 32. Основные понятия для неориентированных графов	191
§ 33. Хроматическое число. Хроматический класс	195
§ 34. Клика. Максимальная клика	201
§ 35. р-цветный граф. Граф с р отображениями Неориентированный
мультиграф, или неориентированный р-граф	204
§ 36. Плоские р-графы	205
§ 37. Подмножество сочленения	210
§ 38. Прадерево. Дерево	217
§ 39. Конечные структуры	223

Г л а в а IV. Перечисление	243

§ 40. Введение	243
§ 41. Метод латинской композиции	243
§ 42. Перечисление путей	246
§ 43. Перечисление элементарных путей	248
§ 44. Перечисление элементарных контуров	252
§ 45. Перечисление последовательностей с повторением	255
§ 46. Перечисление факторов графа	257
§ 47. Перечисление рассечений	263
§ 48. Другие методы и задачи перечисления	265

Г л а в а V. Оптимизация	271

§ 49. Введение	271
§ 50. Числовая функция на графе	271
§ 51. Оптимизация пути в графе без контуров. Теоремы оптимальности	277
§ 52. Метод динамического программирования	279
§ 53. Последовательные графы	291
§ 54. Метод прогрессивных разделений и оценок (метод ветвления и
ограничения)	299
§ 55. Нахождение хорошего решения эвристическим методом	324
§ 56. Применение методов Монте-Карло	338
§ 57. Понятие k-оптимальности	341
§ 58. Оптимизация на прадереве. Отыскание оптимального дерева,
являющегося частичным графом	350
§ 59. Задачи о временном упорядочении	355
§ 60. Оптимизация потока в сети	361
§ 61. Простой граф. Покрытие. Паросочетание	381
§ 62. Задача о назначении	405

П р и л о ж е н и е А. Бинарная булева алгебра. Кольцо классов вычетов
по модулю n. Поля Галуа характеристики р	415

А1. Введение	415
А2. Булева алгебра	415
A3. Кольцо классов вычетов по модулю n	427
А4. Поля Галуа	432
А5. Алгебра по модулю 2	435

П р и л о ж е н и е Б. Кодирование. Коды, обнаруживающие ошибки	439

Б1. Введение	439
Б2. Передача r-выборки	439
БЗ. Коды, обнаруживающие и исправляющие ошибки	445
Б4. Аналогия между циклическими и линейными кодами	460
Б5. Коды сцепления	465
Б6. Декодирование перестановками	468

Литература	472
Именной указатель	475
Предметный указатель	477

Книги на ту же тему

Прикладная комбинаторная математика, Беккенбах Э., ред., 1968
Комбинаторные методы дискретной математики, Сачков В. Н., 1977
Преобразования и перестановки, Калужнин Л. А., Сущанский В. И., 1979
Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
Живые числа. Пять экскурсий, Боро В., Цагир Д., Рольфс Ю., Крафт Х., Янцен Е., 1985
Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
Характеризационная теория синтеза функциональных декомпозиций в k-значных логиках, Горбатов А. В., 2000
Булевы алгебры, Сикорский Р., 1969
Кибернетическое моделирование. Некоторые приложения, Кемени Д. Д., Снелл Д. Л., 1972
Задачник по теории вероятностей, Палий И. А., 2004
Группы и их графы, Гроссман И., Магнус В., 1971
Теория графов, Харари Ф., 1973
Эйлеровы графы и смежные вопросы, Фляйшнер Г., 2002
Графы и их применение, Оре О., 1965
Машины клеточных автоматов, Тоффоли Т., Марголус Н., 1991
Дискретная математика для программистов, Хаггарти Р., 2004
Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
Параллельные алгоритмы целочисленной оптимизации, Хохлюк В. И., 1987
Численные методы оптимизации: Единый подход, Полак Э., 1974
Динамические задачи дискретной оптимизации, Рихтер К., 1985
Методы оптимизации, Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М., 1978
Информатика, Луенбергер Д. Д., 2008
Теория арифметических кодов, Дадаев Ю. Г., 1981
Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение, Морелос-Сарагоса Р., 2005
Основы кодирования, Вернер М., 2006
Эффективное кодирование, Новик Д. А., 1965
Криптография, Смарт Н., 2006
Криптографические методы защиты информации в компьютерных системах и сетях, Иванов М. А., 2001

http://knigoprovod.ru

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему