Решение любой задачи, помеченной (*), автоматический зачет по курсу



Скачать 101.39 Kb.
Дата09.10.2012
Размер101.39 Kb.
ТипЗадача
1. Измерение информации по Шенону
!!!ПРИМЕЧАНИЯ:

1)Нажимайте клавишу F9 - автоматический пересчет отключен.

2)Решение ЛЮБОЙ задачи, помеченной (*), - автоматический зачет по курсу.

Краткое содержание занятия

Практическое знакомство с вычислением энтропии/информации различных источников.
12 задач для самостоятельного решения.
Задача 1. Сравнение количества информации
Какое из соотношений несет в себе БОЛЬШЕ информации:

1) ;

2) .

Если д.с.в. равновероятно принимает целые значения.
РЕШЕНИЕ:

Согласно подходу Шенона, информации тем больше, чем меньше неопределенность. В предположении, что - это дискретная случайная величина (д.с.в.), имеющая областью значений множество целых чисел и равную вероятность иметь любое значение из множества , то выражение 1) оставляет меньшую неопределенность о значении и, следовательно, несет в себе БОЛЬШЕ информации.

1.1. Задачи для самостоятельного решения
1.1.1. Какое из соотношений несет в себе БОЛЬШЕ информации:

1) ;

2) .

Если д.с.в. равновероятно принимает целые значения.
1.1.2. Какое из соотношений несет в себе БОЛЬШЕ информации:

1) ;

2) .

Если д.с.в. равновероятно принимает натуральные значения.
1.1.3. Какое из соотношений несет в себе БОЛЬШЕ информации:

1) ;

2) .

Если д.с.в. принимает значения: , причем вероятность каждого значения пропорциональна .

====================================================================================

Вариантов задач НЕТ. Все решают одно и то же.
Задача 2. Вычисление энтропии Шенона для различных моделей источников

2.1. Канал без помех. Мера информации по Шенону

Найти энтропию для д.с.в. , заданную распределением вероятности :

gif" align=bottom>
РЕШЕНИЕ:
1) Извлекаем из таблицы содержательную часть

; .

2)Проверяем равенство единице суммы вероятностей





3) Вычисляем энтропию по формуле Шенона

- это СИМВОЛЬНАЯ формула

для реального вычисления по заданному вектору вероятностей это нужно переписать так

или так

Откуда следует:

; ;

бит/символ.



2.1. Задачи для самостоятельного решения
2.1.1. Найти энтропию для д.с.в. , заданную распределением вероятности :

.

Варианты:

Приведены значения вероятности P для этих же символов




========================================================================.

2.1.2. Найти энтропию для д.с.в. , заданную распределением вероятности пропорциональным значению . Значения .
Варианты:



========================================================================.

2.1.3. Найти энтропию для д.с.в. , заданную распределением вероятности пропорциональным значению . Значения .
Варианты:

Значения X взять из предыдущей задачи.

==========================================================================
************************

**2.1.4. Создать программу на MathCAD для вычисления энтропии произвольного файла.

a) Программа должна считать энтропию для символов в виде произвольных порций байт фиксированной длины, например, 1 байт или 4 байта.

б) Программа должна считать энтропию для произвольных кусков файла, например, для кусков по 1024 байта или 32000 байт и выводить среднюю энтропию или минимальное число бит необходимых для кодирования файла.

2.2.Канал с помехами. Взаимная информация по Шенону

Д.с.в. и определяются бросанием двух идеальных монет ("орел"=1 и "решка"=0). Значение д.с.в. = сумма значений и . Вычислить количество информации содержащееся в об величине .
РЕШЕНИЕ:

1) Составим закон распределения вероятностей для :

или .

2) Закон распределения вероятностей для совпадает с : .

.

3) Составим закон распределения вероятностей для :

или .

4) Составим закон совместного распределения и

или

или


5) Вычисляем условную энтропию по формуле Шенона

- это СИМВОЛЬНАЯ формула, для вычисления ее следует переписать как

.

Ответ:

бит/символ


2.2. Задачи для самостоятельного решения
2.2.1. Д.с.в. , ... и определяются бросанием трех () идеальных монет ("орел"=1 и "решка"=0). Значение д.с.в. = сумма значений первых двух () монет и . Значение д.с.в. = сумма всех () значений и и . Вычислить количество информации содержащееся в об величине .

Варианты:

1)Число монет , = сумма первых значений; = сумма всех значений.

2),

3),

4),

5),

6),

7),

8),

9),

10),

11),

12),

13),

14),

15),

16),

17),

18),

19),

20),
===================================================================================
2.2.2. Сколько информации о содержится в д.с.в. , где независимы и могут с равной вероятностью принимать значения или . Найти также и .
Варианты:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)см. 2

13)см. 3

14)см. 4

15)см. 5

16)см. 6

17)см. 7

18)см. 8

19)см. 9

20)см. 10
===================================================================================
2.2.3. Д.с.в. и и могут с равной вероятностью принимать значения или . Найти , если совместное распределение вероятностей / есть



Варианты:





2.2.4.

Варианты:

1)

Д.с.в. и определяются бросанием двух идеальных тетраэдров, грани тетраэдров помечены числами от до . Д.с.в. . Найти , , .
2)

