Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации






Скачать 137.98 Kb.
НазваниеПрограмма дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации
Дата публикации09.02.2015
Размер137.98 Kb.
ТипПрограмма дисциплины
e.120-bal.ru > Документы > Программа дисциплины



Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины [Введите название дисциплины] для направления/ специальности
[код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста





Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"


Факультет прикладной математики и кибернетики

Программа дисциплины Теория информации



для направления 090301.65 «Компьютерная безопасность»

подготовки специалистов.


Автор программы: Духин А.А., кфмн, доцент, aadukhin@mail.ru
Одобрена на заседании кафедры Компьютерная безопасность «__11_»___06__ 20 11 г

Зав. кафедрой А.Б.Лось
Рекомендована секцией УМС ФПМ и К «___»____________ 20 г

Председатель А.Ю.Истратов
Утверждена УС факультета ФПМиК «___»_____________20 г.
Ученый секретарь А.Ю.Истратов _______________


Москва 2013

Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы

1Область применения и нормативные ссылки


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

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 090301.65 «Компьютерная безопасность» подготовки специалистов, изучающих дисциплину «Теория информации».

Программа разработана в соответствии с:

  • ФГОС для направления 090301.65 «Компьютерная безопасность».

  • Рабочим учебным планом университета по направлению 090301.65 подготовки специалиста, утвержденным в 2012г.

2Цели освоения дисциплины


Целями освоения дисциплины «Теория информации» являются:

- обеспечение приобретения знаний и умений в соответствии с государственным образовательным стандартом, содействие фундаментализации образования, формирование естественнонаучного мировоззрения, развитие системного мышления;

- ознакомление студентов с основными понятиями дисциплины, такими как: энтропия вероятностной схемы, источники информации, кодирование источников (компрессия информации), коды, исправляющие ошибки, характеристики и параметры кодов, методы кодирования и декодирования, методы построения кодов с заданными корректирующими свойствами, теоремы кодирования в связи с передачей информации по каналам связи;

- овладение навыками работы с литературой по дисциплине, навыками библиографических исследований.

3Компетенции обучающегося, формируемые в результате освоения дисциплины


Процесс изучения дисциплины «Теория информации» направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВПО по направлению «Компьютерная безопасность»

а) общекультурных (ОК)

- владеть культурой мышления, иметь способность к обобщению, анализу, восприятию

информации, постановке цели и выбору путей её достижения (ОК-1);

- уметь логически верно, корректно и аргументировано строить устную и письменную

речь (ОК-2);

- стремиться к саморазвитию, повышению своей квалификации и мастерства (ОК-9);

б) профессиональных (ПК)

- быть готовым к самостоятельной работе (ПК-1)

- быть способным использовать современные прикладные программные средства и

осваивать современные технологии программирования для решения практических задач,

формулируемых при изучении курса «Теория информации»;

- овладевать основными понятиями и положениями дисциплины;

- овладевать методами и способами преобразования информационных потоков для

решения поставленных задач;

- овладевать алгоритмами кодирования и декодирования для получения требуемых

результатов.

В результате освоения дисциплины студент должен:

  • Знать основные определения и утверждения «Теории информации» (ОК-10);

  • Уметь применять на практике методы и алгоритмы теории информации, теории кодирования;

  • Владеть навыками и методами решения практических задач теории информации.

    Методы обучения, способствующие развитию компетенций (ПК), используются на

    протяжение всего учебного процесса.


4Место дисциплины в структуре образовательной программы


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

Изучение её базируется на знаниях и умениях, приобретённых при освоении «Математи-

ческого анализа», «Линейной алгебры», «Теории вероятностей», «Случайных процесс-

сов», «Функционального анализа», «Дискретной математики».

  • Освоение данной дисциплины необходимо для изучения методов синтеза и анализа криптографических систем, для использования алгоритмов компрессии информации, алгоритмов кодирования и декодирования в качестве объектов изучения в курсе теории алгоритмов.


5Тематический план учебной дисциплины




Название раздела

Всего часов

Аудиторные часы

Самостоя­тельная работа

