close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Саратовский государственный университет имени Н.Г. Чернышевского
Факультет компьютерных наук и информационных технологий
УТВЕРЖДАЮ
___________________________
"__" __________________20__ г.
Рабочая программа дисциплины
Методы комбинаторики
Направление подготовки
231000 Программная инженерия
Профиль подготовки
Разработка программно-информационных систем
Квалификация (степень) выпускника
Бакалавр
Форма обучения
очная
Саратов,
2011 год
1. Цели освоения дисциплины «Методы комбинаторики»
Целями освоения данной дисциплины являются формирование общих
представлений о базовых понятиях и теоретических методах комбинаторики,
о современных исследованиях в этой области, а также формирование у
студентов компетенций в области применения методов, основанных на
представлении информации в дискретном виде для решения прикладных
задач.
2. Место дисциплины «Методы комбинаторики» в структуре ООП
бакалавриата «Программная инженерия»
Дисциплина
«Методы
комбинаторики»
входит
в
раздел
«Математический и естественнонаучный цикл. Дисциплина по выбору»
ФГОС-3 ООП направления подготовки «Программная инженерия». Для
успешного усвоения данной дисциплины необходимы компетенции,
сформированные у обучающихся в результате изучения следующих
дисциплин «Теоретическая информатика» и «Дискретная математика».
Сформированные в процессе изучения дисциплины «Методы
комбинаторики» компетенции, необходимы студенту при освоении таких
дисциплин профессионального цикла,
как «Математические основы
искусственного интеллекта», «Теория кодирования и передачи данных».
3. Компетенции обучающегося, формируемые в результате освоения
дисциплины «Методы комбинаторики».
В результате освоения дисциплины «Методы комбинаторики» студент
должен обладать следующими профессиональными компетенциями:

способность оценивать временную и емкостную сложность программного
обеспечения (ПК-13).
В результате освоения дисциплины «Методы комбинаторики»
обучающийся должен:
 Знать:
 основные дискретные структуры: множества, отношения, графы,
комбинаторные структуры;
 методы перечисления для основных дискретных структур;
 основные
методы
и
алгоритмы
теории
отношений,
комбинаторики, связанные с моделированием и оптимизацией
систем различной природы.
 Уметь:
 оценивать временную и емкостную сложность программного
обеспечения
 употреблять специальную математическую символику для
выражения количественных и качественных отношений между
объектами;
 выполнять операции над множествами, применять аппарат теории
множеств для решения задач, исследовать бинарные отношения
на заданные свойства;
 применять аппарат производящих функций и рекуррентных
соотношений для решения перечислительных задач;
 Владеть:
 навыками применения языка и средств методов комбинаторики;
 навыками анализа и синтеза задач, основанных на
представлениях информации;
 навыками решения комбинаторных и теоретико-графовых задач.
4. Структура и содержание дисциплины «Методы комбинаторики»
Общая трудоемкость дисциплины составляет 5 зачетных единицы 180
часов (из них 90 часов аудиторных).
№
п/п
Раздел дисциплины
С Неде
е
ля
м семес
ес тра
т
р
Виды учебной работы,
включая
самостоятельную
работу студентов и
трудоемкость (в часах)
1
Представление
данных
5
1-2
Лек. Лаб
6
ПР
4
С
6
2
Последовательности
5
3-4
6
4
6
3
Разбиения.
Множества
5
5-6
6
4
6
4
Рекуррентные
соотношения
5
7-8
6
4
6
Формы
текущего
контроля
успеваемости
(по неделям
семестра)
Формы
промежуточной
аттестации (по
семестрам)
Участие
в
практических
занятиях -1-2 нед.
Контрольная
работа №1 – 7
нед.
Участие
в
практических
занятиях - 3-4
нед.
Контрольная
работа №1– 7
нед.
Участие
в
практических
занятиях - 5-6
нед.
Контрольная
работа №1– 7
нед.
Участие
в
практических
занятиях - 7-8
нед.
Контрольная
5
Комбинаторика
ряды
6
Алгоритмы поиска
7
8
и 5
9-10
6
4
6
5
11-14
12
8
12
Потоки в сетях
5
15-16
6
4
6
Комбинаторные
алгоритмы.
Матроиды.
5
17-18
6
4
6
ИТОГО
5
Промежуточная аттестация
54
36
54
работа №1 – 7
нед.
Участие
в
практических
занятиях - 9-10
нед.
Контрольная
работа №2 – 17
нед.
Участие
в
практических
занятиях - 11-14
нед.
Контрольная
работа №2 – 17
нед.
Участие
в
практических
занятиях - 15-16
нед.
Контрольная
работа №2 – 17
нед.
Участие
в
практических
занятиях - 17-18
нед.
Контрольная
работа №2 – 17
нед.
Экзамен
36
1.
Представление данных
Проблема представления. Коды, сохраняющие разности. Классы
алгоритмов. Анализ алгоритмов. Целые. Последовательности. Различные
способы представлений конечных последовательностей.
Самостоятельная работа – подробное изучение и сравнение различных
способов представления конечных последовательностей; подготовка к
контрольной работе.
2.
Последовательности
Связанное распределение. Разновидности связанных списков. Стеки и
очередь. Деревья. Представления. Прохождение. Длина путей. Графы.
Связность и расстояние. Изоморфизм. Планарность.
Самостоятельная работа – подробное изучение свойств деревьев;
подготовка к контрольной работе.
3.
Разбиения. Множества
Статистики. Размещения. Перестановки: разложения на циклы, знак
перестановки. Генерирование перестановок. Число сочетаний. Разбиение
чисел. Комбинаторные задачи теории информации. Множества.
Подмножество, множества с повторениями Разбиения множества. Числа
Стирлинга первого и второго рода. Формула включений и исключений.
Решето Эратосфена.
Самостоятельная работа – подробное изучение перестановок и
сочетаний; подготовка к контрольной работе.
4.
Рекуррентные соотношения
Размещения без повторений. Перестановки. Сочетания. Рекуррентные
соотношения.
Процесс
последовательных
разбиений.
Линейные
рекуррентные соотношения с постоянными коэффициентами. Случай равных
корней характеристического уравнения. Производящие функции.
Самостоятельная работа – подробное изучение свойств рекуррентных
соотношений; подготовка к контрольной работе.
Контрольная работа.
5.
Комбинаторика и ряды
Деление многочленов. Алгебраические дроби и степенные ряды.
Действия над степенными рядами. Применение степенных рядов для
доказательства тождеств. Производящие функции. Бином Ньютона. Ряд
Ньютона. Производящие функции и рекуррентные соотношения. О едином
нелинейном рекуррентном соотношении.
Самостоятельная работа – подробное изучение свойств и операций над
степенными рядами; подготовка к контрольной работе.
6.
Алгоритмы поиска
Поиск и другие операции над таблицами. Последовательный поиск.
Логарифмический поиск в статических таблицах. Бинарный поиск.
Оптимальные деревья бинарного поиска. Логарифмический поиск в
динамических таблицах. Сбалансированные сильно ветвящиеся деревья.
Поиск в глубину. Алгоритм Дейкстры нахождения кратчайшего пути.
Алгоритм Флойда нахождения кратчайших путей между парами вершин.
Самостоятельная работа – подробное изучение алгоритмов поиска;
подготовка к контрольной работе.
7.
Потоки в сетях
Транспортные сети. Потоки в сетях. Алгоритмы Форда-Фалкерсона
нахождения потока максимальной величины. Наибольшие паросочетания в
двудольных графах. Системы различных представлений. Разложение на цепи.
Самостоятельная работа – подробное изучение алгоритмов нахождения
потока максимальной величины; подготовка к контрольной работе.
8.
Комбинаторные алгоритмы. Матроиды
Автоматическое построение лабиринтов. Бинарное дерево. Задача о
восьми ферзях. Задача о назначениях (задачи выбора). Ханойская башня.
Жадные алгоритмы решения оптимизационных задач. Основные свойства
матроидов. Теорема Радо-Эдмонса. Матричные матроиды. Графовые
матроиды. Матроиды трансверсалей.
Самостоятельная работа – подробное изучение свойств матроидов;
подготовка к контрольной работе; подготовка к экзамену.
Контрольная работа.
5. Образовательные технологии
В учебном процессе при реализации компетентностного подхода
используются такие активные и интерактивные формы проведения занятий
как модельный метод обучения, метод развивающей кооперации, разбор
конкретных ситуаций, командное выполнение заданий с распределением
ролей. Широко используются мультимедийные презентации при
представлении лекционного материала.
6. Учебно-методическое обеспечение самостоятельной работы студентов.
Оценочные
средства
для
текущего
контроля
успеваемости,
промежуточной аттестации по итогам освоения дисциплины «Методы
комбинаторики».
7. Учебно-методическое и информационное обеспечение дисциплины
«Методы комбинаторики»
а) основная литература:
1. Златопольский Д. М. Программирование: типовые задачи, алгоритмы,
методы — М.: БИНОМ. Лаб. знаний, 2007.
2. Окулов С. М. Дискретная математика. Теория и практика решения задач
по информатике: учеб. пособие. —М.: БИНОМ. Лаб. знаний, 2008.
3. Ахо А. В., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и
алгоритмы (Data Structures and Algorithms).— Киев: Вильямс, 2007.
б) дополнительная литература:
1. Сачков В. Н. Введение в комбинаторные методы дискретной
математики: учеб. пособ. для студентов вузов. — М.: Наука: Гл. ред.
физ.-мат. лит., 1982.с.
2. Мальцев Ю. Н., Петров Е. П. Элементы дискретной математики.
Элементы комбинаторики, теории графов, теории кодирования и
криптографии: учеб. пособие. — Барнаул: Изд-во Алт. гос. ун-та, 2004.
в) программное обеспечение и Интернет-ресурсы
1. Костюкова Н. И. Комбинаторные алгоритмы для программистов
http://www.intuit.ru/department/algorithms/algocombi/
8. Материально-техническое обеспечение дисциплины «Методы
комбинаторики»
Лекционная аудитория с возможностью демонстрации электронных
презентаций при уровне освещения, достаточном для работы с конспектом.
Программа составлена в соответствии с требованиями ФГОС ВПО с
учетом рекомендаций и Примерной ООП ВПО по направлению и профилю
подготовки «Разработка программно-информационных систем».
Автор
доцент
каф. МКиКН
___________ А. С. Иванова
Программа одобрена на заседании кафедры математической
кибернетики и компьютерных наук от года 22.02.2011, протокол № 13.
Заведующий кафедрой
математической кибернетики и
компьютерных наук
___________ А. С. Иванов
Декан факультета КНиИТ,
доцент
___________ А. Г. Федорова
1/--страниц
Пожаловаться на содержимое документа