Главная » Просмотр файлов » Диссертация

Диссертация (1137435), страница 7

Файл №1137435 Диссертация (Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств) 7 страницаДиссертация (1137435) страница 72019-05-20СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Аналогично, 2 * 1 . Следовательно, 1 ∩ 2 – замкнуто и ′′ ⊆ 1 ∩ 2 , что невозможно. Поскольку |J|равно числу псевдосодержаний, мы получили, что для каждой импликации → ∈ J найдется ровно псевдосодержание такое, что ⊆ и * . Рассмотрим любую импликацию → ∈ J и соответствующее ейпсевдосодержание . Если квазизамыкание = не совпадает с , то ⊆ (т.к. каждое псевдосодержание квазизамкнуто), но ′′ = ′′ * иследовательно = .С другой стороны, для любого базиса импликаций J замена импликации → ∈ J на импликацию ∖(→) → никак не влияет на45систему замыканий, которую задает этот базис. Таким образом мы показали, что базис импликаций J минимален тогда и только тогда, когдадля любой импликации → ∈ J квазизамыкание посылки являетсяпсевдосодержанием и у различных импликаций квазизамыкания посылокразличны.2.3.Функциональные зависимости и импликацииРассмотрим многозначный контекст K(, , , ).

Признак на-зывается полным, если для любого объекта ∈ , найдется ∈ такое, что (, , ) ∈ . В терминах теории баз данных, многозначный контекст является отношением. Многозначный контекст называется полным,если все его признаки полны. Для полного многозначного контекста значение признака на объекте обозначается, как (), таким образом,(, , ()) ∈ .Функциональная зависимость → выполнена в полном многозначном контексте (, , , ), если каждая пара объектов , ℎ, ∈ : удовлетворяет условию(∀ ∈ () = (ℎ)) ⇒ (∀ ∈ () = (ℎ)).В [54] было показано, что для любого полного многозначного контекста K = (, , , ), можно построить формальный контекст K :=(2 (), , ), где 2 () – множество всех пар различных объектов из ,а определяется как{, ℎ} ⇔ () = (ℎ).46Тогда, множество ⊆ функционально зависимо от множества ⊆ в контексте K, если и только если в контексте K выполненаимпликация → .В работе [70] было показано обратное сведение: для формального контекста K = (, , ) можно построить многозначный контекст K такой,что импликация → выполнена тогда и только тогда, когда функционально зависимо от в K .

Для контекста K соответствующий многозначный контекст определяется, как K = (, , ∪ {×}, ), где длялюбого ∈ , ∈ () = , если не выполнено и () = ×, если.2.4.Распознавание псевдосодержанийВ этом разделе мы обсудим вычислительную сложность задачи рас-познавания псевдосодержания.Задача 1. Распознавание псевдосодержания (PI)ВХОД: Формальный контекст K = (, , ) и подмножество признаков ⊆ .ВОПРОС: Является ли псевдосодержанием контекста K?Чтобы доказать -трудность задачи PI, мы рассмотрим наиболееизвестную -полную задачу – выполнимость КНФ.Задача 2. Выполнимость КНФ (SAT)ВХОД: Булева КНФ формула (1 , . .

. , ) = 1 ∧ . . . ∧ ВОПРОС: Выполнима ли ?Рассмотрим произвольный вход задачи SAT – КНФ 1 , . . . , с пе-47ременными 1 , . . . , , где = (1 ∨ . . . ∨ ) (1 ≤ ≤ ) – дизъюнкциии ∈ {1 , . . . , } ∪ {¬1 , . . . , ¬ } (1 ≤ ≤ , 1 ≤ ≤ ) – некоторыеперемнные или их отрицания, называемые литералами. По этой КНФ мыпостроим контекст K = (, , ). Определим = {, 1 , . . . , , 1 , ¬1 , . . . , , ¬ , } = {1 , ¬1 , . . .

, , ¬ , , , 1 , . . . , }¬∪ { | 1 ≤ ≤ , 1 ≤ ≤ } ∪ {| 1 ≤ ≤ , 1 ≤ ≤ }Для 1 ≤ ≤ мы определим множества = {1 , ¬1 , . . . , , ¬ } ∖{ , ¬ }. Также для 1 ≤ ≤ и 1 ≤ ≤ мы определим множества¬ = ∖ { } и = ∖ {¬ }.Теперь мы готовы определить отношение .

