МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВПО «Уральский государственный экономический

университет»

УТВЕРЖДАЮ

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

Л.М. Капустина

«_»2011 г.

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

Программа учебной дисциплины Наименование специальности (направления подготовки) 010503 «Математическое обеспечение и администрирование информационных систем»

Екатеринбург 2011

1. ЦЕЛИ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ

Целью изучения дисциплины «Дискретная математика»

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

Изучение дисциплины обеспечивает реализацию требований Государственного образовательного стандарта высшего профессионального образования по федеральному компоненту «Математика» в части, касающейся следующих вопросов:

множества и отображения;

бинарные отношения;

графы и сети;

элементы теории кодирования.

В результате изучения дисциплины студенты должны:

а) знать:

фундаментальные понятия теории множеств: множество, элемент множества, операции с множествами, мощность множества; основные факты теории множеств;

важнейшие классы соответствий: отображение, функция, инъекция, сюръекция, биекция;

основные понятия и факты, связанные с бинарными отношениями; основные классы бинарных отношений: отношение эквивалентности, отношения порядка;

основные понятия теории графов; типовые сетевые модели;

элементарные факты теории кодирования.

б) уметь:

производить операции с различными конечными и бесконечными множествами; применять аппарат теории множеств к решению математических и прикладных задач;

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

строить графические и сетевые модели математических и прикладных задач; исследовать простейшие сетевые модели;

решать задачи, связанные с алфавитным кодированием;

решать типовые комбинаторные задачи и рекуррентные уравнения.

в) иметь навыки:

работы с объектами дискретной математики;

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

исследования свойств дискретных структур.

2. МЕСТО УЧЕБНОЙ ДИСЦИПЛИНЫ В СТРУКТУРЕ

ООП ВПО

Учебная дисциплина «Дискретная математика» является дисциплиной федерального компонента учебного плана подготовки математиков-программистов по специальности 01.05. «Математическое обеспечение и администрирование информационных систем» и изучается во 2–3 семестрах при дневной форме обучения.

Данной дисциплине должно предшествовать изучение дисциплин: «Алгебра и теория чисел», «Математический анализ», «Геометрия и топология», «Информатика», «Программирование».

Знания, умения, навыки, полученные в процессе изучения дисциплины «Дискретная математика» используются при изучении следующих дисциплин: «Теория вероятностей и математическая статистика», «Математическая логика», «Функциональный анализ», «Вычислительная математика», «Экстремальные задачи», «Архитектура вычислительных систем и компьютерных сетей», «Структуры и алгоритмы компьютерной обработки данных», «Базы данных и СУБД», «Параллельное программирование».

3. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ

ДИСЦИПЛИНЫ

3.1. Структура учебной дисциплины Общая трудоемкость дисциплины по дневной форме обучения составляет 128 часов, в том числе:

аудиторных – 53 (лекций – 18, лабораторно-практических занятий – 35), самостоятельная работа – 75, Форма промежуточной аттестации – экзамены во 2-м и 3-м семестрах.

Структура и трудоемкость дисциплины представлена в таблице 1.

График изучения дисциплины в течение семестра (последовательность изучения тем, контрольные работы) приведен в календарно-тематическом плане и размещен на Портале электронных образовательных ресурсов в разделе «Ресурсы».

Таблица 1 – Структура и трудоемкость дисциплины № Наименование разделов, тем Теоретико-множественные оттроль Комбинаторика и рекуррентные соотношения Элементы комбинаторики Рекуррентные соотношения Бинарные отношения на множестве Декартово произведение Отношение эквивалентности и Представление и сравнение частично упорядоченных множеств Бинарные отношения, операции и функции Операции над бинарными отношениями Соответствия и бинарные отнотроль Булевы алгебры и булевы функции Равномощность множеств Некоторые специальные классы 3.2. Содержание учебной дисциплины 1.1. Понятие множества Множество, элемент множества. Конечные и бесконечные множества. Пустое множество. Задание множества с помощью перечисления и с помощью определяющего свойства.

1.2. Теоретико-множественные отношения и операции Отношения между множествами: равенство множеств; подмножество; надмножество; строгое подмножество. Булеан множества. Операции над множествами: пересечение, объединение, разность, симметрическая разность, дополнение. Основные свойства теоретико-множественных отношений и операций.

Диаграммы Эйлера – Венна.

1.3. Отображения Соответствие между множествами. Область определения и область значений соответствия. Обратное соответствие. Отображение множества во множество. Образ элемента области определения. Множество значений отображения. Прообраз и полный прообраз элемента множества значений. Функция (полное отображение). Инъективное, сюръективное и биективное отображения. Обратное отображение. Произведение (композиция) отображений.

2. Комбинаторика и рекуррентные соотношения 2.1. Элементы комбинаторики Правило произведения. Кортежи (размещения с повторениями).

Размещения без повторений. Перестановки. Сочетания без повторений. Перестановки с повторениями данного состава. Сочетания с повторениями.

2.2. Рекуррентные соотношения Рекуррентный способ задания последовательности. Рекуррентное уравнение. Решение линейных рекуррентных уравнений.

Использование рекуррентных соотношений в различных разделах математики. Целые числа и полиномы 3. Бинарные отношения на множестве 3.1. Декартово произведение Упорядоченная пара элементов. Прямое (декартово) произведение двух множеств и его свойства. Упорядоченная тройка, …, nка элементов. Прямое (декартово) произведение трех,…, n множеств.

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

3.3. Отношение эквивалентности и разбиение на классы Бинарное отношение на множестве и семейство соответствующих подмножеств. Матрица бинарного отношения на множестве. Отношение эквивалентности на множестве. Разбиение множества на классы. Классы эквивалентности. Классы разбиения.

Фактор-множество.

3.4. Отношения порядка Отношение квазипорядка. Квазиупорядоченные множества (к. у.

м.). Отношение частичного порядка. Частично упорядоченные множества (ч. у. м.). Отношение линейного порядка. Линейно упорядоченное множество (л. у. м.). Отношения нестрогого и строгого порядка. Упорядоченная структура на множестве.

Цепь. Убывающая цепь. Наименьший (наибольший) элемент ч.

у. м. Минимальный (максимальный) элемент ч. у. м. Условие минимальности (фундированность). Отношение полного порядка. Вполне упорядоченное множество (в. у. м.).

3.5. Представление и сравнение частично упорядоченных множеств Изотонные (монотонные) отображения ч. у. м. Изоморфные вложения ч. у. м. Представление произвольного ч. у. м. Подобие ч. у. м.

4. Бинарные отношения, операции и функции 4.1. Операции над бинарными отношениями Теоретико-множественные операции. Инволюция (обращение) бинарного отношения; умножение (композиция) бинарных отношений.

4.2. Соответствия и бинарные отношения Представление соответствий, отображений и функций бинарными отношениями.

4.3. Булевы алгебры и булевы функции Решетка. Булева алгебра. Булевы операции. Булевы константы и булевы переменные. Булевы функции. Переключательные функции. Теорема о функциональной полноте; примеры функционально полных базисов.

5. Мощность множества 5.1. Равномощность множеств Равномощность множеств (определение). Равномощность множеств как отношение эквивалентности. Классы равномощных множеств. Мощность множества. Критерий равномощности конечных множеств. Равномощность N, Z и Q. Равномощность всех интервалов и R. Равномощность интервала, полуинтервала и отрезка. Равномощность I и R. Неравномощность N и интервала (0; 1). Счтные множества. Несчтные и континуальные множества. Основные теоремы о счтных и континуальных множествах.

5.2. Сравнение мощностей Неравенства и < для мощностей. Примеры. Теорема Кантора (о мощности булеана). Отношения и < как отношения линейного порядка. Теорема Кантора-Бернштейна.

6. Графы 6.1. Элементарные понятия теории графов Классические задачи теории графов. Граф. Вершины и рбра графа. Смежность и инцидентность элементов графа. Изображение графа. Изоморфизм графов. Помеченный граф. Мультиграф.

Псевдограф. Ориентированный граф. Граф бинарного отношения. Подграф. Операции над графами. Маршрут, цепь, простая цепь. Цикл, простой цикл. Ориентированный маршрут, ориентированная цепь, путь. Связный граф. Дерево, лес. Числовые характеристики графа. Регулярный граф. Матрицы смежности и инцидентности.

6.2. Некоторые специальные классы графов Плоский граф. Грань плоского графа. Формула Эйлера для плоского графа. Планарный граф. Гомеоморфизм графов. Теорема Понтрягина–Куратовского (общий критерий планарности графа). Эйлеров цикл и эйлерова цепь. Эйлеровы и уникурсальные графы. Гамильтонов цикл и гамильтоновы графы.

7. Сетевые модели Сетевое моделирование. Сетевая модель. Задача минимизации сети. Задача нахождения кратчайшего пути. Задача нахождения критического пути.

Кодирование и декодирование. Неалфавитное и алфавитное кодирование. Алфавит. Слово. Кодирующий алфавит. Кодирование слова. Сообщения, кодированные сообщения. Однозначная декодируемость. Схема алфавитного кодирования. Префикс и постфикс слова. Свойства префикса и постфикса. Достаточное условие однозначной декодируемости. Граф, соответствующий коду. Критерий однозначной декодируемости (теорема Ал. А.

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

4. ОЦЕНОЧНЫЕ СРЕДСТВА

ДЛЯ ТЕКУЩЕГО КОНТРОЛЯ УСПЕВАЕМОСТИ,

ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ПО ИТОГАМ

ОСВОЕНИЯ ДИСЦИПЛИНЫ И ИХ УЧЕБНОМЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

4.1. Текущий контроль Результаты освоения учебной дисциплины оцениваются следующими средствами текущего контроля успеваемости:

Методическое обеспечение текущего контроля Контрольная работа проводится на практических занятиях. Тематика контрольных работ и типы задач размещены на Портале электронных образовательных ресурсов в разделе «Ресурсы».

Самоконтроль осуществляется по вопросам к каждой теме. Перечень вопросов размещен на Портале электронных образовательных ресурсов в разделе «Ресурсы».

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

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

4.3. Использование балльно-рейтинговой системы для текущего контроля и промежуточной аттестации Для текущего контроля успеваемости и промежуточной аттестации используется балльно-рейтинговая система в соответствии с «Положением об академическом рейтинге».

Текущий рейтинг по дисциплине «Дискретная математика» определяется с учетом посещаемости, участия студентов в аудиторной и самостоятельной работе, выполнении контрольных точек, а также внеаудиторной работе (участие в конференциях, олимпиадах, конкурсах и др.) Требования, критерии оценки для расчета текущего рейтинга по дисциплине размещены на Портале электронных образовательных ресурсов в разделе «Ресурсы».

5. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ

ОБЕСПЕЧЕНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ (МОДУЛЯ)

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

Электронная версия конспекта лекций и презентационных материалов представлены на Портале электронных образовательных ресурсов по дисциплине «Дискретная математика» в разделе «Ресурсы».

Для изучения дисциплины «Дискретная математика» следует использовать основную литературу, дополнительную литературу и Интернет-ресурсы.

а) основная литература:

Судоплатов С. В., Овчинникова Е. В.. Дискретная математика. Инфра-М, НГТУ, 2007.

Новиков Ф.А. Дискретная математика для программистов. Питер, 2009.

Шевелев Ю.П. Дискретная математика. Лань, 2008.

б) дополнительная литература:

1. Романовский И.В. Дискретный анализ. BHV-СПб, 2008.

2. Ерусалимский Я.М. Дискретная математика. Вузовская 3. Капитонова Ю.В. и др. Лекции по дискретной математике. BHV-СПб, 2004.

4. Оре О. Теория графов. Либроком, 2009.

5. Просветов Г.И. Дискретная математика: задачи и решения. БИНОМ. 2009.

6. Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. Айрис-Пресс, 2008.

7. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. Издательство: ФИЗМАТЛИТ, 8. Кузнецов О.П. Дискретная математика для инженера.

9. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. URSS, 2009.

в) Интернет-ресурсы:

1. www.matburo.ru 2. www.allmath.ru 3. www.exponenta.ru 4. www.ru.wikipedia.org/wiki/Дискретная_математика

class='zagtext'> 6. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

УЧЕБНОЙ ДИСЦИПЛИНЫ

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

оборудованные кабинеты и аудитории, аудитории, оборудованные мультимедийными средствами обучения.

Программа составлена в соответствии с требованиями ГОС ВПО по специальности 010503 «Математическое обеспечение и администрирование информационных систем», квалификация – математик-программист.

Программа размещена на Портале электронных образовательных ресурсов в разделе «Ресурсы».

Авторы: кандидат педагогических наук, доцент Боярский М.Д.

кандидат физико-математических наук, доцент Локшин М.Д.

Рецензент – доктор физико-математических наук, профессор Першин В.К.

Программа одобрена на заседании Учебно-методической комиссии факультета сферы услуг и информационных технологий (протокол № 4 от 20 мая 2011 года).