Учебная программа дисциплины дпп. В. 05. Теория информации Специальность: 050201 Математика

Вид материала

Программа дисциплины

Содержание Специальность: 050201 Математика Лекций: 32 час. Дисциплина “Теория информации” является дисциплиной по выбору студентов. Задачи дисциплины Принципы отбора содержания и организации учебного материала Требования к освоению содержания дисциплины Виды контроля Планирование содержания дисциплины Ii. содержание дисциплины Модуль №2 Элементы теории кодирования. Основные понятия. Iii. организация самостоятельной работы Iv. контроль качества освоения дисциплины 3. Итоговый контроль. V. учебно-методичексое обеспечение дисциплины 2. Электронно-программные средства.

Подобный материал:

• Рабочая программа учебной дисциплины дпп. Ф. 07. Теория чисел ооп, 386.12kb.
• Программа дисциплины дпп. Ф. 06 Алгебра специальность 032100 (050201. 65) Математика, 199.61kb.
• Программа дисциплины дпп. Ф. 07 «геометрия» Специальность 032100 (050201. 65) Математика, 296.7kb.
• Учебно-методический комплекс учебной дисциплины дпп. Р. 01. Математическое конструирование, 83.94kb.
• Программа дисциплины дпп ф. 09 «числовые системы» Специальность 032100 (050201. 65), 121.39kb.
• Программа учебной дисциплины история математики специальность 050201 математика с дополнительной, 409.11kb.
• Рабочая программа учебной дисциплины дпп. Ф. 08 Числовые системы ооп, 599.58kb.
• Программа учебной дисциплины методы математической физики специальность «050201 математика, 145.93kb.
• Учебная программа (Syllabus) Дисциплина: Теория судебных доказательств Специальность, 272.03kb.
• Программа дисциплины теория алгоритмов специальность 050201. 65 «Математика» с дополнительной, 454.48kb.

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Иркутский государственный педагогический университет»

Факультет математики, физики и информатики


Утверждено

на заседании совета факультета

математики, физики и информатики

протокол №­­­­­­_____от __________2006 г.

Председатель совета________________

(Кузьмина Н.Д.)

УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ

ДПП. В.05. Теория информации

Специальность: 050201 Математика

Квалификация: Учитель математики


Курс: 4

Семестр: 9

Форма обучения: очная


Количество часов на дисциплину: 66 час.

Количество аудиторных часов: 32 час.; из них:

Лекций: 32 час.

Самостоятельная работа: 34 час.


Итоговый контроль: зачет

I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

Место дисциплины

Дисциплина “Теория информации” является дисциплиной по выбору студентов.

Цель дисциплины

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

Задачи дисциплины

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


Принципы отбора содержания и организации учебного материала

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


Требования к освоению содержания дисциплины

Студент должен знать:

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

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

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

Студент должен уметь разрабатывать информационные модели для решения задач.

Студент должен владеть:

- основными методами построения конечных автоматов,

- методами синтеза конечных автоматов в виде схем из функциональных элементов и задержек.


Виды контроля

Текущий – проводится по каждой учебной единице в форме проверки домашнего задания.

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

Итоговый – проводится в форме зачета.


Планирование содержания дисциплины

№	Название модуля	Часы аудиторных занятий		Часы самостоятельной работы	Всего часов
		Лекции	Практ. занятия
1	Схемы из функциональных элементов и конечные автоматы.	16		16	32
2	Элементы теории кодирования	16		18	34
	Итого	32		34	66

II. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ


Модуль №1 Схемы из функциональных элементов и конечные автоматы.

1) Определение схем из функциональных элементов и основные задачи.

Основные понятия и определения. СФЭ с двоичными входами и выходами. Задачи анализа и синтеза СФЭ.

2) Некоторые методы синтеза схем над элементарным базисом.

Алгоритм, основанный на СДНФ. Компактный многополюсник и оптимизация алгоритма, основанного на СДНФ. Разложение по остаточным и основанный на этом принципе алгоритм. Асимптотическая сложность схем, построенных при помощи указанных алгоритмов. Построение простейших вычислительных устройств в виде СФЭ (сумматор) и сравнение их по сложности.

3) Определение и методы задания конечных автоматов.

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

4) Конечные автоматы с автономным входом.

Определение автономного конечного автомата. Теорема о квазипериодическом виде выходного слова автономного конечного автомата. Доказательство невозможности реализации на конечном автомате умножения чисел.

5) Минимизация конечных автоматов.

Алгоритм минимизации конечных автоматов и примеры минимизации.


Модуль №2 Элементы теории кодирования.

1) Основные понятия теории кодирования.

Общая схема передачи информации. Кодирование его цели, способы и примеры. Коды со свойством префикса (суффикса). Теорема Маркова. Алгоритм распознавания однозначности декодирования алфавитного кода.

2) Криптография и криптоанализ.

Задачи защиты информации. Симметричные криптосистемы. Асимметричные криптосистемы и использование при их построении NP-полных задач. Метод рюкзака. Электронная подпись.

3) Помехоустойчивое кодирование.

Помехоустойчивое кодирование, ошибки, принцип их обнаружения или исправления. Примеры помехоустойчивых кодов. Код Хэмминга. Кодовое расстояние. Корректирующие возможности кода. Порождающая и проверочная матрицы. Коды Рида-Маллера. Мажоритарное декодирование. Линейные коды.


Основные понятия.


Двоичные наборы; схемы из функциональных элементов; конечные автоматы; минимизация конечных автоматов; асимметричные криптосистемы; электронная подпись; помехоустойчивые коды.


III. ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ


I. Построение конечных автоматов в виде программируемых логических матриц.

Задание для самостоятельной работы.

1. Изучить теоретический материал по указанной литературе [1,4 из основного списка литературы].
   
2. Выполнить задания:
   

Осуществить полный цикл реализации преобразования информации в виде конечного автомата и ПЛМ:

a) на основе канонических форм;

b) на основе ДНФ и карт Карно;


Каждый студент получает индивидуальное задание по задачам вышеперечисленных типов.


Контроль. Решенные задачи сдаются на проверку преподавателю, теоретические вопросы выносятся на экзамен.


IV. КОНТРОЛЬ КАЧЕСТВА ОСВОЕНИЯ ДИСЦИПЛИНЫ

1. Текущий контроль.

Проводится по каждой учебной единице в форме проверки домашнего задания.

2. Рубежный контроль.

Проводится по каждому из четырёх модулей в форме контрольных работ с рейтинговой оценкой от 0 до 25 баллов.

3. Итоговый контроль.

Проводится в форме зачет.


Вопросы и задания к зачету.

1. Двоичные наборы, число наборов фиксированной длины, натуральное упорядочивание наборов.


2. СФЭ с двоичными входами и выходами. Задачи анализа и синтеза СФЭ.

3. Алгоритм синтеза СФЭ, основанный на СДНФ. Компактный многополюсник и оптимизация алгоритма, основанного на СДНФ. Асимптотическая сложность.

4. Разложение по остаточным и основанный на этом принципе алгоритм синтеза СФЭ. Асимптотическая сложность

5. Построение простейших вычислительных устройств в виде СФЭ (сумматор) и сравнение их по сложности.

6. Определение конечных автоматов, автоматные таблицы, задание диаграммами. Канонические уравнения конечных автоматов.

7. Конечные автоматы: сумматор, задержка на один и два такта.

8. Определение автономного конечного автомата. Теорема о квазипериодическом виде выходного слова автономного конечного автомата.

9. Доказательство невозможности реализации на конечном автомате умножения чисел.

10. Алгоритм минимизации конечных автоматов и примеры минимизации.

11. Общая схема передачи информации. Кодирование его цели, способы и примеры. Коды со свойством префикса (суффикса).

12. Теорема Маркова.

13. Алгоритм распознавания однозначности декодирования алфавитного кода.

14. Задачи защиты информации. Симметричные криптосистемы.

15. Асимметричные криптосистемы и использование при их построении NP-полных задач. Метод рюкзака.

16. Электронная подпись.

17. Помехоустойчивое кодирование, ошибки, принцип их обнаружения или исправления. Примеры помехоустойчивых кодов.

18. Код Хэмминга. Кодовое расстояние. Корректирующие возможности кода. Порождающая и проверочная матрицы.

19. Коды Рида-Маллера. Мажоритарное декодирование. Линейные коды.


V. УЧЕБНО-МЕТОДИЧЕКСОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ


1. Рекомендуемая литература.

а) Основная.

1. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980.
   
2. Кузнецов О.П. Дискретная математика для инженера. – СПб: Издательство «Лань», 2004.
   
3. Зубков О.В. Дискретные преобразователи информации. Учебное пособие. – Иркутск. Издательство ИГПУ, 2005.
   
4. Карпов Ю.Г. Теория автоматов. – СПб.: Питер, 2002.
   
5. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1985.
   
6. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
   

б) Дополнительная.

1. Лидл Р. Пильц Г. Прикладная абстрактная алгебра. – Екатеринбург: издательство Уральского университета, 1996.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы.М.:

ЛБЗ, 2001.

5. Верещагин И.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999.


2. Электронно-программные средства.

1. Компьютерные демонстрационные программы по математическим моделям алгоритмов (ссылка скрыта – из внутривузовской сети, ссылка скрыта –из Интернета).
   

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

2. Библиотека книг по теоретическим основам информатики на электронном носителе (имеется на кафедре математической информатики).


Составитель: кандидат физ.-мат. наук, доцент кафедры

математической информатики Зубков Олег Владимирович


Утверждено

на заседании кафедры

математической информатики

(протокол № ___ от __________ 200_ г.)


Зав. кафедрой ______________________

Н.А. Перязев


Утверждено

на заседании УМС факультета

математики, физики и информатики

(протокол № ___ от ___________ 200_ г.)


Председатель УМС___________________

Н.Д. Кузьмина