Обзор приложений дискретной математики

Разработка эффективного математического, программного, информационного и технического обеспечения на основе методов дискретной математики

№ п/п

Результаты обучения

Семестр, раздел / тема. Виды учебной деятельности. Краткое содержание

Образовательные технологии

* Неделя

Трудоемкость, час

Форма текущего контроля

4 семестр

Тема: Множества, отношения

Знать и понимать: Способы задания множеств. Операции объединения, пересечения, разности, дополнения и декартова произведения. Бинарные отношения. Способы задания бинарных отношений. Свойства бинарных отношений. Разбиения. Отношения эквивалентности и порядка. Представление n-арных отношений бинарными. Алгебра отношений. Определения функции. Инъекция, сюръекция и биекция. Индуцированная функция. Представление функции с помощью массива Понятие мощности множестваю Счетные множества и их свойства.. Несчетные множества Уметь: Задавать множества. Осуществлять операции объединения, пересечения, разности, дополнения и декартова произведения множеств. Задавать отношения, классифицировать их и применять их.

Лекция1. Множества и операции над ними. Практическое занятие 1. Множества и операции над ними.

Лекция, презентация, Тренинг, тест

2+2

Опрос на практическом занятии

Лекция 2: Отношения Практическое занятии 2: Отношения.

2+2 2+2

Опрос на практическом занятии

Лекция 3: Функции. Счетные и несчетные множества Практическое занятии 3: Функции. Счетные и несчетные множества.

СРС:Изучение материала лекции 1 - 3. Анализ рассмотренных примеров. Выполнение домашних заданий

1-3

Опрос, тест

Тема: . Алгебраические структуры

Знать и понимать:. Основные алгебры с одной и двумя операциями. Жадный алгоритм Уметь: работать с основными алгебрами. Применять жадный алгоритм

Лекция 4Операции и алгебры Алгебраические структуры. Замыкания и подалгебры. Алгебра термов. Свойства операций. Изоморфные алгебры. Практическое занятие 4. Операции и алгебры.

Лекция, презентация, Тренинг, тест

2+2

Опрос на практическом занятии

Лекция 5:Алгебры с одной операцией. Алгебры с двумя операциями. Полугруппы. Моноиды. Группы. Свойства алгебр с одной операцией. Примеры алгебр. Кольца. Области целостности. Поля. Свойства алгебр с двумя операциями. Примеры алгебр Практическое занятие 5: Алгебры с одной операцией. Алгебры с двумя операциями

2+2

Опрос на практическом занятии, тест

Лекция 6:Решетки. Матроиды Ограниченные решетки. Решетки с дополнением. Частичный порядок в решетке. Булева алгебра – дистрибутивная ограниченная решетка. Максимальные независимые подмножества. Базисы. Ранг. Жадный алгоритм. Примеры матроидов из различных областях дискретной математики Практическое занятие 6: Решетки. Матроиды

4-6

2+2

Опрос на практическом занятии

СРС:Изучение материала лекции 4-5 Анализ примеров разобранных на лекции и практических занятиях. Выполнение домашнего задания

Тема: Булевы функции

Знать и понимать Уметь.

Лекция 7. Булевы функции Булевы или двоичные функции. Способы задания. Булевы функции одной и двух переменных и их свойства. Формулы булевой алгебры. Основные законы булевой алгебры. Эквивалентность формул. Принцип двойственности Практическое занятие 7: Булевы функции. Лекция 8. Нормальные формы представления булевых функций Конституенты единицы и нуля. Разложение булевых функций по переменным. Совершенные дизъюктивные (СДНФ) и совершенные конъюктивные нормальные формы (СКНФ). Переход от СДНФ к СКНФ и наоборот. Геометрическое представление булевых функций. Практическое занятие 8:ДНФ и КНФ. Лекция 9: Функциональная полнота и замкнутость Системы элементарных булевых функций. Определение функционально полной системы элементарных булевых функций. Примеры функционально полных базисов. Важнейшие замкнутые классы. Теорема о функциональной полноте. Практическое занятие 9: Минимизация булевых функций Основные понятия и определения: каноническая задача минимизации; импликанта и простая импликанта; сокращенная, тупиковая и минимальная формы; операции элементарного и неполного склеивания; операция поглощения. Метод Квайна – Мак-Клоски. Метод карт Карнау или диаграмм Вейча. Минимизация неполностью определенных функций. Минимизация конъюктивных нормальных форм. Проблема факторизации при упрощении функций. Совместная минимизация систем функций. Минимизация функций в других базисах

Лекция, презентация, Тренинг, тест

2+2

Опрос на практическом занятии

СРС:Изучение материала лекции 6-9. Выполнение домашнего задания.

Опрос на практическом занятии

Тема: Основные виды уточнения понятия алгоритма

Знать и понимать: работу машины Тьюринга, рекурсивной функции, рекурсивных множеств, алгорифмов Маркова Уметь: строить машину Тьюринга и нормальные алгорифмы Маркова, вычисляющие арифметические и алфавитные функции; Доказывать рекурствность функций и множеств.

Лекция 7. Машина Тьюринга Практическое занятие 6:Машина Тьюринга

Лекция, презентация, Тренинг, тест

2+2

Опрос на практическом занятии

СРС:Изучение материала лекции 6. Выпонение домашнего задания.

Опрос на практическом занятии

Лекция 7: Рекурсивные функции. Практическое занятие 7: Рекурсивные функции и множества

Лекция, презентация, Тренинг, тест

2+2

Опрос на практическом занятии

СРС:Изучение материала лекции 8. Выполнение домашнего задания.

Опрос на практическом занятии