Лекции по прикладной алгебре. v2.0 (1127112), страница 28
Текст из файла (страница 28)
12.Z3 ,J(Z3 )Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решётокВ конечных дистрибутивных решётках важную роль играют неатомы (например, в конечной цепи всего один атом), анеразложимые в объединение элементы.391 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решётокВ конечных дистрибутивных решётках важную роль играют неатомы (например, в конечной цепи всего один атом), анеразложимые в объединение элементы.ОпределениеЭлемент z 6= o решётки назовём неразложимым, если изz = x t y следует либо z = x, либо z = y.391 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решётокВ конечных дистрибутивных решётках важную роль играют неатомы (например, в конечной цепи всего один атом), анеразложимые в объединение элементы.ОпределениеЭлемент z 6= o решётки назовём неразложимым, если изz = x t y следует либо z = x, либо z = y.Пример123Атомы любой решётки неразложимы, и в атомной булевойалгебре нет других неразложимых элементов.В решётке h N, | i неразложимы в точности степенипростых чисел.В цепи ни один элемент не является разложимым.391 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решёток...ЛеммаВ конечной решётке каждый ненулевой элемент может бытьпредставлен в виде объединения неразложимых элементов.392 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решёток...ЛеммаВ конечной решётке каждый ненулевой элемент может бытьпредставлен в виде объединения неразложимых элементов.ДоказательствоЕсли элемент b неразложим, то b = b t b.
Пусть b = b1 t b2 иb1 6= b 6= b2 .Если и b1 , и b2 неразложимы, то лемма доказана.В противном случае представляем b1 и/или b2 в видеобъединения строго содержащихся в них элементов, и т.д.В силу конечности решётки указанный процесс закончится,и исходный элемент b будет представлен в видеобъединения неразложимых элементов.392 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиПредставление произвольных элементов решётки черезнеразложимыеОбозначения для подмножеств элементов(дистрибутивной) решётки LIrr L — множество неразложимых в объединениеэлементов L;Irr(x) = { y ∈ Irr L | y 6 x } — множество неразложимыхэлементов L, содержащихся в x.393 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки393 / 432Представление произвольных элементов решётки черезнеразложимыеОбозначения для подмножеств элементов(дистрибутивной) решётки LIrr L — множество неразложимых в объединениеэлементов L;Irr(x) = { y ∈ Irr L | y 6 x } — множество неразложимыхэлементов L, содержащихся в x.Доказанная лемма утверждает, что в конечной решётке каждыйненулевой элемент x допускает представление:Gx =a.a ∈ Irr(x)Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиИзоморфизм ч.у.
множества и неразложимых элементоврешётки его порядковых идеаловЛеммаЕсли P — ч.у. множество, то Irr J(P) ∼= P.394 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки394 / 432Изоморфизм ч.у. множества и неразложимых элементоврешётки его порядковых идеаловЛеммаЕсли P — ч.у. множество, то Irr J(P) ∼= P.ДоказательствоПусть P — ч.у. множество и тогда J(P) — дистрибутивнаярешётка его порядковых идеалов.
Порядковый идеал решёткинеразложим, iff он является главным:xO ⇒ Irr J(P) ∼= J0 (P) = { xO | x ∈ P }.Ранее был установлен изоморфизм между ч.у. множеством исовокупностью его главных идеалов:ϕ : P → J(P ),поэтому P ∼= J0 (P ) = Irr J(P ).ϕ(x) = xO ,Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки395 / 432Irr J(P) ∼= P: примерcO[[[a[[[b[[[ {a, b}OcbaOO∅Рис. 13.Z3 ,множество Irr J(Z3 ) выделеноПрикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиФундаментальная теорема о конечных дистрибутивныхрешёткахТеорема (ФТКДР, Г.
Биркгоф)Всякая конечная дистрибутивная решётка L изоморфнарешётке порядковых идеалов ч.у. множества её неразложимыхэлементов: L = J(Irr L)396 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решёткиФундаментальная теорема о конечных дистрибутивныхрешёткахТеорема (ФТКДР, Г. Биркгоф)Всякая конечная дистрибутивная решётка L изоморфнарешётке порядковых идеалов ч.у. множества её неразложимыхэлементов: L = J(Irr L)Доказательство (набросок)Пусть L = h L, t, u i — конечная дистрибутивная решётка иJ(Irr L) — решётка порядковых идеалов ч.у.
множества Irr L.Рассмотрим отображение ψ : L → J(Irr L) , ψ(x) = Irr(x).Отображение ψ есть биекция.x 6 y ⇔ Irr(x) ⊆ Irr(y) ⇔ ψ(x) ⊆ ψ(y).∴ ψ — (порядковый) изоморфизм между L и J(Irr L).396 / 432Прикладная алгебраАлгебраические решёткиМодулярные и дистрибутивные решётки397 / 432ФТКДР L = J(Irr L): иллюстрацияιOι[[[ι [a[ba [[[[[[ oРис. 14.aLObIrr L[[[b[[[ {a, b}OcO∅J(Irr L)Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды398 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств399 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать400 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи401 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи1Множество объектов X разделено на несколько подмножеств(классов).401 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи1Множество объектов X разделено на несколько подмножеств(классов).2Информация о таком разбиении содержится только в указаниио принадлежности к данным классам элементов конечнойобучающей последовательности (выборки) из X , элементыкоторой называют прецедентами.401 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи1Множество объектов X разделено на несколько подмножеств(классов).2Информация о таком разбиении содержится только в указаниио принадлежности к данным классам элементов конечнойобучающей последовательности (выборки) из X , элементыкоторой называют прецедентами.3Объекты имеют описание на некотором формальном языке,указывающем степень обладания объектами конечным числомпризнаков из множества M = {x1 , .
. . , xn }.401 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: пространство объектовРис. 15. Информационная модель классификации402 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: признаковая матрицаЧасто используется описание в виде объектно-признаковой(0, 1)-матрицы M, в которой объектам соответствуют строки,признакам — столбцы, а элементы матрицы кодируютналичие/отсутствие признаков у объектов.Класс KiОбъект 1Объект 2Объект 3...Объект mix1101...0x2011...1..................xn110...0— для каждого из классов K1 , .
. . , Ks , s > 2. Далее s = 2.403 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: язык описания и решающее правилоЗадача обученияПо матрице M сформулировать решающее правило, котороепо описанию нового объекта из X указывало бы имя класса,его содержащего.404 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: язык описания и решающее правилоЗадача обученияПо матрице M сформулировать решающее правило, котороепо описанию нового объекта из X указывало бы имя класса,его содержащего.Решающее правило должно максимизировать некоторойфункционал, определяющей качество классификации.404 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: язык описания и решающее правилоЗадача обученияПо матрице M сформулировать решающее правило, котороепо описанию нового объекта из X указывало бы имя класса,его содержащего.Решающее правило должно максимизировать некоторойфункционал, определяющей качество классификации.Таким функционалом в подавляющем числе случаев являетсяминимум (не абсолютный!) числа ошибок классификации,однако может также учитываться, например, и доля отказов.404 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: подходы к решению задачиметрические методы (NN, ...);разделяющие поверхности (SVM, ...);потенциальные функции;логические методы;коллективные решающие правила (области компетенции,голосование, алгебраический подход);структурные методы;...реляционный подход (АФП (FCA), ...)405 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: подходы к решению задачиметрические методы (NN, ...);разделяющие поверхности (SVM, ...);потенциальные функции;логические методы;коллективные решающие правила (области компетенции,голосование, алгебраический подход);структурные методы;...реляционный подход (АФП (FCA), ...)Wille R., Ganter B.
Formal concept analysis. Berlin; Heidelberg;New York: Springer-Verl., 1999.405 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииСоответствия Галуа: определениеДалее запись отображений:f (a) записывается как af ,f (A) записывается как f A .406 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииСоответствия Галуа: определениеДалее запись отображений:f (a) записывается как af ,f (A) записывается как f A .ОпределениеПусть P и Q — ч.у. множества.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
