Дискретная математика (стр. 1 )

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

Филиал ФГБОУ ВПО

«Красноярский государственный педагогический университет

им. » в г. Канске

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

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ

Специальность: 050202.65 – Информатика

Канск

2011

УМКД составлен преподавателем филиала, к. ф.-м. н., доцентом

Обсужден на заседании Совета филиала

«_05»_сентября_2011 г.

Председатель Совета филиала

Протокол согласования рабочей программы дисциплины «Дискретная математика» с другими дисциплинами специальности 050202.65 ИНФОРМАТИКА

Наименование дисциплин, изучение которых опирается на данную дисциплину	Предложения об изменениях в пропорциях материала, порядка изложения и т. д.	Принятое решение (протокол №, дата) Совета филиала
Теория алгоритмов. Численные методы. Теоретические основы информатики. Теория вероятностей и математическая статистика. Исследование операций	-	01/11 от 01.01.2001

лист внесения изменений

Дополнения и изменения рабочей программы на 2012/2013 учебный год

В рабочую программу вносятся следующие изменения:

1. ____________________________________________________________

2. ____________________________________________________________

3. ____________________________________________________________

Внесенные изменения утверждаю:

Директор филиала КГПУ им.

"____"___________ 20__г.

СОДЕРЖАНИЕ

1. Пояснительная записка	6
2 Рабочая программа дисциплины	7
2.1.  Выдержка из стандарта	8
2.2.  Введение	9
2.3.  Содержание теоретического курса дисциплины	11
2.4.  Тематический план	12
2.5.  Учебно-методическая (технологическая) карта дисциплины	13
2.6.  Карта литературного обеспечения	15
2.7.  Технологическая карта рейтинга	17
3.  Методические рекомендации для студентов	19
4.  Банк тестовых заданий	23
5.  Тематика рефератов	36
6.  Вопросы для самостоятельной работы	37
7.  Вопросы к экзамену	38

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Учебно-методический комплекс дисциплины (УМКД) «Дискретная математика» для студентов очной формы обучения по специальности 050202.65 «Информатика» состоит из следующих элементов:

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

2.  Методических рекомендаций для студентов, которые содержат советы и разъяснения, позволяющие студенту оптимальным образом организовать процесс изучения дисциплины «Дискретная математика».

3.  Банка тестовых заданий для организации самостоятельной работы студентов и самоконтроля по дисциплине «Дискретная математика».

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

5.  Вопросы для самостоятельной работы студентов по дисциплине «Дискретная математика» для проверки знаний студентов.

6.  Вопросов к экзамену, который является итоговым контролем освоения студентом компетенции в области дискретной математики.

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

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

ВЫДЕРЖКА ИЗ СТАНДАРТА

Настоящая рабочая модульная программа дисциплины (далее программа) составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 050202.65 – Информатика, утвержденного заместителем Министра образования и науки Российской Федерации 31 января 2005 г., номер государственной регистрации № 000 пед/сп (новый)

ДПП. Ф.02

Дискретная математика Рекуррентные соотношения. Способы решения рекуррентных соотношений. Суммы и рекуррентности. Целочисленные функции x, x, mod. Бином Ньютона. Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Полиномиальная формула. Введение в асимптотические методы. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера. Основные комбинаторные конфигурации. Метод включения-исключения. Основные понятия теории графов. Связные графы. Изоморфизм графов. Эйлеровы и гамильтоновы графы. Деревья. Паросочетания, независимые множества и клики. Пленарные графы. Теорема Эйлера и ее следствия. Непланарность графов К5 и Кз, з. Раскраска вершин и ребер графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.

130

Введение

Место дисциплины в реализации основных задач ОПП:

дисциплина «Дискретная математика» относится к циклу дисциплин предметной подготовки. Она занимает одно из центральных мест в системе подготовки учителя по специальности 050202.65 – Информатика.

Место дисциплины в обеспечении образовательных интересов личности студента и в удовлетворении требований заказчиков выпускниками университета по данной ОПП:

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

