Государственное образовательное учреждение

высшего профессионального образования Московской области

«Международный университет природы, общества и человека «Дубна»

(университет «Дубна»)

ИСАУ

кафедра системного анализа и управления

УТВЕРЖДАЮ

проректор по учебной работе

С.В. Моржухина «_»_20 г.

Программа дисциплины Дискретная математика Направление подготовки 080500 Бизнес-информатика Профиль подготовки Электронный бизнес Квалификация (степень) выпускника Бакалавр Форма обучения Очная г. Дубна, 2011г.

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению подготовки – 080500 «Бизнес-информатика» профиль «Электронный бизнес».

Программа рассмотрена на заседании кафедры системного анализа и управления (название кафедры) Протокол заседания № _ от «» 20 г.

Заведующий кафедрой /проф. Е.Н. Черемисина / (подпись) (ФИО)

СОГЛАСОВАНО

директор института САУ _ /проф. Е.Н. Черемисина/ (подпись) (ФИО) Дата «» _ 20 г.

Рецензент: _ (ученая степень, ученое звание, место работы, должность) // (подпись) (ФИО) Дата «» _ 20 г.

Руководитель библиотечной системы _ / В.Г. Черепанова/ (подпись) (ФИО) Дата «» _ 20 г.

1. Цели и задачи освоения дисциплины Данная программа имеет целью ознакомление студентов с фундаментальными структурами, понятиями, методами и алгоритмическими основами современной дискретной математики, формирование у студентов навыков описания дискретных объектов в прикладных задачах, овладение математическим аппаратом, необходимым для последующего изучения моделей информационных и управляющих систем.

2.Место дисциплины в структуре ООП бакалавриата Дисциплина «Дискретная математика» относится к базовой части Математического и естественнонаучного цикла (Б2.Б.1).

Дискретная математика является фундаментом математической кибернетики. Она базируется на основных понятиях теории множеств, развивает их и является отправным пунктом для изучения основ вычислительной техники, языков программирования, дисциплин математического моделирования. Кроме того, дискретная математика представляет собой логически стройное и логически связное здание, и знакомство с основными вопросами этой дисциплины, бесспорно, является важным элементом подготовки современного специалиста в области информации.

Дисциплина «Дискретная математика» базируется на знаниях по математики, полученных в общеобразовательной школьной программе.

Перечень дисциплин с указанием разделов (тем), усвоение которых студентами необходимо для изучения дисциплины «Дискретная математика»:

Линейная алгебра (1 семестр), Теоретические основы информатика (1 семестр) Программирование на языке высокого уровня (1 и 2 семестры), Исследование операций (3 семестр), Теория вероятностей и математическая статистика (3 семестр), Изучение дисциплины «Дискретная математика» дает основу для изучения как последующих курсов профиля «Электронный бизнес»:

Полученные в ходе изучения дисциплины знания необходимы в дисциплинах:

– Теория принятия решений (4 семестр) – Общая теория систем (5 семестр) – Моделирование бизнес-процессов (5 семестр) – Управление инновациями (7 семестр) 3. Компетенции обучающегося, формируемые в результате освоения дисциплины « Дискретная математика».

знания:

Результат обучения компетен Образовательная технология Вид контроля знать основы теории ОК-1 Л1, Л2, Л3, Л4, С1, С2, С3, С4 Д1, Д2, Д3, Д4, К1, множеств;

алгебраических систем основные положения булевой алгебры излагать основные ОК-1 Л11, Л12, Л13, С11, С12, С13 Д11, Д12, Д13, положения теории графов основные определения и теоремы из комбинаторики и теории графов теории кодирования умения:

Результат обучения компетен Образовательная технология Вид задания положения дискретной математики для разработки и изучения моделей информационных и управляющих систем математическую логику и теорию алгоритмов размещения, сочетания, перестановки применение:

Результат обучения компетен Образовательная технология Вид задания методов дискретной математики для формализации предметных задач и их эффективного решения владеть навыками ОК-16 Л1, Л2, Л3, Л4, С1, С2, С3, С4 Д1, Д2, Д3, Д4, К1, решения типичных заданий, решаемых на основе изучаемого теоретического материала 4. Структура и содержание дисциплины «Дискретная математика»

Общая трудоемкость дисциплины составляет 4,25 зачетных единиц 160 часов, из них 68 часов аудиторной нагрузки.

Общая трудоемкость Аудиторные занятия:

Семинары (С) Лабораторные работы (ЛР) Самостоятельная работа:

Курсовая работа Расчетно-графические работы Реферат контроля Теория множеств и Антиномии (парадоксы).

Мощность множества.

множествами.

Представление соответствий.

соответсвиями.

Замкнутое подмножество.

асимметричное, транзитивное отношения.

Отношение предпорядка, порядка, толерантности, эквивалентности.

Понятие нечеткого множества. Наиболее распространенные параметрические функции принадлежности.

операции. Иерархия систем с двумя бинарными операциями.

Алгебраические системы множество алгебры.

Сигнатура алгебры.

отображение.

Автоморфизм.

Гомоморфизм.

Эндоморфизм. Эпиморфизм (сюръекция). Мономорфизм (инъекция). Биморфизм (биекция).

математической логики и операции. Булева алгебра.

Законы булевой алгебры.

функций. Формы записи функций. Приложение булевых функций в области анализа и синтеза функциональных схем алгебра Вебба, алгебра Шеффера, импликативная алгебра, коимпликативная алгебра, алгебра Жегалкина.

всеобщности и существования.Истинностн ое значение предиката.

Элементы теории графов Способы представления Достижимость и связность в Алгоритм нахождения эйлерова цикла. Оценка вычислительной сложности алгоритма.

характеристики графов.

Алгоритм Форда-Беллмана нахождения расстояния от источника до всех вершин.

Алгоритм Дейкстры Алгоритм нахождения расстояний от источника до бесконтурном графе.

отношения. Моделирование Теорема о структуре (теорема Харари о балансе).

Разрезы. Сети. Потоки в сетях. Алгоритм построения максимального потока.

математическая модель устройства с конечной управляющая система.

Способы описания конечных автоматов.

Теория кодирования декодирование при передаче информации по каналам связи с «шумом».

Математическая модель системы связи ошибок.

Раздел 1. Теория множеств и отношений Множества и классы. Антиномии (парадоксы). Пустое множество, подмножество, надмножество, универсум. Мощность множества.

Отношение принадлежности и включения. Кортеж. Операции над множествами.

Разбиение и покрытие. Декартово произведение множеств. Соответствие. Пустое соответствие, полное соответствие. Область определения, прообраз (Dom) соответствия.

Область значений, образ (Im) соответствия. Свойства соответствий. Представление соответствий. Операции над соответсвиями. Соответствие Галуа и его роль в проективном распознавании образов. Замкнутое подмножество. Рефлексивное, симметричное, антисимметричное, асимметричное, транзитивное отношения. Отношение предпорядка, порядка, толерантности, эквивалентности. Фактормножество множества по отношению.

Понятие нечеткого множества. Функция принадлежности. Способы формализации нечетких множеств. Наиболее распространенные параметрические функции принадлежности. Основные логические операции над нечеткими множествами и их свойства. Основные алгебраические операции над нечеткими множествами и их свойства.

Раздел 2. Алгебраические системы Бинарная операция и ее основное множество. Способы задания бинарной операции. Таблица Кэли. Операционный квадрат таблицы Кэли. Группоид. Квазигруппа.

Латинский квадрат. Лупа. Полугруппа. Моноид. Группа. Абелева группа. Группа симметрий фигуры. Симметрическая группа (группа подстановок). Иерархия систем с двумя бинарными операциями. Кольцо. Тело. Поле (коммутативное тело). Поле Галуа.

Алгебраическая система (алгебра). Носитель, основное множество алгебры. Сигнатура алгебры. Универсальная алгебра (собственно алгебра) и реляционная система (модель) как разновидности алгебраической системы (алгебры). Изоморфизм, изоморфное отображение. Автоморфизм. Гомоморфизм. Эндоморфизм. Эпиморфизм (сюръекция).

Мономорфизм (инъекция). Биморфизм (биекция).

Раздел 3. Элементы математической логики и теории алгоритмов Бинарные логические операции. Булева алгебра. Законы булевой алгебры.

Формула. Глубина формулы. Суперпозиция функций. Таблицы истинности и таблицы Кэли. Формы записи функций. ДНФ, КНФ, СДНФ, СКНФ. Карта Карно. Приложение булевых функций в области анализа и синтеза функциональных схем. Дизъюнктивная алгебра, алгебра Вебба, алгебра Шеффера, импликативная алгебра, коимпликативная алгебра, алгебра Жегалкина. Функции k-значной логики и их задание. Конечнозначная функция Вебба и конечнозначная алгебра Вебба. Конечнозначные алгебры Поста, Россера-Тьюкетта.

Предикат. Кванторы всеобщности и существования. Область действия квантора.

Связанное и свободное вхождение переменной в формулу. Интерпретация формулы на непустом множестве. Истинность формулы в данной интерпретации. Истинностное значение предиката.

Раздел 4. Элементы теории графов Граф. Вершина, ребро, дуга. Неориентированный граф, ориентированный граф (орграф). Кратные ребра (дуги). Петли. Смежные вершины, смежные дуги. Степень вершины. Инцидентные ребро и вершина, дуга и вершина. Основные классы графов:

обыкновенный, орграф, псевдограф, мультиграф, сеть. Виды графов: двудольные графы, регулярные графы, полные графы, деревья, планарные графы. Способы представления графов. Изоморфные графы. Подграфы. Маршрут, цепь, простая цепь, (простой) цикл.

Компонента связности. Категории связности в ориентированном графе. Дерево. Остовное дерево. Реберная и вершинная связности графа. Обход графа. Длина маршрута, расстояние между вершинами. Одноместные и двухместные операции над графами.

Достижимость и связность в графах. Алгоритмы определения компонент связности неорграфов и сильных компонент орграфов.

Эйлеров путь в графе. Задача о кенигсбергских мостах. Эйлеров цикл. Теорема о существовании эйлерова цикла.

Алгоритм нахождения эйлерова цикла. Оценка вычислительной сложности алгоритма.

Гамильтонов путь в графе, гамильтонов цикл. NP-полные задачи. Алгоритм с возвратом для поиска всех гамильтоновых циклов в графе. Его вычислительная сложность.

Задача коммивояжера. Алгоритм поиска субоптимального решения. Деревья.

Понятие остова графа. Алгоритмы Краскала и Прима построения минимального остовного дерева. Метрические характеристики графов. Длина маршрута, длина цепи. Вес дуги (ребра). Взвешенные графы и орграфы. Длина пути в обычном и во взвешенном орграфе, расстояние между вершинами. Практическая интерпретация весов.

Алгоритм нахождения кратчайшего пути в ориентированном графе. Сведение задачи в неориентированном (и вообще, в любом) графе к задаче в ориентированном графе. Алгоритм Форда-Беллмана нахождения расстояния от источника до всех вершин.

Оценка временной сложности алгоритма. Алгоритм Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Оценка сложности алгоритма. Пути в бесконтурном графе. Лемма о перенумерации вершин.

Алгоритм нумерации вершин бесконтурного графа (топологическая сортировка).

Алгоритм нахождения расстояний от источника до всех вершин в бесконтурном графе.

Нахождение кратчайших путей между всеми парами вершин в ориентированном графе — транзитивное замыкание отношения. Алгоритм вычисления расстояний между всеми парами вершин Уоршалла и Флойда.

Сети Петри: формальное определение, функционирование. Конечные разметки.

Ограниченность. Моделирование на сетях Петри. Знаковые графы и их практическое применение. Задачи из области социологии малых групп, экономики и политики. Теорема о структуре (теорема Харари о балансе). Знаковые орграфы как модель когнитивных карт.

Контуры положительной и отрицательной обратной связи и устойчивость/изменчивость моделей на орграфах.

Разделяющие множества. Разрезы. Сети. Потоки в сетях. Пропускная способность разреза. Теорема Форда и Фалкерсона о максимальном потоке и минимальном разрезе.

Метод увеличивающих цепей. Алгоритм построения максимального потока.

Раздел 5. Элементы теории автоматов Конечный автомат как математическая модель устройства с конечной памятью и как управляющая система. Способы описания конечных автоматов. Примеры.

Раздел 6. Теория кодирования Кодирование и декодирование при передаче информации по каналам связи с «шумом». Математическая модель системы связи. Блочный двоичный (m,n)-код и функции определяющие систему кодирования и декодирования. Коды с обнаружением ошибок и коды с исправлением ошибок.

5. Образовательные технологии В учебном процессе, помимо чтения лекций, которые составляют 30% аудиторных занятий, широко используются активные и интерактивные формы. В сочетании с внеаудиторной работой это способствует формированию и развитию профессиональных навыков обучающихся.

Для закрепления знаний студентов по отдельным разделам дисциплины «Дискретная математика» задаются домашние задания, целью которых является формирование первых навыков самостоятельной работы.

Перечень обязательных видов работы студента:

посещение лекционных занятий;

ответы на теоретические вопросы на семинаре;

решение практических задач и заданий на семинаре;

алгоритмов;

выполнение домашних работ;

выполнение контрольных работ.

Интерактивные образовательные технологии, используемые в аудиторных занятиях Семестр Лекционные занятия Изучение теоретических материалов дисциплины на лекциях предусматривает показ презентаций. Отдельные лекции излагаются по проблемной технологии.

Семинарские занятия призваны закрепить теоретические знания студентов и познакомить их с методами решения конкретных задач, возникающих при практическом приложении основ дискретной математики.

Семинарские занятия проходят в компьютерной аудитории, оснащенной необходимым программным обеспечением. На каждом семинарском задании задаются упражнения для самостоятельной подготовки. В данном курсе наряду с математическими методами рассматриваются алгоритмы решения задач. Итогом изучения дисциплины является сдача студентами экзамена.

С7 Нормальные формы и эквивалентные преобразования Компьютерный иллюстратор операций над множествами Д2 Построение диаграмм Хассе. Компьютерная реализация модели соответствия Галуа.

Д3 Алгебраические системы. Группоиды, полугруппы, Д4 Алгебраические системы. Кольца, тела, поля, решетки. Д5 Логические функции классической логики. Табличное и формальное задание логических функций.

Эквивалентные преобразования формул.

Д8 Упрощение ДНФ. Карта Карно. Функциональные схемы. логики предикатов Д10 Способы задания графов. Одноместные и двуместные операции над графами Д11 Алгоритм определения категорий связности графа и Д12 Решение задачи коммивояжера и его прикладное Д13 Алгоритмы нахождения кратчайших расстояний и кратчайших путей в графах и орграфах Д 15 Задачи о потоках. Алгоритм Форда-фалкерсона определения максимального потока.

6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов Для обобщающей аттестации студентов выполняется по 14 письменных контрольных работ по основным разделам дисциплины.

КР 2 Компьютерная реализация модели соответствия КР 7 Истинные формулы и эквивалентные соотношения логики КР 9 Алгоритм определения категорий связности графа и Формы контроля и оценочные средства Виды промежуточной аттестации – экзамен в четвертом семестре.

Пример экзаменационного билета Государственное образовательное учреждение высшего профессионального образования Московской области Международный университет природы, общества и Направление 080500.62 — Бизнес-информатика Курс II (4-й семестр) 1. Бинарные логические операции. Таблица истинности и таблицы Кэли.

2. Соответствие Галуа и его роль в проективном распознавании образов.

3. Граф. Вершина, ребро, дуга. Неориентированный граф, ориентированный граф (орграф). Кратные ребра (дуги).

Перечень вопросов, выносимых на экзамен по курсу «Дискретная математика»:

1. Определение множества и классов. Антиномии (парадоксы). Пустое множество, подмножество, надмножество, универсум. Мощность множества.

2. Отношение принадлежности и включения.

Операции над множествами. Разбиение и покрытие. Декартово произведение 1. Соответствие. Пустое соответствие, полное соответствие. Область определения, прообраз (Dom) соответствия. Область значений, образ (Im) соответствия.

2. Свойства соответствий. Полностью определенное, сюръективное, инъективное, функциональное соответствие. Отображение, биективное и взаимно-однозначное соответствие.

3. Представление соответствий. Операции над соответствиями.

4. Соответствие Галуа и его роль в проективном распознавании образов. Замкнутое подмножество.

5. Бинарные отношения. Рефлексивное, симметричное, антисимметричное, асимметричное, транзитивное отношения.

6. Замыкание отношений.

7. Отношение предпорядка, порядка, толерантности, эквивалентности.

Фактормножество множества по отношению эквивалентности.

8. Понятие нечеткого множества. Функция принадлежности. Способы формализации нечетких множеств. Наиболее распространенные параметрические функции принадлежности.

9. Основные логические операции над нечеткими множествами и их свойства.

10. Бинарная операция и ее основное множество. Способы задания бинарной операции. Таблица Кэли. Операционный квадрат таблицы Кэли.

11. Группоид. Квазигруппа. Латинский квадрат. Лупа. Полугруппа. Моноид. Группа.

Абелева группа.

12. Группа симметрий фигуры.

13. Симметрическая группа (группа подстановок).

14. Иерархия систем с двумя бинарными операциями. Кольцо. Тело. Поле (коммутативное тело). Поле Галуа.

15. Алгебраическая система (алгебра). Носитель, основное множество алгебры.

Сигнатура алгебры. Универсальная алгебра (собственно алгебра) и реляционная система (модель) как разновидности алгебраической системы (алгебры).

16. Изоморфизм, изоморфное отображение. Автоморфизм. Гомоморфизм.

Эндоморфизм. Эпиморфизм (сюръекция). Мономорфизм (инъекция). Биморфизм (биекция).

17. Бинарные логические операции. Таблица истинности и таблицы Кэли.

18. Формула. Глубина формулы. Суперпозиция функций.

19. Формы записи функций. Инфиксная, префиксная, постфиксная 20. Булева алгебра. Законы булевой алгебры.

21. Нормальные формы: ДНФ, КНФ, СДНФ, СКНФ.

22. Карта Карно. Приложение булевых функций в области анализа и синтеза функциональных схем.

23. Дизъюнктивная алгебра, алгебра Вебба, алгебра Шеффера, импликативная алгебра, коимпликативная алгебра, алгебра Жегалкина.

24. Функции k-значной логики и их задание. Конечнозначная функция Вебба и конечнозначная алгебра Вебба. Конечнозначные алгебры Поста, Россера-Тьюкетта.

25. Предикат. Соответствие между предикатом функцией и отношением.

26. Кванторы всеобщности и существования. Область действия квантора. Связанное и свободное вхождение переменной в формулу.

27. Интерпретация формулы на непустом множестве. Истинность формулы в данной интерпретации.

28. Истинностное значение предиката.

29. Граф. Вершина, ребро, дуга. Неориентированный граф, ориентированный граф (орграф). Кратные ребра (дуги). Петли. Основные классы графов: обыкновенный, орграф, псевдограф, мультиграф, сеть.

30. Смежные вершины, смежные дуги. Степень вершины. Инцидентные ребро и вершина, дуга и вершина.

31. Виды графов: двудольные графы, регулярные графы, полные графы, деревья, планарные графы.

32. Способы представления графов.

33. Изоморфные графы. Подграфы.

34. Маршрут, цепь, простая цепь, (простой) цикл. Длина маршрута, расстояние между вершинами.

35. Компонента связности. Достижимость и связность в графах. Категории связности в ориентированном графе.

36. Алгоритмы определения компонент связности неорграфов и сильных компонент орграфов.

37. Дерево. Остовное дерево. Реберная и вершинная связности графа.

38. Одноместные и двухместные операции над графами.

39. Эйлеров путь в графе. Задача о кенигсбергских мостах. Эйлеров цикл. Теорема о существовании эйлерова цикла. Алгоритм нахождения эйлерова цикла. Оценка вычислительной сложности алгоритма.

40. Гамильтонов путь в графе, гамильтонов цикл. Алгоритм с возвратом для поиска всех гамильтоновых циклов в графе. Его вычислительная сложность.

41. Задача коммивояжера. Алгоритм поиска субоптимального решения.

42. NP-полные задачи.

43. Деревья. Понятие остова графа. Алгоритмы Краскала и Прима построения минимального остовного дерева.

44. Длина маршрута, длина цепи. Вес дуги (ребра). Взвешенные графы и орграфы.

Длина пути в обычном и во взвешенном орграфе, расстояние между вершинами.

Практическая интерпретация весов.

45. Алгоритм нахождения кратчайшего пути в ориентированном графе. Сведение задачи в неориентированном графе к задаче в ориентированном графе.

46. Алгоритм Форда-Беллмана нахождения расстояния от источника до всех вершин.

Оценка временной сложности алгоритма.

47. Алгоритм Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Оценка сложности алгоритма.

48. Лемма о перенумерации вершин. Алгоритм нумерации вершин бесконтурного графа (топологическая сортировка).

49. Алгоритм нахождения расстояний от источника до всех вершин в бесконтурном 50. Нахождение кратчайших путей между всеми парами вершин в ориентированном графе — транзитивное замыкание отношения. Алгоритм вычисления расстояний между всеми парами вершин Уоршалла и Флойда.

51. Сети Петри: формальное определение, функционирование.

52. Конечные разметки. Ограниченность. Моделирование на сетях Петри.

53. Знаковые графы и их практическое применение. Задачи из области социологии малых групп, экономики и политики.

54. Теорема о структуре (теорема Харари о балансе). Знаковые орграфы как модель когнитивных карт.

устойчивость/изменчивость моделей на орграфах.

56. Разделяющие множества. Разрезы. Сети. Потоки в сетях. Пропускная способность 57. Теорема Форда и Фалкерсона о максимальном потоке и минимальном разрезе.

58. Метод увеличивающих цепей. Алгоритм построения максимального потока.

59. Конечный автомат как математическая модель устройства с конечной памятью и как управляющая система.

60. Способы описания конечных автоматов. Примеры.

61. Кодирование и декодирование при передаче информации по каналам связи с «шумом». Математическая модель системы связи.

62. Блочный двоичный (m,n)-код и функции определяющие систему кодирования и декодирования.

63. Коды с обнаружением ошибок и коды с исправлением ошибок.

Методика формирования результирующей оценки является бально-рейтинговой.

Работа студента на семинарах оценивается в диапазоне от 0 до 60 баллов.

Начисление баллов учитывает сдачу компьютерной реализации алгоритмов, средние оценки за контрольные работы и работы на семинарах. Студент допускается к экзамену, если работа на семинарах оценена более чем на 15 баллов.

Итоги посещаемости и успеваемости фиксируются в промежуточных контрольных точках (8, 12, 16 недели обучения) при помощи трех значений:

«0» – имеет низкую посещаемость и успеваемость (много пропустил, не сдал и одного задания);

«1» – студент имеет среднюю посещаемость и не все задания сдал;

«2» – студент имеет посещаемость и сдачу заданий на 90-100%.

На экзамене студент отвечает на билет, содержащий три вопроса. Ответ на каждый вопрос оценивается в диапазоне от 0 до 10 баллов.

Результирующая оценка по дисциплине формируется следующим образом:

Суммируются баллы, полученные студентом на семинарах и экзамене.

Оценка «неудовлетворительно» – студент получил менее 45 баллов.

Оценка «удовлетворительно» – студент получил от 45 до 65 баллов.

Оценка «хорошо» – студент получил от 65 до 85 баллов.

Оценка «отлично» – студент получил более 85 баллов.

Пример контрольной работы и ответы:

Контрольная работа 2:

Упр 1. Доказать используя основные тождества теории множеств Решение:

A\ (B\C) = {опред \} = A (B\C ) = {опред \} = A (B C ) = {де Моргана} = (A C ) = {опред \} = (A\B) (A C) Упр 2. Дано универсальное множество U={3, 6, 9, 12, 15, 18, 21}, A={6, 15, 18, 21}, B={3, 6, 9, 15}. Задать характеристические вектора для множеств А, В. Какая логическая операция будет соответствовать А\В? Выполнить соответствующую операцию над векторами. Получившийся вектор преобразовать в множество.

Решение:

Характеристические вектора А = ( 0 1 0 0 1 1 1 ), В = (1 1 1 0 1 0 0) Логические операции А\В = А «и» («не» В), где «не» В = (0 0 0 1 0 1 1) Выполнение логических операций А «и» («не» В) = Упр 3. Используя формулу ( А В) = (AB)\ (AB) определить какой набор логических операций над характеристическими векторами соответствует АВ Решение:

( А В) = (AB)\ (AB) = (А «или» В) «и» («не» (А «и» В)) Упр 4. Даны множества A={Аня, Саша, Коля}, B={Пушкин, Лермонтов}. Выписать декартовые произведения АB, В B.

Решение:

АВ = { (А, П), (А, Л), (С, П), (С, Л), (К, П), (К, Л) } ВВ ={ (П, П), (П, Л), (Л, П), (Л, Л) } 7. Учебно-методическое обеспечение дисциплины Рекомендуемая литература Основная:

1. Новиков Ф.А. Дискретная математика для программистов. — СПб: Питер, 2004.

2. Яблонский С.В. Введение в дискретную математику, М.:Высшая школа, Фомичев В.М. Методы дискретной математики в криптологии. – М.: ДИАЛОГ-МИФИ, 2010.

Дополнительная:

1. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. — М.: Логос, 2000.

2. Андерсон Дж.А. Дискретная математика и комбинаторика. – М.: Вильямс, 2004.

8. Материально-техническое обеспечение дисциплины Cпециализированный компьютерный класс (ауд. 1-307, 1-321, 1-322, 1-318), подключенный к сети Интернет и к локальной сети университета (директория GROUPS для обучающихся).

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПООП ВПО по направлению и профилю подготовки 080500 Бизнесинформатика Рецензент: _ // (ученая степень, ученое звание, Ф.И.О., место работы, должность)