Отношение состоит издвух частей. Первая часть определяется как: ∩ {1 , ¬1 , . . . , , ¬ } × = ∪ ℐ̸= = {( , ) | ∈/ , 1 ≤ ≤ , 1 ≤ ≤ }∪ {(¬ , ) | ¬ ∈/ , 1 ≤ ≤ , 1 ≤ ≤ }ℐ̸= = {1 , ¬1 , . . . , , ¬ } × {1 , ¬1 , . . . , , ¬ },∖ {(1 , 1 ), (¬1 , ¬1 ), . . . , ( , ), (¬ , ¬ )}следовательно ′ ∩ {1 , ¬1 , . . .

, , ¬ } это множество объектов, которые соответствуют не входящих в литералам (1 ≤ ≤ ), и ℐ̸= этоотношение контраноминальной шкалы. Остальная часть определяетсяобъектными содержаниями:′= ∖ {, }′ = {} ∪ {1 , . . . , }48′ = {} ∪ , 1 ≤ ≤ ′ = {} ∪ , 1 ≤ ≤ , 1 ≤ ≤ ¬ ′¬= {} ∪ , 1 ≤ ≤ , 1 ≤ ≤ Отметим, что у контекста K есть некоторые объекты с одинаковыми содержаниями (например 1 и 11 ), но это не важно.49 1 2 · · · 1 ¬1 · · · ¬ 1¬1...ℐ̸=× ······ ×× ············ ׬×1×111×1 11¬×1......1׬×1......× ······ ×1¬1...1 ¬1...×1×11¬×......׬×1¬...¬Таблица 2.1.

Контекст K.Для любого подмножества ⊆ {1 , ¬1 , . . . , , ¬ }, которое удо-50влетворяет условию ∩ { , ¬ } ̸= ∅ для 1 ≤ ≤ , мы определим Булевоназначение переменных :⎧⎪⎪⎪, if ∈/ and ¬ ∈ ;⎪⎪⎪⎨ ( ) = , if ¬ ∈/ and ∈ ;⎪⎪⎪⎪⎪⎪⎩ , otherwise ( ∈ and ¬ ∈ );В случае ∈/ и ¬ ∈/ для некоторого 1 ≤ ≤ , назначение не определено. Отметим, что для ⊆ {1 , ¬1 , . . . , , ¬ } Булевоназначение переменных (корректно) определено, если только если * для всех 1 ≤ ≤ .Симметрично, для назначения , определим множество = {¬ |( ) = } ∪ { | ( ) = }.Перед тем, как доказать -трудность задачи PI мы докажемнесколько вспомогательных утверждений. Следующая лемма являетсяключевой в SAT к дополнению задачи PI.Лемма 1.

Если подмножество ⊆ {1 , ¬1 , . . . , , ¬ } замкнуто и *′ для любого 1 ≤ ≤ , то – определено и выполняет т.е. ( ) =. С другой стороны, если назначение выполняет , то замкнуто и * ′ для всех 1 ≤ ≤ .Доказательство. Пусть ⊆ {1 , ¬1 , . . . , , ¬ } и не содержится нив одном ′ (1 ≤ ≤ ), тогда * для всех 1 ≤ ≤ и следовательно (поопределению ) корректно определено. Поскольку ℐ̸= это отношениеконтраноминальной шкалы и любое содержание может быть представленокак пересечение объектных содержаний, то мы получаем ′ = { | ∈/} ∪ {¬ | ¬ ∈/ } ∪ , где ⊆ − {1 , ¬1 , .

. . , , ¬ }. Поскольку51¬ * для любого 1 ≤ ≤ мы также получаем * и * длякаждого 1 ≤ ≤ и 1 ≤ ≤ . Таким образом, = { }.Допустим – замкнуто т.е. ′′ = . Тогда ∩ {1 , . . . , } = ∅ иследовательно для каждого 1 ≤ ≤ найдется некоторый объект ∈ ′′и ′ = { | ∈такой, что ∈/ ′ . Поскольку ∈ / } ∪ {¬ | ¬ ∈/} ∪ { } последнее означает, что ∈ { | ∈/ } ∪ {¬ | ¬ ∈/ }.Тогда, по определению отношения , существует литерал ∈/ или ¬ ∈/, который принадлежит дизъюнкции . Поэтому выполняет длявсех 1 ≤ ≤ .Теперь пусть – Булево назначение переменных и () = .Очевидно, * ′ для всех 1 ≤ ≤ (по определению ). Тогда ′ = { | ∈/ } ∪ {¬ | ¬ ∈/ } ∪ { }.

