Методическое пособие 276
.pdfФГБОУ ВПО «Воронежский государственный технический университет»
Кафедра систем информационной безопасности
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к выполнению курсовой работы по дисциплине «Теория информации» для студентов специальности 090301
«Компьютерная безопасность» очной формы обучения
Воронеж 2014
Составитель канд. техн. наук О.В. Поздышева
УДК 621.382.82
Методические указания к выполнению курсовой работы по дисциплине «Теория информации» для студентов специальности 090301 «Компьютерная безопасность» очной формы обучения / ФГБОУ ВПО «Воронежский государственный технический университет»; сост. О.В. Поздышева. Воронеж, 2014. 60 с.
Методические указания к выполнению курсовой работы содержат материал, направленный на углубленное изучение лекционного материала и приобретение практических навыков при решении различных задач кодирования информации, расчетах основных параметров кода, а также выбор наилучшего метода кодирования для данной задачи.
Методические указания подготовлены в электронном виде и содержатся в файле Поздышева_ТИ_КП.pdf.
Табл. 4. Ил. 9. Библиогр.: 21 назв.
Рецензент д-р техн. наук, проф. А.Г. Остапенко
Ответственный за выпуск зав. кафедрой д-р техн. наук, проф. А.Г. Остапенко
Издается по решению редакционно-издательского совета Воронежского государственного технического университета
© ФГБОУ ВПО «Воронежский государственный технический университет», 2014
1. ОСНОВНЫЕ ПОНЯТИЯ МАРКОВСКИХ ПРОЦЕССОВ
Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова (18561922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать «динамикой вероятностей». В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория Марковских процессов и ее приложения широко применяются в самых различных областях.
Благодаря сравнительной простоте и наглядности математического аппарата, высокой достоверности и точности получаемых решений, особое внимание Марковские процессы приобрели у специалистов, занимающихся исследованием операций и теорией принятия оптимальных решений [4, 9].
Марковские случайные процессы относятся к частным случаям случайных процессов (СП). При этом под случайным процессом понимают процесс случайного изменения состояний какой-либо физической или технической системы по времени или какому-либо другому аргументу.
Классификация Марковских случайных процессов производится в зависимости от непрерывности или дискретности множества значений функции X(t)и параметра t. Различают следующие основные виды Марковских случайных процессов:
•с дискретными состояниями и дискретным временем
(цепь Маркова);
1
•с непрерывными состояниями и дискретным временем
(Марковские последовательности);
•с дискретными состояниями и непрерывным временем
(непрерывная цепь Маркова);
•с непрерывным состоянием и непрерывным временем. Кроме указанных выше примеров классификации
случайных процессов существует еще одно важное свойство. Это свойство описывает вероятностную связь между состояниями случайных процессов. Так, например, если в случайном процессе вероятность перехода системы в каждое последующее состояние зависит только от предыдущего состояния, то такой процесс называется процессом без последействия.
Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.
Если случайная последовательность обладает Марковским свойством, то она называется цепью Маркова.
Марковский случайный процесс называется одно-
родным, если переходные вероятности остаются постоянными в ходе процесса.
Цепь Маркова считается заданной, если заданы два условия [23].
1.Имеется совокупность переходных вероятностей
ввиде матрицы:
.
2
2. Имеется вектор начальных вероятностей
,
описывающий начальное состояние системы.
Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа, как показано на рис. 1.
Рис.1. Ориентированный взвешенный граф
Множество состояний системы Марковской цепи, определенным образом классифицируется с учетом дальнейшего поведения системы.
1. Невозвратное множество (рис. 2).
Рис.2. Невозвратное множество
3
В случае невозвратного множества возможны любые переходы внутри этого множества. Система может покинуть это множество, но не может вернуться в него.
2. Возвратное множество (рис. 3).
Рис. 3. Возвратное множество
В этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его.
3. Эргодическое множество (рис. 4).
Рис. 4. Эргодическое множество
В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.
4
4. Поглощающее множество (рис. 5)
Рис. 5. Поглощающее множество
При попадании системы в это множество процесс заканчивается.
В некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие Марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений.
Основным признаком дискретной Марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими [21].
Кроме того, с учетом наличия и отсутствия тех или иных, упомянутых выше, множеств состояний Марковские цепи могут быть поглощающими, если имеется хотя бы одно поглощающее состояние, или эргодическими, если переходные вероятности образуют эргодическое множество. В свою очередь, эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через
5
определенное количество шагов (циклов) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.
1.1. Марковский процесс с дискретным временем
Итак, модель Марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i-го состояния в j-е состояние), как показано на рис. 6.
Рис. 6. Пример графа переходов
Каждый переход характеризуется вероятностью перехода Pij. Вероятность Pij показывает, как часто после попадания в i-е состояние осуществляется затем переход в j-е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода [21].
Ясно, что у каждого состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие со-
6
стояния должна быть всегда равна 1, как показано на рис.
7) .
Рис. 7. Фрагмент графа переходов (переходы из i-го состояния являются полной группой случайных событий)
Реализация Марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние, как показано на рис. 8. Данный граф является примером Марковской цепи, смоделированной по Марковскому графу, изображенному на рис. 7. Данная цепь является случайной последовательностью и может иметь также и другие варианты реализации.
Рис. 8. Пример Марковской цепи
Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид:
7
и называется уравнением Колмогорова-Чепмена. Уравнение Колмогорова-Чепмена относится к клас-
су рекуррентных соотношений, позволяющих вычислить вероятность состояний Марковского случайного процесса на любом шаге (этапе) при наличии информации о предшествующих состояниях.
1.2. Однородная цепь Маркова. Переходные вероятности. Матрица перехода
Однородной называют цепь Маркова, если условная вероятность pij(s) (переход из состоянияi в состоянииj) не зависит от номера испытания. Поэтому вместоpij(s)пишут просто pij.
Пример 1. Случайное блуждание. Пусть на прямой Ох в точке с целочисленной координатой находится материальная частица. В определенные моменты времени частица испытывает толчки. Под действием толчка частица с вероятностьюp смещается на единицу вправо и с вероятностью1 –p– на единицу влево. Ясно, что положение (координата) частицы после толчка зависит от того, где находилась частица после непосредственно предшествующего толчка, и не зависит от того, как она двигалась под действием остальных предшествующих толчков.
Таким образом, случайное блуждание − пример однородной цепи Маркова с дискретным временем.
Далее ограничимся элементами теории конечных однородных цепей Маркова.
Переходной вероятностьюpij называют условную вероятность того, что из состояния i (в котором система оказалась в результате некоторого испытания, безразлично
8