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

Таблица 3. Разделы дисциплины, изучаемые в 1 семестре.

№ раздела	Наименование разделов	Количество часов
Всего	Аудиторная работа	Самостоятельная работа
Л	ПЗ	ЛР
	Язык математики и основные операции над множествами
	Логика высказываний
	Логика предикатов
	Теория множеств
	Отношения
	Функции
	Итого:

Таблица 4. Разделы дисциплины, изучаемые во 2 семестре.

№ раздела	Наименование разделов	Количество часов
Всего	Аудиторная работа	Самостоятельная работа
Л	ПЗ	ЛР
	Исчисления высказываний и предикатов
	Алфавитное кодирование
	Симметричное шифрование
	Введение в теорию графов
	Итого:

Таблица 5. Разделы дисциплины, изучаемые в 3 семестре.

№ раздела	Наименование разделов	Количество часов
Всего	Аудиторная работа	Самостоятельная работа
Л	ПЗ	ЛР
	Элементы комбинаторики
	Комбинаторный анализ
	Дискретные вероятности
	Итого:
	Всего:

Лабораторные работы

№ работы	№ раздела дисциплины	Наименование лабораторных работ
		Построение таблиц истинности для формул
		Нахождение СДНФ и СКНФ
		Предполные замкнутые классы
		Построение схем из функциональных элементов
		Построение и преобразование формул логики предикатов
		Преобразования формул с кванторами
		Равносильность формул с предикатами
		Предваренная нормальная форма
		Операции над множествами
		Декартово произведение множеств
		Мощность множества
		Принцип включения-исключения
		Обратные отношения и композиции отношений
		Транзитивные отношения
		Отношения порядка
		Минимальные и максимальные элементы
		Инъективные и сюръективные функции
		Биективные функции
		Принцип Дирихле и теорема Эрдёша-Секереша
		Равномощные бесконечные множества
		Правила вывода исчисления высказываний.
		Автоматическое доказательство теорем.
		Формулы исчисления предикатов.
		Правила вывода исчисления предикатов.
		Алгоритм проверки однозначности декодирования.
		Неравенство Макмиллана.
		Коды с минимальной избыточностью.
		Самокорректирующиеся коды. Код Хэмминга.
		Последовательные коды.
		Блочные коды.
		Алгоритм DES.
		Криптоанализ.
		Операции над графами. Деревья.
		Связность графов.
		Алгоритмы Краскала и Дейктры.
		Планарность графов.
		Размещения. Перестановки. Сочетания. Бином Ньютона.
		Сочетания с повторениями. Количество решений уравнения.
		Автоморфизмы графов.
		Мультимножества. Разложение подстановки на циклы.
		Производящая функция
		Экспоненциальная производящая функция
		Подсчет количества корневых деревьев
		Подсчет количества связных графов
		Вероятности суммы, произведения и разности событий
		Теорема Байеса
		Распределения дискретных случайных величин
		Математическое ожидание и дисперсия

Расчетно-графические задания

По каждому разделу студентом выполняется одно индивидуальное расчетно-графическое задание. Темы заданий для каждого студента различны. Задача РГЗ состоит в проверке умений студента и проверки эффективности его самостоятельной работы.

Темы заданий ежегодно обновляются. Общая тематика соответствует тематике лабораторных работ.

Самостоятельное изучение разделов дисциплины

Раздел 1.Имена, именные формы, высказывательные формы. Логические знаки. Таблицы истинности для отрицания, конъюнкции, дизъюнкции.

Раздел 2. Интерпретации переменных. Таблицы истинности. Интерпретации формул.

Раздел 3. Понятие предиката. Основные понятия. Примеры предикатов. Связь с высказываниями. Кванторы. Свободные и связанные переменные. Конечные предметные области.

Раздел 4. Свойства операций над множествами. Мощность конечного множества.

Раздел 5. Понятие отношения. Запись отношения. Бинарные отношения. Тривиальное, универсальное и тождественное отношения. Связь отношения и предиката.

Раздел 6. Понятие функции. Области определения и значений. Всюду определенная функция. Образы, прообразы. Графики функций.

Раздел 7. Алфавит исчисления высказываний. Формулы исчисления высказываний. Алфавит исчисления предикатов.

Раздел 8. Критерий однозначности декодирования.

Раздел 9. Шифрование и дешифрование. Однозначность.

Раздел 10. Основные понятия. Граф, мультиграф, псевдограф. Ориентированные, неориентированные графы. Смежность, инцидентность, степень вершины. Изолированные, концевые вершины.

Раздел 11. Правило суммы. Правило прямого произведения. Размещения с повторениями. Размещения без повторений.

Раздел 12. Понятие производящей функции. Основные свойства производящей функции.

Раздел 13. Массовые случайные явления. Пространство элементарных событий. Понятие события, сумма, произведение, разность событий. Вероятности элементарных событий.