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

КАФЕДРА          ИНФОРМАТИКИ

Учебная  программа

Дисциплина:  "ПРОЕКТИРОВАНИЕ ЭФФЕКТИВНЫХ АЛГОРИТМОВ"

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

Автор  М.И. Дехтярь

 

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

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

2. Знания, умения и навыки, приобретаемые студентами

в результате изучения дисциплины

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

3. Распределение часов по темам и видам учебных занятий

7-8-ой  семестры

---------------------------------------------------------------------------------------------------------

N                Наименование                       Всего  Объем pаботы стyдентов |Фоpма контp.

п/п             разделов и тем                       часов  -----------------------------------

      Лекц.   Прак. Самост.     | Экз. Письм.

       зан. pаб.ст.         |           pаботы|

-----------------------------------------------------------------------------------------------------------

1                              2                                         3           4              5              6         |  7              8

-----------------------------------------------------------------------------------------------------------

1. Модели вычислений                              14            6              4              4

2. Структуры данных и

основные методы                               18            6              8              4

3. Сортировка                                              22          8                8            4                         2

4. Задачи поиска.

Метод расстановки

(хеширование)                                     12          4                6              2

5. Задачи поиска и

работа с множествами                      30         10            10               6                         2

6. Алгоритмы на графах                           38         14            14             8             4          2

7. Вычислительная геометрия              24         10           8             4                        2

8. Умножение матриц и

связанные задачи                               18           4              6              4                        

9. Идентификация строк                           24            8              8              6                        2

10. Синтез программ и базис

функциональных зависимостей             6             2               2             2

11.NP-полные и доказуемо

сложные задачи                                  28         10               8              8                        2

12.Задачи на теpмах

(выpажениях)                                       10            2              2              2              4          _______

И Т О Г О                                      242        84              84            54              8          12

 

Оценка знаний.  В 7-ом семестре проводятся 3 текущих контрольных работы

и экзамен. Каждая из контрольных и экзамен оцениваются по 100- балльной системе. Общая оценка О1 за семестр получается как взвешенная сумма: 

О1 = 60%(1-я контр. +2-я контр. + 3-я контр.) + 40% (экзамен).

В 8-ом семестре проводятся 3 контрольных работы и заключительный экзамен. Оценка за семестр определяется по формуле:

О2 = = 60%(1-я контр. +2-я контр. + 3-я контр.) + 40% (экзамен).

Общая оценка за курс определяется как

О = 50% О1  + 50% О2.

4. Содержание  учебной программы

 

1. Модели вычислений

1.1.Машины с произвольным доступом к памяти. Меры сложнос­ти вычислений. ПДП-машины и машины Тьюринга.

1.2. Линейные программы. Битовые линейные программы. Ветвя­щиеся программы (деревья сравнений).

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

2.Базовые структуры данных и основные методы разработки эффективных алгоритмов

2.1. Списки, стеки (магазины), очереди. Алгоритмы выполнения основных операций.

2.2. Графы, деревья, бинарные деревья. Способы представле­ния. Алгоритмы обхода деревьев.

2.3. Метод разработки алгоритмов "разделяй и властвуй". Алгоритм умножения двоичных чисел. Техническая теорема об оценке роста функций, заданных реккурентными соотношениями. Передача сообщений с открытыми ключами (экспоненциация).

2.4. Динамическое программирование. Оптимальное умножение последовательности матриц. Алгоритм эффективного распознавания кс-языков. Задача глобального выравнивания слов.

3. Сортировка

3.1. Нижние оценки числа сравнений (в "худшем" и в "среднем").

3.2. Алгоритм сортировки обменами (методом "пузырька").

3.3. Алгоритм сортировки слиянием.

3.4. Алгоритм быстрой сортировки Хоара. Оценка сложности

"в среднем".

3.5. Алгоритм пирамидальной сортировки (с помощью дерева).

3.6. Алгоритм лексикографической сортировки.

3.7. Алгоритмы нахождения k-го наименьшего элемента.

3.8. Нижняя оценка числа сравнений для нахождения 2-го по вели­чине элемента множества (теорема Кислицына).

4. Задачи поиска. Метод расстановки (хеширование)

4.1. Алгоритмы выполнения основных операций при исполь­зовании "внешних" и "внутренних" цепей.

4.2. Повторное хеширование. Выбор хеш-функции.

5. Задачи поиска и работа с множествами

 

5.1. Деревья двоичного поиска. Алгоритм построения оптималь­ного дерева двоичного поиска.

5.2. 2-3-деревья. Алгоритмы вставки и удаления элементов из 2-3-дерева.

5.3. Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием массивов и списков.

5.4. Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием древовидных структур (сжатие путей).

5.5. Алгоритм проверки эквивалентности конечных автоматов.

5.6. (*) Красно-черные деревья и операции над ними.

5.7  (*) Биномиальные и фиббоначиевы кучи и алгоритмы работы с ними.

5.8. В-деревья и алгоритмы работы с ними.

5.9. (*) Структуры данных для представления пространственной информации: 2-d деревья, квадродеревья,  R-деревья порядка k.

 

