Антиматроидтар: Реттеулер мен жиындар математикалық жүйесі

Кіріспе

Реттеулердің немесе жиынтардың математикалық жүйесі

Математикада антиматроид – бұл элементтер бірінен соң бірі қосылып жиын құрылатын, ал элемент қосылуға қолжетімді болғаннан кейін, оған қосылғанша қолжетімді болатын процестерді сипаттайтын формалды жүйе. Антиматроидтар көбінесе екі эквивалентті тәсілмен аксиомаланады: мұндай процестің мүмкін күйлерін модельдейтін жиын жүйесі ретінде немесе элементтердің қосылу ретін модельдейтін формалды тіл ретінде. Дилворт (1940) антиматроидтарды зерттеуде алғашқы болып, тор теориясына негізделген тағы бір аксиоматизация қолданды, және олар басқа контекстерде жиі қайта ашылды. Жиын жүйесі ретінде антиматроидтарды анықтайтын аксиомалар матроидтарға өте ұқсас, бірақ матроидтар алмасу аксиомасымен анықталса, антиматроидтар анти-алмасу аксиомасымен анықталады, осы аксиомадан олардың атауы шыққан. Антиматроидтарды сұрлықтардың және жартылай модульді торлардың ерекше жағдайы ретінде, ал ішінара реттеулер мен тарату торларының жалпыламасы ретінде қарастыруға болады. Антиматроидтар, толықтыру арқылы, геометриядағы дөңес жиынтардың комбинаторлық абстракциясы – конвекс геометрияға тең. Антиматроидтар жоспарлау мәселелеріндегі басымдық шектеулерін, симуляциядағы ықтимал оқиғалар тізбегін, жасанды интеллекттегі тапсырма жоспарлауды және адамдардың білім деңгейін модельдеу үшін қолданылған.

Жолдар мен негізгі сөздер

Антиматроидтың жиынтық теориялық аксиомасында бүкіл антиматроидты анықтайтын жолдар деп аталатын белгілі бір арнайы жиынтықтар бар, яғни антиматроидтың жиынтықтары дәл жолдардың бірінділері болып табылады. Егер антиматроидтың кез келген мүмкін жиынтығы болса, одан басқа мүмкін жиынтық құру үшін алынып тасталатын элемент сол жиынтықтың соңғы нүктесі деп аталады, ал тек бір ғана соңғы нүктесі бар мүмкін жиынтық антиматроидтың жолы деп аталады. Жолдар жиынтығы жиынтық қосу арқылы ішінара реттелгенде, антиматроидтың жолдар жиынтығын құрайды. Антиматроидтағы әрбір мүмкін жиынтық үшін және оның әрбір элементі үшін, соңғы нүктесі болатын жиынтығының кіші жиынтығын табуға болады: мұны істеу үшін, элементінен басқа элементтерді біртіндеп алып тастаңыз, осылай алып тастау нәтижесінде мүмкін кіші жиынтық қалмағанша. Сондықтан, антиматроидтағы әрбір мүмкін жиынтық оның жол кіші жиынтықтарының біріндісі болып табылады. Егер жол болмаса, осы біріндідегі әрбір кіші жиынтық жиынтығының бөлшекті кіші жиынтығы болады. Бірақ, егер өзі соңғы нүктесі бар жол болса, оның антиматроидқа жататын әрбір бөлшекті кіші жиынтығы элементін қамтымайды. Сондықтан, антиматроидтың жолдары – бұл олардың бөлшекті мүмкін кіші жиынтықтарының бірінділеріне тең емес нақты мүмкін жиынтықтар. Басқаша айтқанда, берілген жиынтықтар отбасы антиматроидтың жолдар отбасын құрайды, егер және тек егер, отбасының әрбір элементі үшін, элементінің кіші жиынтықтарының біріндісі өзінен бір элемент кем болса. Егер солай болса, онда – элементінің кіші жиынтықтарының бірінділерінің отбасы. Формальді тіл формализациясында антиматроидтың ең ұзын тізбектері негізгі сөздер деп аталады. Әрбір негізгі сөз бүкіл әліпбидің орналасуын құрайды. Егер негізгі сөздер жиынтығы болса, онда сөздердің префикстерінің жиынтығы ретінде анықталуы мүмкін.