Содержание дисциплины «Дискретная математика» глубоко интегрировано в структуру блока дисциплин предметной подготовки.

Изучение данной дисциплины базируется на следующих дисциплинах:

-  Математика.

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

-  Элементы абстрактной и компьютерной алгебры.

-  Информатика.

-  Программирование.

-  Программное обеспечение ЭВМ.

Материал данной дисциплины непосредственно используется для изучения следующих дисциплин:

-  Теория алгоритмов.

-  Численные методы.

-  Теоретические основы информатики.

-  Теория вероятностей и математическая статистика.

-  Исследование операций.

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

Задачи дисциплины:

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

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

-  знакомство с новейшими достижениями в дискретной математике.

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

СОДЕРЖАНИЕ ТЕОРЕТИЧЕСКОГО КУРСА ДИСЦИПЛИНЫ

МОДУЛЬ № 1. Основные методы дискретной математики

Введение. Различие между дискретной и непрерывной, математикой. Счет и перечисление (перебор) как основные методы дискретной математики. Эффект “комбинаторного взрыва”, примеры. Что такое дискретная математика?

1.  Конечные суммы и рекуррентные соотношения

Способы записи конечных сумм. Преобразования сумм. Кратные суммы. Некоторые методы суммирования. Понятие рекуррентного соотношения. Примеры задач, приводящих к рекуррентным соотношениям. Числа Фибоначчи, числа Каталана. Некоторые способы решения рекуррентных соотношений.

2.  Комбинаторные числа

Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Треугольник Паскаля. Бином Ньютона. Некоторые применения бинома Ньютона. Числа Стирлинга 1-го и 2-го рода. Полиномиальные коэффициенты. Полиномиальная теорема.

3.  Введение в асимптотические методы

Символы ~, о, О. Основные правила использования этих символов. Асимптотические решения рекуррентных соотношений. Формула Стирлинга (без доказательства).

МОДУЛЬ № 2. Основные понятия комбинаторики и теории графов

1.  Основные понятия комбинаторики

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

2.  Начала теории Рамсея

Принцип Дирихле. Теорема Рамсея (конечный случай). Числа Рамсея. Применения теоремы Рамсея (теорема Ван дер Вардена).

3.  Элементы теории графов

Понятие графа и мультиграфа; различные способы их представления. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. Подграф. Путь, цепь, простая цепь, цикл, простой цикл. Связные графы. Компоненты связности графа, их число. Изоморфные графы. Эйлеровы графы. Критерий эйлеровости. Гамильтоновы графы. Деревья. Характеризационная теорема. Планарные графы. Укладка графа. Теорема Жордана (без доказательства). Плоские графы. Не планарность графов и . Раскраска вершин графа. Хроматическое число графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Теорема о четырех красках (без доказательства).

.

ТЕМАТИЧЕСКИЙ ПЛАН

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

по специальности 050202.65 «Информатика»

№ п/п	Название модулей и тем	Количество часов
Всего	Из них аудиторные занятия:	Лекции	Практические	Лабораторные	Самостоятельная работа
I.	Основные методы дискретной математики	51	24	12	12	-	27
1	Конечные суммы и рекуррентные соотношения.	17	8	4	4	-	9
2	Комбинаторные числа.	17	8	4	4	-	9
3	Введение в асимптотические методы.	17	8	4	4	-	9
II.	Основные понятия комбинаторики и теории графов	79	52	26	26	-	27
1	Основные понятия комбинаторики.	29	20	10	10	-	9
2	Начала теории Рамсея.	21	12	6	6	-	9
3	Элементы теории графов.	29	20	10	10	-	9
	Итого:	130	76	38	38	-	54

учебно-методическая (ТЕХНОЛОГИЧЕСКАЯ) КАРТА дисциплины

_________ Дискретная математика_________

(наименование)

для студентов основной образовательной программы

специальности 050202.65 «Информатика»

(наименование, шифр)

по очной форме обучения

Модуль	Трудоемкость в часах	№№ раздела, темы	Лекционный курс	Занятия (номера)	Самостоятельная работа студентов	Формы контроля
Вопросы, изучаемые на лекции	Часы	Практические	Часы	Лабораторные	Часы	Содержание	Часы
1. Основные методы дискретной математики	17	Конечные суммы и рекуррентные соотношения.	Способы записи конечных сумм. Преобразования сумм. Кратные суммы. Некоторые методы суммирования. Понятие рекуррентного соотношения. Примеры задач, приводящих к рекуррентным соотношениям. Числа Фибоначчи, числа Каталана. Некоторые способы решения рекуррентных соотношений.	4	Конечные суммы и рекуррентные соотношения.	4	—	—	Конечные суммы и рекуррентные соотношения.	9	Доклады. Вопросы № 1-2. [Перечень вопросов и заданий для самостоятельной работы]. Реферат. Тема № 1-2 [Перечень примерных тематик рефератов]
17	Комбинаторные числа.	Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Треугольник Паскаля. Бином Ньютона. Некоторые применения бинома Ньютона. Числа Стирлинга 1-го и 2-го рода. Полиномиальные коэффициенты. Полиномиальная теорема.	4	Комбинаторные числа.	4	—	—	Комбинаторные числа.	9	Доклады. Вопросы № 3-4. [Перечень вопросов и заданий для самостоятельной работы]. Реферат. Тема № 3-4 [Перечень примерных тематик рефератов]
17	Введение в асимптотические методы.	Символы ~, о, О. Основные правила использования этих символов. Асимптотические решения рекуррентных соотношений. Формула Стирлинга (без доказательства).	4	Введение в асимптотические методы.	4	—	—	Введение в асимптотические методы.	9	Доклады. Вопросы № 5-6. [Перечень вопросов и заданий для самостоятельной работы]. Реферат. Тема № 5. [Перечень примерных тематик рефератов]
2. Основные понятия комбинаторики и теории графов	29	Основные понятия комбинаторики.	Выборки, размещения, перестановки, сочетания, разбиения; их пересчет. Комбинаторный смысл биномиальных коэффициентов. Комбинаторный смысл полиномиальных коэффициентов и чисел Стирлинга. Метод включения-исключения и его применения (оценки для числа элементов, не обладающих ни одним из свойств; формула для числа элементов, обладающих в точности р свойствами). Формулы обращения. Функция Мебиуса. Формула обращения Мебиуса.	10	Основные понятия комбинаторики.	10	—	—	Основные понятия комбинаторики.	9	Доклады. Вопросы № 7-8. [Перечень вопросов и заданий для самостоятельной работы]. Реферат. Тема № 6. [Перечень примерных тематик рефератов]
21	Начала теории Рамсея.	Принцип Дирихле. Теорема Рамсея (конечный случай). Числа Рамсея. Применения теоремы Рамсея (теорема Ван дер Вардена).	6	Начала теории Рамсея.	6	—	—	Начала теории Рамсея.	9	Доклады. Вопросы № 9-10. [Перечень вопросов и заданий для самостоятельной работы]. Реферат. Тема № 7-8. [Перечень примерных тематик рефератов]
29	Элементы теории графов.	Понятие графа и мультиграфа; различные способы их представления. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. Подграф. Путь, цепь, простая цепь, цикл, простой цикл. Связные графы. Компоненты связности графа, их число. Изоморфные графы. Эйлеровы графы. Критерий эйлеровости. Гамильтоновы графы. Деревья. Характеризационная теорема. Планарные графы. Укладка графа. Теорема Жордана (без доказательства). Плоские графы. Не планарность графов и .	10	Элементы теории графов.	10			Элементы теории графов.	9	Доклады. Вопросы № 11-14. [Перечень вопросов и заданий для самостоятельной работы]. Реферат. Тема № 9-10. [Перечень примерных тематик рефератов]
Всего	130			38	—	38	—	—		54

КАРТА литературного обеспечения дисциплины