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

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



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

УТВЕРЖДАЮ

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

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


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

«___»_____________2011 г.


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

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


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

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







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

Бакалавр







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

2011г.













КУРС

2

СЕМЕСТР

4







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

3







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

Б2.Б1.1, Б2.Б1.2

КОРЕКВИЗИТЫ










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

Лекции

27

час.

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




час.

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

27

час.

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

54

час.

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

54

час.

ИТОГО

108

час.







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

Очная







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

зачет







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

кафедра ПМ










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




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










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




Д.Ю. Степанов










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




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




2011 г.

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

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

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

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

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

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

Поставленные цели полностью соответствуют целям ООП.

2. Место дисциплины в структуре ООП

Дисциплина «Дискретная математика» (Б3.Б2.5) относится к базовой части профессионального цикла дисциплин ООП.

Пререквизитами данной дисциплины являются дисциплины математического и естественнонаучного цикла (Б2): «Математический анализ» (Б2.Б1.1), «Геометрия и алгебра» (Б2.Б1.2).

Для изучения дисциплины «Дискретная математика» студент должен:

Знать:

  • основы математического анализа, алгебры и геометрии;

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

Уметь:

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

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

  • проводить сравнительный анализ параметров.

Владеть:

  • элементами математического анализа;

  • основами алгоритмизации.

^ 3. Результаты освоения дисциплины

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

Соответствие результатов освоения дисциплины «Дискретная математика» формируемым компетенциям ООП представлено в таблице


^ Результат обучения

Код

Знания

Код

Умения

Код

Владения

Р6

З.6.1

Теоретические основы теории множеств; математической логики, теории графов

У.6.1

Выполнять операции над множествами, применять аппарат теории множеств для решения задач, исследовать бинарные отношения на заданные свойства

В.6.1

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


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

Знать:

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

  • отображения и функции, виды отображений, основные операции над отображениями;

  • основные понятия комбинаторики, методы решения комбинаторных задач;

  • основные комбинаторные конфигурации, метод включения-исключения;

  • основные понятия теории графов, связные графы, изоморфизм графов;

  • методы решения экстремальных задач на графах, алгоритмы раскраски вершин и ребер графа.

Уметь:

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

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

  • строить нормальные формы и определять функциональную полноту систем функций алгебры логики;

  • решать оптимизационные задачи на графах.

Владеть:

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

  • навыками применения языка и средств дискретной математики.



^ 4. Структура и содержание дисциплины

4.1. Содержание разделов дисциплины:

Тема № 1. Теория множеств

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

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

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

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

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


^ 4.2. Структура дисциплины по разделам, формам организации и контроля обучения

Таблица 1.

Название раздела/темы

Аудиторная работа (час)

СРС

(час)

Итого

Форма текущего контроля

Лекции

Практ./сем.

занятия

Лаб. зан.

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

5

 5




10

 20

Уст. отчет

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

12

 12




24

48

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

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

10

 10




20

40

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

Итого

27

27




54

108

зачет



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

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

Таблица 2.



Формируемые компетенции

Разделы дисциплины

1

2

3

1

3.6.1

х

х

х

2

У.6.1

х

х




3

В.6.1

х

х

х


^ 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. Кузнецов О.П. Дискретная математика для инженера. – СПб.: Изд-во

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

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

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



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

Банк данных теоретических вопросов


  1. Множества. Операции над множествами.

  2. Свойства операций над множествами.

  3. Системы множеств. Булеан и разбиение множеств.

  4. Декартово произведение множеств.

  5. Бинарные отношения и их свойства.

  6. Отображение множеств. Эквивалентные множества.

  7. Комбинаторика: перестановки, размещения, сочетания.

  8. Логические переменные и функции.

  9. Логические функции одной и двух переменных.

  10. Основные логические операции.

  11. Булевы операции и булева алгебра.

  12. Свойства булевых операций.

  13. Виды булевых нормальных форм: ДНФ и КНФ.

  14. Понятие СДНФ и СКНФ. Их связь с таблицей истинности.

  15. Способы минимизации булевых функций.

  16. Базис и алгебра Жегалкина.

  17. Представление функций полиномами Жегалкина.

  18. Полные системы логических функций.

  19. Понятие графа. Способы задания графов.

  20. Операции над графами.

  21. Задача обхода графов.

  22. Понятие эйлерова и гамильтонова циклов.

  23. Понятия маршрута, цепи и циклов в графе.

  24. Количественные характеристики графа: ранг и цикломатическое число.

  25. Базисные циклы и разрезы в графе.

  26. Нахождение кратчайших маршрутов в графе.

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

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

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

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

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

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

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


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


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

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

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

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

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

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

5. Палий И.А. Дискретная математика. Курс лекций. – М.: Изд-во «ЭКСМО», 2008.–352 с.

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

ТПУ, 2005.– 105с.

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

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


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

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

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

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

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

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

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

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

-итоговая аттестация (зачет) 10 баллов.

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


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


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

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


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

(протокол № ____ от «___» _______ 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
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы