Государственное образовательное учреждение высшего профессионального

образования Московской области

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

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

УТВЕРЖДАЮ

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

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

ПРОГРАММА ДИСЦИПЛИНЫ

ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

(наименование дисциплины) по специальности 080801 65 «Прикладная информатика (по областям)»

Форма обучения: очная Уровень подготовки: специалист (выбрать нужное) Курс (семестр): 2(3) г. Дубна, 2010 г.

Программа дисциплины «Основы дискретной математики» по специальности «Прикладная информатика (по областям)»: Учебная программа. Автор: доц. Дедович Т.Г.

Дубна: Университет «Дубна», 2010г.

Автор программы:

ФИО, ученое звание, кафедра доцент Дедович Татьяна григорьевна_ (подпись) Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования и учебным планом по направлению подготовки (специальности) (указывается номер ОКСО, код и наименование направления подготовки (специальности)) Программа рассмотрена на заседании кафедры системного анализа и управления (название кафедры) Протокол заседания № _ от «» 2010г.

Заведующий кафедрой /Черемисина Е.Н. / (ученое звание) (подпись) (фамилия, имя, отчество)

СОГЛАСОВАНО

заведующий выпускающей кафедрой /_ / (ученое звание) (подпись) (фамилия, имя, отчество) «» _ 2010 г.

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

ОДОБРЕНО

декан факультета (директор института, филиала) _ /Черемисина Е.Н./ (ученое звание, степень) (подпись) (ФИО) «» _ 20 г.

Руководитель библиотечной системы _ /Черепанова В.Г./ (подпись) (ФИО) 1. Выписка из ГОС ВПО Рабочая программа модуля дисциплины «Основы дискретной математики» является общей профессиональной дисциплиной федеральной компоненты и составлена на основе требований ГОС ВПО по специальности 080801 65 — «Прикладная информатика (по областям)», квалификация — информатик.

Номер государственной регистрации: 52 мжд / сп (утв. Минобразованием РФ 14.03.2000) Алгебра и геометрия: алгебраические структуры, векторные пространства, линейные отображения; аналитическая геометрия, многомерная геометрия кривых и поверхностей;

Математический анализ: дифференциальное и интегральное исчисления; экстремумы функций; аналитическая геометрия и линейная алгебра; последовательности и ряды; векторный анализ и элементы теории поля; дифференциальные уравнения;

Модуль «Дискретная математика»: логические исчисления, Элементы теории нечетких множеств. Нечеткие алгоритмы.

Теория неопределенности.

Общий объём курса, согласно учебному графику на 2010-2011 учебный год – часов. Из них: лекции – 34 час., семинарские занятия – 34 час, самостоятельная работа – 62 час.

Сдача экзамена в 3-ем семестре.

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

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

Методы обучения Методы обучения на лекционных занятиях включают использование средств мультимедийного представления информации (презентации, схемы, иллюстрации).

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

Требования к студентам Исходный уровень знаний студентов включает знания по математики, полученных в общеобразовательной школьной программе. Студенты должны владеть навыками программирования. Полученные в ходе изучения дисциплины знания необходимые в дисциплинах "Теория принятия решений", "Моделирование экономических процессов и систем", "Теория управления" Виды контроля и формы работ Формы работы студентов предусматривают освоение дисциплины в рамках лекционных занятий (2 часа в неделю) и семинарских занятий (2 часа в неделю).

Предусмотрены задания для домашней работы.

Данная дисциплина предусматривает:

выполнение заданий на семинарских занятиях;

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

Итоговый контроль – экзамен.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Объём дисциплины и виды учебной работы:

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

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

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

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

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

Таблица Кэли. Операционный квадрат таблицы Кэли. Группоид. Квазигруппа. Латинский квадрат. Лупа. Полугруппа. Моноид. Группа. Абелева группа. Группа симметрий фигуры.

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

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

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

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

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

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

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

Раздел 4. Элементы теории графов Граф. Вершина, ребро, дуга. Неориентированный граф, ориентированный граф (орграф).

Кратные ребра (дуги). Петли. Смежные вершины, смежные дуги. Степень вершины.

Инцидентные ребро и вершина, дуга и вершина. Основные классы графов:

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

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

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

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

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

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

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

Метрические характеристики графов. Длина маршрута, длина цепи. Вес дуги (ребра).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

План семинарских занятий 6. Элементы математической Логические функции и таблицы истинности логики и теории алгоритмов логики и теории алгоритмов логики и теории алгоритмов 12. Элементы теории графов Нахождение кратчайших путей и расстояний График выполнения самостоятельных работ студентами работы ВЗ – выдача задания на самостоятельную работу, РК – рубежный контроль, СЗ – сдача и защита задания 7. Учебно-методическое обеспечение дисциплины Рекомендуемая литература Основная:

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

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

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

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

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

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

9. Формы контроля и оценочные средства Перечень вопросов, выносимых на экзамен по курсу «Основы дискретной математики»:

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

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

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

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

5. Соответствие Галуа и его роль в проективном распознавании образов. Замкнутое 6. Бинарные отношения. Рефлексивное, симметричное, антисимметричное, асимметричное, транзитивное отношения.

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

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

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

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

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

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

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

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

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

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

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

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

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

Эндоморфизм. Эпиморфизм (сюръекция). Мономорфизм (инъекция). Биморфизм 18. Бинарные логические операции. Таблица истинности и таблицы Кэли.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример экзаменационного билета _ Международный университет природы, общества и человека “Дубна” Специальность: «Прикладная информатика»

Дисциплина: Основы дискретной математики 1. Бинарные логические операции. Таблица истинности и таблицы Кэли.

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

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

_

КАЛЕНДАРНЫЙ ПЛАН (РАБОЧАЯ ПРОГРАММА)

кафедра системного анализа и управления направление 080801.65 Прикладная информатика (о областям) курс 2 семестр 3 2010/2011 уч.

года Номер 26 мар. алгебры поста, россера-Тьюкетта.

11 нед 2 Эйлеров путь в графе. Задача о Комп., [1] – 10.1-10.3 Алгоритм определения категорий связности графа и А Решение упражнений. Компьютерная 6 К,З 12 нед 2 Метрические характеристики Комп., [1] – 8.7 Алгоритмы нахождения обходов графов. Циклы Эйлера А Решение упражнений. Компьютерная 6 К,З Учебная литература (обязательная) Новиков Ф.А. Дискретная математика для программистов. — СПб: Питер, 2000.

Яблонский С.В. Введение в дискретную математику, М.:Высшая школа, 2003.

Фомичев В.М. Методы дискретной математики в криптологии. М.:ДИАЛОГ-МИФИ, 2010.

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

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