Сөздер бойынша комбинаторика - Combinatorics on words

Сөздер бойынша комбинаторика жаңа өрісі болып табылады математика, тармақталу комбинаторика, зерттеуге бағытталған сөздер және ресми тілдер. Тақырып әріптерге немесе шартты белгілер, және тізбектер олар қалыптастырады. Сөздер бойынша комбинаторика қоса, математикалық оқудың әр түрлі салаларына әсер етеді алгебра және Информатика. Бұл салада көптеген үлестер болды. Алғашқы жұмыстардың кейбіреулері болды квадратсыз сөздер арқылы Axel Thue 1900 жылдардың басында. Ол және әріптестері сөздегі заңдылықтарды байқап, оларды түсіндіруге тырысты. Уақыт өте келе, сөздердің комбинаторикасы оқуда пайдалы болды алгоритмдер және кодтау. Бұл дамуға әкелді абстрактілі алгебра және ашық сұрақтарға жауап беру.

Анықтама

Комбинаторика - бұл аймақ дискретті математика. Дискретті математика - есептелетін құрылымдарды зерттеу. Бұл нысандардың белгілі басы мен соңы бар. Сияқты пәндерге қарама-қарсы болып саналады талдау, қайда есептеу және шексіз құрылымдары зерттеледі. Комбинаторика бұл объектілерді әр түрлі бейнелеу арқылы санауды зерттейді. Сөздердегі комбинаторика - бұл сөздерді және формальды тілдерді зерттеуге бағытталған осы саладағы соңғы жаңалық. Ресми тіл дегеніміз - адамдар ақпарат алмасу үшін пайдаланатын символдар мен белгілердің кез-келген жиынтығы.[1]

Алдымен сөздерді зерттеуге қатысты кейбір терминологияны түсіндіру керек. Ең алдымен, сөз дегеніміз - бұл а-дағы белгілердің немесе әріптердің бірізділігі ақырлы жиынтық.[1] Осы жиынтықтардың бірін жалпы жұрт белгілі алфавит. Мысалы, «энциклопедия» сөзі - ішіндегі символдар тізбегі Ағылшын алфавиті, жиырма алты әріптен тұратын ақырлы жиынтық. Сөзді дәйектілік ретінде сипаттауға болатындықтан, басқа негізгі математикалық сипаттамаларды қолдануға болады. Алфавит - а орнатылды, күткендей, бос жиын Бұл ішкі жиын. Басқаша айтқанда, а бар бірегей ұзындығы нөлге тең сөз. Сөздің ұзындығы реттілікті құрайтын символдар санымен анықталып, | арқылы белгіленедіw|.[1] Тағы да «энциклопедия» мысалын қарап, |w| = 12, өйткені энциклопедияда он екі әріп бар. Идеясы факторинг үлкен сандарды сөздерге қолдануға болады, мұндағы сөз факторы қатарлы таңбалар блогы болып табылады.[1] Сонымен, «циклоп» «энциклопедия» факторы болып табылады.

Бірізділікті өздігінен зерттеуден басқа, сөздегі комбинаториканы қарастырудың тағы бір бағыты - оларды көзбен қалай бейнелеуге болады. Математикада мәліметтерді кодтау үшін әртүрлі құрылымдар қолданылады. Комбинаторикада қолданылатын жалпы құрылым - бұл ағаш құрылымы. Ағаш құрылымы - бұл а график қайда төбелер жол немесе деп аталатын бір жолмен байланысқан шеті. Ағаштардың құрамында болмауы мүмкін циклдар, немесе толық болмауы да мүмкін. Бұл мүмкін кодтау сөз, өйткені сөз таңбалармен құрастырылған және ағашты қолдану арқылы деректерді кодтайды.[1] Бұл объектінің визуалды көрінісін береді.

Негізгі жарналар

Тақырыптың шығу тегі туралы қорытынды жасайтын сөздер туралы комбинаторика туралы алғашқы кітаптар математиктердің тобымен жазылды, олар бірлесіп атымен жүрді. М. Лотер. Олардың алғашқы кітабы 1983 жылы, сөзге комбинаторика кең етек алған кезде жарық көрді.[1]