Лекции

Семинары

Практические занятия

1.

Энтропия и информация вероятностных схем

18

9

-

-

9

2.

Дискретные источники информации

18

9

-

-

9

3.

Оптимальное кодирование источников информации

18

9

-

-

18

4.

Коды, исправляющие ошибки

30

15

-

-

15

5.

Каналы связи. Теоремы кодирования в теории информации

24

12

-

-

12




Итого

108

54

-

-

54



6Формы контроля знаний студентов


Тип контроля

Форма контроля

3-й год

Параметры

Шестой семестр

Текущий


Контрольная домашняяработа

14 неделя*

Письменная работа

Текущий


Курсовая работа

16 неделя

Письменный отчёт по итогам работы

Итоговый

Зачёт




Устный зачёт

Итоговый


Экзамен




Устный экзамен


6.1Критерии оценки знаний студентов


Домашняя контрольная работа составлена из задач по всему материалу курса. Некоторые из задач являются трудоёмкими, требующими продолжительного времени для их решения. Выставляемая оценка, в основном, пропорциональна количеству правильно решённых задач.
В курсовой работе предполагается самостоятельное изучение теоретических разделов, не вошедших в программу курса «Теория информации» с использованием монографий либо периодической научной литературы. В ходе выполнения курсовой работы предполагается решение теоретических и практических задач.

6.2Формирование оценок по дисциплине


О накопл. = 0,5·Одом.контр.р. + 0,5·Окурс.р.
Оитог. = 0,4·Онакопл. + 0,6·Оэкзам.

Оценки по всем формам текущего контроля выставляются по 10-ти бальной шкале.

7Содержание дисциплины



Раздел 1. Энтропия и информация вероятностных схем.

Системы аксиом А.Я. Хинчина и Д.К. Фадеева. Эквивалентность систем аксиом. Теорема о единственности вида функции энтропии. Энтропия объединённой вероятностной схемы, условная энтропия. Теорема о связи энтропии объединённой вероятностной схемы и энтропии схем её составляющих. Понятия взаимной информации исходов, средней взаимной информации, собственной информации исхода, средней собственной информации. Соотношения, связывающие эти понятия. Понятия средней взаимной информации между схемами А и В относительно исхода с, относительно схемы С. Определение взаимной условной информации I((b;с)/а) между исходами bB, cC при фиксированном аА. Соотношение аддитивности информации. Теорема о невозрастании взаимной информации при сюръективных отображениях. Теорема о выпуклости средней взаимной информации. Теорема о локальных экстремумах функции I(A;B).
Раздел 2. Дискретные источники информации.

Математическая модель дискретного источника сообщений. Стационарный источник сообщений. Теорема о существовании энтропии у стационарного источника. Дискретный источник без памяти. Первая и вторая теоремы Шеннона для источников без памяти. Следствия из теорем. Марковские источники сообщений. Энтропия на знак и шаговая энтропия марковского источника. Первая и вторая теоремы Шеннона для марковских источников при глубине зависимости n=1. Определения эргодических источников. Теорема Бирхгофа. Примеры эргодических источников. Теорема об эргодичности источника без памяти. Леммы о свойствах эргодических источников. Теорема Мак-Милана и следствия из неё. Модели открытых текстов.

Раздел 3. Оптимальное кодирование источников информации.

Основные понятия «сжимающих » кодов: средняя длина, префиксный код, оптимальный код. Неравенство Крафта. Алгоритмы кодирования Фано и Шеннона. Понятия об оптимальных кодах и их свойствах. Алгоритм Хаффмана построения оптимального кода в двоичном и

D-ичном случаях. Теорема кодирования источника информации. Теорема Хинчина о нижней грани коэффициента сжатия кода.

Раздел 4. Коды, исправляющие ошибки.

Линейные (n,k) коды. Порождающие и проверочные матрицы. Двойственные коды. Систематические коды и теорема эквивалентности. Верхняя граница Хемминга и её асимптотическое представление. Совершенные коды и их примеры. Верхняя граница Плоткина. Эквидистантные коды и их примеры. Нижняя граница Варшамова-Гилберта и её асимптотическое представление. Стандартное расположение векторного пространства и процедура декодирования с использованием этой таблицы. Декодирование линейных кодов с использованием синдромов. Метод последовательного декодирования Прейнджа. Код Хемминга, кодирование и декодирование. Индуктивное построение проверочной матрицы кода Хемминга. Код двойственный коду Хемминга. Методы построения новых кодов путём добавления общей проверки на чётность, выкалыванием кодовых координат, выбрасыванием слов, добавлением новых кодовых слов, укорочением кодовых слов, с использованием прямой и полупрямой суммы, произведения кодов. Определение циклических кодов, задание их с помощью порождающих многочленов и порождающих матриц. Кодирование и декодирование циклических кодов. Теорема о порождающем многочлене кода, двойственного циклическому. Теорема о порождающих многочленах циклических кодов. БЧХ-коды с параметром d. Теорема о кодовом расстоянии БЧХ-кода. Алгоритм построения БЧХ-кода, исправляющего заданное число ошибок.
Раздел 5. Каналы связи. Теорема кодирования.

Математическая модель дискретного канала без памяти. Пропускная способность канала связи и методы нахождения её для симметричных каналов и в общем случае. Прямая теорема кодирования Шеннона для двоичного симметричного канала. Обратная теорема кодирования Шеннона для двоичного симметричного канала. Следствия из теоремы кодирования.

8Лабораторный практикум


Не планируется.

9Тематика курсовых работ


По отдельному списку. Приложение 1.

10Учебно-методическое и информационное обеспечение дисциплины

10.1Основная литература


  1. Галлагер Р. Теория информации и надёжная связь. М.: Сов. Радио. 1974.

  2. Духин А.А. Теория информации. М.: Гелиос АРВ. 2007.

  3. Мак-Уильямс Ф.Дж., Слоэн Н.Дж. Теория кодов, исправляющих ошибки. М.: Связь. 1979.

  4. Токура Н., Кассами Т., Ивадари Я., Инагаки К. Теория кодирования. М.: Мир. 1978.

  5. Чечёта С.И. Введение в дискретную теорию информации и кодирования. М.: МЦНМО. 2011.

10.2Дополнительная литература


1.Берлекемп Э. Алгебраическая теория кодирования. М.: Мир. 1971.

2. Колесников В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 1982.

3. Чисар И., Кернер Я. Теория информации. М.: Мир, 1985.

4. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М.:

Наука, 1980.

10.3Справочники, словари, энциклопедии


Математическая энциклопедия (т.т.1-5) М.: Изд-во «Советская энциклопедия» 1977-1985.
    1. Программные средства


Программные средства не предусмотрены.

10.4Дистанционная поддержка дисциплины


Дистанционная поддержка дисциплины не предусмотрена.

11Материально-техническое обеспечение дисциплины


Материально-техническое обеспечение дисциплины не предусмотрено.
Приложение 1.
Список тем курсовых работ.


  1. Получить формулу энтропии конечной вероятностной схемы

Н(А) = -i)logp(ai),

исходя из посылок К. Шеннона.

  1. Получить доказательство первой теоремы Шеннона для марковских источников с глубиной зависимости два, т.е. для случая

p(I,j,k)= p(i) p(j/i) p(k/i,j).

  1. Оценить количество последовательностей длины l, порождённых источником

[А,p(s)] c использованием теоремы Фробениуса.

4. Сделать обзор работ по энтропии русского языка.

5. Сделать обзор работ по энтропии литературных языков романской группы.

6. Изучить арифметический метод сжатия информации.

7. Алгоритмы группы L,LZ сжатия информации (Якоб Зив, Абрам Лемпел).

8. Алгоритмы группы LZW сжатия информации (Я. Зив, А. Лемпел, Т. Велч).

9. Обзор методов сжатия видеоинформации.

10. Создать оптимальную программу, реализующую метод Хаффмана для

[A,p(s)] при D≥2.

11. Совершенные коды над конечными полями (по статье Титвайнена)

12. Доказать, что двоичный [23,12,7] – код Голея G23 совершенный.

