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

Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

РАБОЧАЯ ПРОГРАММА дисциплины “ КОМБИНАТОРНЫЕ АЛГОРИТМЫ ” Для специальности: 010200 – “ПРИКЛАДНАЯ МАТЕМАТИКА” Для направлений: 510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА” (магистерские программы 510208 - Математическая кибернетика, 510209 - Математическое и программное обеспечение вычислительных машин)

552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” (магистерская программа 552809 - Технология разработки программных систем)

Санкт-Петербург 2000

Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” “УТВЕРЖДАЮ” Проректор по учебной работе проф. ___________ Ушаков В.Н. РАБОЧАЯ ПРОГРАММА Дисциплины “ КОМБИНАТОРНЫЕ АЛГОРИТМЫ ” Для специальности: 073000 (010200) – “ПРИКЛАДНАЯ МАТЕМАТИКА” Для направлений: 510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА” (магистерские программы 510208 - Математическая кибернетика, 510209 - Математическое и программное обеспечение вычислительных машин)

552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” (магистерская программа 552809 - Технология разработки программных систем)

Факультет компьютерных технологий и информатики (ФКТИ) Кафедра математического обеспечения и применения ЭВМ (МО ЭВМ) Курс – 5 Семестры – 10 Лекции

30- ч.

Экзамен – 10

семестр

Лабораторные занятия

15- ч.

Зачет – 10

семестр

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

45- ч. 30- ч. (число часов из учебного плана) 75- ч.

Примечание. В учебном плане 238 отсутствуют лабораторные работы, и дисциплина является сугубо теоретической.

2000

Рабочая программа обсуждена на заседании кафедры МО ЭВМ “____”_______________2000г., протокол №______.

Рабочая программа согласована с рабочими программами изученных ранее дисциплин: 1) Программирование (1, 2 семестры) 2) Алгоритмы и структуры данных (3, 4 семестры) 3) Дискретная математика (2 семестр) 4) Математическая логика и теория алгоритмов (4 семестр) 5) Алгебра и геометрия (1,2,3 семестры)

Рабочая программа утверждена на методической комиссии ФКТИ “____”_____________2000г.

Цель и задачи дисциплины Цели дисциплины Целью дисциплины “ Комбинаторные алгоритмы ” является изучение и освоение базовых понятий, моделей, методов, структур данных и алгортимов, применяемых при решении и анализе комбинаторных задач определенного класса, а именно: задач вычислительной геометрии (Computational Geometry). Задачи дисциплины • Ознакомить с классом комбинаторных задач вычислительной геометрии и их применениями в различных областях информатики. • Показать эффективность применения изученных ранее моделей, методов и структур данных в алгоритмах вычислительной геометрии. • Освоить новые теоретические факты, модели, специальные структуры данных и методы, лежащие в основе решения комбинаторных геометрических задач. • Ознакомить с основными алгоритмами комбинаторной вычислительной геометрии, с результатами и методами анализа их сложности. • Сформировать навыки корректной и эффективной реализации геометрических алгоритмов, включая элементы их компьютерного исследования и визуализации их работы. Требования к уровню освоению содержания дисциплины В результате изучения дисциплины студенты должны (а) Знать - основные задачи комбинаторной вычислительной геометрии; - основные геометрические понятия и факты, лежащие в основе комбинаторных алгоритмов вычислительной геометрии; - модели вычислений, нижние оценки сложности и фактическую сложность основных комбинаторных алгоритмов вычислительной геометрии; - специальные методы и структуры данных, применяемые при разработке комбинаторных алгоритмов вычислительной геометрии; (б) Уметь - самостоятельно составлять машинные алгоритмы и программы решения комбинаторных задач вычислительной геометрии на основе известных методов и алгоритмов; - модифицировать известные алгоритмы, реализовывать структуры данных, повышающие эффективность комбинаторных алгоритмов вычислительной геометрии; - оценивать сложность комбинаторных алгоритмов на основе теоретических (нижних) оценок, а также используя машинные эксперименты; (в) Иметь представление о - об оптимальных по сложности алгоритмах вычислительной геометрии; - математических методах анализа сложности геметрических задач и алгоритмов; - об областях применения алгоритмов вычислительной геометрии в информатике, программировании и прикладной матеметике.

Содержание рабочей программы Введение Предмет дисциплины (Комбинаторные задачи алгоритмической геометрии) и ее задачи. Исторический обзор. Содержание и форма проведения занятий. Связь с другими дисциплинами учебного плана (в первую очередь с дисциплиной алгоритмы и структуры данных). Часть 1. Алгоритмические модели и специальные структуры данных Тема 1.1. Модели вычислений и сложность алгоритмов Модели вычислений и абстрактные машины. Метод преобразования задач. Нижние и верхние оценки сложности. Деревья решений и нижние оценки сложности. Тема 1.2. Специальные структуры данных в комбинаторных геометрических задачах Структуры данных для работы с множествами: словарь, приоритетная очередь, сливаемая пирамида, сцепляемая очередь. Реализация сцепляемых очередей на базе АВЛ-деревьев. Рандомизированные двоичные деревья поиска и реализация на их основе сцепляемых очередей. Деревья отрезков. Определение, назначение, свойства, построение, операции. Представление планарных графов реберным списком с двойными связями (РСДС). Обход ребер, инцидентных вершине. Обход ребер вокруг грани. Часть 2. Выпуклые оболочки Тема 2.1. Основные алгоритмы Выпуклая оболочка: определения. Постановка задачи и нижняя оценка сложности. Представление многоугольника. Обход многоугольника. Использование векторного произведения как базовой операции. Метод обхода Грэхема. Вариант с упорядочиванием относительно внутренней точки. Вариант с упорядочиванием относительно крайней точки. Модификация Эндрью. Обход методом Джарвиса. Сложность в худшем и среднем. Быстрый алгоритм (QuickCH) построения выпуклой оболочки. Алгоритм построения выпуклой оболочки на основе сбалансированного разделения и слияния. Модификация с построением «мостиков». Построение выпуклой оболочки в реальное время.

Тема 2.2. Расширения и приложения Алгоритмы аппроксимации выпуклой оболочки. Охватывающая оболочка. Оценка приближения. Задача о глубине множества и ее решение. Задача о диаметре множества точек. Нижняя оценка (связь с задачей разделимость множеств). Противолежащие пары. Оптимальный алгоритм нахождения диаметра множества. Часть 3. Геометрический поиск Тема 3.1. Введение в геометрический поиск Виды поиска. Массовый и уникальный поиск. Задача локализации. Задача регионального поиска. Меры оценки алгоритмов поиска: время запроса, память, время предобработки, время коррктировки. Пример решения задачи регионального поиска (подсчета) – метод локусов. Тема 3.2. Задачи локализации точки Принадлежность многоугольнику. Метод луча. Выпуклый многоугольник. Звездный многоугольник. Локализация точки на планарном подразбиении. Метод полос. Предобработка: алгоритм плоского заметания. Локализация. Локализация точки на планарном подразбиении. Метод цепей. Монотонные цепи. Полное множество монотонных цепей графа. Регулярный граф и построение полного множества его монотонных цепей. Регуляризация графа. Локализация в множестве монотонных цепей. Локализация точки на планарном подразбиении. Метод детализации триангуляции. Предобработка. Локализация. Анализ сложности. Тема 3.3. Задачи регионального поиска Метод сетки. Метод квадрантного дерева. Построение адаптивного квадрантного дерева. Процедура поиска. Анализ в худшем случае и в среднем. Метод 2-D дерева. Построение дерева. Поиск. Анализ худшего случая. Региональный поиск. Метод прямого доступа. Двухэтапная схема Дерево отрезков. Метод дерева регионов в задаче регионального поиска. Часть 4. Задачи о близости Тема 4.1. Набор задач о близости Набор задач о близости (Ближайшая пара, Все ближайшие соседи, Евклидово минимальное остовное дерево - ЕМОД, Триангуляция, Поиск ближайшего

соседа). Задача единственности элементов как вычислительный прототип. Нижняя граница сложности. Нижние оценки сложности задач о близости. Тема 4.2. Решение задач о близости Задача о ближайшей паре. Метод сбалансированного разделения и слияния. Диаграмма Вороного. Определение, свойства. Триангуляция Делоне. Построение диаграммы Вороного. Разделяющая цепь. Построение разделяющей цепи. Нижняя оценка для построения диаграммы Вороного. Решение задач о близости с помощью диаграммы Вороного. Решение задачи о Евклидовом МОД. Заключение Другие задачи комбинаторной вычислительной геометрии. Приложения. Перспективы.

