Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 3

Первая процедура состоит в преобразовании исходной информации к виду, при котором, фактически не строя решения, можно вычислить функционал его качества. Трудоемкость хаактеризационных алгоритмов для практических задач оценивается полиномиальнымн функциями, степень которых не превышает 3-5. Расхождение полученных результатов с результатами, полученными математиками-теоретиками, объясняется двумя причинами. Во первых, математики-теоретики оценивают трудоемкость алгоритмов решения комбинаторной задачи экспоненциальной зависимостью, исходя из наихудшего случая, который, как правило, является искусственным, не имеющим на практике места, и, во-вторых, доказывают асимптотические оценки, т.

е. рассматривают предельный переход при а -~ оо (и — размерность задачи). Практически же размерность задачи является конечной 12 Веедеиие величиной. Нап име р р, получение экспоненциальной оценки т даемкости раскраски вершин пронзвольног ф ого графа сновано на зна- тру- шинами: нии максимального числа у(п) пустых подг аф дграфов в графе с и вер- 3"уз, и = О(под 3), У(п) = 4. 31" е)/з п— : Цшод3), 2 3("-'УЗ, Па†д 2( дЗ), класс но эта зависимость справедлива только для ф графов единственного ных, асса, являющихся дополнениями граф М вЂ” М ов уна — озера до полКомбинаторные задачи необходимо рассматривать, принимая а а во внимание исходную конкретную инфо р зрабатывать интеллектуальные ииформа формацию, и на ее базе стратегии их решения.

формационные технологии и Полобно тому как лар слава обогащает нас мнеииамн крупах, так наык математических аналое слунйт срелстаом, еще более соаерщенным, более точным и ясным... Ут.И.Лобачеескиб Глава 1 ОСНОВЫ МНОГОСОРТНЫХ МНОЖЕСТВ 31.1. Мнажествот функция, операция. Способы заданий Любое понятие дискретной математики можно определить с помощью понятия множества. Под инолсесптвом понимают объединение в одно общее объектов, хорошо различаемых нашей интуицией или нашей мыслью. Таково интуитивное определение понятия множества, данное основателем теории множеств Георгом Кантором. Это понятие является в математике первичным и, следовательно, не имеет строгого определения.

Объекты, которые образуют множество, будем называть элеиекталеи множества и обозначать, как правило, малыми буквами латинского алфавита.' Если элемент тп принадлежит множеству М, то будем использовать запись пт б М, в противном случае используем запись уп ф М; знак б принадлежности элемента множеству является стилизацией первой буквы греческого слова бота (есть, быть). Множество, содержащее конечное число элементов, называется кокечнын. Если же множество не содержит ни одного элемента, то оно называется пдсптыи и обозначается Э.

Множество может быть задано различными способами: перечислением элементов (конечные множества) или указанием их свойств (при этом для задания множеств используют фигурные скобки), Например, множество М цифр десятичного алфавита можно задать в виде М = 10, 1,..., 9) или М = 1т/ т целое, О < т < 9), где справа от наклонной черты указано свойство элементов этого множества. Множество М четных чисел можно записать в виде М = 1тп/ тп — четное число).

Множество М' называется подмножеством множества М (М' включено в М) тогда и только тогда, когда любой элемент множества М' принадлежит множеству М: М~ С М Ф+ (тп б Мм -+ пт б М) или М~ С М бр М' = (т~/ пт1 б М); здесь С вЂ” знак включения подмножества; а -+ Ь означает: если а, то Ь; а б+ Ь означает: Ь, если и только если а, В частном случае множества М' н М могут совпадать. 14 Гл.1.

Основы многосортных множеств 61,1, Множество, функция, внерация. Способы задания 15 МфМ. Невключение подмножества М' в множество М обозначается Очевидно, что если множество М, — подмножество множества Мь и множество Мь — подмножество множества М„то оба этих множества состоят из одних и тех же элементов. Такие множества называются равными: М, = Мь.

Если же множество М' — под- мнолсество множества М, а множество М не является по м ством множества М, то множество М называется собственкым ! ! подмножеством множества М; запись: М' СС М. кото Для каждого множества М существует множество элем н е тами рого являются подмножества множества М, и только они. Та- кое множество будем называть 'семейством множества М или булгаком этого множества и обозначать В(М), а множество М бу- дем называть укивгреальным, универсумом или пространством При рассмотрении различных подмножеств и нх свойств часто приходится обращаться к комбинаторике — разделу дискретной математики, посвященному решению задач выбора и расположе- ния элементов некоторого, как правило, конечного множества в соответствии с заданными свойствами, Каждое такое свойство определяет способ построения некото- рой конструкции из элементов множества, называемой комбика- торкой кокуУигурацигй.

Простейшими комбинаторными конфи- гурациями являются размещения, перестановки и сочетания. Размещение А(п, К) мощности К из п элементов (К ( п)— это любая последовательность (т. е. множество с зафиксирован- ным в нем порядком элементов) попарно различных К элемен- тов, взятых из п элементов; для записи размещений использ ются круглые скобки. Первый элемент последовательности можно зафиксировать и способами, второй элемент — п — 1 способами н т.

д. К-й н т. д., - эле- мент — п — К+ 1 способами. Следовательно, количество таких и — 1,...,п — К+1: последовательностей (размещений) равно произведению чисел п, К-1 ~А( КИ='(.— )" (.-К+ )=П( — ) В зло этой конфигурации важен как состав элементов, так и их по- рядок. Размещение при К = и называется перестановкой Р(п). Чи- сло перестановок )Р(п)~ из п элементов есть н-1 П(п — 1)=п (п — 1) ... 2 1=иС 1=0 Сочетанием С(п, К) мощности К из п элементов называется любое подмножество, содержащее К элементов, набранных из п элеме лементов. В сочетании важен только состав элементов, порядок же не играет роли. Очевидно, что числа размещений из и по К, содержащих одни и те же К элементов, равно К!, так как эти размещения отличаются друг от друга только порядкам. Такие размещения соответствуют одному сочетанию.

Следовательно, число сочетаний из и по К элементов есть !А(и, К) ~ п! Р(К) ( — К)! К.' Это числа, кстати, равно К-му коэффициенту в разложении бинома Ньютона (а+ 6)". Рассмотрим образование булеана В(1) от универсума 1 = (у, х, а). Первым множеством является пустое множество Я, не содержащее ни одного элемента. Образуем затем ( ь ) — число саче- г!ь!~ таний из !1! по 1 — множеств, содержащих по одному элементу, затем образуем Ц) множеств, содержащих по два элемента, и т.

д., наконец, образуем множество, содержащее все элементы множества 1. Здесь |1~ — количество элементов конечного множества 1, в дальнейшем называемое мощностлью множества. Очевидна, что мощность !В(1)! булеана от универсума 1 равна 2!ь!: !В(1)1 = 2!~!. В рассматриваемом случае В(1) = (Я, (у), (х), (а), (у, х), (а, х), (а, у), (у, х, а) ). Множество также часто задают графически с помощью диаграмм Эйлера. Например, задание множества ((а, 6, с), (6, д, г)) в пространстве 1 = (а, 6, е, д, г) приведено на рис. 1.1, где замкнутые линии, называемые в дальнейшем кругами Эйлера, ограничивают элементы множест- О О ва, при эхом рамка, в верхнем правом углу которой стоит 1, ограничивает элементы пространства. Другие способы задания множеств будут рассмотрены по мере Рнс.

1.1 необходимости. Одним из важнейших понятий теории множеств является понятие декартова произведения множеств. Декартовым произведением М, х Мь множеств М, и Мь называется множество вида М = ((т;, т )/ т; б М„т к Мь). Гп. 1. Основы многосорзаныт мноокесазв 16 21.1. Мнозкесазво, функция, операция. Способы гадания 17 Подмножество, Г С Мь х М называется функцией, если для каждого элемента х б Ма найдется не более одного элемента у б М„вида (у, х) к Г, при этом функция называется всюду (полностью) определенной; в противном случае функция называется частично определенной (нсдооиределскной).

Множество М образует область определения функции Г, множество ̄— область значений функции Г. Часто вместо записи (у,х) б Г используют запись у = Г(х); при этом элемент х называют аргументом или исрс.ценной, а у — значением функции Г. Сопоставим с декартовым произведением двух множеств прямоугольную решетку, узлы которой взаимно однозначно соответствуют элементам декартова произведения. Подмножество декартова произведения на рисунках будем отмечать зачернением соответствующих элементов. Пример 1.1.

На рпс. 1.2,о пвобравзепо подмпокество деаартова пропввеление зов»веста Мз = (рз, уз, рз, р»1 и М» = (тз, яз, хз), пе явпаюзпеес~ у о- узО- у О— 4 уз О-- уз О-- уО- ! ро†! О Х! 11о— 3 Ь О дз з О Ь О х! яз тз Ь Ь дз "з О т, Рпс. 1.2 а М1 хМ2х ° ° ° хМа=пМ1 з=1 множеств М1, Мз, ..., М„называется множество М = ((т;„т;„..., уи;„) / пз!! б М1, т;, б Мз,..., т;„б М„). Элементами декартова произведения М1 х М2 х ... х М„ являются всевозможные последовательности, каждая из которых фупвппей, па рпс. 1.2,б — подмножество, явюпоазееся полностью определенной фунвппей, на рпс.