Рабочая программа дисциплины дискретная математика icon

Рабочая программа дисциплины дискретная математика



НазваниеРабочая программа дисциплины дискретная математика
Дата конвертации05.06.2013
Размер169.71 Kb.
ТипРабочая программа
скачать >>>

УТВЕРЖДАЮ

Зам. директора Института кибернетики

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


___________ Гайворонский С.А.

«___»_____________2011 г.


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

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


НАПРАВЛЕНИЕ ООП

230700 Прикладная информатика







КВАЛИФИКАЦИЯ (СТЕПЕНЬ)

бакалавр







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

2011 г.













КУРС

1

СЕМЕСТР

2







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

6







ПРЕРЕКВИЗИТЫ

Б2.Б1

КОРЕКВИЗИТЫ

Б2.Б1.В3, Б2.Б3







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

Лекции

27

час.

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




час.

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

45

час.

^ АУДИТОРНЫЕ ЗАНЯТИЯ

72

час.

САМОСТОЯТЕЛЬНАЯ РАБОТА

72

час.

ИТОГО

144

час.







^ ФОРМА ОБУЧЕНИЯ

Очная







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

экзамен







^ ОБЕСПЕЧИВАЮЩЕЕ ПОДРАЗДЕЛЕНИЕ

кафедра ПМ










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




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










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




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










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




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




2011 г.

  1. ^ Цели освоения дисциплины

Целями преподавания дисциплины являются:

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

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

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

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

Поставленные цели полностью соответствуют целям (Ц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




х

х

3

В.1.5

Х

х

х



^ 5. Образовательные технологии

Таблица 3.

Методы и формы организации обучения (ФОО)

ФОО


Методы

Лекции

Практич. раб.

СРС

Дискуссия








IT-методы







Работа в команде








Обучение

на основе опыта









Опережающая самостоятельная работа








Проектный метод









Индивидуальное обучение









Проблемное обучение








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

  • изучение теоретического материала дисциплины на лекциях с использованием компьютерных технологий;

  • самостоятельное изучение теоретического материала дисциплины с использованием Internet-ресурсов, методических разработок, специальной учебной литературы;

  • закрепление теоретического материала при проведении практических работ, выполнение проблемно-ориентированных, творческих заданий.



^ 6. Организация и учебно-методическое обеспечение самостоятельной работы студентов


6.1 Текущая СРС.

  • работа с лекционным материалом, литературой и электронными источниками информации;

  • выполнение домашних заданий;

  • изучение тем, вынесенных на самостоятельную проработку;

  • подготовка к практическим занятиям;

  • подготовка к контрольным работам, к экзамену.



^ 6.2 Творческая проблемно-ориентированная самостоятельная работа

(ТСР).

ТСР направлена на развитие интеллектуальных умений, комплекса универсальных (общекультурных) и профессиональных компетенций, повышение творческого потенциала бакалавров и заключается в:

  • поиске, анализе, структурировании и презентации информации;

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

  • выполнении расчетно-графических работ;

  • исследовательской работе и участии в научных студенческих семинарах и олимпиадах;

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


^ 6.2.1. Содержание самостоятельной работы студентов по дисциплине


  1. Перечень научных проблем и направлений научных исследований;

  2. Алгебраические и кардинальные операции над множествами;

  3. Законы алгебры множеств. Уравнения и системы уравнений;

  4. Выполнение операции над высказываниями;

  5. Упрощение булевых формул;

  6. Проверка полноты систем функций алгебры логики.;

  7. Критические пути в сетевых графиках;

  8. Декомпозиция графов;

  9. Построение остова графа и кодерева графа.


^ 6.3 Контроль самостоятельной работы

Оценка результатов самостоятельной работы организуется как единство двух форм: самоконтроль и контроль со стороны преподавателей.


^ 6.4 Учебно-методическое обеспечение самостоятельной работы студентов

  1. Корниенко А.В. Дискретная математика. Учебное пособие.– Томск:

Изд-во ТПУ, 2000.– 96с.

  1. Офицеров В.В. Дискретная математика. Учебное пособие.– Томск: Изд-

во ТПУ, 2005.– 105с.

3. Кузнецов О.П. Дискретная математика для инженера. – СПб.: Изд-во

«Лань», 2004.– 400 с.


^ 7. Средства (ФОС) текущей и итоговой оценки качества освоения дисциплины

7.1. Входной контроль (пример вопросов тестовой форме)


Входной контроль организован в виде контрольной работы.

Вариант № 1.

  1. Найти область определения функции: .

  2. Построить график функции:

  3. Найти предел числовой последовательности:

  4. Найти пределы функций: a); б) .


