календарный рейтинг-план дисциплины
ОЦЕНКИ | КАЛЕНДАРНЫЙ РЕЙТИНГ-План по дисциплине | Лекции | 16 час. | ||
«Отлично» | А+ | 96– 100 баллов | «Профессиональная подготовка на английском языке» , модуль «Теория графов» | Практ. занятия | 16 час. |
А | 90– 95 баллов | для студентов, обучающихся по направлению 09.04.02 Информационные системы и технологии | Лаб. занятия | ||
«Хорошо» | В+ | 80 – 89баллов | Всего ауд. работа | 32 час. | |
В | 70– 79 баллов | СРС | 76 час. | ||
«Удовл.» | С+ | 65– 69 баллов | ИТОГО | 108 час. | |
С | 55– 64 баллов | Второй семестр (весенний) 2014/2015 учебного года | Итог. контроль | зачет | |
Зачтено | D | больше или равно 55 баллов | Лектор: доцент каф. ВТ . | ||
Неудовлетворительно / незачет | F | менее 55 баллов |
Оценивающие мероприятия | Кол-во | Баллы |
Практические задания | 6 | 60 |
Лабораторные работы | ||
Зачет | 1 | 40 |
Итого | 100 |
Неделя | Дата начала недели | Результат обучения по дисциплине | Вид учебной деятельности по разделам | Кол-во часов | Оценивающие мероприятия | Кол-во баллов | Технология проведения занятия (ДОТ)* | Информационное обеспечение | ||||||||||
Ауд. | Сам. | Практические задания | Выступление | ИДЗ | Рубежный контроль | … | Учебная Литература | Интернет-ресурсы | Видео-ресурсы | |||||||||
1-4 | Раздел 1. Задачи размещения | |||||||||||||||||
1 | 09.02 | Лекция 1. Расстояния в графе: вершина-вершина, вершина ребро, точка-вершина, точка-ребро. Центры и медианы графа, главные и абсолютные центры и медианы, методы их поиска. | 2 | 2 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||||
2 | 16.02 | Практическое занятие 1. Поиск центров и медиан. Решение задач. Решение контрольного задания. | 2 | 4 | 5 | 5 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||
3 | 23.02 | Лекция 2. Обобщение задач размещения: задачи с усилениями, поиск кратных центров и медиан. | 2 | 2 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||||
4 | 02.03 | Практическое занятие 2. Поиск центров и медиан. Поиск кратных центров и медиан. Решение задач. Решение контрольного задания. | 2 | 4 | 5 | 5 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||
5-8 | Раздел 2. Сети | |||||||||||||||||
5 | 09.03 | Лекция 3. Определение сети. Потоки в сетях, алгоритм построения потока. Теорема Форда–Фолкерсона и алгоритм построения максимального потока. | 2 | 2 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||||
6 | 16.03 | Практическое занятие 3. Поиск максимального потока: алгоритмы Форда-Фалкерсона и Эдмонда-Карпа. Решение задач. Решение контрольного задания. | 2 | 4 | 5 | 5 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||
7 | 23.03 | Лекция 4. Построение потока минимальной стоимости. | 2 | 2 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||||
8 | 30.03 | Практическое занятие 4. Поиск потока минимальной стоимости: алгоритм Форда-Фалкерсона, алгоритмы, основанные на выделении циклов отрицательного веса и на поиске минимального пути. Решение задач. Решение контрольного задания. | 2 | 4 | 5 | 5 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||
9 | Конференц-неделя | |||||||||||||||||
9 | 06.04 | Практическое занятие 5. Конференц-неделя. Выступление с обзорными докладами по статьям по темам предыдущих занятий | 14 | 10 | 10 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | |||||||||||
Всего по контрольной точке (аттестации) 1 | 16 | 38 | 20 | 10 | 30 | |||||||||||||
10-13 | Раздел 3. Паросочетания и покрытия | |||||||||||||||||
10 | 13.04 | Лекция 5. Независимые и покрывающие множества. Теорема о числах независимости и покрытий. Максимальные независимые множества вершин. Кратчайшее вершинное покрытие. Доминирующие множества. Паросочетание. | 2 | 2 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||||
11 | 20.04 | Практическое занятие 6. Поиск максимальных независимых множеств. Поиск кратчайшего вершинного покрытия. Решения задач. Решение контрольного задания. | 2 | 4 | 5 | 5 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||
12 | 27.04 | Лекция 6. Определение двудольного графа. Совершенное паросочетание. Задача о свадьбах, теорема Холла. Задача о назначениях и алгоритм ее решения. Транспортная задача и алгоритм ее решения. | 2 | 2 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||||
13 | 04.05 | Практическое занятие 7. Поиск паросочетания максимальной мощности. Поиск паросочетания максимального веса. Решения задач. Решение контрольного задания. | 2 | 4 | 5 | 5 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||
14-17 | Раздел 4. Эйлеровы и гамильтоновы графы. | |||||||||||||||||
14 | 11.05 | Лекция 7. Определение эйлерова и полуэйлерова графов. Лемма о цикле, необходимое и достаточное условие эйлеровости графа. Алгоритм Флери поиска эйлерова цикла. Необходимое и достаточное условие эйлеровости орграфа. Задача почтальона для неориентированного, ориентированного и смешанного графа. | 2 | 2 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||||
15 | 18.05 | Практическое занятие 8. Задача почтальона для неориентированного, ориентированного и смешанного графа. Решение задач. Решение контрольного задания. | 2 | 4 | 5 | 5 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||
16 | 25.05 | Лекция 8.. Определение гамильтонова и полугамильтонова графов, теорема Дирака. Задача коммивояжера. | 2 | 2 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||||
17 | 01.06 | Практическое занятие 9. Метод ветвей и границ для решения задачи коммивояжера. Некоторые эвристические алгоритмы: ближайшего соседа, ближайшей вставки, локальной оптимизации, Эйлера, Кристофидеса. Решение задач. Решение контрольного задания. | 2 | 4 | 5 | 5 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | ||||||||||
Конференц-неделя. | ||||||||||||||||||
18 | 08.06 | Практическое занятие 14. Конференц-неделя. Презентация по одной из проблем теории графов. | 14 | 10 | 10 | ОСН 1,2,3 ДОП 1,2,3 | ИР 1,2,3 | |||||||||||
Всего по контрольной точке (аттестации) 2 | 16 | 38 | 20 | 10 | 30 | |||||||||||||
Экзамен | 40 | |||||||||||||||||
Общий объем работы по дисциплине | 32 | 76 | 40 | 100 |
Информационное обеспечение:
№ (код) | Основная учебная литература (ОСН) | № (код) | Название интернет-ресурса (ИР) | Адрес ресурса | |
ОСН 1 | Bondy, J. A.; Murty, U. S.R. (2008), Graph Theory, Springer, ISBN 978-1-84628-969-9. | ИР 1 | Coursera | http://www. coursera. org | |
ОСН 2 | Tutte, W. T. (2001), Graph Theory, Cambridge University Press, p. 30, ISBN 978-0-521-79489-3 | ИР 2 | Алгоритмы: построение и анализ. | http://www. intuit. ru/studies/courses/534/390/info | |
ОСН 3 | Biggs, N.; Lloyd, E. and Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press. | ИР 3 | Графы и их применение. | http://www. intuit. ru/studies/courses/58/58/info | |
№ (код) | Дополнительная учебная литература (ДОП) | № (код) | Видеоресурсы (ВР) | Адрес ресурса | |
ДОП 1 | Chartrand, Gary (1985), Introductory Graph Theory, Dover, ISBN 0-486-24775-9. | ВР 1 | |||
ДОП 2 | Gibbons, Alan (1985), Algorithmic Graph Theory, Cambridge University Press | ВР 2 | |||
ДОП 3 | Harary, Frank (1969), Graph Theory, Reading, MA: Addison-Wesley |
