Раздел 3 Алгоритмы вычислительной геометрии

Тема 3.1 Задачи вычислительной геометрии и методы их

Решения

Задачи определения взаимного расположения отрезков, прямых и плоскостей

Алгоритмы построения выпуклой оболочки: алгоритм Грэхема, алгоритм Джарниса

Алгоритм отыскания пары ближайших точек

Алгоритмы нахождения площадей фигур

Литература: [3, с. 810-836]; [7, с. 222-251]

Вопросы для самоконтроля

1 Опишите взаимное расположение точки и прямой на плоскости.

2 Опишите взаимное расположение двух прямых на плоскости.

3 Опишите алгоритм проверки принадлежности точки внутренней области многоугольника.

4 Какой многоугольник называется простым?

5 Как найти площадь простого многоугольника?

6 Дайте определение понятию выпуклой оболочки.

7 Опишите алгоритмы построения выпуклой оболочки для N точек плоскости.

8 Опишите методы нахождения корней уравнения: деления отрезка пополам, хорд, Ньютона.

9 Опишите алгоритмы поиска площади фигуры, ограниченной функциями: средних (левых, правых) прямоугольников, трапеции, парабол.

Раздел 4 Рандомизированные алгоритмы

Тема 4.1 Генерирование случайных чисел, распределенных по

Заданным законам. Задачи, решаемые с помощью

Генераторов случайных чисел

Генерирование равномерно распределенных случайных чисел: линейный конгруэнтный метод, аддитивный метод Митчелла и Мура, рандомизация перемешиванием

Нормальное распределение: метод полярных координат, метод прямоугольника-клина-хвоста

Показательное распределение: метод логарифма, метод случайной минимизации

Задачи, решаемые с помощью генераторов случайных чисел: статистические вычисления, моделирование систем массового обслуживания

Литература: [4, с. 207-213]

Вопросы для самоконтроля

1 Опишите линейный конгруэнтный метод генерирования равномерно распределенных случайных чисел.

2 Опишите аддитивный метод Митчелла генерирования равномерно распределенных случайных чисел.

3 Опишите метод Мура генерирования равномерно распределенных случайных чисел.

4 Опишите метод рандомизации перемешиванием.

5 Опишите метод полярных координат для получения нормально распределенных случайных чисел.

6 Опишите метод прямоугольника-клина-хвоста для получения нормально распределенных случайных чисел.

7 Опишите метод логарифма для получения случайных чисел, распределенных по показательному закону.

8 Опишите метод случайной минимизации для получения случайных чисел, распределенных по показательному закону.

Раздел 5 Хеширование и хеш-таблицы

Тема 5.1 Функции хеширования. Задачи, решаемые с