Перечень лабораторных работ 1. Представление линейных упорядоченных списков (сцепляемых очередей) АВЛ-деревьями и/или рандомизированными деревьями (Treaps) 2. Выпуклая оболочка - 1 - Алгоритм Грэхема - Алгоритм Джарвиса 3. Выпуклая оболочка - 2 - Быстрый алгоритм (QuickCH). - Быстрый алгоритм на основе сбалансированного слияния I. - Быстрый алгоритм на основе сбалансированного слияния II (с построением «мостиков»). 4. Выпуклая оболочка - 3 - Построение выпуклой оболочки в реальное время. 5. Выпуклая оболочка - 4 - Аппроксимация выпуклой оболочки. - Диаметр множества точек 6. Геометрический поиск. Локализация точки - Локализация точки на планарном подразбиении. Метод полос - Локализация точки на планарном подразбиении. Метод цепей - Локализация точки на планарном подразбиении. Метод детализации триангуляции 7. Геометрический поиск. Региональный поиск. - Метод квадрантного дерева. - Метод 2-D дерева.

- Метод прямого доступа. Двухэтапная схема. - Метод дерева регионов в задаче регионального поиска . 8. Задачи о близости - Задача о ближайшей паре. - Построение диаграммы Вороного. Триангуляция Делоне. - Задача о Евклидовом МОД. Расчет учебных часов по видам занятий № темы

Название разделов (частей) и тем

Введение

Лекции

Лаборат. занятия

0.5

Объем учебных часов АудиСаВсего тор. мост. Заня- Работа тия 0.5 0.5

Семестр 10

Часть 1.

Алгоритмические модели и специальные структуры данных

10

Тема 1.1.

Модели вычислений и сложность алгоритмов

1

1

1

2

10

Тема 1.2.

3

3

3

6

10

Часть 2.

Специальные структуры данных в комбинаторных геометрических задачах Выпуклые оболочки

Тема 2.1.

Основные алгоритмы

5

3

8

5

13

10

Тема 2.2.

Расширения и приложения

2

1

3

2

5

10

Часть 3.

Геометрический поиск

Тема 3.1.

Введение в геометрический поиск

2

Тема 3.2.

Задачи локализации точки

5

Тема 3.3.

Задачи регионального поиска

5

Часть 4.

. Задачи о близости

Тема 4.1.

Набор задач о близости

2

Тема 4.2.

Решение задач о близости

4 0.5 30

10

10 2

2

4

10

4

9

5

14

10

4

9

5

14

10 10

Заключение ИТОГО:

2

2

4

10

3

7

5

12

10

0.5 45

30

0.5 75

10

15

ЛИТЕРАТУРА К-во экз. в библ. (на кафедре)

№

Название, библиографическое описание

1.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение.- М.: Мир, 1989.-478 с. Майкл Ласло. Вычислительная геометрия и компьютерная графика на С++.-М.: "Издательство БИНОМ", 1997.-304 с. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО, 1999.- 960 с.

2. 3.

Авторы: к.т.н., доцент

С.А.Ивановский

Рецензент к.т.н., доцент каф.ВМ-1

Г.М.Коновалов

Зав. кафедрой Математического обеспечения и применения ЭВМ (разработчик программы и держатель учебного плана) Д.т.н., профессор

А.Р.Лисс

Декан факультета Компьютерных технологий и информатики (обеспечивающего дисциплину) Д.т.н., профессор

И.В.Герасимов

Зав. отделом учебной литературы

О.Н.Смирнова

Председатель методической комиссии факультета Компьютерных технологий и информатики (обеспечивающего дисциплину) к.т.н., доцент

Л.А.Чугунов

Руководитель методического отдела, к.т.н., доцент

Л.А.Марасина