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

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

Рабочая учебная программа

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

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

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

Общий бюджет времени

Семестр Аудиторные занятия (час.) Экза- Контр.

__________________________________________ мены (к-во)

Лекции Практические Итого (к-во)

занятия

_______________________________________________________________________

I 46 46 92 1 3

_______________________________________________________________________

II 38 38 76 1

_______________________________________________________________________

Итого 84 84 168 2 3

________________________________________________________________________

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

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

_______________________________________________________________________

N Тема, вид занятия Кол-во Наименование Литература,

п/п часов занятий задание

_______________________________________________________________________

1 2 3 4 5

_______________________________________________________________________

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

1.1. Л+Пр 2+1 ПДП-машины. Меры 1 гл.1

сложности вычислений.

1.2. Л+ПР 1+2 Линейные программы.

Битовые линейные про-

граммы.Ветвящиеся

программы.

1.3. Л+ПР 2+1 Модельный алгоритмичес-

кий язык и сложность

основных конструкций.

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

основные методы 1 гл. 2

2.1. Л+ПР 1+1 Списки, стеки,очереди.

2.2. Л+ПР 1+2 Графы, деревья, бинарные

деревья. Способы представ-

ления. Алгоритмы обхода.

2.3. Л+ПР 2+2 Метод разработки "разделяй

и властвуй".Алгоритм умно-

жения двоичных чисел.

2.4. Л+ПР 2+2 Динамическое программирова-

ние. Алгоритм распознавания

кс-языков.

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

3.1. Л+ПР 2+2 Нижние оценки числа 1 гл.3

сравнений (в "худшем"

и в "среднем" случаях).

Алгоритмы сортировки

обменами и слиянием.

3.2. Л+ПР 1+1 Алгоритм быстрой сор- 1 гл.3

тировки. Алгоритм

пирамидальной сорти-

ровки.

-3-

______________________________________________________________________

1 2 3 4 5

______________________________________________________________________

3.3. Л+ПР 1+1 Алгоритм лексикографи- 1 гл.3

ческой сортировки.

3.4. Л+ПР 1+1 Алгоритмы нахождения 1 гл.3

k-го наименьшего элемента.

3.5. Л+ПР 2+2 Нижняя оценка числа 5 гл.5

сравнений для нахождения

2-го по величине элемента

(теорема Кислицына).

4. Задачи поиска. Метод

расстановки (хеширование)

4.1. Л+ПР 2+2 Алгоритмы выполнения 5 гл.6

основных операций.

"Внешние" и "внутрен-

ние" цепи.

4.2. Л+ПР 1+3 Повторное хеширование. 2

Выбор хеш-функции.

5. Задачи поиска и работа

с множествами

5.1. Л+ПР 1+2 Деревья двоичного поис- 1 гл.4

ка. Алгоритм построения

оптимального дерева ДВП.

5.2. Л+ПР 2+2 2-3-деревья. Алгоритмы 1 гл.4

вставки и удаления эл-в.

5.3. Л+ПР 4+2 Алгоритмы для операций 1 гл.4

ОБЪЕДИНИТЬ, НАЙТИ:1) с 2

использованием массивов

и списков; 2) с использо-

ванием деревьев.

5.4. Л+ПР 1+1 Алгоритм проверки эквива- 1 гл.4

лентности кон. автоматов.

5.5. Л+ПР 1+2 В-деревья и алгоритмы 2 гл. 4

работы с ними. 5 гл.6

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

6.1. Л+ПР 2+2 Минимальное остовное 1 гл.5

дерево. Поиск в глубину 6 гл. 2

и поиск в ширину. 2

6.2. Л+ПР 2+2 Алгоритм ДШУ для обхода 1 гл.5

орграфа. Алгоритм опреде- 2

ления двусвязных компо-

нент графа.

6.3. Л+ПР 2+2 Алгоритмы построения 1 гл.5

транзитивного замыкания и 6 гл.3

нахождения кратчайших путей. 2

