Кіріспе

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

Мысалдар

Ат жарыстарында фотофиништің қолданылуы кейбір, бірақ барлық емес, тең нәтижелерді немесе (осы контексте аталатындай) "өлі жарыстарды" жойды, сондықтан ат жарысының нәтижесі әлсіз реттеу арқылы модельделуі мүмкін. 2007 жылғы Мэриленд Хант кубогының кедергілер арқылы жүгірісінде "Брюс" анық жеңімпаз болды, бірақ екі жылқы – "Баг Ривер" және "Лир Шарм" екінші орынды бөлісті, ал қалған жылқылар артта қалды; үш жылқы финиш сызығына жетпеді. Бұл нәтижені сипаттайтын әлсіз реттеуде "Брюс" бірінші болады, "Баг Ривер" және "Лир Шарм" "Брюс" кейін, бірақ финиш жасаған барлық басқа жылқылардан бұрын орналасады, ал финиш жасалмаған үш жылқы реттеу бойынша соңғы орынға қойылады, бірақ бір-бірімен тең болады. Евклид жазықтығының нүктелерін координаталар басынан (түбірден) қашықтығы бойынша реттеуге болады, бұл шексіз көп элементтері, тең элементтердің шексіз көп жиынтықтары (координаталар басына ортақ шеңберге жататын нүктелер жиыны) және осы жиынтықтардағы шексіз көп нүктелер бар әлсіз реттеудің тағы бір мысалы. Бұл реттеуде ең кіші элемент (координаталар басының өзі) болғанымен, екінші ең кіші элемент немесе ең үлкен элемент жоқ. Саяси сайлаулардағы қоғамдық пікірді зерттеу әлсіз реттеуге ұқсас реттеудің мысалы болып табылады, бірақ математикалық тұрғыдан басқа тәсілдермен модельдеуге көбірек жарайды. Сауалнама нәтижелерінде бір кандидат екіншісінен анық көш сорғаны байқалуы мүмкін, немесе екі кандидаттың нәтижелері статистикалық тұрғыдан тең болуы мүмкін, яғни олардың сауалнама нәтижелері бірдей емес, керісінше, олар бір-бірінің қателік шегінде болуы мүмкін. Алайда, егер кандидат А кандидат Б-мен статистикалық тұрғыдан тең болса және кандидат Б кандидат В-мен статистикалық тұрғыдан тең болса, кандидат А кандидат В-дан анық жақсы болуы мүмкін, сондықтан бұл жағдайда теңдік транзитивті қатынас емес. Осы мүмкіндікке байланысты, осы типтегі рейтингтерді әлсіз реттеуге қарағанда жартылай реттеу арқылы модельдеу тиімдірек.

Реттелген бөліктер

Жинақтың бөлінісі – бұл жинақтың одағын құрайтын бос емес, бірікпеген кіші жиындықтардың жиыны. Бөлініс, бөліністегі жиындықтардың толық ретімен бірге, Ричард П. Стэнлидің реттелген бөлініс деп атаған құрылымын, ал Теодор Мотцкин жиындықтар тізімін береді. Шекті жинақтың реттелген бөлінісін бөліністегі жиындықтардың шекті тізбегі түрінде жазуға болады: мысалы, {1, 2, 3} жинағының үш реттелген бөлінісі – ...

Қатаң әлсіз реттелуде, салыстыруға келмейтін элементтердің эквиваленттілік кластары жинақтың бөлінісін береді, онда жиындықтар өз элементтерінен толық реттелуді мұралайды, нәтижесінде реттелген бөлініс пайда болады. Керісінше, кез келген реттелген бөлініс қатаң әлсіз реттелуді тудырады, онда егер екі элемент бөліністегі бір жиынға жатса, олар салыстыруға келмейді, ал әйтпесе оларды қамтитын жиындықтардың реті мұраға алынады.

Тапсырыс берудің байланысты түрлері

Жартылай тәртіптемелер қатаң әлсіз тәртіптерді жалпылайды, бірақ салыстырусыздықтың транзитивтілігін қабылдамайды. Трихотомиялық қатаң әлсіз тәртіп қатаң толық тәртіп деп аталады. Бұл жағдайда толықтығының кері бөлігі болып табылатын жалпы алдын ала тәртіп толық тәртіп болып табылады. Қатаң әлсіз тәртіп үшін тағы бір байланысты рефлекстік қатынас – оның рефлекстік жабылуы, (қатаң емес) ішінара тәртіп. Екі байланысты рефлекстік қатынас әртүрлі жағдайларда өзгеше болады, яғни егер ешқайсысы да немесе болмаса: қатаң әлсіз тәртіпке сәйкес келетін жалпы алдын ала тәртіпте ешқайсысы да немесе болмайды, ал рефлекстік жабылу арқылы берілген ішінара тәртіпте де ешқайсысы да немесе болмайды. Қатаң толық тәртіптер үшін бұл екі байланысты рефлекстік қатынас бірдей: сәйкес (қатаң емес) толық тәртіп. Геометриялық тұрғыдан алғанда, берілген шекті жиынның толық тәртібін пермутоэдрдің төбелері ретінде, ал осы жиынның дихотомиясын пермутоэдрдің жақтары ретінде бейнелеуге болады. Бұл геометриялық бейнелеуде жиынның әлсіз тәртібі пермутоэдрдің әртүрлі өлшемдердегі жақтарына сәйкес келеді (пермутоэдрдің өзін қоса алғанда, бірақ бос жиын емес, жақ ретінде). Жақтың кодименсиясы сәйкес әлсіз тәртіптегі эквиваленттілік кластарының санын көрсетеді. Бұл геометриялық бейнелеуде әлсіз тәртіптегі қимылдардың ішінара кубі пермутоэдрдің жақ торларының жабылу қатынасын сипаттайтын граф болып табылады. Мысалы, үш элементтен тұратын пермутоэдр – жай ғана алтыбұрыш. Алтыбұрыштың жақ торында (қайтадан, алтыбұрыштың өзін жақ ретінде қоса алғанда, бірақ бос жиынды қоспай) он үш элемент бар: бір алтыбұрыш, алты қабырға және алты төбе, бұл бір толығымен байланысқан әлсіз тәртіпке, бір байланысы бар алты әлсіз тәртіпке және алты толық тәртіпке сәйкес келеді. Осы 13 әлсіз тәртіптегі қимылдар графигі суретте көрсетілген.

Қолданбалар

Жоғарыда айтылғандай, әлсіз реттер пайдалылық теориясында қолданылады. Әлсіз реттер компьютерлік ғылымда да қолданылған, атап айтқанда лексикографиялық ендік бойынша бірінші іздеу және лексикографиялық топологиялық ретке келтіруге негізделген бөліністі жетілдіру алгоритмдерінде. Бұл алгоритмдерде графтың төбелеріндегі әлсіз рет (төбелерді бөлетін жиынтар жиынтығы түрінде, сондай-ақ жиынтардың толық ретін қамтамасыз ететін екі жақты тізіммен бірге) алгоритм жүргізілімінде біртіндеп жетілдіріледі, нәтижесінде алгоритмнің нәтижесі болып табылатын толық рет құрылады. C++ бағдарламалау тілінің стандартты кітапханасында жиын және көп жиын дерек типтері кіріс деректерін үлгіні құру кезінде көрсетілген салыстыру функциясы бойынша сұрыптайды және олар қатаң әлсіз реттеуді іске асырады деп есептеледі.