Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет

Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет

Автор: Корзун, Дмитрий Жоржевич

Шифр специальности: 05.13.18

Научная степень: Кандидатская

Год защиты: 2002

Место защиты: Петрозаводск

Количество страниц: 185 с. ил

Артикул: 2320718

Автор: Корзун, Дмитрий Жоржевич

Стоимость: 250 руб.

Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет  Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет 

1. Ассоциированные с контекстносвободными грамхматиками системы неотрицательных линейных диофантовых уравнений
1.1. Обозначения и понятийный аппарат
1.1.1. Системы неотрицательных линейных диофантовых
уравнений.
1.1.2. Контекстносвободные грамматики
1.1.3. Дополнительные понятия и обобщения
1.1.4. Равновесие леса разбора
1.1.5. Вазовые преобразования лесов разбора.
1.2. Ассоциированная с КСграмматикой система НЛДУ.
1.2.1. Балансовые соотношения в выводе
1.2.2. Равновесие грамматики
1.2.3. Построение ассоциированной системы.
1.3. Решения ассоциированной системы.
1.3.1. Решения системы и выводы в грамматике
1.3.2. Лес решения .
1.3.3. Общий вид решения
1.3.4. Частные случаи обобщенных выводов
Выводы к главе.
2. Эффективные алгоритмы решения некоторых классов ассоциированных систем неотрицательных линейных диофантовых уравнений
2.1. Анализ простейших классов ассоциированных систем
2.1.1. Операции над множествами ВПП и обозначения
2.1.2. Системы еАНЛДУ
2.1.3. Системы А, ВАНЛДУ и однородные АНЛДУ
2.2. Алгоритмы нахождения базиса Гильберта.
2.2.1. Системы еАНЛДУ.
2.2.2. Алгоритм латинской композиции.
2.2.3. Алгоритм фиктивных правил.
2.3. Анализ вычислительной сложности и тестирование
2.3.1. Наихудншй случай.
2.3.2. Тестирование.
2.3.3. Экспериментальная оценка эффективности алгоритмов
2.4. Алгоритмы нахождения одного решения .
Выводы к главе
Математическая модель стационарной агрегирующей структуры нагрузки канала Интернет
3.1. Задача построения модели структуры нагрузки .
3.2. Дискретная линейная модель структуры нагрузки
3.2.1. Однородные линейные дискретные зависимости
3.2.2. Математическая модель.
3.2.3. Интерпретации математической модели.
3.2.4. Приложения математической модели
3.3. Построение математической модели структуры нагрузки на заданном промежутке времени.
3.3.1. Число уравнений в системе.
3.3.2. Разбиение первичных классов нагрузки на группы .
3.3.3. Коэффициенты системы
3.3.4. Вырождение объемов данных и уравнений.
3.3.5. Показатели качества построенной модели
3.4. Построение структуры нагрузки для длительного периода . .
3.4.1. Оценка интенсивностей источников
3.4.2. Приоритеты источников.
3.4.3. Главные источники нагрузки
3.4.4. Общая вычислительная схема построения структуры
нагрузки но данным мониторинга трафика канала . . .
Выводы к главе.
4. Экспериментальное исследование математической модели структуры нагрузки канала Интернет
4.1. Данные мониторинга трафика
4.1.1. ТСРсопап система мониторинга, сжатия, хранения и обработки данных трафика на уровне потоков
4.1.2. Данные измерений нагрузки базового маршрутизатора Федерального Петрозаводского узла
4.1.3. Разбиение на первичные классы нагрузки.
4.2. Экспериментальный анализ структуры нагрузки.
4.2.1. Описание обнаруженной структуры
4.2.2. Стационарность.
4.2.3. Оценка роста числа обнаруженных источников.
4.2.4. Главные источники нагрузки.
4.2.5. Масштабируемость.
4.3. Репрезентативность общей модели нагрузки .
Выводы к главе
Заключение
Библиографический список использованной литературы
Приложение
П1. Основные характеристики математического обеспечения решения однородных систем АН.ЛДУ
П2. Основные характеристики программной инструментальной системы ТСРсопап
ПЗ. Агрегированные источники v обнаруженные на основных уровнях агрегации
П4. Акт внедрения.
Перечень сокращений и условных обозначений
АНЛДУ система ассоциированная с грамматикой система НЛДУ.
ВПП вектор применения правил.
КСграмматика контекстносвободная грамматика.
ЛДЗ линейная дискретная зависимость.
ЛП линейное программирование.
ЛПУ локальный поставщик услуг Интернет.
МНК метод наименьших квадратов.
НЛДУ неотрицательное линейное диофантово уравнение.
ФПУ Федеральный Петрозаводский узел.
ЦЛП целочисленное линейное программирование.
i бит в секунду.
I I .
1 i Ii ii коэффициент линейной информации. i ivi .i.
ii .
i i .
i .
.
О нулевой вектор, О 0,0,., 0.
множество ВПП для минимальных выводов А А,, Л, . , равновесие леса разбора . равновесие КСграмматики . е пустая цепочка.
е стандартный единичный вектор, е 0,., 0,1,0,., 0.
v, лес разбора с корнями из символов цепочки v и кроной .
лес разбора из циклических деревьев 7, ., Тк, где а од . од. x лес разбора с ВПП ж лес решения.
, , Р, КСграмматика с нетерминальным и терминальным алфавитами Ль Л2 ., А и i,2,., а, множеством правил Р г1,Г2, начальный нетерминал не конкретизирован.
Л базис Гильберта однородной системы НЛДУ.
Ни множество г г С с 6 Р для С АГ, , Р, и е и А.
ийа, 1гаса целая и дробная части вещественного числа а.
х 0дх 3 С О Vх х0 х Сдх.
х 9дх ЗСЬС2 0 х х0 Сдх х С2дх.
0х 0дх эквивалентно записи х 0дх.
осс, а число вхождений сивола и в цепочку а.
П множество ВПП для минимальных выводов Л 5, Л АГ
Р, классы вычислительных задач, которые могут быть решены за полиномиальное время соответственно на детерминированной и недетерминированной машине Тьюринга .
Р класс задач вычисления функции, аргументом которой является программа для недетерминированной машины Тьюринга, а значение равняется числу различных завершаемых за полиномиальное время траекторий выполнения этой программы
ПР аналогично Р, за тем исключением, что машина Тьюринга может использовать оракл вызов подпрограмм решения ИРзадач.
РХ квантиль порядка р 0,1 для выборки X Хх, , Xх.
К, 1 соответственно множество вещественных и неотрицательных вещественных чисел.
гЬэг правая часть правила г грамматики гЬзг а, где г Л 4 а.
8СУ,ии система АНЛДУ для КСграмматики б, ую V и Е.
Тда Тас деревья выводов соответственно для вывода Л а и для псевдоцикла Л оЛа, Л А, аг а1 а Аг и .
ук у суммарные объемы данных для каж
дого из лп классов, переданные через канал на промежутке времени Д.
ху,ю ВПП для вывода у ии.
, Ъ соответственно множество целых и неотрицательных целых чисел.
а0 операция дсупорядочения цепочки а.
а операция округления вещественного числа а.
0, О1 и Р Р композиция, декомпозиция деревьев вывода и преобразование леса разбора Р в лес Р.
А операция симметрической разности мультимножеств.
0 пустое множество.
Введение


