5. Н., А. Курс дискретной математики. –М.: Изд. МАИ, 1992. -264 с.
6. Н., Г. Математическая логика. М.: Едиториал УРСС, 2004.
7. А. Методические указания к курсу «Дискретная математика» по теме «Отображения». УПЛ РГУ. 2005.
8. В. Введение в дискретную математику. –М.: Наука, 1986.
7.2. Дополнительная литература.
9. И., В., И. Элементы комбинаторики. –М.: Наука, 1977.
10. Я. Популярная комбинаторика. - М.: Наука, 1975.
11. А. Алгоритмы на графах. УПЛ ЮФУ. 2007.
12. Математическая логика. М.: ЛКИ, 2008.
13. Н. Комбинаторные методы дискретной математики. –М.: Наука, 1977.
14. В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. – 3-е изд. – СПб.: БХВ-Петербург, 2003. -320с.
7.3. Список авторских методических разработок.
1. А. Методические указания к курсу «Дискретная математика» по теме «Отображения».// В книге М. Дискретная математика: теория, задачи, приложения. –М.: Вузовская книга, 2011.
2. А. Алгоритмы на графах. УПЛ ЮФУ. 2007.
VIII. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
Наличие литературы в отраслевой библиотеке, медиапроектор и компьютер для проведения лекций-презентаций.
VIII. УЧЕБНАЯ КАРТА ДИСЦИПЛИНЫ
«Дискретная математика и математическая логика»
Преподаватель: А.
Кафедра алгебры и дискретной математики
Курс___1__Семестр__1___Группа___5, 6__
Направление подготовки (специальность) математика
№ | Виды контрольных мероприятий | Количество баллов за 1 контрольное мероприятие | Модуль 1 | Модуль 2 | Модуль 3 | Модуль 4 |
Количество баллов по модулю | ||||||
Текущий контроль | ||||||
1. | Посещение лекций | 1 | 5 | 4 | 3 | 4 |
2. | Домашнее задание | 1 | 3 | 2 | 1 | 2 |
3. | Работа на практических занятиях | 1 | 3 | 2 | 1 | 2 |
Рубежный контроль | ||||||
1. | Контрольная работа | 19 | 19 | 19 | ||
2. | Тестирование | 5 | 5 | 5 | 5 | 5 |
Промежуточная аттестация | Макс. к-во баллов | |||||
Зачет | 80 | 35 | 13 | 10 | 22 |
для получения зачёта студент должен набрать от 50 до 80 баллов
Курс___1__Семестр__2___Группа___5, 6__
Направление подготовки (специальность) математика
№ | Виды контрольных мероприятий | Количество баллов за 1 контрольное мероприятие | Модуль 5 | Модуль 6 | Модуль 7 | Модуль 8 |
Количество баллов по модулю | ||||||
Текущий контроль | ||||||
1. | Посещение лекций | 1 | 3 | 5 | 4 | 8 |
Рубежный контроль | ||||||
1. | Тестирование | 5 | 5 | 5 | 5 | 5 |
Промежуточная аттестация | Макс. к-во баллов | Итог мод. 5 8 | Итог мод. 6 10 | Итог мод. 7 9 | Итог мод. 8 13 | |
Экзамен | 40 |
Оитог = 0,5 ∙ «общее число баллов за два семестра» + «Экзамен»
оценка на экзамене:
«3» --- Оитог от 70 до 80 баллов;
«4» --- Оитог от 81 до 90 баллов;
«5» --- Оитог от 91 до 100 баллов;
Преподаватель: А.
Согласовано: заведующий кафедрой: Я.
IX. КРАТКОЕ ИЗЛОЖЕНИЕ ПРОГРАММНОГО МАТЕРИАЛА
9.1. Лекционная программа курса
«Дискретная математика и математическая логика»
Лекций – 70 часов, практических занятий – 16 часов
КЛЮЧЕВЫЕ СЛОВА: высказывание, предикат, множество, комбинаторика, отображение, отношение, алгоритм, машина Тьюринга, граф, алгоритмы на графах.
Семестр 1
Модуль 1. Алгебра высказываний
Лекция 1. Высказывания. Операции над высказываниями: отрицание, дизъюнкция, конъюнкция, эквиваленция, и их простейшие свойства. [3] §1.1.
Лекция 2. Зависимости между операциями. Равносильность в алгебре высказываний. Булева алгебра высказываний. Формулы в алгебре высказываний. Теоремы о подстановке и равносильной подстановке. [3] §§1.1, 1.2.
Лекция 3. Двойственность в алгебре высказываний. Принцип и закон двойственности. Нормальные формы. [3] §§1.3, 1.4, 1.5.
Лекция 4. Основные проблемы алгебры высказываний: равносильности, разрешения, представления. [3] §1.5.
Лекция 5. Релейно-контактные схемы и схемы из функциональных элементов. Анализ, синтез, упрощение схем. Двоичный сумматор. [3] § 1.6.
Модуль 2. Алгебры предикатов и множеств
Лекции 6,7. Предикаты и кванторы. Понятие о предикате. Примеры предикатов. Логические операции над предикатами. Булева алгебра предикатов. Кванторы и их свойства. Применение языка предикатов и кванторов. [3] §§ 2.1, 2.2.
Лекции 8,9. Алгебра множеств. Понятие о множестве и элементе множества. Универсальное и пустое множества. Множества и одноместные предикаты. Операции над множествами: дополнение, объединение, пересечение, разность и симметрическая разность. Булева алгебра множеств. Подмножество. Семейства множеств. [3] § 2.3.
Модуль 3. Теория отображений
Лекция 10. Отображения. Примеры отображений. Образ и прообраз множества при отображении. Свойства образов и прообразов. Композиция отображений. Типы отображений: инъективные, сюръективные, биективные, «никакие». [3] §§ 2.4, 2.5.
Лекции 11, 12. Композиция однотипных отображений (теоремы о композиции однотипных отображений). Обратимость и односторонняя обратимость отображений. Критерии обратимости и односторонней обратимости. [3] § 2.5.
Модуль 4. Элементы комбинаторики
Лекция 13. Комбинаторика. Основной принцип комбинаторики. Число элементов в конечном множестве. Правило суммы. Формула включения-исключения. Декартово произведение множеств. Число элементов в декартовом произведении. [3] §§ 3.1, 3.2.
Лекция 14. Комбинаторика. Множества инъективных и биективных отображений. Размещения и перестановки. [3] §§ 3.3, 3.4.
Лекция 15. Комбинаторика. Сочетания, бином Ньютона. Сочетания с повторениями. Число сюръективных отображений. [3] §§ 3.4, 3.5.
Модуль 5. Алгебры отношений и «0-1» матриц
Лекция 16. Отношения. Примеры отношений. Булевы операции над отношениями. Булева алгебра отношений. Булевы матрицы. Булева алгебра 0-1 матриц. [3] § 4.1.
Лекция 17. Отношения. Бинарные отношения. Свойства бинарных отношений. Примеры отношений обладающих различными комбинациями свойств. Отношения порядка и доминирование. [3] §§ 4.2, 4.3.
Лекция 18. Отношение эквивалентности. Классы эквивалентности и их свойства. Фактор-множество. [3] § 4.4.
Семестр 2
Модуль 6. Булевы функции
Лекция 19. Булевы функции. Множества 
. Теорема о 
. Анализ множества 
. Штрих Шеффера и стрелка Пирса. Многочлены Жегалкина. [3] § 5.1.
Лекция 20. Полнота и замкнутость. Классы Поста 
и 
и их свойства. [3] § 5.2.
Лекция 21. Классы L, S, M и их свойства. [3] § 5.3, 5.4.
Лекция 22. Теорема Поста о полноте (критерий полноты) и следствия из неё. [3] § 5.5.
Лекция 23. Предполные классы их свойства. Существование предполных классов. [3] § 5.6.
Модуль 7. Элементы теории алгоритмов
Лекция 24. Что такое «алгоритм»? Примеры алгоритмов. Алфавит, буквы, слова. Запись слова на ленте. Простейшие операции над словами. Машина Тьюринга. Сложение чисел в унарной системе счисления. [3] § 6.1, 6.2.
Лекция 25. Специальные машины Тьюринга: тождественная, заменяющая, копирующая. Композиция машин Тьюринга. [3] § 6.2, 6.3.
Лекция 26. Машины с полулентами. Объединение машин Тьюринга. [3] § 6.3.
Лекция 27. Разветвление и итерация машин. Универсальный алфавит, универсальная кодировка. Алгоритмическая разрешимость и алгоритмическая неразрешимость. Универсальная машина Тьюринга. [3] § 6.4.
Модуль 8. Элементы теории графов
Лекция 28. Определение графа. Локальные характеристики. Теорема Эйлера о рукопожатиях. [3] §7.1.
Лекция 29. Изоморфизм графов. Геометрические графы. Реализуемость на плоскости и в пространстве. Понятие о критерии Понтрягина и Куратовского. [3] §7.2.
Лекция 30.Пути, цепи, контуры, циклы. Части графа. Связность и сильная связность. Мосты графа. Теорема о мостах. [3] §7.2, 7,3.
Лекция 31. Эйлеровы графы, критерий эйлеровости. [3] §7.4.
Лекция 32. Деревья и леса. Основная теорема о деревьях. Следствия. [3] §7.5.
Лекция 33. Помеченные графы. Перечисление помеченных деревьев. Теорема Келли. Матрицы графов. [3] §7.6.
Лекция 34. Взвешенные графы. Задача о кратчайшем соединении. Алгоритм Краскала. Задача о кратчайшем пути. Алгоритм Дейкстры. [3] §7.7.
Лекция 35. Пространства циклов и разрезов. Потоки в сетях. [3] §7.8.
9.2. План практических занятий
Модуль 1. Алгебра высказываний
Занятие 1. Высказывания. Операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция и их простейшие свойства. Булева алгебра высказываний. Равносильность в алгебре высказываний. Упражнения: [2] 1.1-1.23, [3] 8.1-8.52, [4] вып.1. 1-52.
Занятия 2, 3. Формулы алгебры высказываний. Двойственность в алгебре высказываний. Принцип двойственности и закон двойственности. Нормальные формы. СДНФ. СКНФ. Релейно-контактные схемы и схемы из функциональных элементов. Упражнения: [2] 2.29-3.11, [3] 8.53-8.309, [4] вып.1. 53-309.
Модуль 2. Алгебры предикатов и множеств
Занятие 4. Предикаты. Операции над предикатами. Кванторы, их свойства и применение. Упражнения: [2] 12.1-12.24, [3] 8.310-8.344, [4] вып.2. 310-344.
Занятие 5. Алгебра множеств. Операции над множествами: дополнение, объединение, пересечение, разность и симметрическая разность. Подмножество. Упражнения: [3] 8.345-8.378, [4] вып.2. 1-33.
Модуль 3. Теория отображений
Занятие 6. Отображения. Образ и прообраз при отображении. Свойства образов и прообразов. Суперпозиция отображений. Типы отображений: инъективные, сюръективные, биективные и отображения, не являющиеся ни инъективными, ни сюръективными. Упражнения: [3] 8.379-8.424, [4] вып.2. 40-51, [9] 6.1-6.39.
Модуль 4. Элементы комбинаторики
Занятия 7, 8. Основной принцип комбинаторики. Правило суммы. Формулы включения-исключения. Декартово произведение множеств. Бином Ньютона. Сочетания. Сочетания с повторениями. Перестановки и размещения. Перестановки с повторениями. Упражнения: [1] 1-26, [3] 8.425-8.463, [4] вып.3. 1-38.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
Основные порталы (построено редакторами)