Дискретная математика
 Скачать 0.55 Mb.
|
 УТВЕРЖДАЮ Ректор университета __________О.Н. Федонин “____”___________2017 г. ДИСКРЕТНАЯ МАТЕМАТИКА Методические указания к выполнению самостоятельной работы для студентов очной формы обучения по направлениям подготовки 10.03.01 – «Информационная безопасность», 09.03.02 – «Информационные системы и технологии» (квалификация «бакалавр»), по специальности 10.05.03 – «Информационная безопасность автоматизированных систем» (квалификация «специалист») Брянск 2017 УДК 511 Дискретная математика [Электронный ресурс]: методические указания к выполнению самостоятельной работы для студентов очной формы обучения по направлениям подготовки 10.03.01 – «Информационная безопасность», 09.03.02 – «Информационные системы и технологии» (квалификация «бакалавр»), по специальности 10.05.03 – «Информационная безопасность автоматизированных систем» (квалификация «специалист»). – Брянск: БГТУ, 2017. – 24 с. Разработала В.А. Андросенко, доцент, к.ф.-м. н. Рекомендовано кафедрой «Высшая математика» БГТУ (протокол №7 от 27.03.17) Методические указания публикуются в авторской редакции ВВЕДЕНИЕ В соответствии с учебным планом дисциплина «Дискретная математика» изучается студентами по направлениям подготовки «Информационная безопасность», «Информационные системы и технологии» и специальности «Информационная безопасность автоматизированных систем» в первом семестре в объеме 144 часов. Из них 68 часов отводится для проведения аудиторных занятий (лекции и практическиие занятия) и 76 часов − для самостоятельной работы, усвоение теоретического материала по учебникам и конспекту лекций, подготовка к практическим занятиям, выполнение заданий расчетно-графической работы и домашних заданий, подготовка к контрольным работам и экзамену. Умение описывать дискретные математические объекты, строить прикладные дискретные математические модели и работать с ними составляет необходимую часть ремесла грамотного исследователя, аналитика, практика. Учебная дисциплина «Дискретная математика» направлена на изучение основных понятий, методов и результатов комбинаторики, теории графов. Дисциплина является необходимым языковым и методологическим основанием для формирования знаний и навыков работы с дискретными объектами. Дисциплина «Дискретная математика» является общим теоретическим и методологическим основанием для всех математических дисциплин и дисциплин информационного блока. Целью методических указаний является оказание помощи студентам в организации самостоятельной работы в течение первого семестра. Они содержат: тематику практических занятий и задачи для самостоятельного решения (еженедельные домашние задания); задания расчетно-графической работы; типовые варианты обеих контрольных работ; вопросы к экзамену; тематику и примеры задач, предлагаемых на экзамене; перечень знаний, навыков и умений для получения удовлетворительной оценки. Методические указания определяют объем и направленность самостоятельной работы. Они позволяют студентам рационально планировать время самостоятельной работы над учебным материалом, своевременно начать и правильно расставить акценты при подготовке к промежуточным и итоговой аттестациям. Расчетно-графическая работа выполняется на листах формата А4. Экзаменационный билет содержит три теоретических вопроса и три задачи. 1. ТЕМАТИКА ПРАКТИЧЕСКИХ ЗАНЯТИЙ И ТЕКУЩАЯ САМОСТОЯТЕЛЬНАЯ РАБОТА Практическое занятие №1. Понятие множества. Операции над множествами. Отображение множеств. Самостоятельная работа: выполнение задания №1 расчетно – графической работы; решение задач из [1] Тема 1, §1: № 1-5, §2: № 1-4. Практическое занятие №2. Мощность множества. Основы комбинаторики. Самостоятельная работа: выполнение задания №2 расчетно – графической работы; решение задач из [7] № 2.1, 2.3, 2.4; из [5] № 1.1, 1.2, 1.4, 1.9, 1.11. Практическое занятие №3. Отношения на множестве. Самостоятельная работа: решение задач из [1] Тема 1, §5: № 1-4, из [7] № 4.2, 4.3. Практическое занятие №4. Контрольная работа по теме «Основы теории множеств и комбинаторики». Практическое занятие №5. Основные понятия теории графов: ориентированные и неориентированные графы. Пути, маршруты, циклы, связность графов. Самостоятельная работа: решение задач из [1] Тема 2, §1: № 1-6, из [7] № 5.1, 6.1, 6.2, 6.6. Практическое занятие №6. Задача о кратчайшем пути в графе. Задача Эйлера. Самостоятельная работа: решение задач из [1] Тема 2, §3: № 1-4, из [7] № 6.7, 6.8, 7.1. Практическое занятие №7. Плоские, планарные и непланарные графы. Формула Эйлера. Самостоятельная работа: решение задач из [1] Тема 2, §4: № 1-3 из [7] № 8.1, 8.2. Практическое занятие №8. Раскраска графа. Хроматическое число и хроматический индекс графа. Самостоятельная работа: решение задач из [1] Тема 2, §5: № 1-3. Практическое занятие №9. Представление графов в памяти компьютера. Матрица смежности. Матрица инцидентности. Самостоятельная работа: выполнение задания №3 расчетно–графической работы; решение задач из [4] № 13.13-13.16, 13.19, из [7] № 10.1, 10.2, 10.4. Практическое занятие №10. Код Харари. Деревья и ордеревья. Префиксный код бинарного ордерева. Самостоятельная работа: выполнение задания №4 расчетно–графической работы; решение задач из [7] № 11.2, 11.3, 12.2. Практическое занятие №11. Код Прюфера для деревьев и ордеревьев. Самостоятельная работа: выполнение задания №5 расчетно–графической работы; решение задач из [7] № 12.3, 12.4. Практическое занятие №12. Обход дерева. Понятие списка. Деревья и списки. Деревья и арифметические выражения. Самостоятельная работа: решение задач из [4] № 14.7, 14.8, из [7] № 12.5, 13.1, 13.2. Практическое занятие №13. Контрольная работа по теме «Графы как структура обработки данных». Практическое занятие №14. Понятие абстрактного алфавита и кода, примеры. Двоичные коды. Коды с обнаружением и исправлением ошибок. Самостоятельная работа: решение задач из [4] № 19.9. Практическое занятие №15. Коды Хемминга. Построение кодера и декодера (7, 4) – кода Хемминга. Самостоятельная работа: решение задач из [4] № 19.10. Практическое занятие №16. Булевы функции. Основные логические операции. Построение СДНФ булевой функции. Двойственные булевы функции. Построение СКНФ булевой функции. Самостоятельная работа: выполнение задания №6 расчетно–графической работы; решение задач из [4] № 8.11-8.14. Практическое занятие №17. Основные свойства булевых функций. Функциональная полнота системы булевых функций. Теорема Поста. Самостоятельная работа: решение задач из [4] № 8.15, 8.16, 8.17, 8.19, 8.23, 8.24. 2. РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА ЗАДАНИЕ 1 На множестве действительных чисел заданы функции  и  . Найти  , где A и B – области определения функций и соответственно.
ЗАДАНИЕ 2 1. Четверо студентов сдают экзамен. Сколькими способами могут быть поставлены им оценки, если известно, что никто из них не получил неудовлетворительной оценки? 2. Сколькими способами можно переставить буквы слова «перешеек» так, чтобы четыре буквы ″е″ не шли подряд? 3. На окружности взята 101 точка. Сколько существует вписанных в окружность выпуклых многоугольников с вершинами в этих точках? 4. Сколько различных нечетных чисел, меньших, чем миллион, можно написать с помощью цифр 9, 8, 7, 0? 5. Сколько различных слов можно получить, переставляя буквы в слове «математика»? В слове «парабола»? В слове «интеграл»? 6. На карточках написаны числа 0, 1, 2, 3, 4, 5, 6, 7. Сколько различных четырехзначных четных чисел можно из них составить? 7. В группе 15 девушек и 7 юношей. Сколькими способами можно выбрать из группы четырех дежурных так, чтобы среди них девушек было меньше, чем юношей? 8. Даны две параллельные прямые. На одной из них имеется 10 точек, а на другой – 15. Сколько существует треугольников с вершинами в данных точках? 9. Из лаборатории, в которой работает 20 человек, 5 сотрудников должны уехать в командировку. Сколько может быть составов этой группы, если начальник лаборатории, его заместитель и главный инженер одновременно уезжать не должны? |
