Рабочая программа дисциплины (модуля) Дискретная математика
| Вид материала | Рабочая программа |
- Рабочая программа учебной дисциплины «Дискретная математика» Направление подготовки, 139.29kb.
- Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для, 135.29kb.
- Рабочая программа учебной дисциплины ен. Ф. 01. 03 Дискретная математика для специальности, 184.39kb.
- Рабочая программа дисциплины Дискретная математика (Наименование дисциплины), 129.54kb.
- Рабочая программа Наименование дисциплины дискретная математика по направлению подготовки, 201.9kb.
- Рабочая программа дисциплины «Дискретная математика» Направление подготовки, 125.26kb.
- Рабочая программа дисциплины (модуля) нечеткая математика и принятие решений, 131.73kb.
- Рабочая программа дисциплины «дискретная математика» Рекомендуется для направления, 220.81kb.
- Учебная программа для специальности: (рабочий вариант) 1-310301-02 Математика (научно-педагогическая, 120.64kb.
- Рабочая учебная программа дисциплины (модуля) Математика. Часть, 210.81kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Томский государственный университет
УТВЕРЖДАЮ
Зав кафедрой программной инженерии
д.ф.-м..н., профессор
О. А. Змеев
"_____"__________________2011 г.
Рабочая программа дисциплины (модуля)
Дискретная математика
Направление подготовки
010300 Фундаментальная информатика и информационные технологии
Квалификация (степень) выпускника
Бакалавр
Форма обучения
Очная
Томск
2010
1. Цели освоения дисциплины
Целями освоения дисциплины (модуля) «Дискретная математика» являются получение теоретических знаний по основам дискретной математики.
2. Место дисциплины в структуре ООП бакалавриата
Раздел образовательной программы: Б.3. Профессиональный цикл. Базовая часть.
Для изучения курса необходимо знание математики в объёме общеобразовательной средней школы.
Знания и умения, полученные в ходе освоения данной дисциплины (модуля), понадобятся при изучении таких последующих дисциплин ООП, как:
- математическая логика и теория алгоритмов;
- теория графов;
- алгоритмы и анализ сложности;
- основы программирования;
- базы данных;
- методы оптимизации и исследование операций;
- интеллектуальные системы;
- компьютерные сети;
- теория автоматов и формальных языков;
- теория систем и системный анализ.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля) «Дискретная математика»
Курс «Дискретная математика» способствует выработке у студента следующих компетенций:
- способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК-4);
- способность профессионально владеть базовыми математическими знаниями (ПК-8);
- понимание концепций и абстракций, способность использовать на практике методы дискретной математики (ПК-15).
В результате освоения дисциплины обучающийся должен:
- знать основные понятия и методы дискретной математики;
- уметь применять на практике методы дискретной математики.
Успешно освоившим дисциплину считается студент, обладающий знанием основных понятий дискретной математики и умеющий применять на практике методы решения задач дискретной математики.
4. Структура и содержание дисциплины (модуля) «Дискретная математика»
Общая трудоемкость дисциплины составляет 5 зачетных единиц, 180 часов.
| № п/п | Раздел Дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | ||
| | | | | лекции | сем | самостоятельная работа | |
| 1 | Введение в теорию множеств.. | 1 | 1-2 | 8 | 4 | 10 | |
| 2 | Булевы алгебры | 1 | 3-4 | 8 | 4 | 10 | |
| 3 | Промежуточная аттестация | 1 | 5 | | | | Тест |
| 4 | Элементы комбинаторики | 1 | 6-9 | 8 | 4 | 20 | |
| 5 | Промежуточная аттестация | 1 | 10 | | | | Тест |
| 6 | Бинарные отношения | 1 | 11-14 | 12 | 10 | 20 | |
| 7 | Промежуточная аттестация | 1 | 15 | | | | Тест |
| 8 | Булевы функции | 1 | 16-19 | 12 | 10 | 20 | |
| 9 | Промежуточная аттестация | 1 | 20-21 | | | 20 | Тест Экзамен |
| ИТОГО | | | | 48 | 32 | 100 | |
Лекционный курс
Тема 1. Введение в теорию множеств.
Понятие множества. Операции над множествами. Алгебра множеств.
Тема 2. Булевы алгебры.
Аксиомы булевой алгебры. Принцип двойственности. Булева алгебра и алгебра множеств.
Теоремы булевой алгебры и теоремы алгебры множеств.
Тема 3. Элементы комбинаторики.
Декартово произведение множеств. Кортежи, размещения, сочетания, перестановки. Основные правила комбинаторики. Введение в дискретную теорию вероятностей.
Тема 4. Бинарные отношения.
Определение отношения. Представления отношений. Операции над отношениями. Алгебраические свойства операций над отношениями. Свойства бинарных отношений – рефлексивность, симметричность, транзитивность. Транзитивное замыкание. Алгоритмы нахождения транзитивного замыкания. Отношения эквивалентности, толерантности, порядка и их свойства. Задача о наименьшем покрытии. Алгоритмы решения задачи о наименьшем покрытии. Анализ бинарных отношений. Отображения и функции.
Тема 5. Булевы функции.
Булевы функции. Способы задания булевых функций. Элементарные булевы функции. Фиктивные и существенные переменные. Представление булевой функции формулой. Равносильность формул. Двойственная функция и двойственная формула. Разложение булевой функции по переменным (разложение Шеннона). Совершенные нормальные формы. Минимизация булевых функций. Алгоритм Квайна, алгоритм Блейка-Порецкого. Нахождение минимальных и кратчайших покрытий. Полиномы Жегалкина. Классы линейных, самодвойственных, монотонных булевых функций. Теорема Поста о полноте системы булевых функций. Примеры функционально полных базисов.
.
Семинары.
- Понятие множества. Операции над множествами.
- Алгебра множеств.
3.Аксиомы булевой алгебры. Принцип двойственности.
4. Теоремы булевой алгебры и теоремы алгебры множеств.
5. Декартово произведение множеств. Кортежи, размещения, сочетания, перестановки.
- Правило произведения. Нахождение числа кортежей, размещений, перестановок с помощью правила произведения.
- Определение отношения. Представления отношений. Операции над отношениями. Алгебраические свойства операций над отношениями
- Свойства бинарных отношений – рефлексивность, симметричность, транзитивность. Транзитивное замыкание. Алгоритмы нахождения транзитивного замыкания.
- Отношения эквивалентности, толерантности. Нахождение классов эквивалентности, классов толерантности.
- Отношения порядка. Древесный порядок, редукция древесного порядка.
- Булевы функции. Способы задания булевых функций. Элементарные булевы функции. Фиктивные и существенные переменные.
- Представление булевой функции формулой. Равносильность формул. Двойственная функция и двойственная формула.
- Разложение булевой функции по переменным (разложение Шеннона). Совершенные нормальные формы.
- Минимизация булевых функций. Алгоритм Квайна, алгоритм Блейка-Порецкого. Нахождение минимальных и кратчайших покрытий.
15. Полиномы Жегалкина. Классы линейных, самодвойственных, монотонных булевых функций. Теорема Поста о полноте системы булевых функций. Примеры функционально полных базисов.
5. Образовательные технологии.
В ходе преподавания дисциплины используются следующие образовательные технологии:
- лекционный курс;
- семинарские занятия с решением задач по конкретным темам.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
Самостоятельная работа студентов по дисциплине организуется в следующих формах:
- самостоятельное изучение основного теоретического материала, ознакомление с дополнительной литературой, Интернет-ресурсами;
В качестве учебно-методического обеспечения самостоятельной работы используется основная и дополнительная литература по предмету, Интернет-ресурсы, материал лекций, указания, выданные преподавателем при проведении семинарских занятий.
Текущий контроль успеваемости проводится по результатам ежемесячных контрольных работ по текущим темам.
7. Учебно-методическое и информационное обеспечение дисциплины (модуля) «Дискретная математика».
а) основная литература:
- Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000.
- Быкова С.В., Буркатовская Ю.Б. Булевы функции: Учебное пособие. – Томск, ТГУ, 2008.
- Шрейдер Ю.А. Равенство, сходство, порядок. – Наука, 1971.
- Кристофидес Н. Теория графов. Алгоритмический подход. – М., Мир, 1978.
б) дополнительная литература:
- Липский В. Комбинаторика для программистов. – М., Мир, 1977.
- Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М., Наука, 1984.
- Свами М., Тхуласириман К. Графы, сети и алгоритмы. – М., Мир, 1984.
8. Материально-техническое обеспечение дисциплины (модуля)
Требуется обеспечение литературой, которую в достаточном объеме может предложить книжный фонд Научной библиотеки Томского госуниверситета и факультета информатики.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ООП ВПО по направлению подготовки 010300 Фундаментальная информатика и информационные технологии.
Автор: ст. преподаватель В.В. Матушевский
Рецензент: д.ф.-м.н., профессор О. А. Змеев.
Программа одобрена на заседании кафедры программной инженерии
от ___________ года, протокол № ________.