2010 Задачи к экзамену по курсу МОТП. Решение v2 (1185264), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

н. ф. ] 4 4 … 4ೖ , где индексы  , … , ೖ k всевозможные комбинации,удовлетворяющие условиям:Решение:1) 0 w  w ^ w ೖ w 2) Среди  нет трёх подряд идущих чисел (считая, что индексы  и ೖ присутствуютвсегда).3)  k  x 2, 0, 1, … , 1,  0, ೖ 1 .Очевидно, если д.н.ф. = 1, то все уравнения системы будут выполняться. Действительно, в д.н.ф.найдётся конъюнкт К = 4 4 … 4ೖ 1, у которого индексы  , … , ೖ удовлетворяют условиям 1)3). Из условия 3) сразу же следует выполнимость каждого уравнения системы.Осталось показать, что д.н.ф. - тупиковая.

Поскольку правило склейки неприменимо (нетотрицаний переменных), все конъюнкты различны и правило поглощения не применимо, то потеореме Блейка-Квайна д.н.ф. является максимальной. Невозможность применить правилапоглощения (K V K*K’ => K) следует из того, что характеристические вектора наборов индексовразличных конъюнктов несравнимы между собой. Под характеристическим вектором конъюнктапонимается булев вектор, где 1 стоят на тех (и только тех) местах, которые соответствуют номераминдексов переменных, входящих в этот конъюнкт. А несравнимы они потому, что при добавлениихотя бы одной новой единицы в характеристический вектор какого-либо конъюнкта приведёт кнарушению свойства 2).Значит построенная таким образом д.н.ф.

является тупиковой д.н.ф.,ч.т.дЗадача 18В обучающей таблице класс K1 состоит из всех векторов, принадлежащих шару радиуса 3 сцентром в (0, 0, …, 0), а класс K2 состоит из всех векторов, принадлежащих шару радиуса 4с центром в (1, 1, …, 1). К какому классу будет отнесен объект (0, 1, 0, …, 1) алгоритмом«Кора», если n – четное?Решение:Утверждение: Для любого набора из 3 столбцов (i1, i2, i3) и любой тройки чисел (k1, k2, k3)можно найти такой вектор U из K1 и V из K2, что Ui1 = Vi1 = k1, Ui2 = Vi2 = k2, Ui3 = Vi3 = k3.Доказательство:1)Для класса K1: берём вектор U : Ui = kj для i = ij и Ui = 0 для остальных i. В нем не большетрёх единиц (по построению), следовательно, U отстоит от (0, 0, …, 0) не более, чем на 3 ипринадлежит K1.2)Для класса К2: берём вектор V : Vi = kj для i = ij и Ui = 1 для остальных i.

В нем не большетрёх нулей (по построению), следовательно, V отстоит от (1, 1, …, 1) не более чем на 3 ипринадлежит K2.Следствие: Алгоритм «Кора» не сможет дать ответ ни для какого входного вектора, т.к. несможет найти ни одной тройки столбцов и тройки чисел, позволяющих отличить одинкласс от другого.В обучающей таблице класс представлен объектами (0,0,…,0,0) и (1,1,…,1,1), а класс –Задача 19объектами (1,0,1,0,…) и (0,1,0,1…). Тестовый объект имеет вид y1,1,… ,1, z{0,0,…{}0,0~.К какомуz{|{}{|{классу будет отнесен этот объект алгоритмом «Кора» при четном и нечетном n?[тут сомнительное место в условии.

Мы его подправили, сообразуясь с логикой]Решение:Считаем, что n = 2k. В тестовом объекте k нулей и k единиц.В случае k = 2t получаем:••количество троек, совпадающих с K1 : Г1 =     2. При этом выбирается 1чётная и 2 нечётных позиции из 1-й половины вектора; 2 чётных и 1 нечётная из первой;умножаем на 2, поскольку можем выбирать также из второй половины.количество троек, совпадающих с K2 Г2 =     2. При этом выбирается 1чётная позиция из первой половины, 2 чётных – из второй; 2 чётных из первой, 1 - извторой; умножаем на 2, поскольку можем заменить чётные позиции на нечётные.В итоге, получаем равенство голосов и объект не будет отнесён ни к какому классу.В случае k = 2t+1 получаем:••    2. (Здесь выбираемколичество троек, совпадающих с K1: Г1 = индексы как и в случае k = 2t).

количество троек, совпадающих с K2: Г2 =         . (Здесь выбираем аналогично случаю k = 2t, только при выборе из второй половинывместо чётных позиций берём нечётные (поскольку k = 2t+1)).Г1 1 1 k 1Г2 1 k 1 В итоге, Г1 – Г2 k 1 k 1 k2. То есть выигрывает второй.Задача 20Написать формулу для числа голосов в алгоритме вычисления оценок, если функцияблизости определяется параметрами ε1, …, εn, допустимое число невыполняющихсянеравенств q = 3, а совокупность характеристических векторов опорных множествобразует интервал конъюнкции x &. .

. &x &x&. … &xРешение:[теория – см. лекции Журавлёва, 2008, стр 16..18. Обозначения взяты оттуда же]Предположим (иное не указано в условии), что веса всех признаков и экземпляровклассов одинаковы ( =1 ) . Количество выполнившихся неравенств:NωS, ωS |||aౠ a౟ | ε Индикатор близости векторов по заданному множеству столбцов:NωS, ωS 1, N ωS, ωS |ω| 0,иначеКол-во голосов для заданной строки:Г ! NωS, ωSiΩЗдесь Ω – множество векторов вида (u1 … ul) – подмножеств векторов номеровстолбцов, в которые входят столбцы 1..r и не входят (r+1)..kИтоговое количество голосов за класс Kj :Г ! NωS, ωS :౟ ౠЗадача 21В алгоритме вычисления оценок x11 = 1; x10 = x01 = x00 = 0. Написать формулу для числаголосов, если функция близости определяется параметрами ε1, …, εn, допустимое числоневыполняющихся неравенств равно q, а система опорных множеств состоит из всехподмножеств мощности 2q.Решение:[теория – см.

лекции Журавлёва, 2008, стр 16..18. На стр 17 есть странная фраза про «легковидеть» и q/2, что заставляет подозревать здесь где-то подколку]Фактически, задача сводится к предыдущей с минимальными изменениями.Предположим (иное не указано в условии), что веса всех признаков и экземпляровклассов одинаковы ( =1 ) .Количество выполнившихся неравенств:NωS, ωS |aౠ a౟ | ε Индикатор близости векторов по заданному множеству столбцов:NωS, ωS 1, N ωS, ωS 2 0,иначеКол-во голосов для заданной строки:Г ! NωS, ωSiΩЗдесь Ω – множество векторов вида (u1 … ul) – подмножеств векторов номеровстолбцов, каждый вектор длины 2qИтоговое количество голосов за класс Kj : так как xij для (i, j) != (1, 1) равно нулю, лишниеслагаемые убираются, и остаетсяГ ! NωS, ωS :౟ ౠДоказать, что матрица Φ Φ ‚ ƒ при „ … .Упражнение 1Дополним матрицу Φ ‚ ƒ до квадратной нулевыми строками:Решение:† ' Φ*Φ‡0Тогда:† Φ ˆ0ΦПроизведение полученных матриц в точности совпадает с исходным:† Φ† Φ ΦΦоднако они являются квадратными, значит, можем воспользоваться свойством определителя:‰Š ‰ · ‰Š† Φ† также является вырожденной.† иΦ† матрица ΦВ силу вырожденности матриц Φ.

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

Список файлов ответов (шпаргалок)