Комбинаторные свойства (0,1)-матриц и взвешенные пути на решетках

• Автор: Кроткин, Владислав Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Иркутск
• Количество страниц: 87 с. : ил.

Глава 1. Комбинаторные конфигурации и комбинаторные числа класса отображений

1.1. Комбинаторные конфигурации и их матрицы инцидентности

1.2. Комбинаторные числа класса отображений

1.3. (ОД)-матрицы и классы Райзера

Глава 2. Комбинаторные свойства (ОД)-матриц и проблема Райзера

2.1. Конструктивный подход к вычислению мощности классов Райзера

2.2. Мощность классов Райзера и взвешенные пути на плоских решетках

Глава 3. Перечисление взвешенных путей на решетках

3.1. Рекуррентные соотношения и перечисление взвешенных путей на решетках

3.2. Исследование взвешенных путей на геометрических решетках методом проецирования

3.3. Комбинаторные операторы и преобразование рекуррентных соотношений

Заключение
Список литературы

В настоящее время, в связи с усилением значимости
информационных технологий, задачи теоретической кибернетики и информатики переживают бурный рост и развитие.
А.Н. Колмогоров считал что, «кибернетика занимается изучением систем любой природы, способных воспринимать, хранить и
перерабатывать информацию и использовать ее для управления и регулирования. При этом кибернетика широко пользуется математическим методом и стремится к получению специальных конкретных результатов, позволяющих как анализировать такого рода системы, так и синтезировать их» [73].
При изучении сложных реальных систем и построении их моделей приходится иметь дело с большим количеством параметров, учитывать всевозможные свойства систем и их различные состояния. Поэтому для исследования сложных систем все шире применяются методы дискретной математики в целом и комбинаторного анализа в частности.
По мере развития комбинаторных методов дискретной математики было получено огромное количество результатов, которые могут быть использованы при построении и исследовании дискретных математических моделей различных структур и процессов. Поэтому возникали различные способы классификации и представления материала и схемы комбинаторных построений, позволяющие с единых позиций
рассматривать обширные классы задач и объектов [49, 50].
Начало систематических комбинаторных исследований было
положено трудами Б. Паскаля и П. Ферма. Выделению комбинаторики в самостоятельный раздел математики способствовали работы Я. Бернулли и Г. Лейбница. Множество основополагающих для комбинаторного анализа построений можно найти в дискретно-математической части богатого научного наследия Л. Эйлера. Так, например, одним из самых известных и

общих для комбинаторного анализа является метод производящих функций, разработанный для решения перечислительных задач Л. Эйлером, П. Дирихле и др. Попытки построения общей комбинаторной теории, включающие имеющиеся на тот момент знания в этой области, были предприняты У. Нетто и П.А. Мак-Магоном.
Первые общие схемы комбинаторных построений, позволяющие с единых позиций рассматривать обширные классы задач и объектов, возникли лишь к середине 20-го века. Наиболее известной и широко применяемой подобной конструкцией является схема перечисления Редфилда-Пойа. Они, не зависимо друг от друга, построили схему перечисления отображений конечных множеств в конечные. Удачное сочетание трех факторов: метода производящих функций,
эквивалентности, индуцируемой группами подстановок на множестве отображений, и весов, приписываемых перечисляемым объектам -обеспечивает теории Редфилда-Пойа большую общность и следующую из нее широкую применимость. Метод Редфилда-Пойа получил дальнейшее развитие и многочисленные применения в работах других исследователей [41,43,50, 68].
Резкое ускорение развития комбинаторного анализа и увеличение число работ, в которых ставились и решались теоретические и прикладные задачи комбинаторного характера, можно было наблюдать в конце 50-х годов XX века в связи с появлением и применением электронных вычислительных машин. Многие математики, имеющие до этого весьма разнообразные научные интересы, повели общую разработку задач и теоретических проблем комбинаторного характера. Это создало возможность включения в структуру комбинаторного анализа богатого набора разнообразных методов. Математики, участвующие в этой целенаправленной работе, исходили из близких им областей научных интересов. М. Холл, Р. Брук, В. Магнус исходили из опыта алгебраических исследований и развивали алгебраическую комбинаторику, Г.Дж. Райзер

Рис 2.2.
Таким образом, доказано, что |£/„(2,2)| равно суммарному весу всех путей Моцкина с заданными весовыми коэффициентами. Пути Моцкина (см. рис. 2.2) определяются как последовательность шагов таких, что на каждом шаге из каждой точки с координатами (п,к) можно перейти в одну из трех точек: (п+1,к+1), (п+1 ,/с) или (п+,к-1). Числом Моцкина называется количество всех путей Моцкина, ведущих из начальной вершины с координатами (0,0) в конечную вершину (и, 0), и при этом не опускающихся ниже уровня /с=0.
Числа Моцкина связаны с множеством комбинаторных объектов [22]. Ряд соотношений, связывающих пути и числа Моцкина с известными комбинаторными числами, имеется в [28, 101]. Интересный метод получения производящих функций в виде цепных дробей для чисел связанных с путями Моцкина с заданными весовыми коэффициентами представлен в [32].