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

 

 

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

 

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

 

 

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

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

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

 

 

 

 

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

 

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

            __________________________________________  мены   (к-во)

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

                        занятия

_______________________________________________________________________

  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.