Антиматроид как система в которых множество создается включением элементов по одному за раз

Привет, Вы узнаете о том , что такое антиматроид , Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое антиматроид , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

В математике антиматроид — это формальная система , описывающая процессы, в которых множество создается путем включения элементов по одному за раз, и в которых элемент, однажды доступный для включения, остается доступным до тех пор, пока он не будет включен Антиматроиды обычно аксиоматизируются двумя эквивалентными способами : либо как система множеств, моделирующая возможные состояния такого процесса, либо как формальный язык, моделирующий различные последовательности, в которые могут быть включены элементы. Дилворт (1940) был первым, кто изучал антиматроиды, используя еще одну аксиоматизацию, основанную на теории решеток , и они часто открывались заново в других контекстах.

Аксиомы, определяющие антиматроиды как системы множеств, очень похожи на аксиомы матроидов , но в то время как матроиды определяются аксиомой обмена , антиматроиды определяются аксиомой антиобмена , от которой и происходит их название. Антиматроиды можно рассматривать как частный случай гридоидов и полумодулярных решеток , а также как обобщение частичных порядков и дистрибутивных решеток . Антиматроиды эквивалентны, по дополнению , выпуклым геометриям , комбинаторной абстракции выпуклых множеств в геометрии .

Антиматроиды применялись для моделирования ограничений предшествования в задачах планирования , потенциальных последовательностей событий в симуляциях, планирования задач в искусственном интеллекте и состояний знаний обучающихся людей.

Три представления антиматроида: включение порядка в его семейство допустимых множеств, формальный язык и соответствующий путь частично упорядоченного множества.

Антиматроид можно определить как конечное семейство конечных множеств, называемых допустимыми множествами , со следующими двумя свойствами:

• Объединение любых двух допустимых множеств также допустимо. То есть, закрыто профсоюзами .
• Если — непустое допустимое множество, тогда содержит элемент для которого (набор, образованный путем удаленияхот ) также осуществимо. То есть, является доступной системой множеств .

Антиматроиды также имеют эквивалентное определение как формальный язык , то есть как набор строк, определенных из конечного алфавита символов . Строка, которая принадлежит этому набору, называется словом языка. ЯзыкЛОпределение антиматроида должно удовлетворять следующим свойствам:

• Каждый символ алфавита встречается по крайней мере в одном словеЛ.
• Каждое слово содержит не более одной копии каждого символа. Язык с таким свойством называется нормальным . [
• Каждый префикс слова в также в . Язык с таким свойством называется наследственным .
• Если и есть слова в , и содержит по крайней мере один символ, которого нет в , то есть символхвСтаким образом, что конкатенация это еще одно слово в .

Эквивалентность этих двух форм определения можно увидеть следующим образом. Если является антиматроидом, определяемым как формальный язык, тогда наборы символов в словах образуют доступную систему множеств, замкнутую на объединение. Она доступна по наследственному свойству строк, и можно показать, что она замкнута на объединение повторным применением свойства конкатенации строк. В другом направлении, из доступной системы множеств, замкнутой на объединение , язык обычных строк, все префиксы которых имеют наборы символов, принадлежащих соответствует требованиям формального языка, чтобы быть антиматроидом. Эти два преобразования являются инверсиями друг друга: преобразование формального языка в семейство множеств и обратно, или наоборот, производит одну и ту же систему. Таким образом, эти два определения приводят к математически эквивалентным классам объектов.

Последовательность оболочек плоского множества точек. Отрезки линий показывают края выпуклых оболочек после удаления некоторых точек.

Примерами антиматроидов являются следующие системы:

Цепные антиматроиды

Префиксы одной строки и наборы символов в этих префиксах образуют антиматроид. Например, цепной антиматроид, определяемый строкой имеет в качестве своего формального языка набор строк (где обозначает пустую строку ) и как ее семейство допустимых множеств семейство }.

Посет антиматроиды

Нижние множества конечного частично упорядоченного множества образуют антиматроид, при этом полные слова антиматроида образуют линейные расширения частичного порядка. ] По теореме Биркгофа о представлении для дистрибутивных решеток допустимые множества в антиматроиде частично упорядоченных множеств (упорядоченном по включению множеств) образуют дистрибутивную решетку, и все дистрибутивные решетки могут быть образованы таким образом. Таким образом, антиматроиды можно рассматривать как обобщения дистрибутивных решеток. Цепной антиматроид является частным случаем антиматроида частично упорядоченных множеств для полного порядка .

Обстрел антиматроидов

Последовательность обстрела конечного множества точек на евклидовой плоскости или многомерном евклидовом пространстве формируется путем многократного удаления вершин выпуклой оболочки . Допустимые множества антиматроида, образованные этими последовательностями, являются пересечениями с дополнением выпуклого множества.

Идеальное устранение