Қосылма-бөлуші торлар

Антиматроидтың кез келген екі мүмкін жиынының бірегей ең төменгі жоғарғы шегі (олардың біріндісі) және бірегей ең үлкен төменгі шегі (олардың екеуінде де болатын антиматроидтағы жиындардың біріндісі) болады. Сондықтан, антиматроидтың мүмкін жиындары, жиынтық кіріктіру бойынша ішінара реттелген, тор құрайды. Антиматроидтың әртүрлі маңызды ерекшеліктерін тор теориясының терминдерімен түсіндіруге болады; мысалы, антиматроидтың жолдары сәйкес тордың қосылуға жатпайтын элементтері болып табылады, ал антиматроидтың негізгі сөздері тордағы максималды тізбектерге сәйкес келеді. Антиматроидтардан туындайтын торлар осылайша шекті үлестіру торларын жалпылайды және бірнеше түрлі жолмен сипатталуы мүмкін. Алғашқыда қарастырылған сипаттама тордың азайтуға келмейтін элементтеріне қатысты. Антиматроидтың әрбір элементі үшін оның құрамында жоқ бірегей максималды мүмкін жиыны бар: оны құрамында жоқ барлық мүмкін жиындардың біріндісі ретінде құрастыруға болады. Бұл жиынтық автоматты түрде азайтуға келмейді, яғни ол екі үлкен тор элементінің тоғысқан нүктесі емес. Бұл дұрыс, өйткені әрбір мүмкін жоғары жиынтық құрамында болады, және сондықтан да мүмкін жоғары жиынтықтардың қиылысы да солай болады. Кез келген тордың әрбір элементін азайтуға келмейтін жиындардың тоғысқан нүктесі ретінде, көбінесе бірнеше жолмен жіктеуге болады, бірақ антиматроидқа сәйкес торда әрбір элементтің азайтуға келмейтін жиындардың бірегей минималды жиыны бар, олардың тоғысқан нүктесі болады; бұл жиын элементтерге сәйкес жиындардан тұрады. Яғни, торда азайтуға келмейтін бірегей жіктемелер бар. Екінші сипаттама тордағы аралықтарға қатысты, тор элементтерінің жұбымен анықталатын және барлық тор элементтерін қамтитын кіші торларға қатысты. Аралық атомдық, егер оның әрбір элементі атомдардың біріндісі болса (төменгі элементтен жоғары ең кішкентай элементтер), ал ол Бульдік, егер ол шекті жиынның барлық кіші жиындарының торына изоморфты болса. Антиматроид үшін атомдық әрбір аралық Бульдік болады. Үшіншіден, антиматроидтардан туындайтын торлар – жартылай модульді торлар, олар жоғарғы жартылай модульді заңдылықты қанағаттандырады, яғни кез келген екі элемент үшін және , егер жабады, онда жабады. Бұл жағдайды антиматроидтың мүмкін жиындарына аудару, егер мүмкін жиын басқа мүмкін жиынға жатпайтын бір ғана элементке ие болса, онда бұл бір элементті қосып, антиматроидтағы басқа жиын құруға болады. Сонымен қатар, антиматроидтың торы тоғысқан нүктелердің жартылай үлестіру қасиетіне ие: барлық тор элементтері үшін , , және , егер және бір-біріне тең болса, онда олар да тең. Жартылай модульді және тоғысқан нүктелердің жартылай үлестіру қасиетіне ие тор біріктіру үлестіруші тор деп аталады. Бұл үш сипаттама эквивалентті: бірегей тоғысқан нүктелерге жіктелетін кез келген тордың Бульдік атомдық аралықтары бар және біріктіру үлестіруші, Бульдік атомдық аралықтары бар кез келген тордың бірегей тоғысқан нүктелерге жіктелетіні бар және біріктіру үлестіруші, ал кез келген біріктіру үлестіруші тордың бірегей тоғысқан нүктелерге жіктелетіні және Бульдік атомдық аралықтары бар. Осылайша, біз осы үш қасиеттің кез келгенін біріктіру үлестіруші ретінде пайдалана аламыз. Кез келген антиматроид шекті біріктіру үлестіруші торларын тудырады, ал кез келген шекті біріктіру үлестіруші тор осылайша антиматроидтан туындайды. Шекті біріктіру үлестіруші торларды сипаттаудың тағы бір эквивалентті тәсілі – олардың сатылануы (кез келген екі максималды тізбектің ұзындығы бірдей), ал максималды тізбектің ұзындығы тордың азайтуға келмейтін элементтерінің санына тең. Шекті біріктіру үлестіруші торды білдіретін антиматроидды тордан қалпына келтіруге болады: антиматроидтың элементтерін тордың азайтуға келмейтін элементтері ретінде алуға болады, ал тордың кез келген элементіне сәйкес келетін мүмкін жиын тордағы азайтуға келмейтін элементтердің жиынынан тұрады. Кез келген шекті біріктіру үлестіруші тордың осы бейнеленуі одақтар бойынша жабық жиындардың қолжетімді отбасы ретінде (яғни антиматроид ретінде) қарастырылуы мүмкін, бұл Біркхоффтың бейнелену теоремасының аналогы болып табылады, оған сәйкес кез келген шекті үлестіруші тор одақтар және қиылыстар бойынша жабық жиындардың отбасы ретінде бейнеленеді.

