МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Томский государственный университет систем управления и радиоэлектроники»

(ТУСУР)

Кафедра автоматизированных систем управления

АЛГОРИТМЫ И АНАЛИЗ ИХ СЛОЖНОСТИ

Методические указания к практическим занятиям студентов всех форм обучения для направления 010400 "Прикладная математика и информатика" (квалификация (степень) "магистр") Томск-2011 2 Горитов А.Н.

Алгоритмы и анализ их сложности: методические указания к практическим занятиям студентов всех форм обучения по направлению подготовки "010400 Прикладная математика и информатика" (квалификация (степень) "магистр") / А.Н. Горитов. – Томск: ТУСУР, 2011. – 8 с.

Методические указания разработаны в соответствии с решением кафедры автоматизированных систем управления Составитель: д.т.н., профессор каф. АСУ А.Н. Горитов Методические указания утверждены на заседании кафедры автоматизированных систем управлениям 30 августа 2011 г., протокол № © ТУСУР, каф. АСУ, © Горитов А.Н.

СОДЕРЖАНИЕ

2. Методы и формы организации обучения

3. Место дисциплины в структуре ООП

4. Практические занятия

4.1 Вычислительная сложность алгоритмов

4.2 NP-полные и труднорешаемые задачи

4.3 Метод ветвей и границ

4.4 Поиск подстрок

4.5 Фундаментальные алгоритмы на графах

4.6 Кратчайшие пути во взвешенном графе

4.7 Задачи о потоках

4.8 Задача о паросочетании

4.9 Решение задач с помощью алгоритма с возвратом

5. Список литературы

5.1 Основная

5.2 Дополнительная

1. Цели и задачи дисциплины Целью изучения дисциплины «Алгоритмы и анализ их сложности» является изучение применяемых в программировании (и информатике) структур данных, их спецификации и реализации, а также алгоритмов обработки данных и анализ этих алгоритмов, взаимосвязь алгоритмов и структур.

В результате изучения дисциплины студент должен:

а) иметь представление об основных тенденциях в создании структур данных, методах оптимального использования памяти и времени для обработки структур данных и управления процессами обработки данных;

б) знать и использовать различные (динамические и статистические) структуры данных в соответствии с запросами алгоритмов;

в) создавать списковые и древообразные структуры и управлять организацией этих структур (изменение списков и деревьев посредством включения исключения, замены элементов структур) знать, использовать оптимальные методы поиска и сортировки данных;

г) знать и использовать основные алгоритмы решения классических задач информатики;

д) иметь представление о математических методах анализа алгоритмов; классификации алгоритмических задач по сложности, сводимости алгоритмических задач к известным задачам определенного класса сложности;

е) иметь опыт работы с алгоритмическими языками программирования.

2. Методы и формы организации обучения Процесс изучения дисциплины «Алгоритмы и анализ их сложности» направлен на формирование следующих компетенций:

общекультурные компетенции (ОК):

способностью использовать углубленные теоретические и практические знания в области прикладной математики и информатики (ОК-3);

способность самостоятельно приобретать с помощью информационных технологий и использовать в практической деятельности новые знания и умения, в том числе, в новых областях знаний, непосредственно не связанных со сферой деятельности, расширять и углублять свое научное мировоззрение (ОК-4);

способностью порождать новые идеи и демонстрировать навыки самостоятельной научно-исследовательской работы и работы в научном коллективе (ОК-5);

профессиональные компетенции (ПК):

способностью проводить научные исследования и получать новые научные и прикладные результаты (ПК-1);

способностью разрабатывать концептуальные и теоретические модели решаемых научных проблем и задач (ПК-2);

способностью углубленного анализа проблем, постановки и обоснования задач научной и проектно-технологической деятельности (ПК-3).

Для успешного освоения дисциплины применяются различные образовательные технологии, которые обеспечивают достижение планируемых результатов обучения согласно основной образовательной программе, с учетом требований к объему занятий в интерактивной форме.

Интерактивные формы обучения, которые используются в данном курсе, включают:

«Работа в команде» и «Поисковый метод».

Для контроля освоения компетенций используются следующие формы контроля:

контроль в ходе выполнения практических заданий, опрос по изучаемым разделам дисциплины, тесты. По всем практическим занятиям подготовлены списки контрольных вопросов.

Дисциплина «Алгоритмы и анализ их сложности» относится к вариативной части математического и естественнонаучного цикла ООП. Успешное овладение дисциплиной предполагает предварительные знания математического анализа, вычислительных методов, дискретной математики в объеме, предусмотренном специальностью «Прикладная математика и информатика», а также навыки программирования на языках высокого уровня.

4.1 Вычислительная сложность алгоритмов Алгоритмы и их классификация. Вычислительная сложность алгоритмов.

Литература 1, Контрольные вопросы 1. Какие критерии используются при выборе алгоритмов?

2. Как оценивается трудоемкость алгоритма?

3. Что такое О-нотация и для чего она используется?

4. Какие группы функций можно выделить с помощью О-нотации?

5. Какие рекомендации следует использовать при выборе алгоритмов с помощью Онотации?

4.2 NP-полные и труднорешаемые задачи Массовая и индивидуальная задачи. Сложность алгоритма. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP.

Полиномиальная преобразуемость задач. NP-трудные и NP-полные задачи.

Литература 1, Контрольные вопросы 1. Как оценивается сложность алгоритма?

2. Чем отличаются алгоритмы класса Р от алгоритмов класса NP?

3. Что такое «полиномиальная приводимость задач»?

4. Что такое «Задача принятия решения»?

5. Какая задача является NP-трудной?

4.3 Метод ветвей и границ Метод декомпозиции. Пример.

Поиск с возвратом. Общий алгоритм. Пример.

Метод ветвей и границ. Применение метода при решении задачи о рюкзаке, задаче о назначениях и задаче коммивояжера.

Динамическое программирование. Пример. Нисходящее и восходящее динамическое программирование. Задача определения наиболее длинной общей подпоследовательности.

Задача построения оптимального бинарного дерева поиска.

Литература 1, 2, 8, Контрольные вопросы 1. В чем заключается метод ветвей и границ.

2. Как строятся оценочные функции состояний? Приведите примеры.

3. Что такое динамическое программирование?

4. В каких случаях применяется динамическое программирование?

5. В чем заключается восходящий и нисходящий методы динамического программирования?

Задача поиска подстрок. Простейший алгоритм. Алгоритм Кнута-Морриса-Пратта.

Алгорит Бойера-Мура. Алгоритм Рабина-Карпа.

Литература 1, Контрольные вопросы 1. Что такое префикс–функция, ассоциированная с образцом?

2. Что такое эвристика стоп–символа?

3. В чем состоит эвристика безопасного суффикса?

4. Что такое собственный префикс?

5. Что такое собственный суффикс?

4.5 Фундаментальные алгоритмы на графах Графы: определения и примеры. Представления графов: матрица инциденций, матрица смежности, список пар, списки смежности.

Фундаментальные алгоритмы на графах: Поиск в графе. Поиск в ширину. Поиск в глубину.

Остовные деревья графа. Связные компоненты. Построение и свойства остовных деревьев при поиске в глубину и в ширину.

Эйлеров путь в графе. Алгоритм построения Эйлерова пути.

Циклы: Фундаментальное множество циклов графа. Алгоритм отыскания фундаментального множества циклов в графе.

Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала.

Гамильтонов путь в графе. Нахождение Гамильтонова пути в графе с помощью алгоритма с возвратом Литература 1, 2, 3, 4, 5, 6, Контрольные вопросы 1. Какие способы можно использовать для представления графов как структур данных?

2. Какие структуры данных необходимы для реализации списков смежности?

3. Как реализуются операции добавления и удаления ребер в графе?

4. Как реализуются операции добавления и удаления вершин в графе?

5. Какие шаги включает в себя алгоритм поиска в глубину?

4.6 Кратчайшие пути во взвешенном графе Кратчайшие пути в графе. Кратчайшие пути от фиксированной вершины. Алгоритм Форда-Беллмана. Случай неотрицательных весов: алгоритм Дейкстры. Кратчайшие пути в бесконтурном графе. Топологическая сортировка. Кратчайшие пути между всеми парами вершин. Матрица смежности, матрица достижимости и транзитивное замыкание отношения, алгоритм Уоршалла. Алгоритм Флойда-Уоршалла вычисления расстояний между всеми парами вершин, одновременное построение путей.

Литература 1, 2, 3, 4, 5, 6, Контрольные вопросы 1. Поясните, в чем состоит алгоритм Форда-Беллмана.

2. Поясните, в чем состоит алгоритм Дейкстры.

3. На каком принципе строится алгоритм нахождения кратчайших путей в бесконтурном графе?

4. Что такое «транзитивное замыкание».

5. Поясните, в чем состоит алгоритм Уоршалла.

4.7 Задачи о потоках Задача о максимальном потоке. Введение. Транспортные сети и потоки. Алгоритм Форда-Фалкерсона. Алгоритм Эдмондса-Карпа. Алгоритм Диница.

Задача о потоке минимальной стоимости.

Литература Контрольные вопросы 1. Что такое «Транспортная сеть»?

2. Что такое «Остаточная сеть»?

3. Что такое «Увеличивающий путь»?

4. В чем заключается алгоритм Форда-Фалкерсона?

5. В чем заключается алгоритм Эдмондса-Карпа?

4.8 Задача о паросочетании Паросочетание. Алгоритм определение максимального паросочетания. Задача о полном паросочетании.

Литература Контрольные вопросы 1. Что такое «Двудольный граф»?

2. Что такое «Паросочетание»?

3. Что такое «Чередующаяся цепь»?

4. В чем заключается задача о полном паросочетании?

5. Опишите алгоритм решения задачи о полном паросочетании.

4.9 Решение задач с помощью алгоритма с возвратом Гамильтонов путь. Клики графа.

Литература Контрольные вопросы 1. В чем заключается алгоритм с возвратом?

2. Как применяется алгоритм с возвратом при нахождении гамильтонового пути в графе?

3. Как применяется алгоритм поиска с возвратом при решении задачи нахождения всех клик графа?

1. Горитов А.Н. Основы структур и алгоритмов обработки данных: Учебное пособие. – Томск: ТУСУР, 2007. – 229 с. (50 экз.) 5.2 Дополнительная 2. Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. – Москва: Техносфера, 2004. – 368 с. (13 экз.) 3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие.

– М.: Лаборатория базовых знаний, 2003. – 288 с. (50 экз.) 4. Окулов С. М. Программирование в алгоритмах. – 2-е изд., доп. – М.: БИНОМ.

Лаборатория знаний, 2006. – 384 с. (30 экз.) 5. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. – СПб: Питер, 2002. – 302 с. (19 экз.) 6. Андерсон Д.А. Дискретная математика и комбинаторика. – М.: Издательский дом "Вильямс", 2004. – 960 с. (10 экз.) 7. Липский В. Комбинаторика для программистов. – М.: Мир,1989.– 213 с. (9 экз.) 8. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с. (50 экз.) 9. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. – М: Финансы и статистика; ИНФРА-М, 2009. – 304 с.