Диссертация (1149645)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Череповецкий государственный университетНа правах рукописиПотехина Елена АлексеевнаПрименение произведения Адамара степенных рядовв комбинаторных и вероятностных задачахСпециальность 01.01.09 – дискретная математикаи математическая кибернетикаДиссертация на соискание ученой степеникандидата физико-математических наукНаучный руководитель:кандидат физико-математических наук,доцент Толовиков Михаил ИгоревичЧереповец – 20162ОглавлениеВведение ........................................................................................................................... 3Глава 1.

Произведение Адамара в комбинаторных и вероятностных задачах иметоды его вычисления .................................................................................. 12Глава 2. Применение произведения Адамара степенных рядов к решениюнекоторых комбинаторных задач.................................................................. 372.1 Перечисление замощений прямоугольника плитками размеров 1×1 и1×n ...................................................................................................................

372.2 Перечисление замощений прямоугольника плитками произвольнойдлины............................................................................................................... 422.3 Перечисление упорядоченных разбиений компонент вектора нафиксированные слагаемые ............................................................................ 532.4 Перечисление упорядоченных разбиений компонент вектора напроизвольные слагаемые .............................................................................. 592.5 Применение метода трансфер-матрицы в задаче перечислениязамощений прямоугольника плитками по числу типов взаимногорасположения плиток .................................................................................... 632.6 Осциллирующее случайное блуждание в задаче перечисленияупорядоченных разбиений ............................................................................ 81Глава 3.

Применение произведения Адамара степенных рядов к решениюнекоторых вероятностных задач ................................................................... 883.1 Производящие функции некоторых статистик от серий рекуррентныхсобытий ...........................................................................................................

883.2 Вычисление распределений некоторых статистик от осциллирующегослучайного блуждания ................................................................................ 1013.3 Вероятность замощения прямоугольника плитками ................................ 113Заключение .................................................................................................................. 125Список литературы ..................................................................................................... 1283ВведениеПроизведением Адамара формальных степенных рядов G  x    g k x k иk 0H  x    hk xk называется степенной рядk 0G  x   H  x    g k hk x k .k 0Произведение Адамара степенных рядов находит применение в ряде задачперечислительной комбинаторики и дискретной теории вероятностей.

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

ТехникавычисленияпроизведенияАдамаравзадачахдискретнойматематикинедостаточно развита и не систематизирована.Конкретные комбинаторные и вероятностные задачи, с одной стороны,служат источником примеров, в которых требуется вычислять произведениеАдамара степенных рядов, а с другой – их решение позволяет находить новыеприѐмы вычисления произведений Адамара рациональных функций в более илименее общих ситуациях.Цель диссертационной работы: исследовать возможности примененияпроизведения Адамара степенных рядов для некоторого класса комбинаторных ивероятностных задач.Исходя из целей работы, ставятся следующие задачи:– проанализировать существующие методы вычисления произведенияАдамара степенных рядов рациональных функций;4– проанализировать существующие подходы к решению комбинаторных ивероятностных задач с применением произведения Адамара;– получить новый метод вычисления произведения Адамара степенныхрядов рациональных функций;– используя новый метод вычисления произведения Адамара степенныхрядов рациональных функций, решить ряд комбинаторных задач;– решить некоторые вероятностные задачи с применением произведенияАдамара.Объектом исследования является класс комбинаторных и вероятностныхзадач.Предметом исследования являются комбинаторные и вероятностныезадачи, связанные с применением произведения Адамара степенных рядов, атакже методы вычисления произведения Адамара степенных рядов рациональныхфункций.Методологическую и теоретическую основу исследования составляютнаучные труды отечественных и зарубежных авторов в области комбинаторногоанализа и дискретной теории вероятностей.Методы исследования.

При выполнении исследования использовалисьследующие методы: метод производящих функций, методы линейной алгебры,теории вероятностей, метод трансфер-матрицы, а также алгебраический методвычисления произведения Адамара.Научная новизна результатов исследования:1) Авторомполученновыйкомбинаторно-алгебраическийметодвычисления произведения Адамара рациональных функций. Известный ранееалгебраическийметод([81],[67])вычисленияпроизведенияАдамарарациональных функций требует вычисления определителей порядка m + n. Спомощью методов комбинаторного анализа и линейной алгебры порядокопределителейавтором снижендовеличиныmin(m, n),чторасширяетвозможности применения произведения Адамара для получения решенияконкретных задач в явном виде.52) Спомощьюполученногоавторомновогометодавычисленияпроизведения Адамара найдено общее решение задачи перечисления замощенийпрямоугольника размера 2×r плитками размеров 1×1, 1×m и 1×n, а для n = 3формулы получены автором в явном виде.

Решение этой задачи в частныхслучаях (при n = 2) с помощью комбинаторных методов ранее опубликовали всвоих работах Л. Шапиро [99] и Й.Х. Ким ([95], [96]).3) Полученный автором новый метод вычисления произведения Адамарарациональныхфункцийпозволяетвзадачеперечислениязамощенийпрямоугольника размера 2×r плитками снять ограничения на длину плитки ирешить известную ранее задачу в новой постановке (получено общее решениезадачиперечислениязамощенийпрямоугольника размера 2×r плиткамипроизвольной длины).4) Спомощьюполученногоавторомновогометодавычисленияпроизведения Адамара рациональных функций (теоремы 2.1, 2.2 и 2.3) решеназадача перечисления упорядоченных разбиений компонент двумерного вектора наслагаемые (первая компонента разбивается на слагаемые 1 и n, а вторая – наслагаемые 1 и m, где m, n – произвольные целые числа, m ≥ 2, n ≥ 2).

Ранее этазадача была решена только в частных случаях при n = 2 [80, с. 367].5) С помощью доказанных автором теорем 2.2 и 2.3 решена задачаперечисления упорядоченных разбиений компонент двумерного вектора напроизвольные слагаемые. Полученный автором новый метод вычисленияпроизведения Адамара рациональных функций позволяет в данной задаче снятьограничения на величину слагаемого и решать известную ранее задачу в новойпостановке.6) Комбинаторным методом автором получены явные формулы длявычисления производящей функции весов замощений прямоугольника плиткамипо числу типов взаимного расположения плиток с максимальными длинами вверхнем и нижнем ряду m = 2, n = 2 соответственно, а также при m = 2, n ≥ 2.Объект исследования в данном случае является новым.67) Получено общее решение задачи вычисления производящей функциивесов замощений прямоугольника плитками по числу типов взаимногорасположения плиток, а также вычисления производящей функции весовразбиений.

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

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

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

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации