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

В нем не большетрёх нулей (по построению), следовательно, V отстоит от (1, 1, …, 1) не более чем на 3 ипринадлежит K2.Следствие: Алгоритм «Кора» не сможет дать ответ ни для какого входного вектора, т.к. несможет найти ни одной тройки столбцов и тройки чисел, позволяющих отличить одинкласс от другого.В обучающей таблице класс представлен объектами (0,0,…,0,0) и (1,1,…,1,1), а класс –Задача 19объектами (1,0,1,0,…) и (0,1,0,1…). Тестовый объект имеет вид m1,1,… ,1, no0,0,…oq0,0r.К какомуnopoqopoклассу будет отнесен этот объект алгоритмом «Кора» при четном и нечетном n?[тут сомнительное место в условии. Мы его подправили, сообразуясь с логикой]Решение:Считаем, что n = 2k.

В тестовом объекте k нулей и k единиц.В случае k = 2t получаем:••количество троек, совпадающих с K1 : Г1 = s s s s 2. При этом выбирается 1чётная и 2 нечётных позиции из 1-й половины вектора; 2 чётных и 1 нечётная из первой;умножаем на 2, поскольку можем выбирать также из второй половины.количество троек, совпадающих с K2 Г2 = s s s s 2.

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

То есть выигрывает второй.Задача 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 |#| 0,иначеКол-во голосов для заданной строки:Г ! NωS, ωSiΩЗдесь Ω – множество векторов вида (u1 … ul) – подмножеств векторов номеровстолбцов, в которые входят столбцы 1..r и не входят (r+1)..kИтоговое количество голосов за класс Kj : так как xij для (i, j) != (1, 1) равно нулю, лишниеслагаемые убираются, и остаетсяГ ! NωS, ωS :౟ ౠДоказать, что матрица Φ Φ v w при x y .Упражнение 1Дополним матрицу Φ v w до квадратной нулевыми строками:Решение:z ' Φ*Φ{0Тогда:z Φ |0ΦПроизведение полученных матриц в точности совпадает с исходным:z Φz Φ ΦΦоднако они являются квадратными, значит, можем воспользоваться свойством определителя:}~ } · }~z Φz также является вырожденной.z иΦz матрица ΦВ силу вырожденности матриц Φ.