Материал: ММвСС. Экзаменационные вопросы и ответы
17.Точечные оценки параметров (математическое ожидание и др.).
1.Среднее значение (математическое ожидание): ̅= 1 ∑=1 .
2. Несмещенная (исправленная) дисперсия: 2 |
= |
1 |
∑ |
( − ̅)2. |
|
|
|||||
|
|
−1 |
=1 |
|
|
|
|
|
|
||
3.Несмещенное среднеквадратическое отклонение: = .
4.Коэффициент вариации: = ̅.
18. Интервальные оценки параметров трафика (доверительные интервалы).
Доверительный интервал представляет собой диапазон, для которого можно утверждать, с заданной вероятностью = 1 − , называемой степенью доверия (или надежностью оценки), что он будет содержать оцениваемый параметр.
Доверительный интервал имеет следующую структуру: Точечная оценка ± Фактор надежности × Ошибка
•Точечная оценка – точечная оценка параметра (значение выборочной статистики).
•Фактор надежности – коэффициент, основанный на предполагаемом распределении точечной оценки и степени доверия для доверительного интервала.
•Ошибка – стандартная ошибка выборочной статистики, значение которой получено с помощью точечной оценки.
Доверительный интервал через медиану и СКО (используется редко): ( − ; + ).
Основная процедура для расчета:
1.Определение выборочного среднего ̅.
2.Если распределение не отлично от нормального ( -оценка) и СКО известно:
1)Главная формула: ( ̅− √ < < ̅+ √ ) = 2Ф( ) = , где – надежность оценки (в районе 0.95- 0.99), – оценка для уровня значимости (значение аргумента функции Лапласа, по таблице), – объем выборки.
2)Находим значение функции Лапласа и аргумент по этому значению: Ф( ) = 2, = Ф−1 (2).
3)Доверительный интервал: ( ̅− √ ; ̅+ √ ).
3.Если распределение отлично от нормального (t-распределение) или СКО неизвестно:
1) Главная формула: ( ̅− |
|
< < ̅+ |
|
|
) = = 2 ∫ ( , ) , |
где ( , ) – плотность |
|||||||
|
|
|
|
|
|||||||||
|
|
√ |
|
√ |
0 |
|
|
||||||
распределения Стьюдента, – объем выборки, = √ |
1 |
∑ |
( − ̅)2 |
– исправленное СКО выборки, |
|||||||||
−1 |
|||||||||||||
|
|
|
|
|
|
|
|
|
=1 |
|
|
||
|
– критерий Стьюдента для уровня статистической значимости и количества степеней свободы |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( − 1) (по таблице).
2)Находим из таблицы значений = ( , ).
3)Доверительный интервал: ( ̅− √ ; ̅+ √ ).
Пример.
7 измерений. Даны: среднее арифметическое – 30, выборочная дисперсия – 36, надежность – 0.99.
= 7. ̅= = 30. = 36. = √ = 6. = ( , ) = (0.99,7) = 3.71. Доверительный интервал: (30 − 3.71 6√7 ; 30 + 3.71 6√7 ) = (21.587; 38.413).
19. Гистограммы. Интервалы между пакетами, длина пакетов. Смысловое значение гистограмм. Функции плотности вероятности и функции распределения.
Гистограмма — способ графического представления табличных данных. Количественные соотношения некоторого показателя представлены в виде прямоугольников, площади которых пропорциональны.
|
Среднее значение задержки = ∑ |
|
|
|
||||||
|
|
|
|
|||||||
|
|
|
|
|
|
|
=1 |
|
||
|
|
|
|
|
|
|
|
|||
|
Где |
|
– значение -той задержки, n – количество |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
измерений. |
|
|
|
|||
|
|
|
Джиттер или среднее отклонение |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
= √ |
∑ |
( − )2 |
|
|
|
||
|
|
|
|
|
|
|
||||
|
|
|
|
− 1 |
|
|
|
|
|
|
|
|
|
|
|
=1 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Функция распределения |
Коэффициент вариации: |
||
|
= |
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
Плотность вероятности ( ) — один из способов задания распределения случайной величины, который характеризует сравнительную вероятность реализации тех или иных значений случайной переменной (переменных).
Функция распределения ( ) — функция, характеризующая вероятность того, что случайная величина примет значение, меньшее или равное , где — произвольное действительное число.
|
|
|
|
|
|
|
|
( ) = ′( ), |
( ) = ( ≤ ) = ∫ ( ) |
||||
|
|
|
|
|
−∞ |
|
|
Примеры абсолютно непрерывных распределений |
|||||
• |
Многомерное нормальное распределение |
|
|
• |
Распределение Парето |
|
• |
Непрерывное равномерное распределение |
|
|
• |
Распределение Стьюдента |
|
• |
Нормальное распределение |
|
|
• |
Экспоненциальное распределение |
|
|
Показательный закон распределения (пример) |
|||||
|
Плотность вероятности ( ) |
|
|
|
Функция распределения ( ) |
|
|
|
|
|
|
|
|
|
( ) = −, ≥ 0, |
( ) = 1 − −, ≥ 0 |
|||||||||||
= |
1 |
, |
= |
1 |
, |
|
= |
1 |
, |
= |
ln(2) |
, |
= 0 |
|
|
|
|
||||||||||
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
20. Имитационное моделирование. Принцип построения дискретных событийных моделей. Упрощенная структура системы моделирования и алгоритм функционирования.
Имитационное моделирование – это метод исследования, при котором исследуемая система заменяется ее моделью, которая достаточно точно описывает ее свойства. Модель используется для проведения экспериментов. В результате эксперимента получают данные, которые являются результатами измерений и подлежат статистической обработке для получения оценок численных значений исследуемых параметров.
При построении имитационных моделей сетей связи, как правило, применяются дискретные событийные модели.
Общая структура имитационной событийной модели
Алгоритм функционирования
Инициализация
Да
Очередь событий пуста?
Нет Взять событие из головы очереди, прочитать идентификатор процесса назначения и передать его этому процессу. Модельное время = Время выбранного события
Обновить процесс назначения
Поместить события выработанные данным процессом в очередь событий
Нет Достигнут предел интервала?
Да Останов
21. Получение потока событий с заданными свойствами. Получение случайных чисел с заданной функцией распределения. Метод обратной функции.
Пусть требуется получить значения случайной величины , распределенной в интервале ( , ) с плотностью вероятности ( ).
Метод обратной функции предполагает следующие действия:
1.Необходимо сгенерировать случайную величину (значение случайной величины ), равномерно распределенную в интервале (0,1).
2.Приравнять сгенерированное случайное число известной функции распределения ( ) и получить уравнение:
( ) = ∫ ( ) =
−∞
3. Решая уравнение = −1( ), находим искомое значение .
Пример.
Экспоненциальное распределение ( ) = ∫−∞ ( ) = 1 − − =− = 1 −
− = ln(1 − )
= − ln(1 − )
22. Расчет необходимой пропускной способности канала (линии связи) на примере услуг VoIP.
Частный случай:
1. |
Интенсивность исходящей нагрузки: = 0 = 1000 0.015 = 15 Эрл. |
||||
2. |
Необходимое число "виртуальных" линий: |
( ) = |
= arg min | |
( ) − | = 24. |
|
|
|
0 |
v |
|
0 |
3.Скорость кодирования G.711: 64 Кбит/с.
4.Скорость передачи данных Ethernet: 0 = 85.6 Кбит/с.
5.Интенсивность трафика: = 0 = 24 85.6 = 2054.4 Кбит/с.
6.Выберем модель линии доступа / /1, допустимая задержка 5 мс.
7.Найдем минимально допустимую пропускную способность.
|
|
|
|
|
|
|
1 |
|
||||
|
|
|
|
|
|
|
|
|||||
̅ |
̅ |
|
= |
|||||||||
|
|
|
||||||||||
0 = + = |
|
|
= [ |
|
1] = |
|
|
|
|
|
|
|
2 (1− ) |
|
|
|
|
|
|
|
|||||
|
|
= |
2 (1− ) |
|||||||||
|
|
|
|
|
|
|||||||
|
|
|
|
̅ |
||||||||
|
|
|
|
|
|
|
|
|
|
|
||
мс. = 2.16 Мбит/с.
Общий случай: |
|
|
|
|
|
|
|
|
|
1. |
Интенсивность исходящей нагрузки: = ∑ |
Эрл. |
|
|
|
|
|
|
|
|
=1 |
|
|
|
|
|
|
|
|
2. |
Необходимое количество "виртуальных" линий: |
( ) = |
|
= arg min | |
( ) − |. |
||||
|
|
|
|
0 |
|
v |
|
|
0 |
3.Скорость передачи данных для услуги: бит/с или пакетов/с.
4.Скорость передачи данных в сети: = (1 + ) бит/с.
5.Интенсивность трафика: инт = ∑=1( ) бит/с или инт = ∑=1( ) пакетов/с.
6.Выбор модели / /1 и нормы качества 0 (аппроксимация Маршала):
|
̅ |
|
|
2 |
+ |
2 |
|
2 |
|
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
̅+ |
|
|
|
|
|
|||||||
̅ |
|
( |
|
|
) ( |
|
|
|
̅ |
̅ |
|
, |
= |
|
|||
|
|
|
2 |
|
|
2 |
|
|
|
|
|||||||
≈ |
2(1 − ) |
|
|
|
̅ |
+ |
2) + , |
= |
|
|
|||||||
|
|
|
|
̅ |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
̅– среднее время обслуживания пакета |
|
|
||||||||||||||
7. Оценить дисперсии интервала между заявками 2 |
и времени обслуживания 2. |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8.Оценить требуемую пропускную способность .
23.Задачи динамического программирования. Общее определение подхода к решению задачи. Пример постановки задачи, решаемой методом динамического программирования.
Динамическое программирование – процесс нахождения решения задачи определенного типа, когда ответ на одну задачу может быть получен после решения предшествующей задачи.
Основные принципы динамического программирования:
•Многошаговость (разбиение задачи на подзадачи);
•Оптимальность (оптимальное поведение по отношению к предшествующим решениям).
Основное функциональное уравнение динамического программирования (уравнение Беллмана):
( ) = max{ ( , , ( ( , ))}
q
– вектор состояния, – вектор переменных
Три шага:
1.Разбиение задачи на подзадачи меньшего размера.
2.Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3.Использование полученного решения подзадач для конструирования решения исходной задачи.
Метод динамического программирования сверху включает простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем.
Метод динамического программирования снизу включает переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Классические задачи динамического программирования
•Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
•Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность,
требуется найти самую длинную возрастающую подпоследовательность.
•Задача о вычислении чисел Фибоначчи.
•Алгоритм Флойда — Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
•Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.
Пример постановки задачи. Из большого числа остовов связного неориентированного графа нужно найти один, у которого сумма весов ребер наименьшая.
Примечание. Остов — ациклический2 связный3 подграф данного связного неориентированного графа, в который входят все его вершины.
24. Постановка задачи выбора оптимальной структуры сети (минимальной протяженности линий). Алгоритмы поиска кратчайшего остова графа. Алгоритм Краскала.
Задача. Из большого числа остовов связного неориентированного графа нужно найти один, у которого сумма весов ребер наименьшая.
Алгоритм Краскала. В начале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён.
|
Алгоритм Краскала на примере |
Изображение |
Описание |
|
Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбирается ребро |
|
AD (выделено на рисунке). В результате получаем множество выбранных вершин (A, |
|
D). |
|
|
|
Теперь наименьший вес, равный 5, имеет ребро CE. Так как добавление CE не |
|
образует цикла, то выбираем его в качестве второго ребра. Так, как это ребро не имеет |
|
общих вершин с имеющимся множеством выбранных вершин (A, D), получаем второе |
|
множество выбранных вершин (C, E) |
|
|
|
Аналогично выбираем ребро DF, вес которого равен 6. При этом не возникает ни |
|
одного цикла, так как не существует (среди невыбранных) ребра, имеющего обе |
|
вершины из одного (A, D, F) или второго (C, E) множества выбранных вершин. |
|
|
2Ациклический граф: без циклов.
3Связный граф: между любой парой вершин графа существует как минимум один путь (непосредственный / посредственный).