Раздел 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 Функции хеширования. Задачи, решаемые с

помощью построения хеш-таблиц

Понятия хеш-функции и хеш-таблицы. Методы хеширования: метод деления, метод середины квадратов, метод свертывания

Коллизии. Методы разрешения коллизий: метод открытой адресации и метод цепочек

Задачи, решаемые с помощью построения хеш-таблиц

Литература: [8, с. 567-597]

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

1. Каков принцип построения хеш-таблиц?

2. Существуют ли универсальные методы построения хеш-таблиц? Ответ обоснуйте.

3. Почему возможно возникновение коллизий?

4. Каковы методы устранения коллизий? Охарактеризуйте их эффективность в различных ситуациях.

5. Назовите преимущества открытого и закрытого хеширования.

6. В каком случае поиск в хеш-таблицах становится неэффективен?

7. Как выбирается метод изменения адреса при повторном хешировании?

8. В чем заключается суть каждого метода для разрешения коллизии?

Список используемых источников

1. Кнут, Д. Искусство программирования. Т.1 / Д. Кнут. – М.: Вильямс, 2001. - 976 с.

2. Кнут, Д. Искусство программирования. Т.2 / Д. Кнут. – М.: Вильям, 2001. - 988 с.

3. Кормен, Т Алгоритмы: построение и анализ / пер. с англ. под ред. А. Шейя. – М.:МЦНМО, 2002. – 960 с.

4. Красиков, И. В. Алгоритмы. Просто, как дважды два / И. В. Красиков, И. Е. Красикова. – М.:Эксмо, 2007. – 256 с.

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

6. Макконнелл, Дж. Основы современных алгоритмов. / Дж. Макконнелл. – М: Техносфера, 2004. – 368 с.

7. Окулов, С. М. Программирование в алгоритмах / С. М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2002. – 341 с.

8. Седжвик, Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/ Сортировка/Поиск / пер. с англ. / Роберт Седжвик. – К: Издательство «ДиаСофт», 2001. – 688 с.

9. Хусаинов, Б. С. Структуры и алгоритмы обработки данных. Примеры на языке Си: учеб. пособие / Б. С. Хусаинов. – М.:Финансы и статистика, 2004. – 464 с.