Every two feasible sets of an antimatroid have a unique least upper bound (their union) and a unique greatest lower bound (the union of the sets in the antimatroid that are contained in both of them). Therefore, the feasible sets of an antimatroid, partially ordered by set inclusion, form a lattice. Various important features of an antimatroid can be interpreted in lattice theoretic terms; for instance the paths of an antimatroid are the join irreducible elements of the corresponding lattice, and the basic words of the antimatroid correspond to maximal chains in the lattice. The lattices that arise from antimatroids in this way generalize the finite distributive lattices, and can be characterized in several different ways. The description originally considered by concerns meet irreducible elements of the lattice. For each element of an antimatroid, there exists a unique maximal feasible set that does not contain : can be constructed as the union of all feasible sets not containing This set is automatically meet irreducible, meaning that it is not the meet of any two larger lattice elements. This is true because every feasible superset of contains , and the same is therefore also true of every intersection of feasible supersets. Every element of an arbitrary lattice can be decomposed as a meet of meet irreducible sets, often in multiple ways, but in the lattice corresponding to an antimatroid each element has a unique minimal family of meet irreducible sets whose meet is ; this family consists of the sets for the elements such that is feasible. That is, the lattice has unique meet irreducible decompositions. A second characterization concerns the intervals in the lattice, the sublattices defined by a pair of lattice elements consisting of all lattice elements with An interval is atomistic if every element in it is the join of atoms (the minimal elements above the bottom element ), and it is Boolean if it is isomorphic to the lattice of all subsets of a finite set. For an antimatroid, every interval that is atomistic is also boolean. Thirdly, the lattices arising from antimatroids are semimodular lattices, lattices that satisfy the upper semimodular law that for every two elements and , if covers then covers Translating this condition into the feasible sets of an antimatroid, if a feasible set has only one element not belonging to another feasible set then that one element may be added to to form another set in the antimatroid. Additionally, the lattice of an antimatroid has the meet semidistributive property: for all lattice elements , , and , if and equal each other then they also both equal A semimodular and meet semidistributive lattice is called a join distributive lattice. These three characterizations are equivalent: any lattice with unique meet irreducible decompositions has boolean atomistic intervals and is join distributive, any lattice with boolean atomistic intervals has unique meet irreducible decompositions and is join distributive, and any join distributive lattice has unique meet irreducible decompositions and boolean atomistic intervals. Thus, we may refer to a lattice with any of these three properties as join distributive. Any antimatroid gives rise to a finite join distributive lattice, and any finite join distributive lattice comes from an antimatroid in this way. Another equivalent characterization of finite join distributive lattices is that they are graded (any two maximal chains have the same length), and the length of a maximal chain equals the number of meet irreducible elements of the lattice. The antimatroid representing a finite join distributive lattice can be recovered from the lattice: the elements of the antimatroid can be taken to be the meet irreducible elements of the lattice, and the feasible set corresponding to any element of the lattice consists of the set of meet irreducible elements such that is not greater than or equal to in the lattice. This representation of any finite join distributive lattice as an accessible family of sets closed under unions (that is, as an antimatroid) may be viewed as an analogue of Birkhoff's representation theorem under which any finite distributive lattice has a representation as a family of sets closed under unions and intersections.

