Диссертация (Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств), страница 2

Если ≤ ,то говорят, что элемент меньше, чем или равен ему. Если для несуществует , такого что ≤ , то называют максимальным элементом (относительно ≤).Если ≤ и ̸= , то пишут < и говорят, что строго меньше,чем .11Определение 1.2.

Пусть (, ≤) частично упорядоченное множество. Элемент ∈ называется соседом снизу элемента ∈ , если < и@ ∈ ( < < ). В этом случае называется соседом сверху (обозначается ⪯ ). Направленный граф отношения ⪯ называется графомпокрытия.Графически конечное частично упорядоченное множество (, ≤) может быть представлено с помощью диаграммы Хассе (или просто диаграм­мы [4]). Элементы изображаются в виде точек. Если ⪯ , то размещается “над” (вертикальная координата больше вертикальной координаты), и две точки соединяются линией.Определение 1.3.

Верхней гранью подмножества в упорядоченноммножестве называется элемент ∈ , такой что ≥ для всех ∈ .Точная верхняя грань множества (называемая также наименьшей верх­ней гранью или супремумом) множества (обозначается sup) есть верхняя грань такая, что ≤ 1 для любой верхней грани 1 подмножества .Двойственным образом (с заменой ≥ на ≤) определяется понятие точной(наибольшей) нижней грани или инфимума inf.Определение 1.4. Бинарная операция ⊓ : × → называется полуре­шёточной, если для некоторого ∈ и любых , , ∈ :1. ⊓ = (идемпотентность);2. ⊓ = ⊓ (коммутативность);3. ( ⊓ ) ⊓ = ⊓ ( ⊓ ) (ассоциативность);4. ⊓ = .12Для = {1 , . .

. , } ⊆ и ∈ N мы пишем ⊓ вместо 1 ⊓ . . . ⊓ .Если = {}, то ⊓ = .Определение 1.5. Множество с определённой на нем полурешёточнойоперацией ⊓ называется полурешёткой (, ⊓).Полурешёточная операция ⊓ задает два частичных порядка ⊑ и ⊒на (, ∈ ): ⊑ ⇔ ⊓ = и ⊒ ⇔ ⊓ = .Тогда множество с определённой на нем полурешёточной операцией (, ⊓)будем называть нижней полурешёткой (относительно частичного порядка⊑) и верхней полурешёткой (относительно частичного порядка ⊒).Определение 1.6.

Пусть (, ⊓) — полурешётка. Множество ⊆ называется системой замыканий[54] или семейством Мура[4] (относительно⊓), если ∀, ∈ ( ⊓ ∈ ).Очевидно, что система замыканий (относительно ⊓) с определённойна ней операцией, ∧ : × → и ∧ = ⊓ , образует полурешётку.Определение 1.7. Упорядоченное множество (, ≤) с определёнными нанем полурешёточными операциями ∧ и ∨ называется решёткой, если (, ∧)и (, ∨) являются, соответственно, нижней и верхней полурешётками (относительно ≤).Операции ∧ и ∨ называют операциями взятия точной нижней иверхней грани в решётке или инфимума и супремума, соответственно.Определение 1.8.

Подрешёткой решётки называется подмножество ⊂ такое, что если ∈ , ∈ , то ∧ ∈ и ∨ ∈ .13Полурешёточные операции ∧ и ∨ удовлетворяют в решётках следующему условию: ∧ ( ∨ ) = ∨ ( ∧ ) = (поглощение).Из любой конечной полурешётки можно получить решётку добавлением одного (максимального или минимального в зависимости от типаполурешетки) элемента.Решётка называется полной, если у каждого подмножества его элементов есть супремум и инфимум (всякая конечная решётка является полной).Определение 1.9. Интервал [, ] состоит из всех элементов ∈ , которые удовлетворяют неравенствам ≤ ≤ .

Порядковым фильтром(идеалом) решётки называется подмножество ⊂ такое, что если ∈ , ∈ и ≥ , то ∈ (соответственно, ∈ , ∈ и ≤ , то ∈ ).Элемент решётки называется инфимум-неразложимым или∧-неразложимым (или неразложимым в пересечение), если для любых ̸= и ̸= , не выполняется = ∧ . Элемент решётки называется супремум-неразложимым или ∨-неразложимым (или неразложимымв объединение), если для любых ̸= и ̸= , не выполняется = ∨ .Подмножество полной решётки называется инфимум-плотным,если = {∧∈ | ⊆ }, и супремум-плотным, если = {∨∈ | ⊆}).Определение 1.10.

Пусть (, ≤ ) и (, ≤ ) — частично упорядоченныемножества. Пара отображений : ↦→ и : ↦→ называется соответ­ствием Галуа между частично упорядоченными множествами (, ≤ ) и14(, ≤ ), если для любых ∈ и ∈ :1. 1 ≤ 2 ⇒ (2 ) ≤ (1 );2. 1 ≤ 2 ⇒ (2 ) ≤ (1 );3. ≤ (()) и ≤ (()).Приведённые условия эквивалентны одному: ≤ () ⇔ ≤() [4, 54].1.1.2.Анализ формальных понятийОпределение 1.11. Формальный контекст K есть тройка (, , ), где – конечное множество, называемое множеством объектов, – конечноемножество, называемое множеством признаков, ⊆ × – бинарноеотношение.Отношение интерпретируется следующим образом: для ∈ , ∈ имеет место , если объект обладает признаком .Для формального контекста K = (, , ) и произвольных ⊆ и ⊆ определена пара отображений:′ := { ∈ | для всех ∈ }, ′ := { ∈ | для всех ∈ },которые задают соответствие Галуа между частично упорядоченнымимножествами (2 , ⊆) и (2 , ⊆), а оператор (·)′′ является оператором за­мыкания на ∪˙ — дизъюнктном объединении и , т.е.

