Методические указания для студентов

Основными задачами студента при изучении данной дисциплины являются усвоение фундаментальных понятий и основных методов дискретной математики, алгебры логики, приобретение практических навыков решения задач.

Непременным условием получения допуска к экзамену является выполнение и защита лабораторных и индивидуальной домашней расчётно-графической работ. Допуск к экзамену осуществляет преподаватель, ведущий практикум.

Выполненные лабораторные работы и РГР следует аккуратно оформить на листах формата А4, на титульном листе указать название дисциплины, № и тему работы, фамилии студента и преподавателя, № варианта. Работы обязательно должны включать таблицы, диаграммы, схемы.

После защиты работы преподаватель ставит на титульном листе отметку о зачёте и забирает оформленную работу.

Перечень практических навыков, владение которыми студент должен показать для получения допуска к экзамену, дан в приложении № 1. Теоретический экзамен студент сдаёт лектору, читавшему этот теоретический курс. Перечень всех вопросов, выносимых на экзамен, приведён в конце рабочей программы. Необходимый минимум (minimum minimorum) вопросов, знание которых гарантирует студенту получение положительной оценки, дан в приложении № 2.

Программа составлена в соответствии с Государственным стандартом высшего профессионального образования по направлению подготовки 230200 «Информационные системы».

ПРОГРАММУ СОСТАВИЛ:

Шапорев Сергей Дмитриевич, д. ф-м. н., профессор__________________________

Справка о наличии в библиотеке бгту «Военмех» им. Д.Ф.Устинова учебной литературы

1. Наименование дисциплины: «Дискретная математика»

2. Кафедра И7 «Прикладной математики и информатики»

Список основной литературы

1. Шапорев, С.Д. Дискретная математика / С.Д. Шапорев. СПб.: БХВ-Петербург, 2006, 396 с., 742 экз.

2. Шапорев, С.Д. Математическая логика / С.Д. Шапорев. СПб.: БХВ-Петербург, 2005, 410 с., 800 экз.

Список дополнительной литературы

1. Акимов, О.Е. Дискретная математика: логика, группы, графы / О.Е. Акимов, М.: Лаборатория Базовых Знаний, 2003. 376 с., 30 экз.

2. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.А. Максимова. М.: ФИЗМАТЛИТ, 2004. 256 с., 30 экз.

3. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. СПб.: Питер, 2003. 301 с., 31 экз.

4. Судоплатов, С.В. Математическая логика и теория алгоритмов / С.В. Судоплатов, Е.В. Овчинникова. М: Инфра-М, 2004. 224 с., 30 экз.

Директор библиотеки Н.В. Сесина

Перечень экзаменационных вопросов

1. Множество. Булеан. Способы задания множеств. Основные операции над множествами.

2. Алгебра множеств, её основные формулы.

3. Понятие булевой алгебры. Алгебра множеств как модель булевой алгебры. Конституенты.

4. Декартовы произведения множеств.

5. Бинарные отношения.

6. Отображения множеств. Образы, прообразы, обратные отображения, виды отображений. Функции, их свойства.

7. Бинарные отношения специального вида. Отношения порядка.

8. Эквивалентность и мощность множеств. Кардинальные числа, шкала кардинальных чисел.

9. Конечные, бесконечные, счётные, бессчётные, континуальные множества, их свойства.

10. Арифметика кардинальных чисел.

11. Выборки. Правила суммы и произведения. Перестановки без повторений и с повторениями.

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

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

14. Бином Ньютона. Свойства биномиальных коэффициентов.

15. Формула включений и исключений.

16. Число элементов в объединении множеств.

17. Производящие функции, экспоненциальные производящие функции, действия над ними. Производящие функции некоторых комбинаторных последовательностей.

18. Метод рекуррентных соотношений. Решение линейных рекуррентных уравнений с постоянными коэффициентами.

19. Числа Фибоначчи.

20. Граф (орграф), его элементы. Виды графов (орграфов). Отношения между элементами графа (орграфа). Способы задания.

21. Степень вершины графа (орграфа). Изоморфизм.

22. Связность графов.

23. Маршруты в графах, их виды. Цепь, цикл. Пути в орграфах, их виды. Контур. Теоремы о маршрутах и циклах.

24. Дерево (ордерево). Корневые, бинарные деревья. Теоремы о деревьях.

25. Определения двухполюсной направленной сети, потока. Задача о максимальном потоке. Разрез. Теорема Форда-Фалкерсона.

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

27. Понятие булевой функции (функции двузначной логики). Элементарные булевы функции, логические связки. Формулы алгебры логики, функции, их реализующие.

28. Основные эквивалентные формулы алгебры логики.

29. Элементарная конъюнкция и элементарная дизъюнкция.

30. Дизъюнктивная нормальная форма (ДНФ). Алгоритм приведения булевой функции к ДНФ. Теорема о дизъюнктивном разложении булевой функции.

31. Совершенная дизъюнктивная нормальная форма (СДНФ). Алгоритмы приведения булевой функции к СДНФ.

32. Конъюнктивная нормальная форма (КНФ). Алгоритм приведения булевой функции к КНФ. Теорема о конъюнктивном разложении булевой функции.

33. Совершенная конъюнктивная нормальная форма (СКНФ). Алгоритмы приведения булевой функции к СКНФ.

34. Полиномы Жегалкина. Алгоритмы приведения булевой функции к полиному Жегалкина.

35. Релейно-контактные схемы, их математическое описание и методы построения.

36. Двойственная функция. Принцип двойственности.

37. Понятия функциональной замкнутости и полноты. Классы самодвойственных, линейных, сохраняющих константы и монотонных функций. Теорема Поста о функциональной полноте. Примеры функционально-полных базисов.

38. Задача минимизации булевых функций. Структура n-мерного куба. Сокращённая дизъюнктивная форма (ДНФ). Методы Блейка, Нельсона, Квайна их построения.

39. Метод карт Карно построения сокращённой ДНФ.

40. Тупиковая, минимальная, кратчайшая ДНФ, методы их построения.