8. MA0303 Дискретная математика 1. Описание курса Diskrētā matemātika Discrete mathematics Дискретная математика 1. Уровень учебного курса: B, NT 2. Кредитные пункты: 2 3. Автор курса: Доцент, Dr.Sc.Ing В. Гераськов 4. Testing form Экзамен 5. Preliminary courses Высшая математика, Линейная алгебра 6. Annotation Цели и задачи курса: Изучение основных разделов дискретной математики: теории множеств, математической логики, булевой алгебры, комбинаторики и теории графов применительно к задачам информационных технологий ^ Навыки и компетенции:Студент должен знать конкретные применения аппарата дискретной математики к задачам управления, информатики, экономики и уметь решать простейшие из них. 7. Код курса MA 0303 8. Содержание курса: Темы 1. ^ Введение. Моделирование. Псевдокод. 2. Логика и доказательство. Высказывания и логика. Предикаты и кванторы. Методы доказательств. Математическая индукция. Корректность алгоритмов. 3. Теория множеств. Множества и операции над ними. Алгебра множеств. 4. Aлгоритмы. Целые числа. Матрицы. Сложность алгоритмов. Приложения теории чисел. Матрицы. 5. Отношения. Бинарные отношения. Свойства отношений. Отношения эквивалентности и частичного порядка. 6. Функции. Обратные отношения и композиция отношений. Обратные функции и композиция функций. Принцип Дирихле. 7. Комбинаторика. Правила суммы и произведения. Комбинаторные формулы. Бином Ньютона. Эффективность алгоритмов. 8. Графы. Графы и терминология. Эйлеровы и гамильтоновы графы. Планарные графы. Деревья. 9. Ориентированные графы. Пути в орграфах. Проблема кратчайшего пути в графе. 10. Булева алгебра. Булевы функции. Карта Карно. Логические схемы. Минимизация логических схем. 11. Вычислительные модели. Языки и грамматики. Конечные автоматы. Машина Тьюринга. 12. Теория кодирования. Генератор матриц. Коды Хемминга. 9. Требования к слушателям: Для получения полного объема кредитных пунктов необходимы:Реферат – 10% Домашнее задание – 30% Контрольная работа – 20% Экзамен – 40% 10. Литература Rod Haggarty Discrete Mathematics for Computing, Addison-Wesley, 2002Р. Хаггарти Дискретная математика для программистов, «Техносфера», 2003James A. Anderson Discrete Mathematics with Combinatorics, Prentice Hall, 2001Джеймс Андерсон Дискретная математика и комбинаторика, «Вильямс», 2003Kenneth H. Rosen Discrete Mathematics and Its Applications, McGraw Hill, 1999Strazdiņš I. Diskrētā matemātika, Zvaigzne ABC, Rīga, 2001Brāzma N. Augstākās matemātikas speckurss.1979Шапорев С.Д. Дискретная математика, «БХВ-Петербург», 2007Галушкина Ю.И. Конспект лекций по дискретной математике, «Айрис-пресс», 2007Ерусалимский Я.М. Дискретная математика. «Вузовская книга», М., 2000Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.:1988Detlovs V. Matemātiskās loģikas un kopu teorijas elementi. Rīga, 1988Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. – М,: 1978Новиков Ф.А. Дискретная математика для программистов. – «Питер», СПб,: 2006 2. Методический план ^ Темы курса Литература, источники учебной информации 1. Введение. Моделирование. Псевдокод. [2] гл.1 2. Логика и доказательство. Высказывания и логика. Предикаты и кванторы. [2] гл.2 [14] http://www.rbjones.com/rbjpub/logic/ 3. Методы доказательств. Математическая индукция. Корректность алгоритмов. [2] гл.2 [14] http://www.math.csusb.edu/notes/rel/ 4. Теория множеств. Множества и операции над ними. Алгебра множеств. [2] гл.3 [14] http://www.math.csusb.edu/notes/sets/ 5. Aлгоритмы. Целые числа. Матрицы. Сложность алгоритмов. [4] гл.3, 4, 5 http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/html 6. Приложения теории чисел. Матрицы. [4] гл..3, 4,7, 22http://www.cut-the-knot.com/blue/chinese.html 7. Отношения. Бинарные отношения. Свойства отношений. Отношения эквивалентности и частичного порядка. [2] гл.4 [14] http://www.math.csusb.edu/notes/rel/rel. 8. Функции. Обратные отношения и композиция отношений. Функции. Обратные функции и композиция функций. Принцип Дирихле. [2] гл.5 [14] http://www.math.csusb.edu/notes/proofsl 9. Комбинаторика. Правила суммы и произведения. Комбинаторные формулы. Бином Ньютона. Эффективность алгоритмов. [2] гл.6 [14] http://www.ping.be/~ping1339/tel.htm 10. Графы. Графы и терминология. Эйлеровы и гамильтоновы графы. Планарные графы. Деревья. [2] гл.7 [14] http://www.utc.edu/~cpmawata/peterse/ 11. Ориентированные графы. Пути в орграфах. Проблема кратчайшего пути в графе. [2] гл.8 [14] http://www.cs.sunysb.edu/~algorith/files 12. Булева алгебра. Булевы функции. Карта Карно. Логические схемы. Минимизация логических схем. [2] гл.9 http://www-inst.eecs.berkeley.edu/~cs150/sp97/ 13. Вычислительные модели. Языки и грамматики. Конечные автоматы. [4] гл.17, [5] ch.10 [14] http://iamexwiwww.unibe.ch/studenten/l 14. Теория кодирования. Генератор матриц. Коды Хемминга. [4] гл.18 [14] http://www.ece.unb.ca/tervo/ee4253/ Методические рекомендации Подготовить и защитить реферат (темы рефератов см. ниже)Выполнить домашнее задание и контрольную работу. Ответить на вопросы теоретического минимума. Выполненные работы присылать на электронный адрес: vgeraskov@yahoo.com Заключительная аттестация: согласно организационному плану института и графику сессии.Контрольные заданияТемы рефератов:Приложения теории чиселРекурсивные функции и алгоритмы.Машина Тьюринга.Минимизация логических схем.Алгоритмы поиска кратчайшего пути в графеТест 1 Пусть , , и универсальное множество U = Z, где Z-множество целых чисел. Найти каждое из следующих множеств:a) b) c) d) 2 С помощью алгоритма Евклида найти наибольший общий делитель gcd(2468, 8642) 3 Докажите методом математической индукции высказывание:1 + 5 + 9+…+ (4n — 3= n(2n — 1) для всех натуральных чисел n. 4 a) Преобразовать десятичное число 3275 в двоичное и шестнадцатеричное; b) преобразовать шестнадцатеричное число EB7C516 в восьмеричное и десятичное. 5 Покажите, что высказывание логически эквивалентно высказыванию 6 Пароль, открываюш;ий доступ к компьютеру, состоит из шести символов. Первые два из них — строчные буквы латинского алфавита (всего 26 букв), а оставшиеся четыре могут быть как цифрами, так и строчными буквами. Сколько можно придумать различных паролей? 7 Нарисуйте граф, чья матрица смежности имеет вид: 8 Нарисуйте диаграмму Хассе для частично упорядоченного множества {1, 2, 3, 5, 6, 10, 15, 30} с отношением «х делит у»; 9 Заполните таблицу истинности булева выражения и найдите его дизъюнктивную нормальную форму. 10 Запишите выражение , используя только операции и . Домашнее заданиеМатрица смежности орграфа G имеет видНайдите матрицу достижимости М* этого орграфа.2 С помощью алгоритма Дейкстры найдите кратчайший путь от вершины A до всех остальных вершин в графеВ таблице приведены расстояния (в км) между шестью городами (A, B, C, D, E и F): A B C D E F A - 78 56 73 71 114 B 78 - 132 121 135 96 C 56 132 - 135 85 154 D 73 121 64 - 144 116 E 71 135 85 144 - 185 F 114 96 154 116 185 - Используя алгоритм поиска минимального остовного дерева, найдите кабельную сеть минимальной общей длины, связывающую все шесть городов.^ 5. Дискретная математика. Теоретический минимум. Дать краткое пояснение или определение всем ниже перечисленным терминам (рекомендуется перекопировать таблицу теоретического минимума в отдельный файл, увеличить ячейки правого столбца для записи краткой информации необходимого, на ваш взгляд, содержания/объема.(заполнить правую сторону, подготовить в виде отдельного документа, распечатать и подписать) ^ Студент (ФИО, группа) Учебный предмет Дискретная математика Высказывания, предикаты, кванторы Методы доказательства Математическая индукция Множества и подмножества Операции с множествами Бинарные отношения Свойства отношений Функции Принцип Дирихле Основные принципы (правила) комбинаторики Сочетания, размещения, перестановки Бином Ньютона Граф, ориентированный граф Маршрут, цикл, дерево Эйлеровы и гамильтоновы графы Матрица смежности графа Задача коммивояжера Кратчайший путь в ориентированном графе Будевы функции Карта Карно Логические схемы Языки и грамматики Конечные автоматы Машина Тьюринга Codes, Hamming codes Числа Фибоначи Алгоритмы Сложность алгоритмов Алгоритм Евклида Закон больших чисел ^ 6. Экзамеиационные вопросыПример экзаменационного билета 1 Составить таблицу истинности булева выражения: 2 Изобразить множества, используя диаграммы Венна: 3 Пусть , , , а универсальное множество . Найти множество: 4 Преобразовать шестнадцатеричное число 2С4B в двоичное, восьмеричное и десятичное. 5 Изобразить граф с матрицей смежности: 6 Используя алгоритм Евклида, найти наибольший общий делитель чисел 621 и 437 ( gcd(621, 437)) 7 Сколько 8 битных чисел содержат 3 нуля и 5 единиц? 8 Методом математической индукции доказать, что: 9 Показать, что булева функция может быть реализована логической схемой, содержащей только два элемента (AND и NOT): 10 Пусть . В каждом случае найти |S|. (a) |A| = 3 and |B| = 3 (b) |A| = 3 and |B| = 5 (c) |A| = m and |B| = n Координатор курса: Доцент, Dr.Sc.Ing В.Гераськов