Совершенное исключение порядка хордового графа — это упорядочение его вершин, такое, что для каждой вершиныв, соседивкоторые происходят позже, чем в упорядочении образуют клику . Префиксы совершенных элиминационных упорядочений хордового графа образуют антиматроид

Игры с запуском чипов

Игры со стрельбой фишками, такие как модель абелевой песочной кучи, определяются направленным графом вместе с системой «фишек», размещенных на его вершинах. Всякий раз, когда число фишек на вершиневпо крайней мере, столько же, сколько и число ребер из , можно стрелять , перемещая одну фишку в каждую соседнюю вершину. Событие, которое пожары для th время может произойти только если оно уже выстрелило раз и накоплено ⋅ общее количество чипов. Эти условия не зависят от порядка предыдущих срабатываний и остаются верными до тех пор, покавсрабатывает, поэтому любой заданный граф и начальное размещение фишек, при котором система завершает работу, определяет антиматроид на парах . Следствием антиматроидного свойства этих систем является то, что для заданного начального состояния количество срабатываний каждой вершины и конечное устойчивое состояние системы не зависят от порядка срабатывания

В теоретико-множественной аксиоматизации антиматроида существуют определенные специальные множества, называемые путями , которые определяют весь антиматроид, в том смысле, что множества антиматроида являются в точности объединениями путей. Если любой возможный набор антиматроида, элемент которые можно удалить из для формирования другого допустимого множества называется конечной точкой , а допустимый набор, имеющий только одну конечную точку, называется путем антиматроида. Об этом говорит сайт https://intellect.icu . Семейство путей может быть частично упорядочено включением множеств, образуя частично упорядоченный набор путей антиматроида.

Для каждого допустимого набора в антиматроиде, и каждый элемент хиз , можно найти подмножество путей для которого является конечной точкой: для этого удаляйте по одному элементу за раз, кромехпока ни одно из таких удалений не оставит допустимого подмножества. Таким образом, каждое допустимое множество в антиматроиде является объединением его подмножеств путей. Если не является путем, каждое подмножество в этом объединении является собственным подмножеством . Но, еслиСсам по себе является путем с конечной точкойх, каждое собственное подмножество что принадлежит антиматроиду исключаетх. Таким образом, пути антиматроида — это в точности допустимые множества, которые не равны объединениям их собственных допустимых подмножеств. Эквивалентно, заданное семейство множеств образует семейство путей антиматроида тогда и только тогда, когда для каждого в , объединение подмножеств в имеет на один элемент меньше, чем сам по себе. Если так,Фсамо по себе является семейством объединений подмножеств .

В формальной языковой формализации антиматроида самые длинные строки называются базовыми словами . Каждое базовое слово образует перестановку всего алфавита. Если это набор основных слов,Лможно определить из как набор префиксов слов в .

ЕслиФэто система множеств, определяющая антиматроид, с равно объединению множеств в , то семейство множеств дополняющие наборы вФиногда называется выпуклой геометрией , а множества вГназываются выпуклыми множествами . Например, в антиматроиде оболочки выпуклые множества являются пересечениями заданного множества точек с выпуклыми подмножествами евклидова пространства. Система множеств, определяющая выпуклую геометрию, должна быть замкнута относительно пересечений. Для любого множестваСвГчто не равноУдолжен быть элементхне вСчто можно добавить кСчтобы сформировать другой набор в .

Выпуклая геометрия также может быть определена в терминах оператора замыкания τкоторый отображает любое подмножествоУк его минимальному замкнутому надмножеству. Чтобы быть оператором замыкания,τдолжен иметь следующие свойства:

• : замыкание пустого множества пусто.
• Для каждого подмножестваСизУ,Сявляется подмножеством и .
• В любое время , является подмножеством .

Семейство замкнутых множеств, полученное в результате операции замыкания этого типа, обязательно замкнуто относительно пересечений, но может не быть выпуклой геометрией. Операторы замыкания, определяющие выпуклые геометрии, также удовлетворяют дополнительной аксиоме антиобмена :

• Если является подмножеством , и и являются отдельными элементами которые не принадлежа , нозпринадлежит , затем не принадлежитτ .

Операция замыкания, удовлетворяющая этой аксиоме, называется антиобменным замыканием . Если является замкнутым множеством в замыкании антиобмена, то аксиома антиобмена определяет частичный порядок на элементах, не принадлежащихС, гдех≤ув частичном порядке, когда принадлежит . Еслихявляется минимальным элементом этого частичного порядка, тогда замкнуто. То есть семейство замкнутых множеств антиобменного замыкания обладает тем свойством, что для любого множества, отличного от универсального множества, существует элемент которые могут быть добавлены к нему для получения другого замкнутого множества. Это свойство является дополнительным к свойству доступности антиматроидов, а тот факт, что пересечения замкнутых множеств являются замкнутыми, является дополнительным к свойству, что объединения допустимых множеств в антиматроиде являются допустимыми. Следовательно, дополнения замкнутых множеств любого антиобменного замыкания образуют антиматроид.