Д.с.в. и определяются бросанием двух идеальных тетраэдров, грани тетраэдров помечены числами от до . Д.с.в. . Найти , , .
3)

Д.с.в. может принимать значения с равной вероятностью. Д.с.в. с равной вероятностью может принимать значения . и независимы. . Найти , , ,.
4)

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

.

5)

Д.с.в. определяется бросанием идеального тетраэдра, грани тетраэдра помечены числами от до ; и определяются бросанием идеальной монеты, стороны монеты помечены числами 0 и 1. Д.с.в. . Найти , , .
6)

Д.с.в. определяется бросанием идеального тетраэдра, грани тетраэдра помечены числами от до ; и определяются бросанием идеальной игральной кости, стороны кости помечены числами от 1 до 6. Д.с.в. . Найти , , .

7)

Д.с.в. определяется бросанием идеального тетраэдра, грани тетраэдра помечены числами от до ; и определяются бросанием идеальной игральной кости, стороны кости помечены числами от 1 до 6. Д.с.в. . Найти , , .
8)

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

.
9)
Д.с.в. определяется бросанием идеального тетраэдра, грани тетраэдра помечены числами от до ; определяются бросанием идеальной игральной кости, стороны кости помечены числами от 1 до 6 и определяются бросанием идеальной монеты, стороны монеты помечены числами 0 и 1. Д.с.в. , . Найти , , , , , .

10)

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

.
11)см.1

12)см.2

13)см.3

14)см.4

15)см.5

16)см.6

17)см.7

18)см.8

19)см.9

20)см.10

======================================================================================
2.2.5. Линия связи состоит из 8-и проводов () по которым за один такт передается значение 1 байта. В передатчике все значения байта равновероятны. В канале есть помехи - два () провода оборваны. Определить количество информации, содержащейся в принятом сигнале Y относительно переданного сигнала X.
Варианты:

1),

2),

3),

4),

5),

6),

7),

8),

9),

10),

11),

12),

13),

14),

15),

16),

17),

18),

19),

20),

============================================================================
2.2.6. Линия связи состоит из 8-и проводов по которым за один такт передается значение 1 байта. В передатчике все значения байта равновероятны. В канале есть помехи, которые с вероятностью в каждом такте передачи искажают вероятностью значение одного из битов (одного из проводов). Определить количество информации, содержащейся в принятом сигнале Y относительно переданного сигнала X.
ВАРИАНТЫ:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

16)

17)

18)

19)

20)

**************************

**2.2.7. ЗАДАЧА 2.2.7 НЕ ПРИНИМАЕТСЯ - ДЛЯ НЕЕ ЕСТЬ ОБРАЗЦОВОЕ РЕШЕНИЕ.
См."!Образец оформления решения задачи со звездочкой (взаимная энтропия Шенона).mcd"
Д.с.в. ,

д.с.в. - заданы произвольными строками РАЗНОЙ длины. Длина строк и их содержимое может быть иным. Предполагается, что значение получено по-символьной (вариант: по-битной) передачей через линию с помехами. Найти ,,.

*************************
**2.2.8. ДСВ , если вычислить энтропию, считая символом 1 (одну) цифру, получим H(X)=,бит/символ. Если вычислим энтропию считая символом 3 (три) последовательных цифры - получим H(X)=0.

а) Почему так происходит?

б) Написать программу отыскивающую минимум и максимум H(X) для произвольной строки, выбором размера символа (числа букв на символ).

Похожие:

Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение любой задачи, помеченной (*), автоматический зачет по курсу
Закрепление понимания смысла энтропии Шенона. Практическое знакомство с методами генерации оптимальных кодов
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение любой задачи, помеченной (*) автоматический зачет по курсу
Практическое знакомство с методами генерации помехозащищенных кодов. Кодов обнаружения ошибок и кодов исправления ошибок
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconДвойственность в линейном программировании
Для любой задачи лп можно сформулировать двойственную задачу, являющуюся "зеркальным отражением" исходной задачи, т к она использует...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconУрока геометрии в 8-м классе: "Решение задач. Урок-зачет"
Проверить уровень знаний и умение решать задачи на применение свойств касательных, вписанных и описанных окружностей, медианы тркугольника,...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение многокритериальной задачи линейного программирования методом ограничений
Лабораторные работы по курсу тпр
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение задачи Коши
Учебно-тематические планы лекционных занятий по курсу «Уравнения в частных производных»
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconВопросы к экзамену по курсу "Введение в акустику"
Звуковые волны. Различные типы задач акустики (задачи о свободных волнах; задачи с начальными условиями; краевые задачи; задачи о...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение любой задачи 1
Здесь необходимо ориентироваться на те средства, которые предоставляют системы программирования и вычислительная техника, на которой...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconВведение в комбинаторику
Все это необходимо для изучения и построения формальных моделей и позволяет научиться такому подходу к любой задаче. При этом решение...
Решение любой задачи, помеченной (*), автоматический зачет по курсу iconРешение задач, аналогичных индивидуальным заданиям. Зачет проводится в письменном виде
Зачет осуществляется с учетом рейтинга по индивидуальным заданиям и рейтинга по результатам решения задач на письменном зачете
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org