для произвольного ⊆ или ⊆ имеют место следующие соотношения [54]:1. ⊆ ′′ (экстенсивность),152. ′′′′ = ′′ (идемпотентность),3. если ⊆ , то ′′ ⊆ ′′ (изотонность).Множество называется замкнутым, если ′′ = [54].Определение 1.12. Формальное понятие формального контекста K =(, , ) есть пара (, ), где ⊆ , ⊆ , ′ = и ′ = . Множество называется объёмом, а — содержанием понятия (, ).Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.Множество формальных понятий контекста K, которое мы будем обозначать посредством B(, , ), частично упорядочено по вложению объёмов: формальное понятие = (, ) является менее общим (более част­ным), чем понятие = (, ), (, ) ≤ (, ), если ⊆ , что эквивалентно ⊆ ( — обобщение ).Подмножества произвольного множества, замкнутые относительнозаданной на нем операции замыкания, образуют полную решётку [4, 54].Множество всех понятий формального контекста K образует полную решётку [54].Определение 1.13.

Множество понятий контекста B(, , ) образуетрешётку B(, , ) := (B(, , ), ∧, ∨), где (1 , 1 ) ∧ (2 , 2 ) = (1 ∩2 , (1 ∩ 2 )′ ). и (1 , 1 ) ∨ (2 , 2 ) = ((1 ∩ 2 )′ , 1 ∩ 2 ). Такие решёткиназывают решётками понятий или решётками Галуа[54].Любая полная решётка изоморфна решётке понятий некоторогоформального контекста [54]. В качестве объектов этого контекста нуж-16но выбрать ∧-неразложимые элементы, а в качестве признаков — ∨неразложимые элементы исходной решётки.

Тогда объект в контекстебудет обладать признаком , если элемент решётки, соответствующий ,находится “под” элементом, соответствующим .Определение 1.14. Строчно- (столбцево-)редуцированным называетсятакой формальный контекст, в котором всякое объектное (признаковое)понятие является ∨-неразложимым (∧-неразложимым). Редуцированнымназывается формальный контекст, являющийся одновременно строчно- истолбцево-редуцированным.Определение 1.15. Пусть дан K = (, , ) — формальный контекст и, ⊆ , тогда выражение → называется импликацией (на мно­жествах признаков), если ′ ⊆ ′ (или ⊆ ′′ ), т.е. все объекты из ,обладающие множеством признаков , обладают также множеством признаков .Аналогичным образом определяются импликации на множествах объектов.

Наличие импликации → в контексте K соответствует тому, чтов диаграмме решётки B(K) формальное понятие (′ , ′′ ) находится нижеформального понятия ( ′ , ′′ ).Импликации формального контекста удовлетворяют аксиомам Армстронга [54] для произвольных , , :1. → ;2. Если → то ∪ → ;3. Если → и ∪ → то ∪ → .17Помимо определённых выше однозначных (one-valued) формальных контекстов в анализе формальных понятий изучаются многозначные(many-valued) контексты:Определение 1.16.

Многозначный формальный контекст есть четвёрка(, , , ), где , , — множества (объектов, признаков и значенийпризнаков, соответственно), а — тернарное отношение ⊆ × × ,задающее значение признака , причём:(, , ) ∈ и (, , ) ∈ влечёт = Многозначные признаки могут рассматриваться как отображения → , таким образом, можно обозначать () = вместо (, , ) ∈ .Процедура сведения многозначных контекстов к однозначным называется шкалированием (scaling). Для шкалирования каждый признак многозначного контекста представляется формальным контекстом, называемым шкалой.Определение 1.17. Шкала для признака многозначного контекста(, , , ) есть (однозначный) контекст S := ( , , ) такой, что() ⊆ . Объекты в шкале называются значениями шкалы, а признаки— признаками шкалы.В нашей работе для построения таксономии алгоритмов использовалось два варианта шкалирования — порядковое шкалирование и номиналь­ное шкалирование.

Порядковая шкала O := (, , ≤) используется дляпризнаков, значения которых упорядочены относительно некоторого порядка ≤, а обладание объектом некоторым значением признака влечёт обладание всеми меньшими значениями признака. С помощью номинальной18шкалы O := (, , =) представляют несравнимые между собой значенияпризнаков, например, цвет.Возможные виды шкалирования рассмотрены в [54].1.1.3.Теория алгоритмов и вычислительная сложностьУпотребляя понятия из данного раздела мы будем использовать определения из книги [55] и ее русского перевода [8].Одним из фундаментальных понятий теории вычислительной сложности является (массовая) задача, под которой понимается некоторый общий вопрос, на который следует дать ответ. Обычно задача содержитнесколько параметров или свободных переменных, конкретные значениякоторых не определены.

Задача Π определяется следующей информацией:(1) общим списком всех ее параметров(2) формулировкой тех свойств, которым должен удовлетворять от­вет или, другими словами, решение задачи.Индивидуальная задача получается из массовой задачи Π, если всемпараметрам задачи присвоить конкретные значения.Теория NP-полных задач строится только для задач разрешениясвойств (decision problems). Такие задачи имеют только два возможныхрешения - “да” или “нет”.