Өрнектер

Сөз ішіндегі өрнектер

Сөздер бойынша комбинаториканың дамуына үлкен үлес қосты Axel Thue (1863–1922); ол қайталануды зерттеді. Сэнің басты үлесі шексіздіктің бар екендігінің дәлелі болды квадратсыз сөздер. Квадратсыз сөздердің іргелес қайталанатын факторлары болмайды.[1] Түсіндіру үшін, «жаз» квадратсыз болмайды, өйткені m қатарынан қайталанады, ал «энциклопедия» квадратсыз болады. Thue өзінің шексіз квадратсыз сөздердің бар екендігі туралы болжамдарын қолдана отырып дәлелдейді ауыстырулар. Ауыстыру - бұл таңбаны алу және оны сөзбен ауыстыру тәсілі. Ол осы әдісті өзінің басқа үлесін сипаттау үшін пайдаланады Сәрсенбі - Морзе дәйектілігі, немесе Сәрсенбі - Морзе сөзі.[1]

Сквер шаршысыз сөздерге екі құжат жазды, олардың екіншісі - Сш-Морзе сөзінде. Марстон Морз атауына кіреді, өйткені ол Сью сияқты нәтижені тапты, бірақ олар өз бетінше жұмыс істеді. Сондай-ақ, Сю қабаттаспайтын сөздің бар екенін дәлелдеді. Бір-бірімен қабаттаспайтын сөз - бұл x және y таңбалары үшін xyxyx өрнегі сөз ішінде болмаған кезде. Ол екінші мақаласында шексіз қабаттаспайтын сөздер мен квадратсыз сөздер арасындағы байланысты дәлелдеуді жалғастырады. Ол екі түрлі әріптің көмегімен жасалынатын қабаттаспайтын сөздерді қабылдайды және оларды ауыстыруды үш әріптен тұратын төртбұрышты сөзге қалай айналдыруға болатындығын көрсетеді.[1]

Бұрын сипатталғандай, сөздер таңбалар арқылы жасалған тізбектерді зерттей отырып зерттеледі. Өрнектер табылған және оларды математикалық сипаттауға мүмкіндік бар. Үлгілер не болдырмауға болатын, не сөзсіз болуы мүмкін. Жұмысына елеулі үлес қосқан сөзсіз өрнектер немесе заңдылықтар болды Фрэнк Рэмси 1930 ж. Оның маңызды теоремасы k, m≥2 бүтін сандарында ең аз оң бүтін R (k, m) бар екенін айтады, сондықтан толық графиктің екі түске боялғанына қарамастан, әрқашан бір түсті субграфия болады. әр түс.[1]

Сөзсіз үлгілерді зерттеуге басқа да үлес қосушылар жатады ван дер Верден. Оның теоремасы егер натурал сандар k кластарға бөлінсе, онда с сыныбы белгілі бір ұзындықтағы арифметикалық прогрессияны қамтитын сыныбы бар дейді. Ан арифметикалық прогрессия - бұл көршілес сандар арасындағы айырмашылық тұрақты болып қалатын сандар тізбегі.[1]

Еркін үлгілерді зерттегенде секвиповерлер сонымен қатар зерттеледі. Кейбір өрнектер үшін x, y, z өрнектері x, xyx, xyxzxyx, .... түрінде болады, бұл квадратсыз немесе сөзсіз өрнектер сияқты тағы бір өрнек. Coudrain және Шютценбергер негізінен осы дыбыс күштерін зерттеді топтық теория қосымшалар. Одан басқа, Зимин дыбыс күштерінің бәрі сөзсіз болатындығын дәлелдеді. Бүкіл өрнек көрініп тұр ма, немесе тек бірнеше секунды ғана қайталана береді ме, оны болдырмау мүмкін емес.[1]

Әліпби ішіндегі өрнектер

