страница 1
Ф 27-019
Учреждение образования
“Гродненский государственный университет имени Янки Купалы”
-
УТВЕРЖДАЮ
Декан факультета математики и информатики
___________________ ____________
_____________ _____ г.
Регистрационный № УД- _____/р.
|
Дискретная математика и
теория графов
Учебная программа для специальности:
(рабочий вариант)
1-31 03 01-05 Математика (информационные технологии)
Факультет математики и информатики
Кафедра алгебры, геометрии и методики преподавания математики
Курс 1, 2
Семестр 1, 2, 3
Лекции
|
102
|
|
Экзамен
|
3
|
|
(количество часов)
|
|
|
(семестр)
|
Практические (семинарские) занятия
|
102
|
|
Зачет
|
2, 3
|
|
(семестр)
|
|
(количество часов)
|
|
|
|
Лабораторные занятия
|
|
|
|
| | |
(количество часов)
|
|
|
| Всего аудиторных часов по дисциплине |
204
|
|
Форма получения высшего образования
|
дн
| | |
(количество часов)
|
|
|
|
Составила И.Б.Просвирнина, кандидат физико-математических наук, доцент
2010 г.
Рабочая программа составлена на основе учебной программы для специальности 1-40 01 01 Программное обеспечение информационных технологий, утверждённой_________________________________________________________________________________Рег. № ____________________________
Рассмотрена и рекомендована к утверждению в качестве рабочего варианта на заседании кафедры алгебры, геометрии и методики преподавания математики
26.06.2010 г., протокол №10
Заведующий кафедрой
____________________ А.А. Гринь
Одобрена и рекомендована к утверждению на заседании методической комиссии специальностей факультета математики и информатики
29.06.2010 г., протокол № 6
Председатель
_______________ __________________
Одобрена и рекомендована к утверждению на заседании Совета факультета математики и информатики
30.06.2010 г., протокол № 6
Учёный секретарь
_______________ __________________
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Курс «Дискретная математика и теория графов» (ДМ и ТГ) предназначен для студентов, обучающихся по специальности 1-40 01 01 – программное обеспечение информационных технологий.
Основной спецификой дискретной математики и теории графов является алгоритмическая основа и демонстрация использования дискретности в современной науке. ДМ и ТГ включает ряд разделов, которые стали развиваться наиболее интенсивно в середине прошлого столетия в связи с появлением ЭВМ. Этот курс является не только фундаментом математической кибернетики, но и важным звеном математического образования для специалистов в области прикладной математики и информатики.
В курсе ДМ и ТГ изучаются: комбинаторный анализ, булевы функции, конечные графы, элементы теории кодирования.Цель курса – изучение конструкций и алгоритмов дискретной математики и теории графов.
Задачи изучения курса:
– рассмотреть основные понятия и методы комбинаторного анализа;
– рассмотреть булевы функции, основные алгоритмы построения дизъюнктивных нормальных форм, результаты Поста о полноте;
– рассмотреть основные конструкции и базовые результаты теории графов;
– рассмотреть алфавитные и самокорректирующиеся коды и способы их построения.
Требования к уровню освоения дисциплины.
Студенты должны
знать:
– основные методы комбинаторики;
– булевы функции;
– основные понятия и базовые результаты теории графов;
– элементы теории кодирования;
уметь:
– решать основные задачи комбинаторики, булевых функций, теории графов и теории кодирования;
– применять методы дискретной математики и теории графов для математического моделирования и решения прикладных задач.
Требования к компетенциям
академическим:
– знание основных комбинаторных конструкций, биномиальной и полиномиальной теорем, метода включения и исключения, методов решения рекуррентных соотношений;
– знание основных понятий и конструкций, связанных с булевыми функциями, методов построения дизъюнктивной и конъюнктивной нормальных форм, теоремы Поста о функциональной полноте;
– знание базовых понятий и конструкций теории конечных графов;
– представление об алфавитных и самокорректирующихся кодах, знание элементарных примеров таких кодов.
социально-личностным:
– умение работать в команде при выполнении учебных и научных проектов;
– умение работать с учебной и научной литературой, проводить анализ прочитанного, резюмировать полученную информацию.
профессиональным:
– знание конструкций и алгоритмов дискретной математики и теории графов, изложенных в курсе «Дискретная математика и теория графов»;
– умение применять методы дискретной математики и теории графов к решению задач математического моделирования.
СОДЕРЖАНИЕ УЧЕБНОГО МАТЕРИАЛА
№
п/п
|
Наименование
раздела, темы дисциплины
|
Содержание в соответствии с
типовой учебной программой (учебной программой)
|
1
|
Комбинаторный анализ.
|
Перестановки и сочетания. Биномиальная и полиномиальная теоремы. Метод включения и исключения, его применение. Рекуррентные соотношения. Числа Фибоначчи. Производящие функции.
|
2.
|
Булевы функции.
|
Понятие булевой функции. Дизъюнктивная и конъюнктивная нормальные формы. Теорема Поста о функциональной полноте. Алгоритмы построения сокращенных и тупиковых дизъюнктивных нормальных форм.
|
3.
|
Графы.
|
Изоморфизм графов. Метрические инварианты графа. Двудольные графы. Теорема Кенига. Деревья, их эквивалентные определения. Остов графа. Матричная теорема Кирхгофа. Вершинная независимость. Оценки числа независимости. Вершинные и реберные покрытия. Паросочетания. Теорема Галлаи. Паросочетания в двудольных графах. Теорема Холла. Вершинная и реберная связность. Обходы графов. Эйлеровы циклы. Критерий эйлеровости. Гамильтоновы циклы. Достаточные условия гамильтоновости. Вершинная и реберная раскраски графов. Хроматическое число и хроматический индекс, их оценки. Матроиды. Представление матроидов. Жадный алгоритм.
|
4.
|
Элементы теории кодирования.
|
Понятие кодирования. Алфавитное кодирование. Самокорректирующиеся коды.
|
УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА
Номер раздела, темы,
занятия
|
Название раздела,темы, занятия;
перечень изучаемых вопросов
|
Количество аудиторных часов
|
Материальное обеспечение занятия (наглядные, методические пособия и др.)
|
Литература
|
Формы контроля знаний
|
лекции
|
практические (семинарские) занятия
|
лабораторные занятия
|
управляемая самостоятельная работа студентов
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
1
|
Раздел 1. Комбинаторный анализ.
|
22
|
20
|
|
2
|
|
[1] - [5]
|
|
2
|
Раздел 2. Булевы функции.
|
20
|
18
|
|
2
|
|
[1] - [5]
|
|
3
|
Раздел 3. Графы.
|
38
|
36
|
|
2
|
|
[1] - [5]
|
|
4
|
Раздел 4. Элементы теории кодирования.
|
22
|
18
|
|
2
| |
[1] - [5]
|
Контроль-ная работа
|
ИНФОРМАЦИОННО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
№
п/п
| Перечень |
|
Основная литература
|
1
|
Яблонский С.В. Введение в дискретную математику. – М.: Наука. – 1979, 272 с.
|
2
|
Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.
|
3
|
Мощенский А.В., Мощенский В.А. Курс математической логики. Мн.: БГУ, 1999. – 129 с.
|
4
|
Мощенский А.В., Мощенский В.А. Математические основы информатики. Мн.: БГУ, 2002. – 149 с.
|
5
|
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 382 с.
|
|
Дополнительная литература
|
6
|
Андерсон Дж.А. Дискретная математика и комбинаторика. – М.: Издательский дом «Вильямс», 2004. – 960 с.
|
7
|
Липский В. Комбинаторика для программистов. – М.: Мир, 1988. – 213 с.
|
8
|
Новиков Ф.А. Дискретная математика для программистов. – М.: Техносфера, 2005. – 399 с.
|
9
|
Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 380 с.
|
10
|
Оре О. Основы теории графов. – М.: Наука, 1980. – 336 с.
|
11
|
Хаггарти Р. Дискретная математика для программистов. – М.: Техносфера, 2005. – 399 с.
|
12
|
Берж К. Теория графов и ее применение. – М., Изд. иностр. лит., 1962. – 340 с.
|
13
|
Кристофидес Н. Теория графов: алгоритмический подход – М.: Мир, 1978. – 432.
|
14
|
Уилсон Р.Дж. Введение в теорию графов. – М.: Мир, 1977. – 207 с.
|
15
|
Фляйшнер Г. Эйлеровы графы и смежные вопросы. – М.: Мир, 2002. – 331 с.
|
16
|
Плотников А.Д. Дискретная математика. – М.: Новое знание, 2005. – 288 с.
|
ПРОТОКОЛ СОГЛАСОВАНИЯ УЧЕБНОЙ ПРОГРАММЫ
ПО ИЗУЧАЕМОЙ УЧЕБНОЙ ДИСЦИПЛИНЕ
С ДРУГИМИ ДИСЦИПЛИНАМИ СПЕЦИАЛЬНОСТИ
Название дисциплины, с которой требуется согласование
|
Название кафедры
|
Предложения об изменениях в содержании учебной программы по изучаемой учебной дисциплине
|
Решение, принятое кафедрой, разработавшей учебную программу
(с указанием даты и номера протокола)
|
|
|
|
|
|
|
|
|
6. ДОПОЛНЕНИЯ И ИЗМЕНЕНИЯ К УЧЕБНОЙ ПРОГРАММЕ
ПО ИЗУЧАЕМОЙ УЧЕБНОЙ ДИСЦИПЛИНЕ
на ____ / _____ учебный год
№
п/п
|
Дополнения и изменения
|
Основание
|
|
|
|
|
|
|
Учебная программа пересмотрена и одобрена на заседании кафедры
(протокол № __ от _______ 200__ г.)
Заведующий кафедрой __________________________ ______________ _______________________
(степень, звание) (И.О.Фамилия)
страница 1
|