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

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

 

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

 

* - последовательность недель может быть изменена в связи с изменениями графика учебного процесса и т. п. …