Рабочая программа дисциплины Теоретические основы информатики (стр. 2 )

Построение систематического кода. Таблица проверок. Кодер и декодер систематического кода. Канонический систематический код. Код Хемминга. Матричные коды.

6. Элементы теории автоматов. Понятие автомата. Классификация автоматов. Описание автомата. Автоматные функции.

Дискретные устройства без памяти (комбинационные схемы). Логические элементы. Базис элементов. Решение прямой и обратной задачи.

Машина Тьюринга как автомат с бесконечной памятью. Решение алгоритмических задач с использованием машины Тьюринга.

Понятие конечного автомата. Способы описания конечного автомата (табличный, диаграмма Мура). Виды элементов памяти конечных автоматов (задержка, триггер, двоичный счетчик). Понятие о полноте элементов. Правила построения схем. Решение прямой и обратной задачи. (*) Эквивалентные автоматы.

7. Элементы криптографии. Терминология криптографии. Обзор криптографических методов. Постановка задачи шифрования. Схема криптосистемы с симметричным шифрованием. Некоторые методы шифрования. Совершенная стойкость шифра. Требования, предъявляемые к ключам. Шифрование с открытым ключом. Формирование ключей и шифрование в криптосистеме RSA. Электронная подпись. Вычисление и проверка подлинности электронной подписи.

Перечень тем лекционных занятий

№ п/п	Наименование лекции	Содержание лекции
1	Введение	Место информатики в системе наук. Исходные понятия информатики. Формы представления информации. Знак, алфавит.
2	Введение	Элементы теории вероятностей.
3	Энтропия как мера неопределенности	Понятие энтропии. Свойства энтропии. Условная энтропия. Энтропия и информация.
4	Информация, измерение информации	Формулы Хартли и Шеннона. Измерение количества информации. Информация и алфавит
5	Кодирование символьной информации (ч.1)	Понятие кода, кодирования. Первая теорема Шеннона. Постановка задачи кодирования. Равномерное кодирование.
6	Кодирование символьной информации (ч.2)	Алфавитное неравномерное кодирование. Оптимальные коды. Блочное кодирование.
7	Кодирование числовой информации (ч.1)	Представление чисел в компьютере. Системы счисления. Преобразование целых и вещественных чисел.
8	Кодирование числовой информации (ч.2)	Кодирование и обработка в компьютере целых и вещественных чисел в компьютере.
9	Передача информации	Характеристики канала связи. Влияние шумов на пропускную способность канала. Дискретные каналы.
10	Теория помехоустойчивого кодирования	Принципы помехоустойчивого кодирования. Граница Хемминга.
11	Построение помехоустойчивых кодов (ч.1)	Построение систематического кода. Таблица проверок. Кодер и декодер систематического кода. Канонический систематический код.
12	Построение помехоустойчивых кодов (ч.2)	Код Хемминга. Матричные коды.
13	Описание конечных автоматов. Комбинационные схемы.	Понятие автомата. Описание автомата. Автоматные функции. Дискретные устройства без памяти (комбинационные схемы). Логические элементы.
14	Конечные автоматы.	Виды элементов памяти конечных автоматов. Правила построения схем. Решение прямой и обратной задачи.
15	Машина Тьюринга	Машина Тьюринга. Решение задач в машине Тьюринга.
16	Элементы криптографии (ч.1)	Понятия криптографии. Методы симметричного шифрования.
17	Элементы криптографии (ч.2)	Асимметричная схема шифрования. Метод RSA.
18	Элементы криптографии (ч.3)	Электронная подпись.

Перечень тем лабораторных работ

