Pdf дискретная математика – ДИСКРЕТНАЯ МАТЕМАТИКА — PDF

docplayer.ru

ДИСКРЕТНАЯ МАТЕМАТИКА — PDF

Транскрипт

1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФИЛИАЛ ФГБОУ ВО «ВЛАДИВОСТОКСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И СЕРВИСА» В Г. НАХОДКЕ КАФЕДРА МЕНЕДЖМЕНТА И ЭКОНОМИКИ ДИСКРЕТНАЯ МАТЕМАТИКА Рабочая программа дисциплины по направлению подготовки Бизнес-информатика тип ОПОП прикладной бакалавриат Находка 06

2 Рабочая программа дисциплины «Дискретная математика» составлена в соответствии с требованиями ФГОС ВО по направлению подготовки Бизнес-информатика и Порядком организации и осуществления образовательной деятельности по образовательным программам высшего образования программам бакалавриата, программам специалитета, программам магистратуры (утв. приказом Минобрнауки России от 9 декабря 03 г. N 367). Составитель Гусев Е.Г., канд.наук, доцент кафедры МЭ Утверждена на заседании кафедры менеджмента и экономики от г., протокол 8 Редакция 06 года, рассмотрена и утверждена на заседании кафедры менед ж- мента и экономики от «5» сентября 06 г., протокол. Заведующий кафедрой Власова Е.М.

3 Цель и задачи освоения дисциплины (модуля) Целью изучения дисциплины «Дискретная математика» является ознакомление студентов с такими классическими разделами дискретной математики как алгебра высказываний (и некоторые ее приложения), дискретный анализ, теория множеств, теория предикатов, комбинаторика, теория неориентированных и ориентированных графов, которые являются основой многих других дисциплин математического, технического и экономического циклов. Изучая математическую логику и теорию множеств, студенты, по сути, знакомятся с современным математическим языком, являющимся, как известно, языком любой науки. Перечень планируемых результатов обучения по дисциплине (модулю), соотнесенных с планируемыми результатами освоения образовательной программы Планируемыми результатами обучения по дисциплине (модулю), являются знания, умения, владения и/или опыт деятельности, характеризующие этапы/уровни формирования компетенций и обеспечивающие достижение планируемых результатов освоения образовательной программы в целом. Перечень компетенций, формируемых в результате изучения дисциплины, приведен в таблице. Таблица — Формируемые компетенции Название ОПОП (сокращенное название ОПОП) Б-БИ Компетенции ПК-7-способность использовать основные методы естественнонаучных дисциплин в профессиональной деятельности для теоретического и экспериментального исследования Знания Умения Владения Знания/ умения/ владения (ЗУВ) основ дискретной математики ориентироваться в математических методах и использовать инструментальные средства для исследования объектов профессиональной деятельности; терминологией и навыками решения задач дискретной математики. 3 Место дисциплины (модуля) в структуре основной образовательной программы Дисциплина «Дискретная математика» относится к базовой части математического и естественнонаучного цикла дисциплин для направлений «Бизнес-информатика», «Радиотехника», «Инфокоммуникационные технологии и системы связи», «Информационные системы и технологии», «Технология транспортных процессов» и вариативной части этого цикла для направления «Прикладная информатика» Изучение дисциплины «Дискретная математика» не требует предварительного изучения других дисциплин. В то же время данная дисциплина является основой многих других дисциплин технического, экономического и даже гуманитарного циклов и практически всех дисциплин математического цикла. Некоторые разделы, изучаемые в курсе дискретной математики, такие как метод математической индукции и, отчасти, теория множеств могут изучаться (и изучаются) в рамках таких дисциплин как математический анализ и линейная алгебра. 4. Объем дисциплины (модуля) Объем дисциплины (модуля) в зачетных единицах с указанием количества академических часов, выделенных на контактную работу с обучающимися (по видам учебных занятий) и на самостоятельную работу по всем формам обучения, приведен в таблице 3.

4 Таблица 3 Общая трудоемкость дисциплины Название ОПОП Форма обучения Индекс Семестр курс Трудоемкость Объем контактной работы (час) СРС Форма аттестации (З.Е.) Всего Аудиторная Внеаудитор ная лек прак лаб ПА КСР Б-БИ ОФО Б..Б З 5 Структура и содержание дисциплины (модуля) 5. Структура дисциплины (модуля) Тема. «Метод математической индукции (ММИ)» ( час.). Стандартный ММИ. Возвратный ММИ. Неравенство Коши-Буняковского. Неравенство Коши. Тема. «Высказывания. Логические операции» ( час.). Понятие высказывания. Основные логические операции. Определение высказывания. Таблицы истинности. Тема 3. «Основные тождества логики высказываний» ( час.). Равносильные (равные) высказывания. Основные логические тождества (законы). Тема 4. «Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)» ( час). Возведение высказывания в степень. Элементарные конъюнкция (ЭК) и дизъюнкция (ЭД). Определение ДНФ и КНФ. Теоремы о ДНФ и КНФ. Тема 5. «Совершенные дизъюнктивные нормальные формы (СДНФ). Совершенные конъюнктивные нормальные формы (СКНФ)» ( час.). Полные элементарные конъюнкция (ПЭК) и дизъюнкция (ПЭД). Определение СДНФ и СКНФ. Теоремы о СДНФ и СКНФ. Тема 6. «Приложения алгебры высказываний» ( час.). Упрощение двухполюсников. Тема 7. «Полиномы Жегалкина» ( час.). Сложение по модулю. Определение многочлена Жегалкина. Теорема о полиноме Жегалкина. Тема 8. «Дискретный анализ» ( час.). Переключательные (булевы) функции (ПФ). Способы задания ПФ. Специальные разложения ПФ. Частные ПФ. Минимизация ПФ и неполностью определенных ПФ. Булевы функции, сохраняющие константы. Замкнутые и полные классы булевых функций. Двойственные и самодвойственные булевы функции. Монотонные булевы функции. Линейные булевы функции. Теорема о функциональной полноте. Шефферовы функции. Примеры функционально полных базисов. Тема 9. «Введение в теорию множеств» ( час.). Понятие множества. Основные определения, терминология. Основные теоретикомножественные операции. Круги Эйлера (диаграммы Венна). Основные теоретикомножественные тождества. Булеан (степень) множества. Декартовы произведения. Декартова степень. Тема 0. «Предикаты» ( час.). Понятие n-местного предиката. Основные определения, терминология. Обратные предикаты. Отношения. Суперпозиция отношений. Отношение эквивалентности. Отношение порядка. Частично упорядоченные множества (ЧУМ). Линейно упорядоченные множества (ЛУМ). Лексикографический порядок. Тема. «Функции и отображения» ( час.).

5 Функциональные отношения. Области определения и значений. Образы и прообразы элементов и множеств. Суперпозиция отображений. Инъективные, сюръективные и биективные отображения. Сужение отображения. Обратные отображения. Согласованные отображения. Операции. Тема. «Элементы комбинаторики» ( час.). Основные принципы комбинаторики. Перестановки, размещения, сочетания. Свойства сочетаний. Перестановки с повторениями, размещения с повторениями, сочетания с повторениями. Бином Ньютона, следствия. Формула включений и исключений. Беспорядки. Тема 3. «Теория неориентированных графов» ( час.). Введение в теорию графов основные понятия и определения. Дополнительные и самодополнительные графы. Матричные представления графов. Маршруты, цепи, циклы. Метрические характеристики графов. Подграфы. Операции над графами. Двудольные графы. Поиск в ширину. Деревья. Алгоритм Краскала. Эйлеровы графы. Теорема о разложении графа на попарно реберно-непересекающиеся цепи. Гамильтоновы графы. Планарные графы. Теорема Фари (Вагнера). Теорема Эйлера. Критерий Понтрягина-Куратовского. Раскраски. Хроматический полином. Тема 4. «Ориентированные графы» ( час.). Основные понятия и определения. Типы орграфов. Матричные представления орграфов. Нахождение сильных компонент. Базы и антибазы. Независимые множества вершин в орграфах. Доминирующие множества вершин в орграфах. Тема 5. «Элементы теории алгоритмов». ( час.). Вычислимые функции и алгоритмы. Понятия примитивно- рекурсивной и частичнорекурсивной функций. Машина Тьюринга. Нормальный алгоритм Маркова. Алгоритмы Колмогорова, Ляпунова. Алгоритмически неразрешимые проблемы… Перечень тем практических / лабораторных занятий Тема. «Метод математической индукции (ММИ)» ( часа, метод «мозгового штурма»). Доказательство равенств. Доказательство неравенств. Доказательство свойств. Тема. «Высказывания. Логические операции» ( час.). Построение таблиц истинности. Тема 3. «Основные тождества логики высказываний» ( час.). Доказательство тождеств с помощью таблиц истинности. Тема 4. «Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)» ( час.). Приведение высказываний к ДНФ и КНФ. Тема 5. «Совершенные дизъюнктивные нормальные формы (СДНФ). Совершенные конъюнктивные нормальные формы (СКНФ)» ( час.). Построение высказываний по таблице истинности. Тема 6. «Приложения алгебры высказываний» ( час.). Задачи на голосование. Тема 7. «Полиномы Жегалкина» ( часа, метод Jigsaw). Приведение высказывания к полиному Жегалкина двумя способами. Тема 8. «Дискретный анализ» ( часа, метод Learning Together ). Проверка системы булевых функций на полноту. Тема 9. «Введение в теорию множеств» ( часа, метод Jigsaw). Понятие множества. Основные определения, терминология. Основные теоретикомножественные операции. Круги Эйлера (диаграммы Венна). Основные теоретикомножественные тождества. Булеан (степень) множества. Декартовы произведения. Декартова степень. Тема 0. «Предикаты» ( часа, метод «снежный ком»). Понятие n-местного предиката. Основные определения, терминология. Обратные предикаты. Отношения. Суперпозиция отношений. Отношение эквивалентности. Отношение по-

6 рядка. Частично упорядоченные множества (ЧУМ). Линейно упорядоченные множества (ЛУМ). Лексикографический порядок. Тема. «Функции и отображения» ( часа, метод «снежный ком»). Функциональные отношения. Области определения и значений. Образы и прообразы элементов и множеств. Суперпозиция отображений. Инъективные, сюръективные и биективные отображения. Сужение отображения. Обратные отображения. Согласованные отображения. Операции. Тема. «Элементы комбинаторики» (4 часа, метод «мозгового штурма»). Основные принципы комбинаторики. Перестановки, размещения, сочетания. Свойства сочетаний. Перестановки с повторениями, размещения с повторениями, сочетания с повторениями. Бином Ньютона, следствия. Формула включений и исключений. Беспорядки. Тема 3. «Теория неориентированных графов» (4 час.). Введение в теорию графов основные понятия и определения. Дополнительные и самодополнительные графы. Матричные представления графов. Маршруты, цепи, циклы. Метрические характеристики графов. Подграфы. Операции над графами. Двудольные графы. Поиск в ширину. Деревья. Алгоритм Краскала. Эйлеровы графы. Теорема о разложении графа на попарно реберно-непересекающиеся цепи. Гамильтоновы графы. Планарные графы. Теорема Фари (Вагнера). Теорема Эйлера. Критерий Понтрягина-Куратовского. Раскраски. Хроматический полином. Тема 4. «Ориентированные графы» (4 час.). Основные понятия и определения. Типы орграфов. Матричные представления орграфов. Нахождение сильных компонент. Базы и антибазы. Независимые множества вершин в орграфах. Доминирующие множества вершин в орграфах. Тема 5. «Элементы теории алгоритмов». (4 час.) Рекурсивные функции. Нормальные алгоритмы. Машина Тьюринга. 6. Методические указания для обучающихся по освоению дисциплины (модуля) Лекционные и практические занятия построены как типичные лекционные занятия классической математической дисциплины в соответствии с требованиями государственных стандартов для подготовки специалистов вышеперечисленных специальностей. При проведении лекционных занятий используется презентационный пакет, созданный с помощью ПО «Power Point». При проведении практических занятиях применяются следующие интерактивные методы обучения — метод Jigsaw студенты организуются в группы по 4-6 человек для работы над заданием, которое разбито на фрагменты (логические или смысловые блоки). Каждый член малой группы находит материал по своей части. Затем студенты, изучающие один и тот же вопрос, но состоящие в разных малых группах, встречаются и обмениваются данной информацией. Далее они возвращаются в свои малые группы и обучают всему новому, что узнали сами от других членов малых групп. На заключительном этапе преподаватель может попросить любого члена команды ответить на любой вопрос по данной теме; — метод Learning Together учебная группа студентов разбивается на разнородные (по уровню обученности) группы в 3-5 человек. Каждая малая группа получает одно задание, являющееся подзаданием какого-либо задания, над которым работает вся учебная группа. В результате совместной работы малых групп достигается решение общего задания; — метод «мозгового штурма» метод представляет собой разновидность групповой дискуссии, которая характеризуется сбором всех вариантов решений, гипотез и предложений, рожденных в процессе осмысления какой-либо проблемы, их последующим анализом с точки зрения перспективы дальнейшего использования или реализации на практике; — метод «снежный ком» цель наработка и согласование мнений всех членов группы. При использовании этой техники в активное обсуждение включаются практически все студенты.

7 При изучении курса студенты должны самостоятельно более углубленно изучить темы, предложенные учебной программой. В рамках изучения дисциплины «Дискретная математика» предполагаются следующие виды контроля знаний студентов домашние задания; индивидуальные домашние задания; контрольные работы; промежуточная аттестация; итоговая аттестация (экзамен в форме тестирования). 7. Перечень учебно-методического обеспечения для самостоятельной работы 7. Перечень и тематика самостоятельных работ студентов по дисциплине ИДЗ. Метод математической индукции. Доказательство равенств, неравенств, делимости и других свойств методом математической индукции.. Комбинаторика. Решение комбинаторных задач на использование формул и свойств числа сочетаний, размещений, перестановок, а также формулы включений и исключений. Контрольные работы. Высказывание. Формализация высказываний. Построение таблиц истинности. Приведение высказывания к ДНФ, СДНФ, КНФ, СКНФ.. Теория множеств. Вычисление множеств. Составление теоретико-множественного выражения к известному множеству. Изображение множеств на кругах Эйлера. 3. Теория графов. Построение графа по заданной степенной последовательности. Нахождение метрических характеристик графа. Построение дополнительного графа и определенных типов подграфов. 7. Контрольные вопросы для самостоятельной оценки качества освоения учебной дисциплины. В чем суть метода математической индукции?. Сформулируйте понятие высказывания. Приведите примеры высказываний и предложений, таковыми не являющимися. 3. Дайте определения основных логических операций. 4. Какова зависимость количества строк таблицы истинности булевой функции от числа логических переменных? 5. Какая форма высказывания называется ДНФ, КНФ, СДНФ, СКНФ? 6. Перечислите шаги алгоритма приведения высказывания к ДНФ, КНФ с помощью логических преобразований. 7. Перечислите шаги алгоритма приведения высказывания к СДНФ, СКНФ с помощью таблицы истинности. 8. Дайте определение полинома Жегалкина. 9. Опишите известные Вам способы приведения высказывания к полиному Жегалкина. 0. Дайте характеристику основных классов булевых функций.. Что называется замыканием множества булевых функций?. Перечислить свойства замыкания. 3. Сформулируйте теорему Поста о функциональной полноте. 4. Дайте понятие множества. 5. Дайте определения основных операций над множествами. 6. Что такое булеан? 7. Дайте определение n- местного предиката. 8. Какое отображение называется инъективным? Приведите примеры инъекции и отображения, не являющегося инъективным. 9. Какое отображение называется сюръективным? Приведите примеры сюръективного отображения и отображения, таковым не являющимся. 0. Что такое биекция? Приведите примеры.

8 . Перечислите основные свойства комбинаторики.. По какой формуле вычисляется число сочетаний с повторениями и без повторений? 3. Какова формула для подсчета числа размещений с повторениями и без повторений? 4. Дайте определения неориентированного и ориентированного графов. 5. Перечислите метрические характеристики графа. 6. Какие операции над графами Вам известны? 7. Опишите алгоритм Краскала? 8. Дайте определения Эйлерова графа. Приведите примеры. 9. Дайте определение Гамильтонова графа. Приведите примеры. 30. Сформулируйте теорему Эйлера. 3. Как строится хроматический полином? 3. Опишите известные Вам матричные представления графов. 33. Как устроена Машина Тьюринга? 34. Как определяется любой нормальный алгоритм? 7.3 Методические рекомендации по организации СРС В качестве самостоятельной работы предполагается выполнения домашних заданий, подготовка докладов и сообщений. 7.4 Рекомендации по работе с литературой Систематическое изложение основных разделов дискретной математики приведено в учебнике Новикова Ф.А. «Дискретная математика для программистов». В данном издании описаны важнейшие алгоритмы над дискретными объектами, а также основные способы представления объектов дискретной математики с помощью стандартных структур данных. В процессе изучения курса необходимо большое внимание уделить изучению основ теории графов, поскольку в теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Теория графов является, по сути, языком дискретной математики. В учебном издании Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. достаточно полно изложены теоретические основы теории графов. При этом большое внимание уделяется вопросам применения теории графов к решению прикладных задач и построению эффективных алгоритмов. При изучении курса студент должен не только приобрести знания в различных областях дискретной математики, но и овладеть техникой оперирования с дискретными объектами. Именно этому и посвящено учебное издание Грэхем Р., Кнут Д., Паташник О. «Конкретная математика Основание информатики». В помощь студентам в изучении дисциплины «Дискретная математика» имеются учебнометодическик разработки, подготовленные преподавателями кафедры математики и моделирования, включающие теоретический материал, практические задания, указания и методы решения задач по темам программы дисциплины. К ним относятся следующие издания. Шишмарев Ю.Е. Дискретная математика Конспект лекций. Ч..-Владивосток Изд-во ВГУЭС, Шишмарев Ю.Е. Дискретная математика Конспект лекций. Ч.. -е изд., испр. и доп. Солодухиным К.С. — Владивосток Изд-во ВГУЭС, Шишмарев Ю.Е. Дискретная математика Конспект лекций. Ч..-Владивосток Изд-во ВГУЭС, Емцева Е.Д., Солодухин К.С. Дискретная математика Курс лекций. Ч.3.-Владивосток Изд-во ВГУЭС, Емцева Е.Д. Дискретная математика Конспект лекций. Ч.4.-Владивосток Изд-во ВГУЭС, Емцева Е.Д., Солодухин К.С. Дискретная математика. Конспект лекций. Ч.5. — Владивосток Изд-во ВГУЭС, Шишмарев Ю.Е., Емцева Е.Д., Солодухин К.С. Дискретная математика. Сборник задач. Ч..-Владивосток Изд-во ВГУЭС, 000.

9 8. Шишмарев Ю.Е., Емцева Е.Д., Солодухин К.С. Дискретная математика. Сборник задач. Ч.. -е изд., испр. и доп. — Владивосток Изд-во ВГУЭС, Солодухин К.С. Дискретная математика. Сборник задач. Ч.3. — Владивосток Изд-во ВГУЭС, Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине (модуля) Примерный перечень вопросов к зачету. Понятие алгебраической системы, примеры алгебраических систем.. Классы алгебраических систем. 3. Функции алгебры логики. Равенство функции. Тождества для элементарных функций. 4. Совершенная дизъюнктивная нормальная форма, совершенная конъюктивная нормальная форма. 5. Полные системы. 6. Теорема Жегалкина. 7. Замкнутые классы. Двойственность, класс самодвойственных функций. 8. Теорема Поста. 9. k-значные функции. 0. Математическая логика. Аксиоматический метод.. Логика высказываний.. Логика предикатов. 3. Комбинаторные функции. Правило суммы, правило произведения. 4. Перестановки. Упорядоченные подмножества. Перестановки с повторениями. 5. Мультимножества. 6. Биномиальная теорема. Полиномиальная теорема. 7. Числа Стирлинга. Числа Белла. 8. Понятие графа. Способы задания графов. 9. Изоморфизм графов. Операции над графами. 0. Маршруты, цепи и циклы. Метрические характеристики графов. Остовное дерево.. Фундаментальная система циклов. Циклический и коциклический ранги графа.. Эйлеровы и Гамильтоновы графы. 3. Деревья. 4. Планарные, двойственные графы. Раскрашивание графов. 5. Основные алгоритмы на графах и сетях. 6. Конечные и бесконечные множества основные определения, спецификации, порождающие процедуры, описание соответствия между множествами, счетное, несчетное множества. 7. Нечеткие множества, свойства нечетких множеств. 8. Алгебра множеств свойства операций над множествами. 9. Принцип двойственности, тождественные преобразования, уравнения с множествами. 30. Круги Эйлера и диаграммы Венна, произведения множеств, покрытия и разбиения. 3. Отношения бинарные и многомерные отношения, области определения и значения, счечения, композиция отношений. 3. Общие свойства отображения и функции функциональные отношения, типы отображений и мощность множеств, образы и прообразы, композиция. 33. Позиционные системы счисления двоичная система. 34. Прямые, обратные и дополнительные коды, представление чисел с фиксированной и плавающей точкой и операции над ними, диапазон и погрешности представления. 35. Модели принятия решений при нечеткой исходной информации. 36. Понятие автомата. Описание автоматов. Законы функционирования автоматов. 37. Конечный автомат как математическая модель устройства с конечной памятью и как управляющая система.

10 38. Задачи теории автоматов задача анализа, задача синтеза, задача полноты, задача эквивалентных преобразований. 39. Способы описания конечных автоматов. Минимизация конечных автоматов. 40. Преобразование автомата Мили к эквивалентному автомату Мура. Преобразование автомата Мура к эквивалентному автомату Мили. 4. Распознающие автоматы. 4. Понятие алгоритма. Основные свойства алгоритмов, требования к алгоритмам, алгоритмически разрешимые и неразрешимые проблемы. Схемы алгоритмов установления разрешимости. 43. Схемы потоков данных и алгоритмов. 44. Машина Тьюринга. Вычисление функций и предикатов на машине Тьюринга. Универсальная машина Тьюринга. Типовые задания Задание Даны отрезки A=[-m;n], B=[-n;m), C=(m; m+n] Найдите следующие множества и изобразите на числовой прямой задания а) д) и в координатной плоскости задания ж) з) а) A B \ C б) (A B) C в) (C B)\(C B) г) A ( B C ) д) A B \ C ж)a B и B A з) А Задание Даны множество A целых чисел, кратных 3 и множество B четных чисел на множестве целых чисел U={n m ; ; m+n}. Найдите следующие множества и изобразите кругами Эйлера задания а) е) и в координатной плоскости задания ж) з) а) A B A б) B A в) B A г) B A д) B A е) B ж)a B B A Задание 3 Для заданной булевой (переключательной) функции трех переменных а) постройте таблицу истинности, найдите двоичную форму булевой функции и приведите функцию к СДНФ и СКНФ; б) найдите многочлен Жегалкина и дайте ответ на вопрос, является ли данная булева функция линейной; в) с помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ; г) найдите двумя способами (с помощью карт Карно и методом Квайна) МДНФ; д) постройте соответствующий граф-схему, логический элемент и релейно-контактную схему. е) Каким классам Поста принадлежит эта функция?. F(x, y, z)= x y z x ;. F(x, y, z)= x y z x ; 3. F(x, y, z)= x y z x ; 4. F(x, y, z)= x y z x ; 5. F(x, y, z)= x y z x ; 6. F(x, y, z)= x y z x ; 7. F(x, y, z)= z x y x ; В з)

11 8. F(x, y, z)= x y z x ; 9. F(x, y, z)= z x x y ; 0. F(x, y, z)= z x x y. Задание 4 Является ли полной заданная система функций? Образует ли она базис?. J x y, x y ;. J x y, x y ; 3. J x y, x y ; 4. J x y, x y ; 5. J x y, x y ; 6. J x y, x y ; 7. J x y, x y ; 8. J x y, x y ; 9. J x y, x y ; 0. J x y, x y. Задание 5 Даны графы и. Найдите,,,. Для графа найдите матрицы смежности, инцидентности, число компонент связности, цикломатическое число и все маршруты длины, исходящие из вершины. Задайте этот граф списком дуг

12 Задание 7. Решите задачи. В ящике болт и 5 винтиков разных размеров. Нужно подобрать винтика. Сколькими вариантами вы можете это сделать?..в ящике 7 болтов и 5 винтиков разных размеров. Нужно подобрать болта и 3 винтика. Сколькими вариантами вы можете это сделать? 3. В школе олимпийского резерва обучаются лыжников и 5 конькобежцев. Сколько способов сформировать из них команду на соревнования по зимним видам спорта, в которую должны войти 3 лыжника и 4 конькобежца? 4. У 6 компьютеров и ноутбуков обнаружены признаки вирусной активности. Для того, чтобы проверить систему следует выборочно проверить компьютера и 3 ноутбука. Сколькими способами можно сделать? 5. Группу из 6 студентов должны разбить на подгруппы для работы в разных компьютерных классах. Сколько существует всех возможных вариантов формирования подгрупп, если в трех компьютерных классах соответственно 5, 4 и 7 работающих ЭВМ? 6. Из 5 красных и 7 белых гладиолусов формируют букеты. Сколькими способами можно составить букеты из 4 красных и 3 белых гладиолусов? 7. В новую компьютерную фирму для трудоустройства обратились менеджера, 7 консультантов и 0 программистов. Сколькими способами директор может сформировать трудовой коллектив, если он набирает одного менеджера, двух консультантов и трех программистов?

13 8. В роте имеется 3 офицера и 40 солдат. Сколькими способами может быть составлен наряд, включающий одного офицера и трех солдат? 9. Какое возможно максимальное число автомобильных номеров, состоящих из трех цифр и трех букв, если используемый алфавит включает 3 буквы? 0. Сколькими способами можно зажечь n светофоров, из которых k могут находиться в одном из трех состояний (красный, желтый, зеленый), а остальные n- k в одном из двух состояний (красный, зеленый)? Задание 8. Сколько двузначных чисел можно составить из нечетных цифр так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры?. Сколько трехзначных номеров можно составить из нечетных цифр так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры? 3. Сколько двузначных чисел можно составить из цифр, кратных трем так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры? 4. Сколько трехзначных номеров можно составить из цифр,,3,4,5,6,7 так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры. 5. Сколько трехзначных номеров можно составить из цифр 3,4,5,6,7, 8,9 так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры? 6. Сколько двузначных чисел можно составить из цифр 3,4,5,6,7, 8 так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры? 7. Сколько различных трехзначных номеров для автомашин одной серии можно составить из четных цифр так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры? 8. Сколько различных трехзначных номеров для автомашин одной серии можно составить из всех цифр так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры? 9. Сколько различных трехзначных номеров для автомашин одной серии можно составить из нечетных цифр так, чтобы ) использовались любые из них; ) цифры не повторялись; 3) использовались одинаковые цифры? 0. Сколько различных четырехзначных номеров для автомашин одной серии можно составить из всех цифр так, чтобы ) использовались любые из них; ) цифры не повторялись;

14 3) использовались одинаковые цифры? Задание 9. Найдите разложение бинома по степеням ) 3ab 5 3ab 4 ) 3 x 3 x 6 3) ( 3 ) 6. 4) 5) (- ) 4 ; 6) ( 3 ) 5 ) 7) (3b ) 5 8) (+3a ) 4 9) (x y 3 ) 6 0) (-3x ) 6 4 ( ) Задание 0. Найдите множество истинности для следующих двухместных предикатов, заданных на указанном множестве своих переменных. Сравните предикаты Р (х; у) и Р (х;у)= Р (у;x), если задана высказывательная форма ) «y делится на x»; М х ={,3,6}; М y ={,3, 9,, 5}; ) «y < x»; М х ={, 3, 6, 8}; М y ={, 3, 6, 9}; 3) «x y <»; М х ={5, 6,}; М y =={3, 5, 7}; 4) «x y >»; М х ={3,6,}; М y ={, 5, 7}; 5) «x y >»; М х ={3,8}; М y ={, 5, 7}; 6) «x y», М х ={,, 3}; М y ={3, 4}; 7) «x y 0», М х ={,, 3}; М y ={; 4}; 8) «x<y+4», М х ={,3,6,8}; М y ={, 5}; 9) «x<y +4», М х ={,3,6,8}; М y ={, 5}; 0) «x y 5», М х ={,6,9}; М y ={, 0}. Задание. Заданы два нечетких множества A(x) и B(x) на универсальном множестве Е. ) Определите, будет ли одно из этих множеств A и B доминировать над другим; ) Произведите логические операции над нечеткими множествами A и B а) A, б) B, в) A B, г) A B, д) A B, е) A B, 3) Произведите следующие алгебраические операции над нечеткими множествами а) A B, б) A ˆ B, в) А, г) А 0,5, если известно, что ) A=0,4 x +0,8 x +0,9 x 3 +0 x 4 и B=0, x + x +0,7 x 3 +0,3 x 4; ) A=0,3,8x +0, x + x 3 +0,5 x 4 и B=0, x +0 x +0,6 x 3 +0,5 x 4; 3) A= x +0,5 x +0,6 x 3 +0,7 x 4 и B=0,8 x +0, x +0,4 x 3 +0 x 4; 4) A=0,6 x +0,5 x +0,4 x 3 +0 x 4 и B=0,8 x +0, x + x 3 +0,9 x 4; 5) A=0,5 x +0,3 x +0,4 x 3 +0, x 4 и B=0,7 x +0, x +0 x 3 +0,9 x 4;

15 6) A=0,5 x +0,3 x +0,6 x 3 +0,7 x 4 и B=0,4 x +0 x +0,3 x 3 +0, x 4; 7) A=0,4 x +0,3 x +0 x 3 +0,7 x 4 и B=0,8 x + x +0,7 x 3 +0, x 4; 8) A=0, x +0 x +0,5 x 3 +0,6 x 4 и B=0,8 x +0,4 x +0,7 x 3 + x 4; 9) A=0, x +0,7 x +0,3 x 3 +0,6 x 4 и B=0, x +0,4 x +0, x 3 +0,5 x 4; 0) A=0, x +0,3 x +0,8 x 3 +0 x 4 и B=0,7 x + x +0,9 x 3 +0,5 x 4. 9 Перечень основной и дополнительной учебной литературы, необходимой для освоения дисциплины (модуля) а) Основная литература. Вороненко А. А., Дискретная математика. Задачи и упражнения с решениями учебнометод. пособие для студентов вузов / А. А. Вороненко, В. С. Федорова. — М. ИНФРА- М, с.. Куликов В.В. Дискретная математика учебное пособие для студентов вузов / В. В. Куликов. — М. РИОР, с. 3. Новиков Ф.А. Дискретная математика для бакалавров и магистров учебник для студентов вузов / Ф. А. Новиков. — -е изд. — СПб. Питер, с. 4. М. А. Первухин, А. А. Степанова, Дискретная математика и теория кодирования (Комбинаторика). — Владивосток Изд-во ВГУЭС, 00. http// б) Дополнительная литература. Н.Я. Виленкин, А.Н. Виленкин, П.А. Виленкин. Комбинаторика.- М. ФИМА, МЦНМО, Г.П. Гаврилов, А.А. Сапоженко. Задачи и упражнения по курсу дискретной математики.- М. Физматлит, Ю.И. Галушкин, А.Н. Марьямов, Конспект лекций по дискретной математике. С упражнениями и контрольными работами. — МАйрис-пресс, с. 4. В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. Лекции по теории графов. — М. Ленанд, Е Д. Емцева, К. С. Солодухин. Дискретная математика курс лекций в 5 ч. Ч Владивосток Изд-во ВГУЭС, с. 6. Е Д. Емцева, К. С. Солодухин, Дискретная математика курс лекций Ч.3. — Владивосток Изд-во ВГУЭС, с. 7. Новиков Ф.А. Дискретная математика для программистов. СПб. Питер, Романовский И.В. Дискретный анализ СПб. Невский Диалект БВХ — Петербург, С. В. Судоплатов, Е. В. Овчинникова, Дискретная математика. Новосибирск ИНФРА- М Изд-во НГТУ, Шишмарев Ю.Е. Дискретная математика конспект лекций. Ч. — -е изд., испр. и доп. К.С. Солодухиным — Владивосток Изд-во ВГУЭС, с. Шишмарев Ю. Е. Дискретная математика конспект лекций. Ч. — Владивосток Издво ВГУЭС, с.. Ю.Е. Шишмарев, Е Д. Емцева, К. С. Солодухин, Дискретная математика сборник задач Ч.- Владивосток Изд-во ВГУЭС, с. 3. Яблонский С.В.; Под ред. В.А. Садовничего. Введение в дискретную математику. — М. Высшая школа, 00.

16 0. Перечень ресурсов информационно — телекоммуникационной сети «Интернет» а) полнотекстовые базы данных ЭБС «Юрайт» http// ЭБС «Руконт» http// Ресурс Цифровые учебные материалы http//abc.vvsu.ru/ б) интернет-ресурсы http//window.edu.ru/resource/869/44869 http// 0 Материально-техническое обеспечение дисциплины (модуля) Техническое и лабораторное обеспечение аудитория с мультимедийным оборудованием. Словарь основных терминов Высказывание предложение, которое может быть истинно или ложно. Граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Комбинаторика — раздел математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов. Множество — совокупность различных элементов, мыслимая как единое целое (Бертран Расселл). Отображение соответствие между множествами, при котором каждому элементу одного множества ставится в соответствие единственный элемент другого множества. Предикат функция с множеством значений {0,}, определенная на декартовом произведении множеств, или, в другой терминологии, — множество истинности такой функции.