"Специальные дискретные задачи"

Вопросы к экзамену по курсу доц. В. В. Бухваловой и доц. Н. С. Григорьевой

"Специальные дискретные задачи"

Раздел "Вычислительная геометрия"

Основные категории и типы алгоритмов, используемые в вычислительной геометрии (с примерами).
Модель вычислений. Основные характеристики алгоритмов.
Метод преобразования задач и его свойства.
Сортировка целых чисел (постановка задачи, сложность, оптимальный алгоритм).
Сортировка кортежей (оптимальный алгоритм).
Сортировка слиянием (спецификация, рекуррентное уравнение и два способа его решения).
Решение одного класса рекуррентных уравнений.
Основная теорема об алгебраическом дереве решений.
Задача об уникальности элементов и эквивалентные ей задачи вычислительной геометрии.
Задача о пересечении множеств и эквивалентные ей задачи вычислительной геометрии.
Задача о построении евклидова минимального остовного дерева.
Различные постановки задачи о выпуклой оболочке точек и доказательство их эквивалентности.
Алгоритм Грэхема и доказательство его оптимальности.
Методы аппроксимации выпуклой оболочки.
Задача о ближайшей паре на прямой и плоскости.
Свойства диаграммы Вороного.
Оптимальный алгоритм построения диаграммы Вороного.
Задача о максимумах множества точек (постановка задачи и связь с задачей построения выпуклой оболочки).
Оптимальный алгоритм нахождения максимумов множества точек на плоскости.
Применение линейного программирования для решения задач раскроя.
Теорема о минимальном квадрате для размещения гармонических квадратов. • Теорема о минимальном квадрате для размещения квадратов с заданной суммарной площадью.
Теорема о существовании специальной нумерации для размещения прямоугольников.
Теорема о конечном множестве размещений, содержащем оптимальное размещение.
Метод зон (спецификация ).
Правила сокращения перебора размещений в методе зон.

Раздел "Теория расписаний"

Основные модели и понятия теории расписаний
Система заданий с древовидной структурой, Алгоритм и доказательство его корректности.
Двухпроцессорные расписания для системы заданий с произвольным упорядочением. Алгоритм построения расписания.
Теорема о списочном алгоритме.
Задача составления расписания с прерываниями для независимых заданий.
Сравнение расписаний различных типов. Лемма об оценке общего времени простоя.
Сетевое планирование. Алгоритм нахождения времен наступления событий.
Двухпроцессорная конвейерная задача. Алгоритм Джонсона и доказательство его оптимальности.
Задача минимизации максимального штрафа.
Задачи для одного процессора с прерываниями. Теорема о максимальном количестве прерываний.
Задача минимизации числа запаздывающих заданий.
Задача минимизации суммарного штрафа
Общая задача параллельного упорядочения. Метод ветвей и границ.
Многопроцессорная конвейерная задача.
Алгоритмы решения задач об упаковке в контейнеры.
Гарантированные оценки точности алгоритмов решения задачи об упаковке в контейнеры.
Задачи составления расписаний с учетом затрат на передачу данных.
Алгоритм обнуления дуг.
Циклические задачи составления расписаний.
Приближенные алгоритмы составления расписаний. Сравнение различных алгоритмов.

ЛИТЕРАТУРА

Бухвалова В.В. Задача прямоугольного раскроя: метод зон и другие алгоритмы. — СПб.: СПбГУ, 2001.
Ласло М. Вычислительная геометрия и компьютерная графика на С++. — М.: «Издательство БИНОМ», 1997.
Препарата Ф., Шеймос М. Вычислительная геометрия: введение. — М.: Мир, 1989.
Григорьева Н.С. Теория расписаний. Методические указания. СПб.: СПбГУ, 1995.
Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы.- М.: Наука, 1984, 384 с.
Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы.- М.: Наука, 1989, 328 с.
Теория расписаний и вычислительные машины /Под ред. Э.Г.Коффмана - М.: Наука, 1984. 334 с.