Рабочая программа учебной дисциплины «Дискретная математика» по специальности 230701 «Прикладная информатика»

Наименование разделов и тем

Максимальная учебная нагрузка

Количество аудиторных часов

Внеаудиторная самостоятельная работа студентов

Уровень освоения

всего

практических

Раздел 1 Множества. Операции над множествами

14

10

4

4

Тема 1.1 Понятие множества. Примеры множеств. Элемент множества. Подмножество. Мощность конечного множества. Пустое множество.

Равенство множеств. Универсальное множество. Операции над множествами: объединение, пересечение, разность, дополнение. Способы задания множеств: с помощью списка, с помощью характеристического свойства, с помощью порождающей процедуры. Система подмножеств множества.

Алгебра (под) множеств и ее законы. Изменение мощности множеств при операциях над множествами.

Векторы (кортежи), прямое произведение, проекция.

2

2

2

2

2

2

2

Практическая работа № 1

Прямое произведение множеств.

Построение диаграмм Эйлера - Венна

Тема 1.2 Понятие соответствия. Образ и прообраз. Область определения и область значения соответствия. Всюду определенное соответствие. Сюръективное соответствие. Однозначное (функциональное) соответствие.

2

2

2

Тема 1.3 Обратное соответствие. Обратимое соответствие. Взаимно однозначное соответствие (1-1-соответствие, биекция). Мощность бесконечного множества. Равномощность бесконечного множества своему подмножеству. Счетные множества. Несчетные множества (континуум).

Понятие функции. Область определения и область значения функции. Обратная функция. Функции многих аргументов

6

2

4

2

2

Самостоятельная работа № 1 Реферат по темам: (1 по выбору студента) Обратное соответствие. Обратимое соответствие. Взаимно однозначное соответствие (1-1-соответствие, биекция). Мощность бесконечного множества. Равномощность бесконечного множества своему подмножеству. Счетные множества. Несчетные множества (континуум).

Понятие функции. Область определения и область значения функции. Обратная функция. Функции многих аргументов

Тема 1.4 Тип функции. Суперпозиция функций. Способы задания функции: с помощью формулы, свойством значений, с помощью порождающей процедуры, с помощью таблицы, с помощью программы (конструктивные и неконструктивные функции).

2

2

2

3

Практическая работа № 2

Задание числового ряда с помощью порождающей процедуры.

Тема 1.5 Понятие отношения. Бинарные отношения. Свойства отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Транзитивное замыкание отношения. Обратное отношение.

Отношение эквивалентности. Класс эквивалентности. Отношение строгого и нестрогого порядка. Отношение линейного и частичного порядка.

Лексикографический порядок векторов.

2

2

2

2

2

Раздел 2 Комбинаторика.

14

8

6

6

Тема 2.1. Основные объекты комбинаторики. Типы комбинаторных задач. Правило суммы и правило произведения.

Формула включения и исключения. Размещения с повторениями. Размещения без повторений.

2

2

2

2

2

Практическая работа № 3

Решение комбинаторных задач

Практическая работа № 4

Размещения с повторениями.

Размещения без повторений.

Бином Ньютона

Тема 2.2 Перестановки. Сочетания без повторений.

Бином Ньютона, свойства биномиальных коэффициентов, треугольник Паскаля.

6

2

2

4

2

2

Практическая работа № 5

Решение комбинаторных задач

Вычисление сочетаний без повторений

Самостоятельная работа № 2 Решение задач.

Тема 2.3 Сочетания с повторениями. Задача перечисления.

2

2

2

2

Практическая работа № 6

Перестановки. Сочетания без повторений.

Тема 2.4 Лексикографический порядок. Двумерные выборки.

4

2

2

2

Самостоятельная работа № 3

Решение задач. Двумерные выборки.

Раздел 3 Основы общей алгебры

26

18

2

8

Тема 3.1 Понятие алгебры. Замкнутые операции. N-арные операции, бинарные операции, арность операции.

Тип алгебры, сигнатура. Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева, дистрибутивность справа.

Два вида процедур в алгебре: вычисление формул и преобразование формул.

2

2

3

3

3

Тема 3.2 Изоморфизм алгебр. Гомоморфизм алгебр. Полугруппа. Единица полугруппы. Моноид. Группа. Обратный элемент.

Способ задания (полу)групп: с помощью бинарной таблицы и с помощью образующих.

Решетка. Наименьшая верхняя грань, наибольшая нижняя грань. Единственность максимального и единственность минимального элемента. Единица решетки и нуль решетки. Решетка подмножеств любого множества.

6

2

4

2

2

2

Самостоятельная работа № 4 Задание (полу) групп: с помощью бинарной таблицы и с помощью образующих.

Индивидуальные задания

Тема 3.3 Высказывание. Логические связки: конъюнкция, дизъюнкция, отрицание, импликация, разделительное "или", эквивалентность.

Таблицы истинности для логических функций.

4

2

2

3

3

Самостоятельная работа № 5 Таблицы истинности для логических функций. Индивидуальные задания

Тема 3.4 Логические функции от нуля переменных (константы), от одной переменной, от двух переменных.

Применение к переключательным схемам. Алгебра логических функций. Вычисление логических функций.

2

2

3

3

Тема 3.5 Проблема полноты. Функционально полная система функций (в сильном смысле и в слабом смысле). Эквивалентности формул.

2

2

3

Тема 3.6 Алгоритм перехода от таблицы функции к формуле (построение СДНФ).

2

2

2

3

Практическая работа № 7

Построение СДНФ

Тема 3.7 Булева алгебра и ее законы. Изоморфизм булевых алгебр (алгебры множеств и алгебры логических функций).

2

2

3

Тема 3.8 Функциональная полнота некоторых систем функций. Алгебра Жегалкина.

Функциональная полнота алгебры Жегалкина. Ортогональные функции. Монотонные функции.

2

2

3

3

Тема 3.9 Классы логических функций. Монотонные функции. Линейные функции. Отношение двойственности функций.

Функции, двойственные самим себе (самодвойственные функции).

Функции, сохраняющие нуль. Функции, сохраняющие единицу.

4

2

2

3

3

Самостоятельная работа № 6 Реферат на тему: Классы логических функций. Монотонные функции. Линейные функции. Отношение двойственности функций. Функции, двойственные самим себе (самодвойственные функции). Функции, сохраняющие нуль. Функции, сохраняющие единицу.

Раздел 4 Понятие предиката Логика предикатов

4

4

4

Тема 4.1 Понятие предиката. Кванторы

Кванторы всеобщности и существования. Связанные переменные. Область действия квантора.

2

2

3

Тема 4.2 Эквивалентные соотношения в логике предикатов.

Чистая логика предикатов и прикладные логики предикатов.

2

2

4

3

3

Практическая работа № 8

Выполнение обычных логических операций над предикатами.

Практическая работа № 9

Формализация предложений с помощью логики предикатов.

Раздел 5. Графы

20

16

8

4

Тема 5. 1 Понятия графа. Классификация графов: по наличию ориентирования ребер (неориентированный и ориентированный графы), по наличию кратности ребер (простой граф и мульти граф).

Отношение смежности между вершинами, матрица смежности. Отношение инцидентности между вершинами и ребрами. Степень вершины. Изолированные вершины, висячие вершины.

Пустой граф, полный граф. Матрица смежности, степень вершины. Подграф и часть графа. Звезда вершины графа. Полный граф. Клика

2

2

2

2

2

Тема 5.2 Максимальный и минимальный (относительно некоторого свойства) подграф. Изоморфизм графов. Неориентированные графы. Путь, цепь, простая цепь, цикл.

Связанные вершины. Связный граф. Компоненты связности

Длина пути. Расстояние между вершинами в связном графе. Аксиомы метрики (расстояния).

2

2

2

3

3

3

Практическая работа № 10

Построить граф и указать на нем путь, цепь, простую цепь, цикл

Тема 5.3 Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах. Алгоритм построения Эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера).

Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость.

2

2

4

2

2

Практическая работа № 11

Нахождение центра графа

Практическая работа № 12

Определение радиуса графа

Тема 5.4 Виды связности: сильная связность, односторонняя связность, слабая связность. Компонента сильной связности.

Конденсация, граф конденсации. Ациклический граф.

Топологическая сортировка.

2

2

3

3

Тема 5.5 Деревья. Оптимизационные задачи на графах. Задача о кратчайшем пути

Неориентированные деревья. Ориентированные деревья. Применение деревьев: классификация, представление формул, бинарное дерево поиска.

Оптимизационные задачи на графах Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов.

Ранжирование вершин. Задача о кратчайшем пути во взвешенном графе. Алгоритм Дейкстры

2

2

3

3

3

Тема 5.6 Оптимизационные задачи на графах. Сетевое планирование. Потоки в сетях

Оптимизационные задачи на графах.

2

2

3

Тема 5. 7 Алгоритм поиска увеличивающей цепи. Разрезы. Пропускная способность разреза.

2

2

3

Тема 5.8 Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное замыкание. Графы и бинарные отношения.

Отношения эквивалентности и отношения порядка в терминах графов. Матричные методы анализа мульти графов. Двудольные графы. Задача о раскраске графа.

6

2

2

4

3

3

Практическая работа № 13

Раскраска графа

Самостоятельная работа № 7. Задача о раскраске графа.

Раздел 6 Элементы теории автоматов

14

6

6

8

6.1 Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний. Таблица автомата. Принцип работы автомата. Диаграмма автомата.

8

4

4

4

2

Самостоятельная работа № 8 Принцип работы автомата.

Практическая работа № 14

Диаграмма автомата

6.2 Словарная функция автомата. Финальная функция автомата. Правильный автомат (автомат Мура). Упрощённый вид диаграммы для правильных автоматов. Автомат, распознающий свойство слова, и его построение.

6

2

2

4

2

Практическая работа №15

Построение автомата

Самостоятельная работа №9 Диаграмма автомата. Индивидуальные задания

Самостоятельная работа №10

Упрощённый вид диаграммы для

автоматов. Индивидуальные задания.

Подготовка к экзамену

Всего часов

92

62

30

30