13. Доказать, что троичный [11,6,5] – код Голея G11 совершенный.

14. Коды Рида-Малера. Определение. Кодирование и декодирование. Весовые спектры.

15. Эквидистантные коды. Определение. Свойства. Примеры.

16. Вывести тождества Мак-Уильямс. Рассмотреть примеры нахождения спектров двоичных

кодов.

17. Создать алгоритм построения БЧХ-кода для GF(pα), как обобщение случая р=2, α=1.

Привести примеры.

18. Разработать оптимальную программу для нахождения С- пропускной способности ДКБП.

19. Методы построения матриц Адамара. Квадратично-вычетные коды.

20. Исследования по классификации классов эквивалентности матриц Адамара.

Приложение 2

Типовой вариант домашней контрольной работы.

1. Как изменится величина энтропии дискретной вероятностной схемы, если:

а) уменьшить максимальное значение вероятностей исходов,

б) увеличить максимальное значение вероятностей исходов?

Ответ обосновать.
2. Вычислить энтропию вероятностной схемы А, распределение которой задано плотностью

f(x) = exp(-x) для x ≥ 0, 0 для х < 0


  1. Покажите, что функция f(x) = -xlnx является выпуклой вверх на интервале (0,∞) функцией.

4. Каждому числу 1,2,4,17,98 поставим в однозначное соответствие в качестве кодового слова его двоичное разложение. Будет ли такой код однозначно декодируемым?

5. Найти такое наименьшее nN и распределение (p1,…,рn), при которых существуют оптимальные коды, различающиеся наборами длин кодовых слов.

6. Задан источник без памяти

[А,р(s)] = [(a1,…,a7), p1=0,3, p2=0,25, p3=0,15, p4=p5=0,1 p6=p7=0,05].

а) Построить двоичные коды, используя алгоритмы Фано, Шеннона и Хаффмана.

б) Подсчитать среднюю длину для каждого из построенных кодов.

7. При передаче по ДСК искажается не более одной компоненты, тот есть, если

h = g + e – слово на выходе ДСК, то вес вектора ошибок W(e)≤1.

Для кодов G(3,2) = {(000),(110),(011),(101)}

G(5,2) = {(00000),(10110),(01101),(11011)}

построить возможные последовательности на выходе канала.


  1. .Задан источник без памяти [A,p(s)] = [{0,1}, p(0) = 0,995, p(1) = 0,005].

Кодируются лишь те порождаемые источником двоичные последовательности

= (ε1 ,…,εn ), n = 100, которые содержат не более трёх единиц. В качестве кодовых слов используются двоичные векторы = (δ1 ,…,δm ).

Определить:

а) каково должно быть m, чтобы обеспечить однозначное декодирование?

б) какова вероятность порождения последовательности, которой не соответствуют

кодовые слова? (Указание: примените распределение Пуассона).



  1. Подсчитать вероятность ошибки декодирования при передаче по ДСК равновероятных кодовых слов линейного кода, задаваемого порождающей матрицей




  1. Построить двоичный код Хемминга H(15,11,3).

а) Выписать порождающую и проверочную матрицы.

б) Закодировать информационную последовательность g = (11111100000).

в) Декодировать вектор h = (111000111000111).


  1. Найти код, двойственный к коду кратных повторений.


12. Убедиться, что код G, заданный порождающей матрицей
G =
является циклическим. Найти его порождающий многочлен, проверочный многочлен и

проверочную матрицу.






Добавить документ в свой блог или на сайт

Похожие:

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки подготовки...

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки/ специальности...

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 081100....

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 081100....

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов 4 курса направления 080100....

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов 4 курса направления 080100....

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 230100. 62 Информатика...

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 230100. 62 Информатика...

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины [Введите название дисциплины] для направления/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 035800. 62 «Фундаментальная...

Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации iconПрограмма дисциплины для направления/ специальности подготовки бакалавра/...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 080200. 62 «Менеджмент»...






При копировании материала укажите ссылку © 2016
контакты
e.120-bal.ru
..На главную