Рабочая программа учебной дисциплины "Математические основы безопасности информационных технологий", страница 2

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

·  переводить числа в разные позиционные системы счисления, выполнять арифметические операции в разрядных сетках с плавающей и фиксированной запятой  с использованием машинных кодов;

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

·  строить формальный вывод в исчислении высказываний, приводить примеры формального вывода в исчислении предикатов;

·  записывать алгоритмы на языке машины Тьюринга.

·  реализовать на ЭВМ изученные алгоритмы и вычислять их сложность.  

1.3.  ФОРМЫ КОНТРОЛЯ

Текущий контроль. В процессе обучения студенты выполняют расчетные задания и лабораторные работы, результаты выполнения защищают  преподавателю. Предусмотрены по 4 индивидуальных задания в 1,2, 3 и 4 семестрах, которые студенты выполняют в письменной форме и сдают преподавателю. Если задание выполнено неверно, то оно возвращается студенту для доработки.

Промежуточная аттестация. Для контроля усвоения студентами данной дисциплины учебным планом предусмотрены:  экзамены в 1 и 3 семестрах, зачет во 2 и 4 семестрах, курсовая в 4-м семестре.

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

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

(Распределение часов)

Наименование разделов и тем	Очная форма обучения
	Количество часов
	Лекции	Практ. занятия	Сам. работа	Всего часов по теме
Тема 1.  Основы теории информации и кодирования	9	17	1	27
Тема 2.  Системы счисления и машинная арифметика	8	17	1	26
Тема 3.  Основы теории множеств и комбинаторики	9	26	1	36
Тема 4.  Основы теории графов	10	14	1	25
Тема 5.  Алгебра  логики  и элементы теории формальных систем	18	20	1	39
Тема 6.  Основы теории алгоритмов	10	18	1	29
Тема 7. Введение в анализ алгоритмов	6	8	1	15
Тема 8. Простейшие методы сортировки массива	4	2	2	8
Тема 9. Теоретико-числовые алгоритмы	3	4	2	9
Тема 10. Рекурсивные алгоритмы	3	4	2	9
Тема 11.  Алгоритмы поиска	3	4	2	9
Тема 12. Динамические структуры данных	3	4	2	9
Тема 13. Вычислительные алгоритмы	3	4	2	9
Итого	87	142	19	250
	89	142	19	250

2.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ПРОГРАММЫ

Тема 1. Основы теории информации и кодирования.

Понятие и принципы измерения информации в модели Шеннона. Информационная неопределенность, количество информации – формулы Хартли и Шеннона. Энтропия и ее свойства. Избыточность источника информации. 

Понятие кода, равномерные и неравномерные коды. Условие Фано.  Избыточность кода, количество и объем информации. Понятие оптимального кодирования, характеристики оптимальности кода. Методы оптимального кодирования.  

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

Сжатие информации. Сжатие без восстановления информации. Сжатие с восстановлением информации для числовых массивов и последовательностей. 

Криптографическое кодирование (шифрование) информации. Понятие ключа. Принципы замены и перестановки. Шифр Цезаря. Шифр Вижинера. 

Передача информации: понятие канала передачи информации, скорость передачи информации (техническая и информационная) и пропускная способность канала связи.

Тема 2. Системы счисления и машинная арифметика.

Позиционные системы счисления. Представление числа в натуральной системе счисления. Алгоритмы перевода чисел в разные систем счисления. Операции округления в позиционных системах и погрешности  в результате округления. Понятие об уравновешенных системах счисления. 

 Представление чисел в ЭВМ в разрядных сетках с фиксированной и плавающей запятой. Диапазоны представимых чисел, понятие машинного нуля и переполнения разрядной сетки. Операции над числами, представленными с плавающей запятой. Машинные коды. Арифметические операции над числами, представленными в машинных кодах.

Тема 3. Основы теории множеств и комбинаторики. 

Понятие множества. Упорядоченные и неупорядоченные множества. Способы задания множеств: список элементов, разрешающая и порождающая процедуры. Операции над множествами. Доказательство теоретико-множественных соотношений. Конечные и бесконечные множества. Мощность множества. Теорема Кантора.

Объекты и методы комбинаторного анализа. Основные правила комбинаторики. Базовые комбинаторные объекты: перестановки, размещения, сочетания, разбиения. Формулы расчета комбинаторных чисел.  Свойства и оценки комбинаторных чисел.

Метод включений и исключений. Метод траекторий. Рекуррентные уравнения (РУ): общее понятие,  линейные РУ первой степени и их решение.

Ряды и производящие функции: понятие числовых и переменных рядов, сумма ряда, сходимость рядов и область сходимости, свойства степенных рядов, понятие обыкновенной производящей функции. Примеры применения производящих функций для доказательства комбинаторных соотношений. Решение линейного РУ второй степени с использованием производящих функций. 

Тема 4. Основы теории графов.

Понятие и виды графов. Способы представления графов. Маршруты и связность. Расстояния в графе. Части графа и операции над графами. Графы и бинарные отношения. Изоморфизм графов.