Построение и преобразования графиков. Параметры. Часть 1.

Построение и преобразования графиков. Параметры. Пособие предназначено для углубленного изучения школьного курса математики, содержит большое количество разноуровневого тренировочного материала. В книге представлена программа для проведения элективных курсов в профильных и предпрофильных классах. Пособие адресовано широкому кругу учащихся, абитуриентов, студентов педагогических вузов, учителей.

Построение и преобразования графиков. Параметры. Часть 1.

Построение и преобразования графиков. Параметры. Часть 1.

Задачу максимизации (минимизации) линейной функции от двух переменных с п линейными ограничениями (это двумерная задача линейного программирования) можно решить со сложностью 0{п log п).
Указание. Вначале строим пересечение заданных полуплоскостей со сложностью O согласно задаче 309 и получаем выпуклый т—угольник, т < п. Минимизация (максимизация) данной линейной функции на этом т—угольнике равносильна проведению опорной прямой, старшие коэффициенты которой определяются этой функцией. Сложность максимизации (минимизации) поэтому согласно задаче 310 равна O.
Глава 2. Неравенства для выпуклых фигур и тел
Удивительно, что казалось бы более сложную задачу линейного программирования Меджидцо и Дайер независимо решили со сложностью О(п). Дело в том, что им удалось сделать это, не строя явно выпуклый многоугольник, на котором максимизируется (минимизируется) линейная функция. Этот алгоритм (довольно сложный) можно найти в [55]. Они же показали, что и трехмерная задача линейного программирования решается со сложностью О(п). Меджидо также показал (см. [55]), модифицировав свой алгоритм, что задача вычисления числа R — радиуса наименьшего круга, покрывающего данные п точек, также может быть решена со сложностью 0(п) Так как этот алгоритм сложен, предлагаем более простую задачу
Вычислить объемлющий радиус R для данных п точек со сложностью 0(п2) и памятью 0(1).
Указание. Непосредственное применение задачи 26 дает алгоритм с оценкой 0(п3). Но можно вначале взять любую накрывающую данные точки окружность, потом уменьшить ее радиус так, чтобы на ней оказалась одна из данных точек, потом можно уменьшить радиус (и сдвинуть центр) так, чтобы на накрывающей окружности оказалось две точки (все это делается со сложностью О(п), если они образуют диаметр окружности, то все закончено, в противном случае можно, уменьшая радиус и сдвигая центр построить накрывающую окружность с тремя точками на ней (опять со сложностью 0(п)), и если бы этот треугольник был бы остроугольным, то это и была бы минимальная накрывающая окружность. Если же треугольник тупоугольный, то все данные точки, лежащие на окружности, содержатся на ее дуге меньшей половины окружности. Опять сдвигая центр и уменьшая радиус, можно получить объемлющую окружность, на которой появится еще минимум одна из данных точек, не лежащая на этой дуге, и т.д. На самом деле двигать окружности не надо, достаточно для соответствующих треугольников вычислять (строить) радиусы описанных окружностей и из них выбирать максимум с помощью известного алгоритма. Для вычисления изменений радиуса можно использовать формулу для радиуса описанного круга R = abc/As. Чтобы избежать вычисления корней, можно использовать формулу R2 = о262с2/1652, а площадь треугольника вычислять как в задаче 300.
Общая же задача линейного программирования с п линейными ограничениями решается пока только со сложностью п0<. Наилучшие результаты в этом направлении получены Ю. Е. Нестеровым и их можно найти в [46]. Знаменитый же алгоритм симплекс-метода имеет только экспоненциальную оценку сложности, причем показано на специально построенных примерах, что ее нельзя заменить на полиномиальную. Однако на практике различные его модификации по-прежнему остаются наиболее быстрыми.
Рассмотрим теперь задачу вычисления диаметра у данной точечной совокупности.
Найти все диаметры п—точечного множества со сложностью O.
Указание. Сначала вычислим выпуклую оболочку со сложностью 0(п log п). Задачу достаточно решить для нее. Пусть она будет т—угольником. Проведем через одну точку все прямые, параллельные его сторонам. Они образуют т углов с общей вершиной. Проведем биссектрисы этих углов. Все это требует сложности 0(тп) = 0(п) в любой из моделей вычисления. Для каждой из этих биссектрис построим пару параллельных ей опорных прямых со сложностью O(logm). На них лежит только по одной вершине тп—угольника. Эти вершины образуют отрезок. Нужный нам диаметры находятся среди этих отрезков. Действительно, пусть есть какой-то диаметр. Проведем через его концы перпендикуляры. Согласно задаче 22 они являются опорными прямыми и не содержат сторон многоугольника. Повернем их на минимальный возможный угол так, чтобы оба они стали параллельны одной из построенных биссектрис. В силу минимальности поворота обе полученные параллельные прямые по прежнему образуют опорную полосу для т—угольника. Эта полоса появлялась в нашем построении, значит один из построенных выше отрезков совпадает с данным диаметром, ч.т.д. Чтобы найти все диаметры, достаточно упорядочить построенные отрезки по величине. Это можно сделать со сложностью O, причем найдем все диаметры, которых не больше га, как видно из проведенного рассуждения. Впрочем, можно найти все диаметры, сделав rn — l сравнений с помощью стандартного алгоритма поиска максимума.

[свернуть]

Похожие страницы

Предложения интернет-магазинов