Разработка эффективного математического, программного, информационного и технического обеспечения на основе методов дискретной математики
| № п/п | Результаты обучения | Семестр, раздел / тема. Виды учебной деятельности. Краткое содержание | Образовательные технологии | * Неделя | Трудоемкость, час | Форма текущего контроля | ||||||||||
| 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. Выполнение домашнего задания. | Опрос на практическом занятии | |||||||||||||||
| Лекция 8: Нормальные алгорифмы Маркова. Алгоритмически неразрешимые проблемы. Практическое занятие 8: Нормальные алгорифмы Маркова | Лекция, презентация, Тренинг, тест | |||||||||||||||
| СРС:Изучение материала лекции 8. Выполнение домашнего задания. | опрос | |||||||||||||||
| ИТОГО | Общий объем дисциплины | |||||||||||||||
| в том числе: | Аудиторная нагрузка | |||||||||||||||
| Лекции | ||||||||||||||||
| Лабораторные работы | ||||||||||||||||
| СРС | зачет | |||||||||||||||
* - последовательность недель может быть изменена в связи с изменениями графика учебного процесса и т. п. …