Неориентированные графы, в которых выпуклые множества (подмножества вершин, содержащие все кратчайшие пути между вершинами в подмножестве) образуют выпуклую геометрию, являются в точности птолемеевыми графами .

Каждые два допустимых множества антиматроида имеют уникальную наименьшую верхнюю границу (их объединение) и уникальную наибольшую нижнюю границу (объединение множеств в антиматроиде, которые содержатся в них обоих). Таким образом, допустимые множества антиматроида, частично упорядоченные включением множеств, образуют решетку . Различные важные особенности антиматроида можно интерпретировать в терминах теории решеток; например, пути антиматроида являются неприводимыми относительно соединения элементами соответствующей решетки, а основные слова антиматроида соответствуют максимальным цепям в решетке. Решетки, которые возникают из антиматроидов таким образом, обобщают конечные дистрибутивные решетки и могут быть охарактеризованы несколькими различными способами.

• Описание, первоначально рассмотренное Дилвортом (1940), касается неприводимых к мэтчу элементов решетки. Для каждого элемента антиматроида существует единственный максимально допустимый набор хкоторый не содержитх:Схможет быть построено как объединение всех допустимых множеств, не содержащих . Этот набор автоматически является неприводимым к встрече, что означает, что это не встреча двух больших элементов решетки. Это верно, потому что каждое допустимое надмножество содержит , и то же самое, следовательно, справедливо для любого пересечения допустимых супермножеств. Каждый элемент произвольной решетки может быть разложен как встреча неприводимых к встрече множеств, часто несколькими способами, но в решетке, соответствующей антиматроиду, каждый элементТимеет уникальное минимальное семейство множеств, допускающих пересечения, пересечением которых являетсяТ; это семейство состоит из множествСхдля элементовхтакой что осуществимо. То есть, решетка имеет единственные неприводимые разложения .
• Вторая характеристика касается интервалов в решетке, подрешеток, определяемых парой элементов решетки. состоящий из всех элементов решетки Интервал является атомистическим , если каждый элемент в нем является объединением атомов (минимальных элементов выше нижнего элементах), и он является булевым , если он изоморфен решетке всех подмножеств конечного множества. Для антиматроида каждый интервал, который является атомистическим, также является булевым.
• В-третьих, решетки, возникающие из антиматроидов, являются полумодулярными решетками , решетками, которые удовлетворяют верхнему полумодулярному закону , согласно которому для каждых двух элементовхиу, еслиуобложки затем обложки . Переводя это условие в допустимые множества антиматроида, если допустимое множествоИимеет только один элемент, не принадлежащий другому допустимому множеству то этот один элемент может быть добавлен к для формирования другого множества в антиматроиде. Кроме того, решетка антиматроида имеет свойство meet-semidistributive : для всех элементов решетки , и , если и равны друг другу, то они также оба равны . Полумодулярная и полудистрибутивная решетка называется решеткой с дистрибутивным соединением .

Эти три характеристики эквивалентны: любая решетка с уникальными meet-неприводимыми разложениями имеет булевы атомистические интервалы и является join-дистрибутивной, любая решетка с булевыми атомистическими интервалами имеет уникальные meet-неприводимые разложения и является join-дистрибутивной, и любая join-дистрибутивная решетка имеет уникальные meet-неприводимые разложения и булевы атомистические интервалы. Таким образом, мы можем назвать решетку с любым из этих трех свойств join-дистрибутивной. Любой антиматроид порождает конечную join-дистрибутивную решетку, и любая конечная join-дистрибутивная решетка происходит из антиматроида таким образом. [ Другая эквивалентная характеристика конечных join-дистрибутивных решеток заключается в том, что они градуированы (любые две максимальные цепи имеют одинаковую длину), а длина максимальной цепи равна количеству meet-неприводимых элементов решетки. Антиматроид, представляющий конечную решетку с дистрибутивным соединением, может быть восстановлен из решетки: элементы антиматроида могут быть взяты как неприводимые к пересечению элементы решетки, а допустимое множество, соответствующее любому элементухрешетки состоит из множества неприводимых элементовутакой чтоуне больше или равнохв решетке.

Это представление любой конечной джойн-дистрибутивной решетки как доступного семейства множеств, замкнутых относительно объединений (то есть как антиматроида), можно рассматривать как аналог теоремы Биркгофа о представлении , согласно которой любая конечная дистрибутивная решетка имеет представление как семейство множеств, замкнутых относительно объединений и пересечений.

Мотивированный проблемой определения частичных порядков на элементах группы Коксетера , Армстронг (2009) изучал антиматроиды, которые также являются сверхразрешимыми решетками . Сверхразрешимый антиматроид определяется полностью упорядоченным набором элементов и семейством множеств этих элементов. Семейство должно включать пустое множество. Кроме того, оно должно обладать свойством, что если два множестваАиБпринадлежат к семейству, если теоретико -множественная разность непусто, и еслихэто наименьший элемент , затем также принадлежит к этому семейству. Как замечает Армстронг, любое семейство множеств этого типа образует антиматроид. Армстронг также дает решеточно-теоретическую характеристику антиматроидов, которые может образовывать эта конструкция.

Если и два антиматроида, оба описаны как семейство множеств над одной и той же вселенной элементов, затем еще один антиматроид , объединение и , можно сформировать следующим образом:А∨Б= Это другая операция, чем соединение, рассматриваемое в решеточно-теоретических характеристиках антиматроидов: она объединяет два антиматроида, чтобы сформировать другой антиматроид, а не объединяет два множества в антиматроиде, чтобы сформировать другой набор. Семейство всех антиматроидов над одной и той же вселенной образует полурешетку с этой операцией соединения.

Объединения тесно связаны с операцией замыкания, которая отображает формальные языки в антиматроиды, где замыкание языкаЛявляется пересечением всех антиматроидов, содержащих как подъязык. Это замыкание имеет в качестве своих возможных множеств объединения префиксов строк в . В терминах этой операции замыкания, соединение является замыканием объединения языков и . Каждый антиматроид может быть представлен как объединение семейства цепных антиматроидов или, что эквивалентно, как замыкание множества базовых слов; выпуклое измерение антиматроидаАминимальное количество цепных антиматроидов (или, что эквивалентно, минимальное количество базовых слов) в таком представлении. ЕслиФэто семейство цепочечных антиматроидов, все основные слова которого принадлежат , затем генерирует тогда и только тогда, когда допустимые наборы включить все пути . ПутиАпринадлежащий к одной цепи антиматроид должен образовывать цепь в пути частично упорядоченного множестваА, поэтому выпуклая размерность антиматроида равна минимальному числу цепей, необходимых для покрытия частично упорядоченного множества путей, что по теореме Дилворта равно ширине частично упорядоченного множества путей.

Если у вас есть представление антиматроида как замыкания множества Проще говоря, это представление можно использовать для отображения допустимых множеств антиматроида в точки г-мерное евклидово пространство: назначить одну координату на базовое слово , и сделать значение координат допустимого набора быть длиной самого длинного префикса это подмножество . С этим внедрением, является подмножеством другого допустимого множества тогда и только тогда, когда координаты для все меньше или равны соответствующим координатам . Таким образом, размерность порядка включения допустимых множеств не превышает выпуклой размерности антиматроида. Однако в общем случае эти две размерности могут сильно различаться: существуют антиматроиды с размерностью порядка три, но с произвольно большой выпуклой размерностью.

Число возможных антиматроидов на множестве элементов быстро растет с числом элементов в множестве. Для множеств из одного, двух, трех и т. д. элементов число различных антиматроидов равно

Как ограничения по времени предшествования, так и ограничения по времени освобождения в стандартной нотации для теоретических задач планирования могут быть смоделированы антиматроидами. Бойд и Фейгл (1990) используют антиматроиды для обобщения жадного алгоритма Юджина Лоулера для оптимального решения задач планирования с одним процессором с ограничениями по предшествованию, в которых цель состоит в минимизации максимального штрафа, вызванного поздним планированием задачи.

Глассерман и Яо (1994) используют антиматроиды для моделирования порядка событий в системах моделирования дискретных событий .

Пармар (2003) использует антиматроиды для моделирования прогресса в достижении цели в задачах планирования искусственного интеллекта .

В теории оптимальности , математической модели развития естественного языка , основанной на оптимизации при ограничениях, грамматики логически эквивалентны антиматроидам

В математической психологии антиматроиды использовались для описания возможных состояний знаний обучающегося человека. Каждый элемент антиматроида представляет собой концепцию, которую должен понять обучающийся, или класс задач, которые он или она могли бы решить правильно, а наборы элементов, которые образуют антиматроид, представляют собой возможные наборы концепций, которые мог бы понять один человек. Аксиомы, определяющие антиматроид, можно неформально сформулировать так: изучение одной концепции никогда не может помешать обучающемуся изучить другую концепцию, и что любое возможное состояние знаний может быть достигнуто путем изучения одной концепции за раз. Задача системы оценки знаний состоит в том, чтобы вывести набор концепций, известных данному обучающемуся, путем анализа его или ее ответов на небольшой и хорошо подобранный набор задач. В этом контексте антиматроиды также называются «пространствами обучения» и «пространствами хорошо оцененных знаний».

Вау!! 😲 Ты еще не читал? Это зря!

• матроид ,

Исследование, описанное в статье про антиматроид , подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое антиматроид и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.