Разработаны и обоснованы соответствующие полиномиальные алгоритмы нахождения некоторого решения и псевдополиномиальные атгоритмы нахождения базиса Гильберта полиномиальные при ограничении на число элементов в базисе. Выполнен теоретический и экспериментальный с применением ЭВМ анализ их вычислительной сложности. В третьей главе разрабатывается и исследуется математическая модель стационарной агрегирующей структуры нагрузки канала Интернет. Предлагаемая модель определяется базисом Гильберта однородной системы АНЛДУ. Эта система строится по данным мониторинга трафика канала. Предложены алгоритмы оценки вероятностной компоненты нагрузки для получения общей модели нагрузки канала для длительного периода времени. Рассмотрены также некоторые способы возможного практического применения модели. Четвертая глава посвящена вычислительному эксперименту с предложенной в главе 3 моделью структуры нагрузки. Экспериментально проверяются и подтверждаются такие свойства модели структуры нагрузки как стационарность, масштабируемость и компактность. Для проверки пригодности применения модели структуры в составе общей модели нагрузки канала проведена оценка, вероятностной компоненты нагрузки, после чего общая модель нагрузки проверяется на репрезентативность методами статистической проверки гипотез. В приложении даны сводные характеристики реализованного проблемноориентированного программного обеспечения и некоторые экспериментальные данные. Научная новизна и результаты, выносимые на защиту. Получен синтаксический метод построения системы АНЛДУ по произвольной КСграмматике и двум произвольным цепочкам над ее алфавитом, который позволяет получать более широкий класс систем, чем у М. Найдена трехкомпонентная формула общего решения произвольной системы АНЛДУ, которая сводит задачи ее численного решения к построению обобщенных выводов в грамматике. Эти выводы определяются с точностью до вхождения циклов, до порядка применения правил и порядка следования символов в цепочках. Для произвольной однородной системы АНЛДУ разработаны, обоснованы и протестированы два алгоритма нахождения базиса Гильберта, полиномиальных при ограничении на число элементов в базисе, и полиномиальный алгоритм нахождения некоторого ее решения. Эти алгоритмы более эффективны для данного класса систем но сравнению с известными алгоритмами решения однородных систем НЛДУ. Разработана дискретная математическая модель стационарной агрегирующей структуры нагрузки канала Интернет в виде базиса Гильберта однородной системы АНЛДУ. Модель позволяет компактно описать нагрузку канала, имеет полезную содержательную интерпретацию и ряд важных приложений, а также может быть эффективно построена с помощью ЭВМ по данным мониторинга трафика канала. Для проведения вычислительных экспериментов реализована программная система ТСРсопап, обеспечивающая сбор и обработку данных мониторинга трафика. Реализованы алгоритмы построения структуры нагрузки и оценивания вероятностной компоненты нагрузки. По данным мониторинга базового маршрутизатора Федерального Петрозаводского узла ФПУ построена модель структуры и общая модель нагрузки с оцениванием ее вероятностной компоненты. Статистическими методами подтверждены стационарность, масштабируемость и компактность модели структуры нагрузки, а также репрезентативность общей модели нагрузки. В диссертационной работе используются методы теории формальных грамматик, линейного диофантова анализа, математического моделирования, дискретной и вычислительной математики, теории сложности алгоритмов. Разработка программных средств сбора данных о работе элементов гетерогенных сетей на базе связующих технологий 1, которые выполнялись по межвузовской научнотехнической программе Вычислительная техника, автоматизация и интеграция сетей, а также в рамках персонального кандидатского проекта Комитета по науке и высшей школе Администрации СанктПетербурга и Конкурсного центра фундаментального естествознания Министерства образования России. Результаты работы внедрены в Территориальном центре международных связей и телевидения АО Ростелеком см. I4.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.247, запросов: 244