Супер ерігіш антиматроидтар

Коксетер тобының элементтеріндегі ішінара тәртіптерді анықтау мәселесіне байланысты, суперірінетін торлар болатын антиматроидтар зерттелді. Суперірінетін антиматроид элементтердің толық реттелген жиыны және осы элементтердің жиындарының отбасы арқылы анықталады. Отбасы бос жиынды қамтуы керек. Бұған қоса, егер екі жиын және отбасыға жатса, егер жиындық теориялық айырмасы бос емес болса және егер , ең кіші элементі болса, онда да отбасыға жатады. Армстронгтың айтуынша, осы типтегі кез келген жиындар отбасы антиматроид құрайды. Армстронг сондай-ақ осы құрылым арқылы жасала алатын антиматроидтардың торлық сипаттамасын ұсынады.

Санақ

Элементтер жиынтығындағы мүмкін антиматроидтардың саны жиынтықтағы элементтер саны артумен бірге жылдам өседі. Бір, екі, үш, және т.б. элементтері бар жиындар үшін, ерекше антиматроидтардың саны:

Қолданбалар

Теориялық жоспарлау мәселелерінің стандартты жазуындағы басымдық және босату уақытының шектеулері антиматроидтар арқылы модельделуі мүмкін. Антиматроидтарды қолдану Юджин Лоулердің ашкөз алгоритмін жалпылау үшін, басымдық шектеулері бар бір процессорлы жоспарлау мәселелерін оңтайлы шешуге мүмкіндік береді, мұндағы мақсат – тапсырманы кешіктіруден туындайтын ең жоғары айыпты азайту. Дискретті оқиғаларды модельдеу жүйелерінде оқиғалардың ретін модельдеу үшін антиматроидтар қолданылады. Жасанды интеллект жоспарлау мәселелеріндегі мақсатқа қадамдық прогресті модельдеу үшін антиматроидтар қолданылады. Оптималдылық теориясында, шектеулер аясында оңтайландыруға негізделген табиғи тілдің дамуының математикалық моделінде грамматикалар логикалық тұрғыдан антиматроидтарға тең. Математикалық психологияда антиматроидтар адамның білім алушысының білімінің мүмкін болатын жай-күйін сипаттау үшін қолданылады. Антиматроидтың әрбір элементі оқушының түсінуі тиіс түсінік немесе оның дұрыс шеше алатын проблемалар класын көрсетеді, ал антиматроидты құрайтын элементтер жиынтығы бір адамның түсіне алатын түсініктердің мүмкін жиынтығын білдіреді. Антиматроидты анықтайтын аксиомалар, бір түсінікті үйрену оқушының басқа түсінікті үйренуіне ешқашан кедергі келтірмейді және білімнің кез келген мүмкін жай-күйі бір уақытта бір түсінікті үйрену арқылы қол жеткізіледі деп бейресми түрде айтуға болады. Білімді бағалау жүйесінің міндеті – белгілі бір оқушының қандай түсініктерді білетінін, оның кішкентай және жақсы таңдалған проблемалар жиынтығына берген жауаптарын талдау арқылы анықтау. Бұл контексте антиматроидтар "оқу кеңістіктері" және "жақсы бағаланған білім кеңістіктері" деп те аталады.