Основная образовательная программа подготовки специалиста по специальности

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ Комбинаторные алгоритмы Основная образовательная программа подготовки специалиста по специальности 010400 Прикладная математика и информатика Автор: Ланина Н.Р., к.т.н., доцент кафедры М и ММЭ Рецензенты: Верещагин Б.М., к.ф.-м.н., доцент, Богомолов Р.А., к.ф.-м.н., доцент Цели освоения дисциплины Целью изучения курса «Комбинаторные алгоритмы» является подготовка студентов на уровне, необходимом и достаточном для: усвоения материала специальных дисциплин; практической работы по специальности; формирования умения исследовать математическую задачу, выбрать для её решения необходимую структуру данных и программно реализовать алгоритм решения этой задачи. Основными задачами изучения данной дисциплины являются: изучение применяемых в программировании математических методов, позволяющих разрабатывать эффективные алгоритмы; изучение структур данных, их спецификации и реализации, алгоритмов обработки данных и анализ этих алгоритмов, взаимосвязь алгоритмов и структур данных; формирование целостной системы знаний о классических алгоритмах программирования, области их применения; формирование у студентов математической культуры и развитие логического мышления; обучение решению прикладных задач математическими методами; развитие способности творчески подходить к решению профессиональных задач. В результате изучения курса студенты должны знать: об основных методах решения «труднорешаемых» задач, т.е. задач, имеющих более чем полиномиальную сложность; об основных алгоритмах на графах и псевдографах, их теоретической сложности. . должны уметь: разрабатывать программы, используя изложенные в курсе общие схемы, методы и приемы построения алгоритмов; доказывать корректность составленного алгоритма и оценивать основные характеристики его сложности; реализовывать алгоритмы и используемые структуры данных средствами языков программирования высокого уровня (например, С++); экспериментально (с помощью компьютера) исследовать эффективность алгоритма и программы. Объем дисциплины и виды учебной работы (для всех направлений подготовки, на которых обеспечивается данная дисциплина). Общая трудоемкость дисциплины составляет 165 часов. № п/п Шифр и наименование направления с указанием профиля (названием магистерской программы), формы обучения Курс Семестр Виды учебной работы в часах Вид итогового контроля (форма отчетности) Трудоемкость в часах/ЗЕТ Всего аудит. Часов в интеракт. форме (из ауд.) ЛК ПР/ СМ ЛБ Часы на СРС (для дисц. с экзаменом включая часы на экзамен) 1 010200 Прикладная математика и информатика 5 9 165 92 - 46 46 - 73 экзамен Содержание дисциплины Разделы дисциплины и виды занятий (в часах). Примерное распределение учебного времени: № п/п Наименование раздела, темы Количество часов для специальности 010200 «Прикладная математика и информатика» Всего ауд. ЛК ПР ЛБ Сам.раб. 1 ИСЧЕРПЫВАЮЩИЙ ПОИСК 44 22 22 – 36 2 АЛГОРИТМЫ НА ГРАФАХ 40 20 20 – 34 3 NP-ПОЛНЫЕ ЗАДАЧИ 8 4 4 – 3 ИТОГО 92 46 46 – 73 Содержание разделов дисциплины ИСЧЕРПЫВАЮЩИЙ ПОИСК § 1. Алгоритмы с возвратом и их свойства § 2. Задача о велосипедном замке § 3. Генерация комбинаторных объектов § 4. Задача о ходе коня § 5. Задача о восьми ферзях § 6. Задача о паросочетаниях § 7. Метод ветвей и границ на примере задачи оптимального выбора (о рюкзаке) § 8. Задача коммивояжера и её решение методом ветвей и границ § 9. Динамическое программирование на примере задачи о порядке перемножения цепочки матриц § 10. Дерево оптимального поиска. Построение дерева оптимального поиска § 11. Решение задачи коммивояжера методом динамического программирования § 12. Жадные алгоритмы применительно к труднорешаемым задачам АЛГОРИТМЫ НА ГРАФАХ § 1. Графы и способы их машинного представления. Сильно ветвящиеся деревья и способы их машинного представления § 2. Метод поиска в глубину в графе. Метод поиска в ширину в графе. Задачи, решаемые с помощью поиска в глубину § 3. Алгоритм нахождения эйлерова цикла в графе. Алгоритм нахождения гамильтонова цикла в графе. Нахождение в графе точек сочленения § 4. Остовное дерево наиманьшей стоимости. Алгоритмы Крускала и Прима построения остовного дерева § 5. Задача об изоморфизме графов и пути ее решения. Задача об изоморфизме двух деревьев, как частный случай задачи об изоморфизме графов § 6. Нахождение кратчайших путей в графе. Алгоритм Форда-Беллмана нахождения расстояний от вершины-источника до остальных вершин § 7. Алгоритм Дейкстры нахождения расстояний от вершины-источника до остальных вершин. § 8. Алгоритм Уоршаллла и Флойда нахождения расстояний между всеми парами вершин § 9. Восстановление по расстояниям кратчайшего пути § 10. Определение расстояний в бесконтурном графе с использованием топологической сортировки § 11. Сети. Потока в сетях. Теорема Форда-Фалкерсона о максимальном потоке § 12. Алгоритм нахождения максимального потока в сети NP-ПОЛНЫЕ ЗАДАЧИ § 1. NP-класс. Полиномиальная сводимость задач. Эквивалентность задач. NP–полная задача § 2. Примеры доказательства NP-полноты. Пути решения NP-полных задач Темы для самостоятельного изучения № п/п Наименование раздела дисциплины. Тема. Форма самостоятельной работы Форма контроля выполнения самостоятельной работы Количество часов 1 ИСЧЕРПЫВАЮЩИЙ ПОИСК Контрольная работа № 1 Проверка контрольной работы 36 2 АЛГОРИТМЫ НА ГРАФАХ Контрольная работа № 2 Проверка контрольной работы 34 3 NP-ПОЛНЫЕ ЗАДАЧИ Контрольная работа № 2 Проверка контрольной работы 3 Учебно-методическое обеспечение и информационное обеспечение дисциплины Литература основная литература 1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом “Вильямс”, 2010.- 400 с. 2. Вирт Н. Алгоритмы и структуры данных. Издательство: М.: ДМК Пресс, 2010. - 274 с. 3. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. - М,.: Мир, 1981. 368 с. 4. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы. М.: Издательский дом “Вильямс”, 2010. - 720 с. 5. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск. М.: Издательский дом “Вильямс”, 2012. - 832 с. 6. Липский В. Комбинаторика для программистов. М.: Мир, 1988. дополнительная литература 1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с. 2. Браунси, Кен. Основные концепции структур данных и реализация в С++. М.: Издательский дом “Вильямс”, 2002.- 320 с. 3. Дмитриева М.В., Кубенский А.А. Элементы современного программирования: Учебное пособие. Спб.: Изд-во С.-Петербургского университета, 1991. - 272 с. 4. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Расширенный курс.– М: Известия, 2011.– 512 с. 5. Новиков Ф.А. Дискретная математика для программистов. Спб: Питер, 2009. - 384 с. электронно-библиотечные системы (ЭБС), базы данных, информационно-справочные и поисковые системы Главная ссылка http://scintific.narod.ru/literature.htm#PhysMath Техническая библиотека http://techlibrary.ru Электронная библиотека попечительского совета МГУ http://lib.mexmat.ru/ VILennins Home Page http://www.vilenin.narod.ru/Mm/Books/Books.htm Физико-математическая библиотека EqWorld http://eqworld.ipmnet.ru/ru/library.htm Материально-техническое обеспечение дисциплины персональные компьютеры программное обеспечение: Microsoft Visual Studio С++ либо другая аналогичная среда программирования. электронный конспект лекций пакет демонстрационно-обучающих программ по темам: «Исчерпывающий поиск», «Алгоритмы на графах» двадцать четыре варианта индивидуальных заданий в электронном виде Перечень вопросов к экзамену 1. Алгоритмы с возвратом и их свойства (с доказательством основного свойства) 2. Задача о велосипедном замке и методы её решения. Оценка максимальной сложности. Генерация всех подмножеств конечного множества 3. Генерация размещений, сочетаний, перестановок (с повторениями и без) 4. Генерация композиций, разбиений 5. Задача о ходе коня и методы её решения. Оценка максимальной сложности 6. Задача о восьми ферзях и методы её решения. Оценка максимальной сложности 7. Задача о паросочетаниях и методы её решения. Оценка максимальной сложности 8. Задача оптимального выбора (о рюкзаке) и методы её решения. Оценка максимальной сложности 9. Задача коммивояжёра и методы её решения. Оценка максимальной сложности 10. Задача о порядке перемножения цепочки матриц и методы её решения. Оценка максимальной сложности 11. Дерево оптимального поиска. Построение дерева оптимального поиска. Сложность алгоритма 12. Графы и способы их машинного представления. Сильно ветвящиеся деревья и способы их машинного представления 13. Метод поиска в глубину в графе. Метод поиска в ширину в графе. Задачи, решаемые с помощью поиска в глубину 14. Алгоритм нахождения эйлерова цикла в графе. Сложность алгоритма 15. Алгоритм нахождения гамильтонова цикла в графе. Сложность алгоритма. Нахождение в графе точек сочленения 16. Алгоритмы нахождения остовного дерева наиманьшей стоимости. Сложность алгоритмов 17. Задача об изоморфизме графов и пути ее решения. Оценка максимальной сложности. 18. Алгоритм Форда-Беллмана нахождения расстояний от вершины-источника до остальных вершин. Сложность алгоритма 19. Алгоритм Дейкстры нахождения расстояний от вершины-источника до остальных вершин. Сложность алгоритма 20. Алгоритм Уоршаллла и Флойда нахождения расстояний между всеми парами вершин Сложность алгоритма 21. Восстановление по расстояниям кратчайшего пути. Сложность алгоритма 22. Определение расстояний в бесконтурном графе с использованием топологической сортировки. Сложность алгоритма 23. Сети. Потока в сетях. Теорема Форда-Фалкерсона о максимальном потоке 24. Алгоритм нахождения максимального потока в сети 25. NP-класс. Полиномиальная сводимость задач. Эквивалентность задач. Задача о выполнимости. NP–полная задача 26. Примеры доказательства NP-полноты. Пути решения NP-полных задач Примерные варианты контрольных работ Контрольная работа №1. «Исчерпывающий поиск» 1. Решить задачу коммивояжера для пяти городов а) методом ветвей и границ; б) с помощью «жадного» алгоритма. Сравнить полученные решения Cij I II III IV V I  27 11 9 18 II 36  43 13 25 III 30 16  20 24 IV 14 12 26  17 V 15 25 30 12  2. Методом динамического программирования построить дерево оптимального поиска по заданным частотам обращения к внутренним ключам: a1 = 5, a2 = 1, a3 = 3, a4 = 4, a5 = 2. Частоты обращения к внешним ключам считать равными 0. Контрольная работа №2. «Алгоритмы на графах. NP-полные задачи» 1. Составить упорядоченные по алфавиту списки смежности графа; затем, начиная с вершины «k», выполнить обходы «в глубину» и «в ширину» (в обоих случаях пронумеровать вершины в порядке их прохождения; составить множества древесных Т и обратных В рёбер). 2. В данном нагруженном орграфе: а) с помощью алгоритма Форда-Беллмана найти расстояния от вершины-источника «1» до остальных вершин; б) по известным расстояниям восстановить кратчайший путь от вершины-источника «1» до вершины «6». 3. В данном нагруженном орграфе: а) с помощью алгоритма Дейкстры найти расстояния от вершины-источника «1» до остальных вершин; б) по известным расстояниям восстановить кратчайший путь от вершины-источника «1» до вершины «5».

Похожие:

	Учебно-методический комплекс дисциплины фтд. 1 Основы кинезиологии... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 11 Основы коммуникативной... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины гсэ. В устойчивое развитие... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины фтд основы фитодизайна основная... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины сд. 14 Биологическая химия... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины ен. Ф. 04. Общая химия основная... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины сд. Ф. 6 Экономика физической... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины фтд. 4, Сд. В микология основная... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины дс. 5 Экология почв основная... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины сд. 14, Сд. Ф. 14 Биологическая... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины сд. 11, Сд. Ф. 11 Зоология... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 21 Методы географических... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины ен. Ф. 04. Химия: высокомолекулярные... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины сд. Ф ботаника с основами... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины гсэ. В 1 Семьеведение Основная... Основная образовательная программа подготовки специалиста по специальности «050720 Физическая культура»		Основная образовательная программа подготовки специалиста по специальности... Основная образовательная программа подготовки специалиста по специальности (специальностям)