Заметим, что′′′ ∩ {1 , ¬1 , . . . , , ¬ } = ∩ {1 , ¬1 , . . . , , ¬ } и ⊆ . Сле-довательно замкнуто тогда и только тогда, когда ∩ {1 , . . . , } = ∅.Предположим, что ∈ ∩ {1 , . . . , } для некоторого 1 ≤ ≤ . Это′означает, что ∈ ′ и ∈ ¬для всех ∈/ и ¬ ∈/ .

Отсюдаи по определению отношения следует, что дизъюнкция не выполненапри назначении .2Утверждение 1. Если существует такое 1 ≤ ≤ , что ⊆ ′ , то замкнуто.⋂︀ ′Доказательство. Пусть ⊆ ′ и ∈ . Тогда ′′ = ∈/ ∩⋂︀¬ ′= . В случае когда ∈/ мы можем представить ′′ как¬ ∈/ ′′′ = ( ∪ {})′′ ∩ = .Теперь мы готовы доказать -трудность задачи PI.252Теорема 1.

Задача PI co -трудна.Доказательство. Мы сведем SAT к PI. По данному входу задачи SAT – = 1 ∧ . . . ∧ , мы построим контекст K, который был описан выше (см.Таблицу 2.1). Мы рассмотрим множество = ∖ {} как множество, прокоторое нужно узнать является ли оно псевдосодержанием. Таким образом,соответствующий вход задачи PI это (K, ) и нужно доказать, что КНФ выполнима тогда и только тогда, когда не является псевдосодержаниемконтекста K. Не ограничивая общности можно считать, что для любого1 ≤ ≤ дизъюнкция ∨ ¬ входит в (добавление таких дизъюнкцийне влияет на выполнимость).(⇒) Пусть выполнима и пусть – булево назначение переменных,которое выполняет т.е.

() = . Рассмотрим множество = {}∪ .Как мы позже увидим является псевдосодержанием, ⊂ и ′′ = * , а это значит, что – не может быть псевдосодержанием. Для началапроверим, что ′′ = . Поскольку ∈ нам следует проверить только,¬что * ′ , где ∈ { , 1 , .

. . , } ∪ { | 1 ≤ ≤ , 1 ≤ ≤ } ∪ {|1 ≤ ≤ , 1 ≤ ≤ }. Очевидно * ′ потому, что не пусто. ПоЛемме 1 для любого 1 ≤ ≤ , * ′ , поэтому * . Следовательно ′¬ ′ * и * (1 ≤ ≤ , 1 ≤ ≤ ). Для того, чтобы доказать,что является псевдосодержанием мы покажем, что любое собственноеподмножество замкнуто. Рассмотрим произвольное множество ⊂ .Если ∈ тогда (т.к. ̸= ) найдется литерал ∈ {1 , ¬1 , . . . , , ¬ }такой, что ∈ и ∈/ . Таким образом, по Утверждению 1 подмножество замкнуто. Теперь пусть ∈/ тогда, если = ∖ {} = поЛемме 1 подмножество замкнуто. Если ̸= ∖ {} тогда ⊂ и по53Утверждению 1 подмножество замкнуто.(⇐) Теперь пусть псевдосодержание является собственным подмножеством (т.е. ⊂ ) и ′′ * .

Характеристики

Список файлов диссертации

Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств
Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6381
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее