комбинаторные конфигурации, метод включения-исключения основные понятия теории графов, связные графы, изоморфизм графов методы решения экстремальных задач на графах, алгоритмы

УТВЕРЖДАЮ
Зам. директора Института кибернетики
по учебной работе

___________ Гайворонский С.А.
«___»_____________2011 г.


РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
ДИСКРЕТНАЯ МАТЕМАТИКА

НАПРАВЛЕНИЕ ООП
230700 Прикладная информатика




КВАЛИФИКАЦИЯ (СТЕПЕНЬ)
бакалавр




БАЗОВЫЙ УЧЕБНЫЙ ПЛАН ПРИЕМА
2011 г.






КУРС
1
СЕМЕСТР
2




КОЛИЧЕСТВО КРЕДИТОВ
6




ПРЕРЕКВИЗИТЫ
Б2.Б1

КОРЕКВИЗИТЫ
Б2.Б1.В3, Б2.Б3




ВИДЫ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ И ВРЕМЕННОЙ РЕСУРС:

Лекции
27
час.

Лабораторная работа

час.

Практические занятия
45
час.

АУДИТОРНЫЕ ЗАНЯТИЯ
72
час.

САМОСТОЯТЕЛЬНАЯ РАБОТА
72
час.

ИТОГО
144
час.




ФОРМА ОБУЧЕНИЯ
Очная




ВИД ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ
экзамен




ОБЕСПЕЧИВАЮЩЕЕ ПОДРАЗДЕЛЕНИЕ
кафедра ПМ





ЗАВЕДУЮЩИЙ КАФЕДРОЙ

В.П. Григорьев





РУКОВОДИТЕЛЬ ООП

О.В. Марухина





ПРЕПОДАВАТЕЛЬ

В.В.Офицеров



2011 г.

Цели освоения дисциплины
Целями преподавания дисциплины являются:
формирование фундаментальных знаний у студентов при изучении вопросов теоретико-множественного описания математических объектов, основных проблем теории графов и методологии использования аппарата математической логики, составляющих теоретический фундамент описания функциональных систем;
приобретение навыков решения основных задач по ряду разделов дискретной математики: теория множеств и отношения на множествах, теория графов, функции алгебры логики;
приобретение навыков самостоятельного изучения отдельных тем дисциплины и решения типовых задач;
усвоение полученных знаний студентами, а также формирование у них мотивации к самообразованию за счет активизации их познавательной деятельности.
Поставленные цели полностью соответствуют целям (Ц1–Ц5) ООП.

2. Место дисциплины в структуре ООП
Дисциплина «Дискретная математика» (Б2.В6) относится к вариативной части математического модуля дисциплин ООП.
Пререквизитами данной дисциплины являются дисциплины математического и естественнонаучного цикла (Б2): «Линейная алгебра и аналитическая геометрия» (Б2.Б1.1), «Математический анализ» (Б2.Б1.2)
Кореквизитами данной дисциплины являются дисциплина математического и естественнонаучного цикла (Б2): «Теория систем и системный анализ» (Б2.Б5) и дисциплина профессионального цикла (Б3) «Имитационное моделирование» (Б3.В4).
Для изучения дисциплины «Дискретная математика» студент должен:
Знать:
основы математического анализа, алгебры и геометрии;
современные тенденции развития информатики и вычислительной техники, компьютерных технологий.
Уметь:
применять математические методы и вычислительную технику для решения практических задач;
программировать на одном из алгоритмических языков;
проводить сравнительный анализ параметров.
Владеть:
элементами математического анализа;
основами алгоритмизации.


3. Результаты освоения дисциплины
При изучении дисциплины бакалавры должны изучить общие принципы теоретико-множественного описания математических объектов, основные проблемы теории графов и методологию использования аппарата математической логики; знать способы задания множеств, булевых функций и графов, а также основные методы оперирования с ними; выбирать оптимальные методики при решении задач теории множеств, математической логики и теории графов.
Соответствие результатов освоения дисциплины «Дискретная математика» формируемым компетенциям ООП представлено в таблице

Результат обучения
Код
Знания
Код
Умения
Код
Владения

Р1
З.1.5
Методы теории множеств, математической логики, алгебры высказываний, теории графов, теории автоматов, теории алгоритмов.
У.1.5
Способы задания множеств, булевых функций и графов, а также основные методы оперирования с ними.
В.1.5
Опытом решения задач теории множеств, математической логики и теории графов.

В результате освоения дисциплины студент будет:
Знать:
способы задания множеств, основные операции над ними, отношения между элементами множеств, их свойства и виды отношений;
отображения и функции, виды отображений, основные операции над отображениями;
основные понятия комбинаторики, методы решения комбинаторных задач;
основные комбинаторные конфигурации, метод включения-исключения;
основные понятия теории графов, связные графы, изоморфизм графов;
методы решения экстремальных задач на графах, алгоритмы раскраски вершин и ребер графа.
Уметь:
употреблять специальную математическую символику для выражения количественных и качественных отношений между объектами;
доказывать основные теоремы теории множеств выполнять операции над множествами, применять аппарат теории множеств для решения задач, исследовать бинарные отношения на заданные свойства,
строить нормальные формы и определять функциональную полноту систем функций алгебры логики;
решать оптимизационные задачи на графах.
Владеть:
практическим опытом решения задач теории множеств, математической логики, комбинаторных и теоретико-графовых задач.
навыками применения языка и средств дискретной математики.
4. Структура и содержание дисциплины
4.1. Содержание разделов дисциплины:
Тема № 1. Теория множеств

Понятие множества. Конечные и бесконечные множества. Способы задания множеств. Подмножества. Множество всех подмножеств данного множества. О числе к-элементных подмножеств n-элементного множества. Определение мощности множества всех подмножеств конечного множества (с использованием формулы бинома Ньютона). Универсальное множество. Понятие алгебры. Алгебра множеств. Понятия алгебраических и кардинальных операций. Алгебраические операции над множествами. Законы алгебры множеств. Двойственность в алгебре множеств. Уравнения и системы уравнений в алгебре множеств. Основные леммы, используемые при решении уравнений в алгебре множеств. Мощность множества. Понятие счетного множества и континуума. Канторовская диагональная процедура. Примеры счетных множеств. Доказательство счетности множества алгебраических чисел. Свойства счетных множеств. Необходимые и достаточные условия бесконечности множества. Примеры континуальных множеств. Теорема Кантора-Бернштейна. Доказательство существования иррациональных и трансцендентных чисел. Кардинальные операции над множествами. Прямое произведение множеств. Проекция множеств.

Тема № 2. Математическая логика

Высказывания. Операции над высказываниями. Алгебра логики. Табличный способ задания функций. Таблица истинности. Формулы и функции алгебры логики. О числе функций алгебры логики от n переменных. Равносильные формулы. Законы алгебры логики. ДНФ и КНФ. Разложение функций алгебры логики по к переменным. СДНФ и СКНФ. Логические следствия. Проблема разрешимости в алгебре логики. Тавтологии и противоречия. Основные схемы доказательств: если x то y, доказательство от противного, доказательство построением цепочки импликаций, доказательство разбором случаев. Суперпозиция функций алгебры логики. Полные системы функций. Понятие базиса. Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина. Замкнутые классы функций. Линейные функции. Монотонные функции. Теорема о монотонных функциях. Двойственность в алгебре высказываний. Самодвойственные функции. Функции, сохраняющие константы 0, 1. Теорема Поста о функциональной полноте.

Тема № 3. Теория графов

Основные понятия. Способы представления графов, перечисление графов. Матрицы инцидентности и смежности. Эйлеровы циклы. Теорема Эйлера. укладки графов. Укладка графов в трехмерном пространстве. Планарность. Формула Эйлера для плоских графов. Деревья и их свойства. Связность графа. Раскраска графа. Хроматическое число. Потоки в сетях: теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе. Алгоритм нахождения максимального потока. Теорема о целочисленности. Задача о назначениях. Дискретные экстремальные задачи: алгоритм Краскаля нахождения минимального основного дерева. Методы определения крат-чайших путей в графе. Алгоритм Форда-Беллмана. Алгоритм Дейкстры.




4.2. Структура дисциплины по разделам, формам организации и контроля обучения
Таблица 1.
Название раздела/темы
Аудиторная работа (час)
СРС
(час)
Итого
Форма текущего контроля


Лекции
Практ./сем.
занятия
Лаб. зан.




1. Теория множеств
6
 8

14
 28
Уст. отчет

2. Математическая логика
11
 22

33
66
Контроль. работа

3. Теория графов
10
 15

25
50
Контроль. работа

Итого
27
45

72
144
экзамен




4.3. Распределение компетенций по разделам дисциплины

Распределение по разделам дисциплины планируемых результатов обучения по ООП, формируемых в рамках данной дисциплины и указанных в пункте 3.


Таблица 2.

Формируемые компетенции
Разделы дисциплины



1
2
3

1
3.1.5
Х
Х
х

2
У.1.5


·

Приложенные файлы

  • doc 44859196
    Размер файла: 141 kB Загрузок: 0

Добавить комментарий