№ разд	№ ЛР	Тематика лабораторной работы
2	Теория информации (6 уч. ч.)
ЛР_0	Элементы теории вероятностей.
ЛР_1	Расчет энтропии, количества информации.
ЛР_2	Частотный анализ текста. Определение типа сообщения.
3	Кодирование информации (10 уч. ч.)
ЛР_3(1)	Сравнение методов кодирования.
ЛР_3(2)	Сопоставление блочного и алфавитного кодирования.
ЛР_4 (1)	Кодирование чисел. Ч. 1. Системы счисления.
ЛР_4 (2)	Кодирование чисел. Ч. 2. Нормализация чисел.
ЛР_4 (3)	Кодирование чисел. Ч. 3. Операции с кодами чисел.
4	Передача информации (4уч. ч.)
ЛР_5 (1)	Исследование дискретных каналов связи. Ч. 1. Симметричный канал.
ЛР_5 (2)	Исследование дискретных каналов связи. Ч. 2. Канал со стиранием.
5	Помехоустойчивое кодирование (4 уч. ч.)
ЛР_6 (1)	Построение систематического кода. Ч. 1. Канонический код.
ЛР_6 (2)	Построение систематического кода. Ч. 2. Код Хемминга.
6	Элементы теории автоматов (6 уч. ч.)
ЛР_7 (1)	Ч. 1. Комбинационные схемы.
ЛР_7 (2)	Ч. 2. Конечные автоматы.
ЛР_8	Алгоритмическая машина Тьюринга.
7	Элементы криптографии (6 уч. ч.)
ЛР_9 (1) ЛР_9 (2) ЛР_9 (3)	Методы шифрования. Кодирование с закрытым ключом. Построение электронной подписи.

Примерные вопросы для контроля и самоконтроля
по разделам (темам)

№ п/п	Наименование раздела (темы)
2	Теория информации Исходные понятия информатики: сообщение, информация, источник и приемник информации. Сигнал и его информационные параметры. Виды информации (непрерывная, дискретная). Преобразование форм представления информации. Универсальность дискретного представления информации. Понятие энтропии. Свойства энтропии. Энтропия и информация. Статистическое определение информации. Информация и алфавит. Формула Шеннона.
3	Кодирование информации Математическая постановка задачи кодирования. Неравномерное алфавитное кодирование с разделителем кодов. Оптимальные коды (Хаффмана, Шеннона-Фано). Равномерное двоичное кодирование. Байт. Стандарты компьютерных кодов. Системы счисления. Позиционные системы счисления. Перевод целых и дробных чисел в различные системы счисления. Системы счисления, используемые в компьютере. Перевод целых и дробных чисел между системами счисления с основанием 2 – 8 – 16. Представление целых чисел в компьютере. Сложение и умножение целых чисел. Дополнительный код двоичного числа. Вычитание двоичных целых чисел. Нормализованная форма вещественного числа. Представление вещественных чисел в компьютере. Сложение и умножение нормализованных двоичных чисел. Влияние ограниченной разрядности чисел на точность вычислений. Понятие переполнения и машинного нуля.
4	Передача и хранение информации Понятие канала и линии связи. Характеристики канала связи: ширина пропускания, пропускная способность, скорость передачи. Влияние шумов на пропускную способность канала. Параллельная передача данных в компьютерных линиях. Последовательная передача. Модемная связь. Постановка задачи хранения информации. Хранение элементарных данных в памяти компьютера. Идентификаторы. Структуры данных. Классификация и примеры структур данных. Размещение структур данных в ОЗУ: последовательные и связанные списки. Размещение данных на внешних носителях. Понятия физической записи, файла, каталога (папки), структур каталогов. Блок, кластер
5	Помехоустойчивое кодирование Общие принципы помехоустойчивого кодирования. Классификация корректирующих кодов. Избыточность помехоустойчивого кода. Принципы обнаружения и исправления ошибок в систематических кодах. Понятие кодового вектора, кодового расстояния. Граница Хемминга. Порядок построения систематического кода. Таблица проверок. Кодер и декодер систематического кода. Построение канонического систематического кода по заданной производящей матрице или схеме кодера. Построение кода Хемминга.
6	Элементы теории автоматов Понятие автомата. Описание автомата. Автоматные функции. Дискретные устройства без памяти. Построение комбинационной схемы по логической функции (или наоборот). Решение алгоритмических задач с помощью машин Поста и Тьюринга. Конечные автоматы. Способы описания конечных автоматов (табличный, с помощью диаграмм). Виды элементов памяти конечных автоматов; их диаграммы. Построение конечного автомата по системе уравнений, таблице значений, диаграмме или для заданной схемы автомата построение его описания.
7	Элементы криптографии Методы шифрования. Стойкость шифра. Представление об асимметричной криптосистеме. Использование электронной подписи.

перечень учебно-методического обеспечения
для самостоятельной работы обучающихся
по дисциплине Учебно-методическое обеспечение

Для организации самостоятельной работы обучающихся используется следующее обеспечение: