birmaga.ru
добавить свой файл

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

Томский государственный университет


УТВЕРЖДАЮ
Декан факультета информатики

Сущенко С.П.

"_____" ____________ 2010 г.

Рабочая программа дисциплины
АЛГОРИТМЫ И АНАЛИЗ СЛОЖНОСТИ

Направление подготовки
230700 Прикладная информатика

Квалификация выпускника
Бакалавр

Форма обучения
Очная

Томск – 2010

1. Цели освоения дисциплины

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

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

Раздел образовательной программы: Б.3. Профессиональный цикл. Базовая часть.

Для изучения курса необходимо знание следующих дисциплин:


  • основы программирования,

  • дискретная математика,

  • математическая логика и теория алгоритмов,

  • теория графов,

  • математический анализ I (функции одной переменной),

  • алгебра и геометрия.

Для того, чтобы приступить к изучению курса «Алгоритмы и анализ сложности», студент должен обладать следующими знаниями и умениями:

  • знать теорию множеств, теорию отношений, теорию графов, теорию функций одной переменной, логику высказываний и логику предикатов первого порядка,

  • знать основы компьютерных технологий и языков программирования,

  • иметь твердые знания основных структур данных в программировании,

  • уметь строить алгоритмы решения поставленной задачи,

  • уметь разрабатывать программы для ЭВМ.

Знания и умения, полученные в ходе освоения данной дисциплины (модуля), понадобятся при изучении таких последующих дисциплин ООП, как:


  • программирование 4 (ООП),

  • теория автоматов и формальных языков.

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

Курс «Алгоритмы и анализ сложности» способствует выработке у студента следующих компетенций:

  • способность моделировать и проектировать структуры данных и знаний, прикладные и информационные процессы (ПК-9),

  • способность применять к решению прикладных задач базовые алгоритмы обработки информации, выполнять оценку сложности алгоритмов, программировать и тестировать программы (ПК-10).

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

  • знать принципы разработки эффективных алгоритмов, методы исследования и теорию сложности алгоритмов, набор базовых алгоритмов,

  • уметь применять их при создании программных и информационных систем, а также при их анализе,

  • владеть общепрофессиональными знаниями методов разработки и анализа алгоритмов для решения практических задач.

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

4. Структура и содержание дисциплины (модуля) «Алгоритмы и анализ сложности»

Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часов.




п/п

Раздел

дисциплины


Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)

Формы текущего контроля успеваемости (по неделям семестра)

Форма промежуточной аттестации (по семестрам)













всего

лекции

лаборатории

самостоятельная работа




1

Методы анализа алгоритмов

3

1




2










2

Задача сортировки

3

1




1










3

Алгоритмы внутренней сортировки

3

1-3




8










4

Порядковые статистики


3

4




2










5

Внешняя сортировка

3

4




3







Экзамен

6

Лабораторная работа №1

3

1-4







8

20

Сдача лабораторной работы

7

Хеширование

3

5




3










8

Лабораторная работа №2

3

5-6







4

20

Сдача лабораторной работы

9

Информационные деревья

3

5-7




7








10

Информационные таблицы

3

7




2










11

Поиск цепочек символов

3

8




4







Экзамен

12

Лабораторная работа №3

3

7-8







4

20

Сдача лабораторной работы

13

Эффективные алгоритмы на графах

3

9-11




12










14

Комбинаторные алгоритмы

3

12




4







Экзамен

15

Лабораторная работа №4

3

9-12






8

20

Сдача лабораторной работы

16

Комбинаторные алгоритмы на графах

3

13-14




5










17

Модели вычислений и машины Тьюринга

3

14




3










18

Лабораторная работа №5

3

13-14







4

20

Сдача лабораторной работы

19

Теория алгоритмов

3

15




2










20

Связь задач по сложности

3

15




2








21


NP-полнота задачи выполнимости

3

16




2










22

Связь NP-полных задач

3

16




2







Экзамен

23

Лабораторная работа №6

3

15-16







4

20

Сдача лабораторной работы

ИТОГО




3




216

64

32

120





Лекционный курс

Часть 1. Методы анализа алгоритмов

Вход и выход алгоритма. Представление алгоритмов в командах компьютера и на языке высокого уровня. Временная и емкостная сложности алгоритма. Полиномиальные и экспоненциальные виды функций сложности. Исследование временной сложности в наихудшем и в среднем. Теоремы о рекуррентных соотношениях для сложности. Экспериментальное исследование сложности алгоритмов. Генерация случайных входных данных. Статистическая обработка результатов исследования сложности алгоритмов.

Часть 2. Сортировка


2.1. Задача сортировки

Дерево решений в задаче сортировки. Минимально возможная трудоемкость в наихудшем. Оптимальные алгоритмы. Инверсии. Перестановки.

2.2. Алгоритмы внутренней сортировки

Простейшие алгоритмы. Алгоритм Шелла. Быстрая сортировка Хоара, оценка его сложности в среднем. Пирамидальная сортировка. Сортировка слиянием. Цифровая сортировка. Цифровая сортировка строк.

2.3. Порядковые статистики

Задача определения k-го элемента. Алгоритм, основанный на быстрой сортировке, его сложность в среднем. Алгоритм, эффективный в наихудшем случае.

2.4. Внешняя сортировка

Особенности задачи сортировки информации на файлах. Сбалансированное слияние. Многофазная сортировка, ее анализ. Особенности практической реализации.

Часть 3. Поиск

3.1. Хеширование

Задача хеширования. Хеш-функция. Хеш-таблица с областью переполнения, поиск, удаление элементов. Хеш-таблица с открытой адресацией, эффективность поиска в среднем. Применение хеш-таблиц в файлах.

3.2. Информационные деревья

Построение случайного дерева. Поиск в случайном дереве, его средняя трудоемкость. Идеально сбалансированные деревья. Удаление элементов из дерева. АВЛ-деревья. Фибоначчиевы деревья, их максимальная высота. Добавление и удаление в АВЛ-дереве. Деревья для задачи объединения множеств. В-деревья, их пpименение для файлов. 2-3-деревья, их применение для словарей, сцепляемых очередей, очередей с приоритетами. Прошитые словари и очереди.

3.3. Информационные таблицы

Таблица как база данных. Иерархическая упорядоченность в таблице. Косвенная адресация. Поиск по нескольким ключам. Включающий поиск. Операции проекции и соединения таблиц, как обобщение поиска.

3.4. Поиск цепочек символов

Алфавит. Цепочка. Задача распознавания. Алгоритм Бойера-Мура. Конечный автомат (КА), его функционирование. Распознавание цепочек с помощью КА. Алгоритм Кнута-Морриса-Пратта. Алгоритм Рабина-Карпа. Распознавание множества цепочек.


Часть 4. Комбинаторные алгоритмы, алгоритмы на графах

4.1. Эффективные алгоритмы на графах.

Эйлеров путь в графе. Остовное дерево наименьшей стоимости, алгоритмы Прима и Крускала. Поиск в глубину в неориентированном графе. Выделение компонент связности. Двусвязные компоненты. Сильно связные компоненты. Нахождение кратчайших путей во взвешенном графе, алгоритмы Флойда и Дейкстры. Транзитивное замыкание, алгоритм Уоршалла.

4.2. Комбинаторные алгоритмы

Перебор вариантов. Бэктрекинг, общий алгоритм. Генерация цепочек символов по грамматике. Оптимизационные задачи. Метод ветвей и границ для решения оптимизационных задач. Задача коммивояжера. Оценки трудоемкости. Приближенные решения задачи коммивояжера. Жадный алгоритм ближайшего города и локальная оптимизация, оценки качества решения. Приближенное решение задачи коммивояжера с помощью минимального остова.

4.3. Комбинаторные задачи на графах

Минимальная раскраска графа, переборный алгоритм. Приближенные алгоритмы раскраски графа, основанные на понятии соцветных вершин. Раскраска методом ветвей и границ. Гамильтонов цикл. Поиск клик в графе. Узельное покрытие.

Часть 5. Теория алгоритмов и NP-полные задачи

5.1. Модели вычислений и машины Тьюринга

Модель равнодоступной адресной машины (РАМ), ее связь с языком программирова­ния. Машина Тьюринга. Связь машины Тьюринга и РАМ. Детерминированная (ДМТ) и недетерминированная (НМТ) машины Тьюринга. Детерминированное моделирование НМТ.

5.2. Теория алгоритмов

Языки и задачи. Машина Тьюринга, как распознаватель цепочки языка. Тезис Черча. Частичные алгоритмы. Алгоритмически неразрешимые проблемы.

5.3. Связь задач по сложности

NP-полные и NP-трудные задачи. Класс языков P-SPACE. Связь ДМТ и НМТ по емкостной сложности. Связь классов языков P-SPACE, P, NP-полных и NP-трудных.


5.4. NP-полнота задачи выполнимости

Классы P и NP задач. Теорема Кука о задаче выполнимости булевых формул. NP-полнота задачи выполнимости.

5.5. Связь NP-полных задач

Задача КНФ- и 3-КНФ-выполнимости. Клики. Узельное покрытие. Гамильтоновы циклы. Задача коммивояжера.

Лабораторный практикум

Лабораторная работа №1. Реализовать 5 алгоритмов внутренней сортировки:


  • рекуррентное слияние,

  • сортировку Шелла,

  • пирамидальную сортировку,

  • быструю сортировку с одним рекурсивным вызовом,

  • цифровую сортировку целых неотрицательных чисел.

Сравнить трудоемкости алгоритмов для различных длин входных массивов.

Лабораторная работа №2. Реализовать многофазную сортировку с 2 входными файлами для заданного числа сортируемых значений N и длины начальных серий L.

Лабораторная работа №3. Построить хеш-таблицу, для поиска в которой используется метод открытой адресации (отдельные варианты для линейных проб, квадратичных проб и двойного хеширования). Для всех вариантов рассчитать среднюю трудоемкость поиска элементов при заданных коэффициентах заполненности хеш-таблицы.

Лабораторная работа №4. Написать программу построения красно-черного, АВЛ- или 2-3-дерева с возможностью добавления и поиска элементов, либо случайного бинарного дерева с возможностью добавления и удаления элементов.

Лабораторная работа №5. Реализовать 2 из следующих 3 алгоритмов поиска в строке по образцу:

  • алгоритм Бойера-Мура,

  • алгоритм Кнута-Морриса-Пратта,

  • алгоритм Рабина-Карпа.

Лабораторная работа №6. Реализовать 2 алгоритма расчета маршрута коммивояжера:

  • переборный алгоритм с отсечениями (метод ветвей и границ),
  • приближенный алгоритм обхода на основе минимального остова.


5. Образовательные технологии

В ходе преподавания дисциплины используются следующие образовательные технологии:

  • разбор конкретных ситуаций,

  • решение профессиональных задач из реальной предметной области,

  • самостоятельное проектирование.

6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.

Самостоятельная работа студентов по дисциплине организуется в следующих формах:

  • самостоятельное изучение основного теоретического материала, ознакомление с дополнительной литературой, Интернет-ресурсами,

  • индивидуальное выполнение проектов.

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

Вопросы и задания для текущего контроля:

  1. Сортировка слиянием – рекурсивный и рекуррентный варианты.

  2. Сортировка Шелла.

  3. Пирамидальная сортировка.

  4. Быстрая сортировка: идея, трудоемкость в среднем и наихудшем.

  5. Быстрая сортировка: идея, разделение опорным элементом, варианты с одним или двумя рекурсивными вызовами, емкостная сложность.

  6. Цифровая сортировка целых чисел.

  7. Цифровая сортировка строк.

  8. Порядковые статистики: алгоритм с линейной трудоемкостью в среднем.

  9. Порядковые статистики: алгоритм с гарантированной линейной трудоемкостью.

  10. Двух- и многопутевое сбалансированное слияние.

  11. Многофазная сортировка: идея, реализация для двух входных лент.

  12. Многофазная сортировка: идея, реализация для m>2 входных лент.
  13. Хеширование. Идея, метод цепочек. Использование хеширования для данных на ВУ.


  14. Хеширование. Идея, метод открытой адресации. Варианты реализации.

  15. Хеширование. Метод открытой адресации. Средняя трудоемкость поиска.

  16. Случайное бинарное дерево. Построение, поиск, удаление элементов.

  17. Случайное бинарное дерево. Трудоемкость поиска в наихудшем и среднем.

  18. Идеальное дерево. Максимальная и средняя трудоемкость поиска.

  19. АВЛ-деревья. Деревья Фибоначчи. Трудоемкость поиска. Структура вершины.

  20. Добавление вершины к АВЛ-дереву.

  21. Удаление вершин из АВЛ-дерева.

  22. В-деревья. Структура вершины. Поиск значения. Оценки трудоемкости. 2-3-деревья.

  23. Добавление значения к В-дереву.

  24. Удаление значения из В-дерева.

  25. Поиск подстроки. Алгоритм Бойера-Мура.

  26. Поиск подстроки с помощью конечного автомата.

  27. Поиск подстроки. Алгоритм Кнута-Морриса-Пратта.

  28. Поиск подстроки. Алгоритм Рабина-Карпа.

  29. Выделение минимального остова. Алгоритм Прима.

  30. Выделение минимального остова. Алгоритм Крускала.

  31. Поиск кратчайших путей. Алгоритм Дейкстры.

  32. Поиск кратчайших путей и транзитивное замыкание графа. Алгоритмы Флойда и Уоршолла.

  33. Выделение двусвязных компонент графа.

  34. Сильно связные компоненты. Алгоритм с однократным поиском в глубину.

  35. Сильно связные компоненты. Алгоритм с двукратным поиском в глубину.

  36. Варианты поиска оптимального маршрута коммивояжера. Маршрут на основе минимального остова.

  37. Задача коммивояжера. Алгоритм ближайшего города.

  38. Задача раскраски графов. Минимальная раскраска графа по методу ветвей и границ.

  39. Задача раскраски графов. Алгоритмы, основанные на степенях вершин.

  40. Алгоритмы раскраски графов, основанные на склеивании вершин.

  41. Раскраска транзитивно-ориентируемых графов.
  42. Недетерминированные алгоритмы и их моделирование с помощью детерминированных.


  43. NP-полные и NP-трудные задачи.

  44. Диаграмма классов задач. Связь классов P-space и NP-space.

  45. Основные идеи доказательства NP-полноты задачи выполнимости булевых формул.

  46. NP-полнота задач КНФ- и 3-КНФ-выполнимости.

  47. NP-полнота задачи о k-клике.

  48. NP-полнота задачи о вершинном покрытии.

  49. NP-полнота задачи о гамильтоновом цикле в ориентированном графе.

  50. NP-полнота задач о гамильтоновом цикле в неориентированном графе и b-коммивояжера.

  51. NP-трудность задачи коммивояжера – оптимальный и субоптимальный вариант.

7. Учебно-методическое и информационное обеспечение дисциплины (модуля) «Алгоритмы и анализ сложности»

Литература:

  1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир,1979.

  2. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1990.

  3. Гудман С., Хидетмиеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981. – 368 с.

  4. Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978. – 275 c.

  5. Ершов А.П. Теоретическое программирование. – М.: Наука, 1977.

  6. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. – М.: Мир, 1978.

  7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001.

  8. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.

  9. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.– М.: Мир,1980. – 476 с.

Программное обеспечение:

  • Microsoft Visual Studio,

  • Delphi или Lazarus.

    8. Материально-техническое обеспечение дисциплины (модуля)

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


Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ООП ВПО по направлению подготовки 230700 «Прикладная информатика».

Автор: к.техн.н., доцент А.Л. Фукс.

Рецензент: д.техн.н., профессор Ю.Л. Костюк.

Программа одобрена на заседании Ученого Совета факультета информатики
от «_____»______________201__г., протокол № _____.