6.   Алгоритмы на графах

6.1. Минимальное остовное дерево.

6.2. Поиск в глубину и поиск в ширину в неориентированных и ориентированных графах. Топологическая сортировка.

6.3. (*) Алгоритм Дойча-Шорра-Уэйта для обхода ориентированного графа.

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

6.5. Алгоритмы построения транзитивного замыкания графа и нахождения кратчайших путей.

6.6. Задача о кратчайших путях из одного источника (алгоритм Дейкстры)..

6.7. Задача о максимальном потоке в сетях. Алгоритм Форда- Фалкерсона.

6.8. Алгоритм нахождения максимального потока за кубическое время.

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

 

7. (*)  Вычислительная геометрия

 

7.1. Задача об охране галереи.

7.2. Алгоритмы триангуляции многоугольников.

7.3. Триангуляции Делоне и диаграммы Вороного.

7.4. Построение выпуклого замыкания множества точек на плоскости.

7.5. Нахождение оптимального пути робота на плоскости с препятствиями.

8.   Умножение матриц и связанные задачи

8.1. Алгоритм Штрассена для умножения матриц.

8.2. НВП-разложение матриц.

8.3. Сложность обращения матриц, вычисления определителя и решения системы линейных уравнений.

8.4. Алгоритм ЧР для умножения булевых матриц.

8.5. Связь между умножением булевых матриц и нахождением транзитивного замыкания графа.

9.   Идентификация строк

9.1. Регулярные выражения, языки и недетерминированные конечные автоматы. Распознавание образцов, задаваемых регу­лярными выражениями.

9.2. Алгоритм Морриса-Пратта для задачи вхождения подслов.

9.3. (*) Алгоритм Бойера-Мура  для задачи вхождения подслов

    9.4. (*) Алгоритм  Кнута-Морриса-Пратта (Монте-Карло и Лас-Вегас)

9.5. Суффиксные деревья и решаемые с их помощью задачи.

Алгоритм построения суффиксного дерева за линейное (от его размера) время.

9.6. (*). Двyстоpонние детеpминиpованные магазинные автоматы и pаспознаваемые ими языки.

9.7. (*) Задача локального выравнивания слов. Ее приложение к биоинформатике.

10.. Синтез программ  и базис функциональных зависимостей

10.1. Вычислительные модели Тыугу и функциональные зависимости в реляционных БД. Алгоритм поиска от цели ("обратная волна").

10.2. Алгоритм поиска от данных ("прямая волна") и его реализация за линейное время.

 

11. NP-полные задачи

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

11.2. Примеры NP-полных задач в логике, теории графов, алгебре, комбинаторике, математическом программировании: 3-КНФ, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ГАМИЛЬТОНОВ ЦИКЛ, РАСКРАСКА, 3-СОЧЕТАНИЕ, РАЗБИЕНИЕ, РЮКЗАК, 0-1 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРО­ВАНИЕ, КОММИВОЯЗЖЕР, МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ, УРАВНЕНИЯ В СЛОВАХ и др.

11.3. (*)  Сильная NP-полнота задачи 3-РАЗБИЕНИЕ. Задача о бартерных сделках (выводимость в коммутативной полугруппе).

11.4. Подходы к решению NP-полных задач с использованием эвристических и приближенных алгоритмов.

11.5. (*) Веpоятностные алгоpитмы. Распознавание составных чисел за полиномиальное вpемя с помощью веpоятностого алгоpитма.

11.6. (*)  Класс PSPACE. Полнота задачи QBF в этом классе. PSPACE- полные игpы (обобщенная геогpафия, гекс).

11.7. (*) Доказyемо тpyдные задачи. Экспоненциальная сложность задачи об истинности фоpмyл с огpаниченными квантоpами и задачи о pегyляpных выpажениях с квадpатами.

11.8. Обзор абстрактной теории сложности.

 

12. (*) Задачи на теpмах (выpажениях)

12.1. Линейный алгоpитм yнификации теpмов.

12.2. Линейный алгоpитм для опpеделения общих подвыpажений.

12.3. Алгоpитм для выводимости pавенства выpажений.

Примечание. Разделы и пункты, отмеченные (*), являются дополнительными и могут  включаться или не включаться в программу по выбору лектора.

6. Литература

Основная:

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

           2.Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы(построение и анализ). МЦНО, М.,1999.

 

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

 

3. Н.Вирт. Алгоритмы и структуры данных.- М.:Мир, 1989.

4. М.Гэри, Д.Джонсон. Вычислительные машины и трудноре­шаемые задачи. М.:Мир, 1982.

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

6. В.Липский. Комбинаторика для программистов.-М.:Мир,1988.

7. Д.Мейер. Теория реляционных баз данных. М.:Мир, 1987.

8. Х.Пападимитриу, К.Стайглиц. Комбинаторная оптимизация. Алгоритмы и сложность.- М.:Мир, 1985.

9. Ф. Препарата, М. Шеймос. Вычислительная геометрия. Введение. – М.- Мир, 1989.

 

.