6.4. Л+ПР 2+2 Задача о максимальном

потоке в сетях. Алгоритм 8 гл.6

Форда- Фалкерсона.

6.5. Л+ПР 4+4 Алгоритм нахождения макс. 6 гл.4

потока за кубическое время. 8 гл.9

6.6. Л+ПР 2+2 Простые сети и задача о 6 гл.4

максимальном паросочетании.

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

7.1. Л+Пр 2+1 Задача об охране галереи. 9

7.2. Л+ПР 2+2 Алгоритмы триангуляции 6 гл. 6

многоугольников.

7.3. Л+ПР 2+1 Триангуляции Делоне и 6 гл.6

диаграммы Вороного.

7.4. Л+ПР 2+2 Построение выпуклого замыкания 6 гл. 3,4

множества точек на плоскости. 9 гл. 35

7.5. Л+ПР 2+1 Нахождение оптимального пути

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

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

связанные задачи 1 гл.6

8.1. Л+ПР 1+1 Алгоритм Штрассена для

умножения матриц.

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

Сложность обращения мат-

риц, вычисления опред.

и решения системы линейных

уравнений.

8.3. Л+ПР 3+3 Алгоритм ЧР для умножения

булевых матриц. Связь между

умножением булевых матриц

и нахождением транзитивного

замыкания графа.

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

9.1. Л+ПР 2+2 Регулярные выражения, языки

и НКА.Распознавание образцов,

задаваемых регулярными выр-ми.

9.2. Л+ПР 2+2 Алгоритм Морриса-Пратта для

задачи вхождения подслов.

9.3.(*) Л+ПР 1+1 Алгоритм Бойера-Мура для 2 гл.34

задачи вхождения подслов

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

(Монте-Карло и Лас-Вегас)

9.5. Л+ПР 2+2 Суффиксные деревья и решаемые

с их помощью задачи.Алгоритм

построения СД за линейное (от

его размера) время.

9.6.(*) Л+ПР 2+2 Двyстоpонние детеpминиpованные

магазинные автоматы и их языки.

9.7.(*) Л+ПР 1+1 Задача локального выравнивания

слов. Ее приложение к биоинформатике.

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

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

10.1. Л+ПР 2+2 Вычислительные модели и

функциональные зависимости 7 гл.5

в реляционных БД. Алгоритм

поиска от цели.

10.2.Л+ПР 2+2 Алгоритм поиска от данных

за линейное время. 7 гл.5

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

11.1. Л 2 Классы P и NP.Теорема 1 гл.10

Кука-Левина о NP-полноте SAT.

11.2. Л+ПР 4+4 Примеры NP-полных задач в 1 гл. 10

логике, теории графов, 4 гл. 2,5

алгебре, комбинаторике,

11.3. Л+ПР 1+1 Сильная NP-полнота задачи 4 гл.3

3-РАЗБИЕНИЕ. Задача о 4

бартерных сделках.

11.4. Л+ПР 1+2 Подходы к решению NP-полных 4 гл.3

задач с использованием

эвристических и приближенных

алгоритмов.

11.5.(*) Л+ПР 1+1 Веpоятностные алгоpитмы. 4

Вероятностное распознавание

составных чисел.

11.6.(*) Л+ПР 1+1 Класс PSPACE. Полнота задачи 4

QBF в этом классе. PSPACE- 4 гл.4

полные игpы.

11.7.(*) Л+ПР 2+1 Доказyемо тpyдные задачи. 1 гл.11

11.8. Л 2 Обзор абстрактной теории

сложности.

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

(выpажениях)

12.1. Л+ПР 2+2 Линейный алгоpитм

yнификации теpмов.

12.2. Л+ПР 2+2 Линейный алгоpитм для

опpеделения общих

подвыpажений.

12.3. Л+ПР 2+2 Алгоpитм для выводимости

pавенства выpажений.

_________________________________________________________________________

В С Е Г О 168

_________________________________________________________________________

Литература

Основная:

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

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

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

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

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

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

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

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

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

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