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