Алқалар дөңгелек дәйектілік сөздерінен құрастырылған. Олар жиі қолданылады музыка және астрономия. Сент-Мари шыбындары 1894 жылы 2 екенін дәлелдеді2n−1n екілік де Брюйн ұзындығы 2 алқаn. Де Брюйн алқасында белгілі бір әріптер саны бойынша ұзындықтағы сөздерден тұратын факторлар бар. Сөздер алқада бір рет қана пайда болады.[1]

1874 жылы, Бодот соңында орын алатын кодты әзірледі Морзе коды екілік де Брюйн алқаларының теориясын қолдану арқылы. Мәселе Сен-Мари қаласынан бастап жалғасты Мартин 1934 жылы де Брюйн құрылымының сөздерін жасау алгоритмдерін қарастыра бастады. Содан кейін ол жұмыс істеді Өлімнен кейін 1943 ж.[1]

Тіл иерархиясы

Сөздердегі комбинаторикадағы ең көп қолданылатын нәтиже - Хомский иерархиясы,[тексеру қажет ] әзірлеген Ноам Хомский. Ол 1950 жылдары ресми тілді оқыды.[2] Оның тілге көзқарасы тақырыпты жеңілдеткен. Ол сөздің нақты мағынасын елемейді, жиілік пен контекст сияқты белгілі бір факторларды ескермейді және барлық терминдерге қысқа мерзімді үлгілерді қолданады. Хомский шығармасының негізгі идеясы - тілді төрт деңгейге немесе тілге бөлу иерархия. Төрт деңгей: тұрақты, контекстсіз, контекстке сезімтал, және санауға болатын немесе шектеусіз.[2] Тұрақты - ең күрделі, ал санауға болатын - ең күрделі. Оның жұмысы сөздегі комбинаторикадан пайда болғанымен, ол басқа пәндерге, әсіресе, қатты әсер етті Информатика.[3]

Сөз түрлері

Штурм сөздері

Штурм сөздері, Франсуа Штурм жасаған, сөздердің комбинаторикасында тамыры бар. Штурм сөздерінің бірнеше балама анықтамалары бар. Мысалы, шексіз сөз - әр теріс емес бүтін сан үшін n + ұзындығының n + 1 нақты факторлары болған жағдайда ғана штурм.[1]

Линдон сөзі

A Линдон сөзі - берілген алфавиттің үстінен сөз, ол өзіне сәйкесінше қарапайым және реттелген түрінде жазылған конъюгатия сыныбы. Линдон сөздері өте маңызды, өйткені кез-келген х х сөзі үшін y теорема Чен, Фокс және Линдон, кез-келген сөзде факторизация сөздері болатын Линдон сөздерінің ерекше факторизациясы бар екендігі айтылады өспейтін. Осы қасиетке байланысты Линдон сөздері зерттеу үшін қолданылады алгебра, нақты топтық теория. Олар идеясының негізін құрайды коммутаторлар.[1]

Көрнекі ұсыну

Кобхэм қатысты жұмыс жасады Юджин Проухе жұмыс істейді ақырлы автоматтар. Математикалық график жиектерден және түйіндер. Шекті автоматтармен шеттері алфавиттегі әріппен белгіленеді. Графикті пайдалану үшін түйіннен басталып, соңғы түйінге жету үшін шеттермен жүреді. График бойынша өткен жол сөзді құрайды. Бұл ақырлы график, өйткені түйіндер мен шеттердің есептелетін саны бар, және екеуін тек бір жол байланыстырады айқын түйіндер.[1]

Гаусс кодтары, жасалған Карл Фридрих Гаусс 1838 жылы графиктерден жасалған. Нақтырақ айтқанда, а жабық қисық үстінде ұшақ қажет. Егер қисық тек өзінің үстінен тек бірнеше рет кесіп өтсе, онда қиылыстарды қолданылған алфавиттің әріпімен белгілейді. Қисық бойымен жүре отырып, сөз қиылысу кезінде әр әріпті жазу арқылы анықталады. Гаусс бір символ сөзде пайда болған кездегі арақашықтық ан тіпті бүтін.[1]

Топтық теория