^ 7.2. Банк данных теоретических вопросов для экзамена


  1. Множества. Способы задания множеств. Основные операции над множествами.

  2. Доказательство основных законов алгебры множеств. Принцип двойственности.

  3. Взаимно-однозначное соответствие. Эквивалентные множества. Мощность множеств.

  4. Счётные множества. Мощность континуума. Теоремы о счётных множествах.

  5. Доказать, что множество рациональных чисел счётно. Доказать, что множество действительных чисел несчётно.

  6. Отображение. Виды отображений. Подстановки.

  7. Теорема об отображениях. Правило равенства. Правило суммы. Правило произведения.

  8. n-местное отношение. Бинарное отношение. Способы задания бинарного отношения на конечном множестве. Виды бинарных отношений.

  9. Основные свойства матриц бинарных отношений.

  10. Отношения эквивалентности. Основное свойство классов эквивалентности. Ранг отношения. Класс вычетов.

  11. Отношения толерантности. Отношения частичного порядка. Линейный порядок.

  12. Соединение. Соединение с повторением. Соединение без повторения. Перестановка. Количество перестановок. Размещение. Количество размещений. Сочетания. Количество сочетаний. Основные свойства сочетаний.

  13. Метод включений и исключений. Формула включений-исключений. Задача о беспорядках.

  14. Формальный степенной ряд. Производящая функция. Равенство формальных степенных рядов. Сложение и вычитание формальных степенных рядов. Умножение и деление формальных степенных рядов.

  15. Рекуррентное соотношение. Возвратная последовательность. Характеристический многочлен. Общее решение рекуррентного соотношения. Теорема о рекуррентных соотношениях.

  16. Граф. Ориентированный граф. Неориентированный граф. Смежность и инцидентность. Способы задания графа. Матрицы графа. Степени вершины.

  17. Подграф. Часть графа. Виды графов. Изоморфизм графов. Теорема об изоморфизме графов.

  18. Маршруты в ориентированных и неориентированных графах. Связность. Достижимость.

  19. Дерево. Основные свойства деревьев. Ориентированное дерево. Бинарные деревья. Остов.

  20. Задача о построении кратчайшего остовного дерева. Алгоритм Прима. Проблема Штейнера.

  21. Задача о построении дерева кратчайших расстояний. Алгоритм Дейкстры.

  22. Задача о построении матрицы кратчайших расстояний. Алгоритм Флойда.

  23. Сеть. Поток в сети. Задача о максимальном потоке в сети. Разрез.

  24. Доказать теорему Форда – Фалкерсона.

  25. Остаточная пропускная способность. Остаточная сеть. Алгоритм Форда – Фалкерсона нахождения максимального потока.

  26. Геометрическая реализация графа. Теорема о реализации конечного графа в трёхмерном евклидовом пространстве.

  27. Планарный граф. Грань графа. Доказать формулу Эйлера для планарных графов.

  28. Доказать, что граф К5 не планарен. Доказать, что граф К33 не планарен.

  29. Независимое множество вершин графа. Вершинная раскраска. Правильная раскраска. Хроматическое число графа. Доказать теорему о 5 красках.

  30. Эйлеров путь. Эйлеров граф. Алгоритм построения эйлерова пути в эйлеровом графе. Критерий эйлеровости графов.

  31. Гамильтонов граф. Теорема Дирака.

  32. Задача коммивояжёра. Метод ветвей и границ.

  33. Бином Ньютона (теорема с доказательством).

  34. Доказательство свойств биномиальных коэффициентов. Треугольник Паскаля.

  35. Доказательство полиномиальной формулы.



^ 8. Учебно-методическое и информационное обеспечение дисциплины


  1. Андерсон Дж. Дискретная математика и комбинаторика. – М.: Изд-во

«Вильямс», 2004.–960 с.

2. Кузнецов О.П. Дискретная математика для инженера. – СПб.: Изд-во «Лань», 2004.– 400 с.

3. Плотников А.Д. Дискретная математика: учебное пособие. – М.: Изд-во «Новое знание», 2005.–288 с.

4. Судоплатов С.В., Овчинникова Е.В. Дискретная математика. – М.: Изд-во

«ИНФРА-М», 2005.–256 с.

5. Палий И.А. Дискретная математика. Курс лекций. – М.: Изд-во

«ЭКСМО», 2008.–352 с.

6. Корниенко А.В. Дискретная математика. Учебное пособие.– Томск: Изд-во ТПУ, 2000.– 96с.

7. Офицеров В.В. Дискретная математика. Учебное пособие.– Томск: Изд-во

ТПУ, 2005.– 105с.

8. Новиков Ф.А. Дискретная математика для программистов. – Спб.: Изд-во

«Питер», 2004. – 302 с.

^ 9. Рейтинг качества освоения дисциплины

Распределение учебного времени:

Лекции 27 часов

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

Самостоятельная работа студентов 72 часов

^ Основные положения по рейтинг-плану дисциплины

На дисциплину выделено 100 баллов и 6 кредитов, которые распределяются следующим образом:

-текущий контроль 90 баллов;

-итоговая аттестация (экзамен) 10 баллов.

Допуск к сдаче экзамена осуществляется при наличии более 60 баллов, обязательным является выполнение всех индивидуальных заданий и контрольных работ.


10. Материально-техническое обеспечение дисциплины


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


Программа составлена на основе Стандарта ООП ТПУ в соответствии с требованиями ФГОС по направлению и профилю подготовки 230700 «Прикладная информатика»


Программа одобрена на заседании кафедры ПМ

(протокол № _1_ от «__1_» __09__ 2011 г.).


Автор к.ф.-м. н., доцент каф. ПМ ________________ В.В. Офицеров




Нажми чтобы узнать.

Похожие:

Рабочая программа дисциплины дискретная математика iconФакультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Рабочая программа дисциплины дискретная математика iconФакультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Рабочая программа дисциплины дискретная математика iconРабочая программа дисциплины дискретная математика

Рабочая программа дисциплины дискретная математика iconНаправление: 010100. 62 «Математика» Подготовка
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Рабочая программа дисциплины дискретная математика iconРабочая программа дисциплины теория информационных процессов и систем
Пререквизиты: «Информатика», «Математика», «Математическая логика и теория алгоритмов», «Дискретная математика»
Рабочая программа дисциплины дискретная математика iconРабочая программа дисциплины дискретная математика
Профиль подготовки: Автоматизация технологических процессов и производств в нефтегазовой отрасли
Рабочая программа дисциплины дискретная математика iconФакультет математики
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Рабочая программа дисциплины дискретная математика iconРабочая программа дисциплины дискретная математика
В результате освоения данной дисциплины бакалавр приобретает знания, умения и навыки, обеспечивающие достижение целей Ц1, Ц3, Ц5...
Рабочая программа дисциплины дискретная математика iconПрограмма дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика»

Рабочая программа дисциплины дискретная математика iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 Социология подготовки бакалавра
Требования к студентам: Учебная дисциплина “Дискретная математика для социологов” (4-й и 5-й модули учебного плана 1-го курса факультета...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы