Дискретная математика (998286), страница 24
Текст из файла (страница 24)
Более подробное изложение можно найти в многочисленных классических учебниках, например (15). Классическое описание автоматического доказательства теорем методом резолюций имеется в (241. Эта книга содержит описание различных стратегий и усовершенствований метода резолюций, а также многочисленные примеры применений.
Алгоритмы 4.3.3 и 4.5.7 являются упрощенными модификациями алгоритмов, описанных в [241. Упражнения 4.1. Пусть х щ р: = х -+ у йг р — > х. Доказать, что формула С, содержащая только связку щ, является тавтологией тогда и только тогда, когда каждая переменная входит в нее четное число раз. 4.2. Описать процедуру, которая перечисляет множество термов для заданных конечных множеств переменных, констант и функторов. 4.3.
Пусть м формула А теории Х вЂ” не тавтология. гн А — множество всех частных случаев А. ° а+: =ао А. Доказать, нто г'+ противоречива, то есть, что 1-с~ В и 1-г.+ В. 4.4. Доказать, что формула (Ух А(х) — + Ух В(х)) + (Ух (А(х) -г В(х))) об щезначима.
4.5. Доказать методом резолюций: Нг, А -+ ( — + А 4г В). ГЛАВА 5 Комбинаторика Предмету комбинаторики не так просто дать краткое исчерпывающее определение. В некотором смысле слово «комбинаторика» можно понимать как синоним термина «дискретная математика», то есть исследование дискретных конечных математических структур. На школьном уровне с термином «комбинаторика» связывают просто набор известных формул, служащих для вычисления так называемых камбинаторньп чисел, о которых идет речь в первых разделах атой главы. Может показаться, что зти формулы полезны только для решения олимпиадных задач и не имеют отношения к практическому программированию.
На самом деле зто далеко не так. Вычисления на дискретных конечных математических структурах„которые часто называют каибинаторными вычислениями, требуют комбинаторного анализа для установления свойств и выявления оценки применимости используемых алгоритмов. Рассмотрим злементарный жизненный пример. Пример Пусть некоторое агентство недвижимости располагает базой данных из и записей, причем каждая запись содержит одно предложение (что имеется) и один запрос (что требуется) относительно объектов 'недвижимости.
Требуется найти все такие пары записей, в которых предложение первой записи совпадает с запросом второй, и, наоборот, предложение второй записи совпадает с запросом первой. (На бытовом языке зто называется подбором вариантов обмена.) Допустим, что используемая СУБД позволяет проверить вариант за одну миллисекунду.
Нетрудно сообразить, что при «лобовом» алгоритме поиска вариантов (каждая запись сравнивается с каждой) потребуется п(п — 1)/2 сравнений. Если и = 100, то все в порядке — ответ будет получен за 4,95 секунды. Но если и = 100 000 (более реальный случай), то ответ будет получен за 4 999 950 секунд, что составляет без малого 1389 часов и вряд ли может считаться приемлемым. Обратите внимание, что мы оценили только трудоемкость подбора прямых вариантов. а существуют еше варианты, когда число участников сделки больше двух ... 1З5 бл.
Комбинаторные конфигурации Этот пример показывает, что комбинаторные вычисления требуют предварительного анализа и количественной оценки исходных задач и используемых алгоритмов. Задачи обычно оцениваются с точки зрения размера, то есть общего количества различных вариантов, среди которых нужно найти решение, а алгоритмы оцениваются с точки зрения сложности. При этом различают сложность по времени (или временную сложность), то есть количество необходимых шагов алгоритма, и сложность по памяти (или вмкостную сложность), то есть объем памяти, необходимый для работы алгоритма. Во всех случаях. основным инструментом такого анализа оказываются формулы и методы, рассматриваемые в этой главе. 5.1.
Комбинаторные конФигурации Во многих практических случаях возникает необходимость подсчитать количество возможных комбинаций объектов, удовлетворяющих определенным условиям. Такие задачи называются комбинаторными. Разнообразие комбинаторных задач не поддается исчерпывающему описанию, но среди них есть целый ряд особенно часто встречающихся, для которых известны способы подсчета. 5.1.1. КОмбин«ктОРные зеДЙчи Для формулировки и решения комбинаторных задач используются различные модели комбинаторньп конфигураций. Рассмотрим следующие две наиболее популярные. 1, Дано и предметов.
Их нужно разместить по та ящикам так, чтобы выполнялись заданные орраничения. Сколькими способами это можно сделать? 2. Рассмотрим множество функций Г: Х -+ У, где )Х~ = п, (У~ = т, Х = (1,...,и). Не ограничивая общности, можно считать, что У = (1,..., та), Р = (Р(1),..., Р(п)), 1 < Р(г) < т. Сколько 'существует функций Г, удовлетворяющих заданным ограничениям7 ЗАМЕЧАНИЕ Болыпей частью соответствие конфнгурэпий, описанных на «языке ящиков» и на «языке функций», очевидно, поэтому доказательство праанлыюсти способа подсчета (вывод формулы) можно провести на любом языке.
Если сведение одной модели к другой не очевидно, то оно включается в доказательство. 5.1.2. Размещени Число всех функций (при отсутствии ограничений), или число всех возможных способов разместить и предметов по т ящикам называется, числом размвщвний и обозначается У(пг, о). Глава 5. Комбинаторика 1зб ТЕОРЕМА У(т,и) = т" Доказатальство Каждый из и предметов можно разместить т способами. Пример При игре в кости бросаются две кости и выпавшие на верхних гранях очки складываются.
Какова вероятность выбросить 12 очков? Каждый возможный исход соответствует функции Р: (1,2) -+ (1,2, 3,4,5,6) (аргумент — номер кости, результат — очки на верхней грани). Таким образом, всего возможно У(6,2) = 6в = 36 различных исходов. Из них только один (6+ 6) дает двенадцать очков. Вероятность 1/36, 5.1.3. Размещения без повторений Число инъективных функций, или число всех возможных способов разместить и предметов по т ящикам, не более чем по одному в ящик, называется числом раэиев4ений без повторений и обозначается А(т, и) или [т]„, или (т)„. т! ТЕОРЕМА А(ти, и) = (т — и)! Доказатвльство Ящик для первого предмета можно выбрать т способами, для второго — ти — 1 способами, и т.
д, Таким образом, т! А(т,и) =то (т — 1) °... (т — и+1) = П (т — и)1 По определению считают, что А(т, и): =6 при и > т и А(т, 0): =1 Пример В некоторых видах спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. Сколько возможно различных исходов, если в соревновании участвуют и участников? Каждый возможный исход соответствует функции Р: (1,2, 3) -+ (1.т) (аргумент — номер призового места, результат — номер участника).
Таким образом, всего возможно А(и, 3) = и(и — 1)(и — 2) различных исходов. 5.1.4. Перестановки Число взаимнооднозначных функций, илн число иереаиановок и предметов, обо- значается Р(и). 5. Коыбинаторныа конфигурации ТЕОРЕМА Р(и) = и! ДОКАЗАТЕЛЬСТВО Р(и) = А(и, и) = и (и — 1) ° (и — и+ 1) = и (и — 1) 1 = ™ Пример Последовательность Я = (Еы...,Е ) непустых подмножеств множества Е (б с 2в, Е; с Е, Е, -,г. о) называется девочкой в Е, если Ч1 Е 1..т — 1 Е; С Е,н.т Яс Е; у1 Е;+ы Цепочка б называется полной цепочкой в Е, если Щ = 1Е1 Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующее подмножество Е;+т получено из предыдущего подмножества Е, добавлением ровно одного элемента из Е и, таким образом, ~Ет~ =.1, Щ = 2,..., (Е ~ = (Е~ = т.
Следовательно, полная цепочка определяется порядком, в котором элементы Е добавляются для образования очередного элемента полной цепочки. Отсюда количество полных цепочек — зто количество перестановок элементов множества Е, равное т!. 5.1.5. Сочетания Число строго монотонных функций, или число размещений и неразличимых предметов по т ящикам, не более чем' по одному в ящик, то есть число способов выбрать из т ящиков и ящиков с предметами, называется числом сочетаний и обозначается С(т, и) или С" или ("). ТЕОРЕМА С(т, и) = т! ий(т — и)! доказательство 1. Число размещений беэ повторений нужно разделить на число перестановок, поскольку предметы неразличимы.
2. Число сочетаний является числом строго монотонных функций, потому что строго монотонная функция Г: 1..и — т 1.,т определяется набором своих значений, причем 1 < Р(1) « Р(и) < т. другими словами, каждая строго монотонная функция определяется выбором и чисел из диапазона 1..т. Таким образом, число строго монотонных функций равно числу и-элементных подмножеств т-элементного множества, которое, в свою очередь, равно числу способов выбрать и ящиков с предметами из ти ящиков. и По определению С(т, и): = 0 при и > т.
138 Глава б. Комбинаторика Пример В начале игры в домино каждому играющему выдается 7 костей из имеющихся 28 различных костей. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элементного множества. Имеем: — 1184040. 28! 28. 27 26 25 24 23. 22 7!(28 — 7)! 7 8 ° 5 4 3 2 1 5.1.6. Сочетания с повторениями Число монотонных функций, или число размещений и неразличимых предметов по т ящикам, называется числам сочетаний с иовгаореяиями и обозначается У(т, и). ТЕОРЕМА У(т, и) = С(п + т — и) Доюззатальство Монотонной функции 7": (1,..., п) — з (1,..., зи) однозначно соответствует строго монотонная функция 7"'.
(1,...,и) -+ (1,...,п+т — Ц. Это соответствие устанавливается следующей процедурой. 7'(1): =7(1) ( первые элементы совпадают ) 1ог з' бззю 2 Го и Йо зт Г'(з) = 1(з — 1) С)зеа 7"'(з):=7'(з — 1) + 1 ( плато 1 езве З" (з) з = 1'(з — 1) + 1(з) — 7 (з — 1) ( цедъем ) еой Ы еад Еог Пример Сколькими способами можно рассадить и вновь прибывших гостей среди т гостей, уже сидящих за круглым столом? Очевидно, что между т сидящими за круглым столом гостями имеется т промежутков, в которые можно рассаживать вновь прибывших.
Таким образом, это можно сделать (т+ п — 1)! У(т,п) =С(т+и — 1,п) = способами. и! (т — 1)! 5.2. Подстановки В атом разделе рассматриваются подстановки и перестановки, которые на самом деле являются равнообъемными понятиями, Для вычисления количества >.2. Подстноеки 1З9 терестановок в подразделе 5.1А установлена очень простая формула: Р(п) = п1 Применяя эту формулу при решении практических задач, не следует забывать, гто факториал — это очень быстро растущая функция, в частности, факториал эастет быстрее экспоненты.
Действительно, используя известную из математического анализа формулу Стирлинга п! т 42хпп"е " или, более точно «/2япп"е " < и1 С «/2япп"е "+ч О~"! нетрудно показать, что п! Вгп — = +оо, а-~+оо 2" 5.2.1. Группа подстановок Взаимнооднозначная функция у: Х вЂ” г Х называется подстановкой на Х. ЗАМЕЧАНИŠ—-- Всли множество Х конечно ()Х! = и), то, ие ограничивая общности, можно считать, что Х = 1,т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
