Введение в прикладную комбинаторику, Кофман А. (984071)
Текст из файла
А. КОФМАН Введение в прикладную комбинаторику Перевод с французского В. П. МЯКН!йЕВА и В. Е. ТАРАКАНОВА Под редакцией Б. А. СЕВАСТЬЯНОВА ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКИИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТ Москва 1975 ОГЛАВЛ ЕН И Е Предисловие редактора перевода Список основных обозначений Гл а за 1. Пересчет. Применение производящих функций $9 $ !О Глава П. Развитие методов пересчета 60 60 70 73 78 87 97 ячейкам 114 . 125 , 127 по ячей- .
133 . 145 . 151 $22 9 23 $1 $2 $3 $4 $5 6 $7 $8 $1! $12 $13 $ !4 й 15 $16 $ !7 9 18 9 19 % 20 $21 Введение Теоретико-множественное произведение. Понятие г-выборки Размещения. Сочетания Пересчет. Перечисление. Классификация. Оптимизация Производящие функции Сведения о коиечноразностных операторах з-преобразование Применение производящей функции, Энумераторы и денумера- торы сочетаний Денумераторы размещений Основные последовательности и формулы для пересчета Введение Формула включения и исключения Использование общего метода решета в теории чисел Задача о встречах Беспорядки и совпадения Перманент матрицы Группы подстановок. Перестановки. Транспозицин Денумерагоры цинловых классов Классифицирование. Схема размещения элементов по Урновые схемы Задача о супружеских парах, или задача Люка Перестановки с запретными положениями.
Размещение кам Противоречивые перестановки Латинские прямоугольники 9 9 10 16 18 20 24 37 44 47 !64 Г л а в а П1. Свойства графов Введение ....,...,....,...,... 154 Граф, Определение.......,...,,,... 155 Понятие пути .....,....,,...,... 161 Сильно связный граф. Разложение на ыаксимальные сильно связные подграфы. Транзитивное замыкание н пересчет путей 164 Порядковая функция графа без контуров...,....
172 Функция Гранди,.....,,...,...,,, 177 Внутренняя устойчивость. Внешняя устойчивость . . . , . . 180 Ядра графа ...,...,....,...,,, !86 Основные понятия для неориентированных графов,.... 191 Хроматическое число. Хроматический класс....,... 195 Клика. Максимальная клика . . . . , . . . , . . . . . 201 р-цветный граф Граф с р отображениями Неориентированный мулыиграф, или неориентированный р-граф , . . . . . . , 204 Плоские р-графы,,...,,...,,..., ., 205 Подмножество сочленения ...,,...,...,, 2!О Прадерево.
Дерево,...,...,,...,, 217 Конечные структуры.............., .. 223 6 24. 4 25 $26 $2? $28 $29. $30 5 31. 5 32 ф 33 $34 6 35 6 36 $ 37 6 38 й 39 . 243 Г л а в а Гч'. Перечисление , 243 , 243 . 246 , 248 . 252 . 255 , 257 . 263 Введение Метол латинской композиции Перечисление путей Перечисление элементарных путей Перечисление элементарных контуров Перечисление последовательностей с повторением Перечисление факторов графа Перечисление рассечений Другие методы и задачи перечисления 6 40. $41 5 42 6 43 й 44 $45 $ 46 $47 $48 .
271 Г л а в а Ч. Оптимизация . 277 . 279 ности Метод динамического программирования Последовательные графы $52 6 53 б 54 , 291 Метод прогрессивных разделений и оценок (метод ветвления и ограничения) . . . . . . . . . . . . . . . , . . . . 299 Нахождение хорошего решения эвристическим методом... 324 Применение методов Монте. Карло . . .
. . . . . . . . 338 6 55 6 56 $49. Введение . 271 6 50. Числовая функция на графе.............. 271 6 51. Оптимизация пути в графе без контуров. Теоремы оптнмаль- ,,.....,.341 оптимального дерева, , 350 . 355 , 361 , 381 . 405 П р и л о ж е н и е А. Бинарная булеза алгебра. Кольцо классов вычетов по модулю и. Поля Галуа характеристики р...
415 , 415 . 415 . 42? . 432 . 435 Приложен не Б, Кодирование. Коды, обнаруживающие ошибки Б1. Введение Б2. Передача г-выборки БЗ. Коды, обнаруживающие и исправляющие ошибки Б4. Аналогия между циклическими и линейными кодами Б5. Коды сцепления Бб. Декодирование переетановкамн Литература Именной указатель Предметный указатель 6 67. Понятие й-оптимальности й 58. Оптимизация на прадереве. Отыскание являющегося частичным графом й 59. Задачи о временнбм упорядочении З 60. Оптимизация потока в сети й 61. Простой граф. Покрытие.
Паросочетание 6 62. Задача о назначении А1. Введение А2. Булеза алгебра А3. Кольцо классов вычетов по модулю и А4. Поля Галуа А5. Алгебра по модулю 2 . 439 439 . 439 . 445 . 460 . 465 . 468 . 472 . 475 , 477 ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Развитие вычислительной техники и исследования операций вызвало повышенный интерес к комбинаторной математике. Оно привело, с одной стороны, к постановке новых комбинаторных задач, а с другой стороны, дало эффективные способы их решения с помощью электронных цифровых вычислительных машин. В предлагаемой книге известного французского математика и педагога А.
Кофмана излагаются основы прикладной комбинаторики. В ней рассматриваются математические вопросы, представляющие большой интерес для практических приложений, а именно: элементы теории перечисления, теории графов, оптимизации и некоторые другие. Наряду с доказательствами основных предложений приводится большое число практических рецептов и алгоритмов решения комбинаторных задач, позволяющих зачастую получить численный результат.
При написании книги автор стремился к тому, чтобы читатель, не обладающий предварительной подготовкой, получил дополнительный стимул к изучению этой области математики. Этому способствует большое количество примеров и иллюстративного материала. Простота и наглядность изложения делают ее доступной самому широкому кругу читателей. В процессе перевода и редактирования было выявлено н исправлено значительное количество ошибок и неточностей оригинала, особенно большим изменениям подверглись главы 1Ъ' и Ъ', Севастьянов Б. А.
СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ (а, Ь, ..., 1), Е )( а !ы А 8 А=В (А(, Сагб(А) В с А В ий А В !ь А АОВ АП В С В,В А — В У, =)! Уз У! ФФУз )!!х Ех Е1х Х Е )со С ЕО!ХЕ1з!Х ° ° ° ХЕ! ! (Еи Еи '' Еа) [Ер, Е,, ..., Ер [ А,"„ С" Си! из ""ив 1и А )' (я) (2) Ег (х) Ьг (х) 01 (х) й) (х) з(и, г) Множество. Множество частей множества Е. Элемент а принадлежит множеству А. Пустое множество.
Множество А совпадает с множеством В. Число элементов конечного множества А. Множество В содержится в множестве А. Множество В строго содержится в множестве А. Множество В не содержится в множестве А. Объединение двух множеств. Пересечение двух множеств. Дополнение В по отношению к А. Разность. Из свойства У, следует свойство У,. Свойства У! и У, эквивалентны. Для всех х. Квантор общности. Существует х. Квантор существования. Существует одно и только одно х. Множество целых неотрицательных чисел; Х= (О, 1, 2, 3, ...!.
Х вЂ” (О). Множество всех целых чисел: Е (...,— 3,— 2,-1,0,1,2,3,...). Множество всех действительных чисел.  — (0). Множество всех комплексных чисел. Произведение и множеств Е1'1, Е1з), ..., Е1"1. Упорядоченнан г-выборка. Неупорядоченная г-выборка. Число размещений без повторения из га элементов по и. Число сочетаний без повторения из ги элементов по и. Число разбиений множества на й неупорядоченных выборок без повторения. Натуральный логарифм числа А Производящая функция, или я-преобразование функции 1(и), определенной на Х.
Экспоненциальная производящая функция, или экспоненциальное х-преобразование функции Г(з), определенной на Х. Оператор, переводящий 1(х) в 1(я+ й). Оператор, переводящий 1(х) в 1(х+ й) — 1(х). б Оператор взятия производной — 1(х) от 1(х). бх Оператор умножения ) (х) нз действительное число й. Числа Стирлинга первого рода. з(и, г) (А) Ол Вл ь бе( (( а ((, ( а ( рег ~(а)) Рл (зм гз' '' ' зл) Ь (и, Ь) Т (и, Ь) Мл Е(г, и] К(г, и) ГА Г А ОсЕХЕ ц+ А 6 = (Е, Г) или О = (Е, ц) О" (Хги Хэм „., Х,л) Г а «„Ь а(~ Ь а (6) НО) ц О =(Е Ц) (х,, х, , х, ) и (х",) у(6) тир(А) )п( (А) А ту В А зз В з)»зз л(х,, х,,, ..., х,л) р(х;„х,,, ..., х,"„) орт шах пНп с(ц ) 6=(Х,У, Г) Р(А; к), )л(х) и†= Ь (глоба) + СО (р) Числа Стирлиига второго рода.
Символ Кронекера. Целая часть числа А. Число беспорядков и элементов. Число перестановок и элементов с Ь совпадениями. Определитель матрицы ()а(). Перманент матрицы ))а!!. Денумератор цикловых классов. Присоединенные числа Стирлинга первого рода. Присоединенные числа Стирлинга второго рода. Число перестановок л «супружеских пар».
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