Уолтер Франц Антон фон Дайк топ теориясындағы сөздер бойынша комбинаторика жұмысын 1882 және 1883 жылдары жарияланған еңбегімен бастады. Ол сөздерді топ элементтері ретінде қолданудан бастады. Лагранж 1771 жылы өз жұмысымен үлес қосты ауыстыру топтары.[1]

Топ теориясында зерттелетін сөздер бойынша комбинаториканың бір қыры - қысқартылған сөздер. Топ кейбір алфавиттегі сөздермен құрылады, соның ішінде генераторлар және кері элементтер, aā немесе āa түрінде көрінетін факторларды қоспағанда, алфавитте кейбір a. Қысқартылған сөздер aā, āa факторлары бірегей сөз шыққанға дейін элементтерді жою үшін қолданылған кезде пайда болады.[1]

Нильсен түрлендірулері дамыды. А элементтерінің жиынтығы үшін тегін топ, Нильсен түрленуіне үш түрлендіру арқылы қол жеткізіледі; элементті кері мәнге ауыстыру, элементті өнім Өзінің және басқа элементтің және кез-келген элементті жоюдың 1-ге теңдігі. Осы түрлендірулерді қолдану арқылы Нильсен кішірейтілген жиынтықтар пайда болады. Төмендетілген жиынтық ешбір элементті басқа элементтермен көбейтіп, толықтай бас тартуға болмайды дегенді білдіреді. Нильсен түрлендірулерімен штурм сөздерінің байланыстары да бар.[1]

Қарастырылған мәселелер

Топтық теориядағы сөздер бойынша комбинаториканы зерттеу кезінде қарастырылатын бір мәселе келесідей: екі элемент үшін х, у а жартылай топ, x = y құрайды модуль анықтаушы қарым-қатынастар х және у. Пошта және Марков осы мәселені зерттеп, оны анықтады шешілмейтін. Шешімсіз дегеніміз - теорияны дәлелдеу мүмкін емес.[1]

The Бернсайд сұрақ шексіздікті қолдана отырып дәлелденді текшесіз сөз. Бұл сұрақ топта генераторлардың белгілі бір саны болса және x критерийлеріне жауап берсе, топ шектеулі ме деген сұрақ туындайдыn= 1, топтағы х үшін.[1]

Сөздерге байланысты көптеген мәселелер шешілмейді Хат алмасу мәселесі. Кез келген екі гомоморфизмдер жалпы доменмен және жалпы кодоменмен Post-хаттың мысалы бар, ол сөздің бар-жоғын сұрайды доменде . Пост бұл мәселені шешуге болмайтынын дәлелдеді; Демек, осы негізгі проблемаға дейін жеткізілетін кез-келген сөз проблемасы да шешілмейді.[1]

Басқа қосымшалар

Сөздердегі комбинаториктердің қосымшалары бар теңдеулер. Маканин теңдеулер сөзден құралған кезде, шекті теңдеулер жүйесінің шешімін табуға болатындығын дәлелдеді.[1]

Сондай-ақ қараңыз

Пайдаланылған әдебиеттер

  1. ^ а б c г. e f ж сағ мен j к л м n o б q р с т сен v w х ж Берстел, Жан; Доминик Перрин (сәуір, 2007). «Сөздердегі комбинаториканың пайда болуы». Еуропалық Комбинаторика журналы. 28 (3): 996–1022. дои:10.1016 / j.ejc.2005.07.019.
  2. ^ а б Джегер, Герхард; Джеймс Роджерс (шілде 2012). «Ресми тіл теориясы: Хомский иерархиясын нақтылау». Корольдік қоғамның философиялық операциялары B. 367 (1598): 1956–1970. дои:10.1098 / rstb.2012.0077. PMC  3367686. PMID  22688632.
  3. ^ Моралес-Буэно, Рафаэль; Баена-Гарсия, Мануэль; Кармона-Седжудо, Хосе М .; Кастилло, Глэдис (2010). «Факторларды болдырмайтын сөздерді санау». Математика және технологияның электронды журналы. 4 (3): 251.

Әрі қарай оқу

Сыртқы сілтемелер