ДИСКРЕТНАЯ МАТЕМАТИКА
Учебная программа дисциплины
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ВЛАДИВОСТОКСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ЭКОНОМИКИ И СЕРВИСА
ИНСТИТУТ ИНФОРМАТИКИ, ИННОВАЦИЙ И
БИЗНЕС-СИСТЕМ
КАФЕДРА МАТЕМАТИКИ И МОДЕЛИРОВАНИЯ
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебная программа дисциплины
по специальностям
230101.65 Вычислительные машины, комплексы, системы и сети
230201.65 Информационные системы и технологии
080801.65 Прикладная информатика
Владивосток
Издательство ВГУЭС
2014
ББК 22.1
Учебная программа по дисциплине "Дискретная математика" составлена в соответствии с требованиями государственного стандарта России. Предназначена для студентов специальностей 230101.65 Вычислительные машины, комплексы, системы и сети, 230201.65 Информационные системы и технологии, 080801.65 Прикладная информатика.
Составитель: д-р экон. наук, профессор кафедры математики и моделирования
Утверждена на заседании кафедры математики и моделирования от 7.02.2011 г., протокол № 7, редакция 2014г.
Рекомендована к изданию учебно-методической комиссией Института информатики, инноваций и бизнес – систем.
© Издательство Владивостокского
государственного университета
экономики и cервиса, 2014
ВВЕДЕНИЕ
Дискретная математика - это цикл математических наук, изучающих свойства конечных множеств. В настоящее время эти науки бурно развиваются, что определяется тремя очень важными факторами:
1) развитием компьютерной техники и компьютерных наук, которые базируются, а по существу являются продолжением дискретной математики;
2) запросами различных прикладных наук - теории управления, экономики, оптимизации и многих, многих других;
3) логикой внутреннего развития этих наук. Появлением новых разделов, глубоких интересных проблем, развитием мощных методов их решения.
Все это и предопределило тот факт, что различные разделы дискретной математики все настойчивее внедряются не только в университеты, но и в технические и экономические вузы и даже в гуманитарные.
Дисциплина предназначена для ознакомления студентов с основными понятиями разделов математики, традиционно объединяемых в рамках цикла «Дискретная математика»: алгебра высказываний, дискретный анализ, теория множеств, комбинаторика, теория графов и др. С учетом специфики основных разделов курса и специальностей, для которых он предназначен, повышенное внимание уделяется формированию у студентов практических навыков решения задач, а также проблемам решения прикладных задач с точки зрения возможности их программной реализации на компьютере. В то же время изложение теоретического материала сопровождается строгим математическим обоснованием.
1.ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ УКАЗАНИЯ
1.1.Цель и задачи изучения дисциплины
Целью изучения дисциплины "Дискретная математика" является ознакомление студентов с такими классическими разделами дискретной математики как алгебра высказываний (и некоторые ее приложения), дискретный анализ, теория множеств, теория предикатов, комбинаторика, теория неориентированных и ориентированных графов, которые являются основой многих других дисциплин математического, технического и экономического циклов. Изучая математическую логику и теорию множеств, студенты, по сути, знакомятся с современным математическим языком, являющимся, как известно, языком любой науки.
1.2.Связь с другими дисциплинами
Изучение дисциплины "Дискретная математика" не требует предварительного изучения других дисциплин. В то же время данная дисциплина является основой многих других дисциплин технического, экономического и даже гуманитарного циклов и практически всех дисциплин математического цикла. Некоторые разделы, изучаемые в курсе дискретной математики, такие как метод математической индукции и, отчасти, теория множеств могут изучаться (и изучаются) в рамках таких дисциплин как математический анализ и линейная алгебра.
1.3.Компетенции, которые должен приобрести студент
в результате изучения дисциплины
В результате изучения дисциплины "Дискретная математика" студенты должны знать основные определения и понятия изучаемых разделов дискретной математики, уметь сформулировать и доказать основные результаты этих разделов. В ходе практических занятий студенты должны приобрести навыки решения типичных заданий, решаемых на основе изучаемого теоретического материала. Кроме того, у студентов должны быть сформированы компетенции, позволяющие им решать нестандартные теоретические и практические задачи.
1.4.Объем и сроки изучения курса
Дисциплина "Дискретная математика" общим объемом 140 часов изучается в течение второго семестра.
1.5.Основные виды занятий и особенности их
проведения в результате изучения дисциплины
Лекционные занятия построены как типичные лекционные занятия классической математической дисциплины.
Практические занятия построены как типичные практические занятия классической математической дисциплины.
1.6. Виды текущего, промежуточного и итогового контроля
знаний студентов по дисциплине и способы их проведения
В рамках изучения дисциплины "Дискретная математика" проводятся следующие виды контроля знаний студентов по дисциплине:
-домашние задания;
-текущие контрольные работы;
-индивидуальные домашние задания (ИДЗ);
-промежуточные аттестации (с учетом результатов выполнения домашних заданий, текущих контрольных работ, ИДЗ);
-в т. ч. виды контроля по итогам семестра: экзамен.
2.СОДЕРЖАНИЕ КУРСА
Темы лекционных занятий
Тема 1. «Метод математической индукции (ММИ)». Стандартный ММИ. Доказательство равенств. Возвратный ММИ. Доказательство неравенств. Неравенство Коши-Буняковского. Неравенство Коши.
Тема 2. «Высказывания. Логические операции». Понятие высказывания. Основные логические операции. Определение высказывания. Таблицы истинности.
Тема 3. «Основные тождества логики высказываний». Равносильные (равные) высказывания. Основные логические тождества (законы).
Тема 4. «Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)». Возведение высказывания в степень. Элементарные конъюнкция (ЭК) и дизъюнкция (ЭД). Определение ДНФ и КНФ. Теоремы о ДНФ и КНФ.
Тема 5. «Совершенные дизъюнктивные нормальные формы (СДНФ). Совершенные конъюнктивные нормальные формы (СКНФ)». Полные элементарные конъюнкция (ПЭК) и дизъюнкция (ПЭД). Определение СДНФ и СКНФ. Теоремы о СДНФ и СКНФ. Построение высказываний по таблице истинности.
Тема 6. «Приложения алгебры высказываний». Упрощение двухполюсников. Задачи на голосование.
Тема 7. «Полиномы Жегалкина». Сложение по модулю 2. Определение многочлена Жегалкина. Два способа приведения высказывание к полиному Жегалкина. Теорема о полиноме Жегалкина.
Тема 8. «Дискретный анализ». Переключательные (булевы) функции (ПФ). Способы задания ПФ. Специальные разложения ПФ. Частные ПФ. Минимизация ПФ и неполностью определенных ПФ. Булевы функции, сохраняющие константы. Замкнутые и полные классы булевых функций. Двойственные и самодвойственные булевы функции.
Монотонные булевы функции. Линейные булевы функции. Теорема о функциональной полноте. Шефферовы функции. Примеры функционально полных базисов.
Тема 9. «Введение в теорию множеств». Понятие множества. Основные определения, терминология. Основные теоретико-множественные операции. Круги Эйлера (диаграммы Венна). Основные теоретико-множественные тождества. Булеан (степень) множества. Декартовы произведения. Декартова степень.
Тема 10. «Предикаты». Понятие n-местного предиката. Основные определения, терминология. Обратные предикаты. Отношения. Суперпозиция отношений. Отношение эквивалентности. Отношение порядка. Частично упорядоченные множества (ЧУМ). Линейно упорядоченные множества (ЛУМ). Лексикографический порядок.
Тема 11. «Функции и отображения». Функциональные отношения. Области определения и значений. Образы и прообразы элементов и множеств. Суперпозиция отображений. Инъективные, сюръективные и биективные отображения. Сужение отображения. Обратные отображения. Согласованные отображения. Операции.
Тема 12. «Элементы комбинаторики». Основные принципы комбинаторики. Перестановки, размещения, сочетания. Свойства сочетаний. Перестановки с повторениями, размещения с повторениями, сочетания с повторениями. Бином Ньютона, следствия. Формула включений и исключений. Беспорядки.
Тема 13. «Теория неориентированных графов». Введение в теорию графов: основные понятия и определения. Дополнительные и самодополнительные графы. Матричные представления графов. Маршруты, цепи, циклы. Метрические характеристики графов. Подграфы. Операции над графами. Двудольные графы. Поиск в ширину. Деревья. Алгоритм Краскала. Эйлеровы графы. Теорема о разложении графа на попарно реберно-непересекающиеся цепи. Гамильтоновы графы. Планарные графы. Теорема Фари (Вагнера). Теорема Эйлера. Критерий Понтрягина-Куратовского. Раскраски. Хроматический полином.
Тема 14. «Ориентированные графы». Основные понятия и определения. Типы орграфов. Матричные представления орграфов. Нахождение сильных компонент. Базы и антибазы. Независимые множества вершин в орграфах. Доминирующие множества вершин в орграфах.
Тема 15. «Рекуррентность». Возвратные задачи. Исчисление сумм. Арифметические ряды. Арифметические таблицы.
Тема 16. «Алгоритмы и логические схемы алгоритмов». Понятия примитивно рекурсивной и частично рекурсивной функций. Машина Тьюринга. Нормальный алгорифм Маркова. Алгоритмы Колмогорова, Ляпунова. Алгоритмически неразрешимые проблемы.
3. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО
ИЗУЧЕНИЮ КУРСА
При изучении курса студенты должны самостоятельно более углубленно изучить темы, предложенные учебной программой. С этой целью разработаны темы самостоятельных работ. Особое внимание в результате подготовки необходимо уделить изучению литературы.
3.1.Темы самостоятельных работ
Контрольные работы
1. ДНФ, СДНФ, приложения алгебры высказываний.
2. Теория множеств, предикаты.
Индивидуальные домашние задания (ИДЗ)
1. ИДЗ по методу математической индукции;
2. ИДЗ по дискретному анализу;
3. ИДЗ по теории бинарных предикатов;
4. ИДЗ по теории неориентированных графов.
3.2. Обзор рекомендованной литературы
Систематическое изложение основных разделов дискретной математики приведено в учебнике «Дискретная математика для программистов». В данном издании описаны важнейшие алгоритмы над дискретными объектами, а также основные способы представления объектов дискретной математики с помощью стандартных структур данных.
В процессе изучения курса необходимо большое внимание уделить изучению основ теории графов, поскольку в теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Теория графов является, по сути, языком дискретной математики. В учебном издании Лекции по теории графов / , , достаточно полно изложены теоретические основы теории графов. При этом большое внимание уделяется вопросам применения теории графов к решению прикладных задач и построению эффективных алгоритмов.
При изучении курса студент должен не только приобрести знания в различных областях дискретной математики, но и овладеть техникой оперирования с дискретными объектами. Именно этому и посвящено учебное издание «Конкретная математика: Основание информатики».
4. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
4.1.Основная литература
1. , Дискретная математика: учебное пособие для студентов вузов М.: РИОР. 2010.
2. , Дискретная математика и теория кодирования (Комбинаторика): практикум Владивосток: Изд-во ВГУЭС.2010.
3., Дискретная математика. - М.: РИОР, 2010.
4. Е Д. Емцева, , Дискретная математика. - Владивосток: Изд-во ВГУЭС, 2008.
5. , , Дискретная математика. - М,; Новосибирск: ИНФРА-М : Изд-во НГТУ, 2007.
6. , Дискретная математика для программистов. - СПб.: Питер, 2009.
7. , , Дискретная математика. - М.: Академия, 2008.
4.2.Дополнительная литература
1. ; Под ред. . Введение в дискретную математику. - М.: Высшая школа, 2001.
2. , Сапоженко и упражнения по курсу дискретной математики.- М.: Наука, 1992.
3. , , Виленкин .- М.: ФИМА, МЦНМО, 2006.
4. Шапорев математика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2006.
5. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
6. Горбатов дискретной математики. - М.: Высшая школа, 1986.
7. Ерусалимский математика: теория, задачи, приложения. – М.: Вузовская книга, 2000.
8. Романовский анализ – СПб.: Невский Диалект: БВХ - Петербург, 2003.
9. Перязев теории булевых функций. – М.: Физматлит, 1999.
10. Акимов математика: логика, группы, графы. - М: Лаборатория Базовых Знаний, 2003.
11. Москинова математика. Математика для менеджера в примерах и упражнениях. – М.: Логос, 2003.
12. Теория графов. - М.: Наука, 1980.
13. Теория графов. - М.: Мир, 1973.
14. Гильберт Д, Основания математики. - М.: Наука, 1979.
15. Мальцев системы. - М.: Наука, 1970.
16. Введение в математическую логику.- М.: Мир, 1974.
17. Цхай теория графов. - Алма-Ата: Наука, 1971.
18. Теория графов и ее применение. - М.: ИЛ, 1962.
19. , Касьянов графов: алгоритмы обработки деревьев. - Новосибирск: Наука, 1994.
20. Блох -схемы и их применение. - Минск.: Вышейш. школа, 1975.
21. Перечисление графов. - М.: Мир, 1977.
22. Потоки в сетях. – М.: Мир, 1966.
23. Конечные графы и сети. - М.: Наука, 1973.
24. Теория графов. - М.: Мир, 1988.
25. , Адельсон-Вельский математика для инженера. - М.: Энергоатомиздат, 1988.
26. Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. - М.: ИЛ, 1963.
4.3. Список учебно-методических разработок
1. Шишмарев математика: Конспект лекций. Ч.1.-Владивосток: Изд-во ВГУЭС, 1997.
2. Шишмарев математика: Конспект лекций. Ч.1. – 2-е изд., испр. и доп. - Владивосток: Изд-во ВГУЭС, 2001.
3. Шишмарев математика: Конспект лекций. Ч.2.-Владивосток: Изд-во ВГУЭС, 2002.
4. , Солодухин математика: Курс лекций. Ч.3.-Владивосток: Изд-во ВГУЭС, 2002.
5. Емцева математика: Конспект лекций. Ч.4.-Владивосток: Изд-во ВГУЭС, 2003.
6. , Солодухин математика. Конспект лекций. Ч.5. - Владивосток: Изд-во ВГУЭС, 2008.
7. , , Солодухин математика. Сборник задач. Ч.1.-Владивосток: Изд-во ВГУЭС, 2000.
8. , , Солодухин математика. Сборник задач. Ч.1. – 2-е изд., испр. и доп. - Владивосток: Изд-во ВГУЭС, 2002.
9. Солодухин математика. Сборник задач. Ч.3. - Владивосток: Изд-во ВГУЭС, 2006.
5. КОНТРОЛЬНЫЕ ВОПРОСЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ ОЦЕНКИ КАЧЕСТВА ОСВОЕНИЯ ДИСЦИПЛИНЫ
1.Сформулируйте и докажите методом математической индукции неравенство Коши-Буняковского.
2.Сформулируйте и докажите методом математической индукции неравенство Коши.
3.Что такое ЭД, ЭК, ДНФ, КНФ, ПЭК, ПЭД, СДНФ, СКНФ?
4.Любое ли высказывание приводимо к ДНФ, к КНФ?
5.Какая переменная называется булевой (логической)?
6.Как определяется степень булевой переменной?
7. Сколько строк содержит таблица истинности высказывания от n переменных?
8.Какие основные логические тождества и законы вы знаете?
9.Сформулируйте теорему о СДНФ, о СКНФ?
10.Дайте определение булевой функции?
11.Всякое ли высказывание является примером булевой функции?
12.Сколько найдется различных булевых функций от n переменных? Почему?
13.Что такое суперпозиция булевых функций?
14.Какой класс булевых функций называется замкнутым? Приведите примеры замкнутых классов.
15.Какой класс булевых функций называется полным? Приведите примеры полных классов.
16.Чему равно замыкание замкнутого класса булевых функций?
17.Дайте определение булевых функций, сохраняющих константы?
18.Дайте определение линейной булевой функции?
19.Дайте определение монотонной булевой функции?
20.Как найти функцию, двойственную к заданной? А с помощью таблицы истинности?
21.Дайте определение самодвойственной булевой функции?
22.Какие из классов B0, B1, L, M, S являются замкнутыми? Докажите.
23.Сформулируйте и докажите теорему о функциональной полноте?
24.Каким образом можно ограничить сверху мощность любого полного класса булевых функций?
25.Дайте определения инъективного, сюръективного и биективного отображений.
26.Что такое суперпозиция отображений?
27.Дайте определение основных операций над множествами? Докажите их основные свойства.
28.Дайте определение n-местного предиката. Какой предикат называется свойством, отношением?
29.В чем различие отношений порядка и эквивалентности?
30.Что такое разбиение множества?
31.Что такое ЧУМ и ЛУМ?
32.Сформулируйте основные принципы комбинаторики.
33.Сформулируйте и докажите формулу включений и исключений.
34.Дайте определения перестановок, сочетаний, размещений (с повторениями и без повторений) По каким формулам они вычисляются? Докажите.
35.Сформулируйте и докажите бином Ньютона и основные следствия из него.
36.Дайте определение неориентированного графа, ориентированного графа, мультиграфа, псевдографа.
37.Дайте определение вершины графа, ребра графа, степени (валентности) вершины.
38.Какие вершины называются смежными? (То же для ребер).
39.Что такое однородный (регулярный) граф?
40.Какой граф называется связным?
41.Дайте определение маршрута, цепи, цикла, простой цепи, простого цикла в графе.
42.Чем в ориентированном графе отличается путь от маршрута?
43.Что такое дерево, лес? Дайте несколько определений и докажите их эквивалентность.
44.Какой граф называется взвешенным?
45.Сформулируйте и обоснуйте алгоритм Краскала.
46.Какие операции над графами вы знаете?
47.Дайте определение эйлерова графа, квазиэйлерова, гамильтонова.
48.Сформулируйте и докажите критерий эйлеровости для графов.
49.Какой граф называется планарным?
50.В чем отличие планарного графа и плоского графа?
51.Что такое грань плоского графа?
52.Сформулируйте и докажите теорему Эйлера.
53.Сформулируйте теорему Понтрягина-Куратовского.
54.Какой граф называется триангулированным?
55.Что такое хроматическое число графа?
56.Какой граф называется бихроматическим? Приведите примеры.
57.Докажите теорему о пяти красках.
58.Дайте определение базы, антибазы, сильной базы орграфа.
59.Для чего используется алгоритм Робертса-Флореса? В чем он заключается?
60.Дайте определения различных видов связности орграфов.
61.Какое множество вершин называется независимым, доминирующим?
62.Что такое сильные компоненты? Как они находятся?
63.Что такое иосифово подмножество?
64.Решите задачу о ханойской башне с четырьмя колышками и в бесконечном числе случаев.
65.Дайте определение примитивно рекурсивной функции.
66.Дайте определение частично рекурсивной функции.
67.Дайте определение общерекурсивной функции.
68.Из чего состоит машина Тьюринга?
69.Что такое память машины Тьюринга?
70.Дайте определение функции, правильно вычислимой по Тьюрингу.
71.В каком случае две машины Тьюринга называются эквивалентными?
72.Что такое композиция машин Тьюринга?
73.Сформулируйте тезис Тьюринга.
74.Сравните ляпуновские и марковские схемы алгоритмов.
75.Что такое ограничения марковского типа?
76.Что такое ограничения ляпуновского типа?
