ММАПР №14. Потоки с отсутствием последействия, с ограниченным последействием и рекуррентные потоки.

Пусть теперь  – моменты поступления заявок пуассоновского потока. Тогда для любого  функция распределения

или .

Таким образом, для пуассоновского входящего потока промежутки времени между моментами поступления заявок статистически независимы и имеют одинаковое экспоненциальное распределение.

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

Тогда для любого числа

. (1)

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

ЛИПО №5. Сортировка Шелла

Этот алгоритм – усовершенствование прямых методов сортировки, являющийся сортировкой простыми вставками с убывающим шагом.

Эта сортировка основана на следующих положениях:

1. Сортировка простыми вставками очень эффективна для массивов, которые почти упорядочены.

2. Для малого числа элементов сортировка прямым методом с трудоемкостью порядка O(n²) часто более эффективна чем сортировка улучшенным методом из – за простоты реализации и отсутствия дополнительных действий, кроме сравнения и перестановок.

В методе Шелла сортировка простыми вставками применяется сначала к отдельным подмассивам(спискам) с малым числом элементов, что позволяет частично упорядочить весь массив. Затем сортировка с простыми вставками применяется к спискам с постепенно увеличивающимся количеством элементов.

Исходный массив:

а₁…а_n.

Введем h₁ – шаг сортировки.

На 1^ом этапе сортируется h₁ списков с малым числом элементов. h₁=4.

1) а₁,а₅,a₉ …

2) а₂,а₆,a₁₀ …

3) а₅,а₇,а₁₁…

4) а₄,а₈,а₁₂…

На следующем этапе шаг сортировки уменьшается (выбирается h₂<h₁) и процесс повторяется . Это выполняется для последовательности шагов h₁…h_k до того, как последний шаг k=1.

Пример. Пусть задан массив 25,57,48,37,12,92,86,33.

1) Сортируются 4 подмножества с помощью метода простых вставок (h₁=4)

25 57 48 37 12 92 86 33

Получим:

2) h₂=2;

12 57 48 33 25 92 86 37

Получим:

В общем случае значение шагов сортировки может быть произвольным( должно выполняться h₁>h₂>…>h_n). Причем последний должен быть = 1.

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология