Сборник решений задач по математике для поступающих в вузы. Группа Б

Сборник решений задач по математике. Пособия помогут при подготовке к выпускным экзаменам в средней школе, сдаче ЕГЭ и вступительным экзаменам в вуз. Книги адресованы школьникам старших классов, абитуриентам, репетиторам и преподавателям.
В помощь абитуриентам публикуется, полный сборник задач по математике с решениями под редакцией М.И. Сканави по всем группам сложности.

Сборник решений задач по математике для поступающих в вузы. Группа Б

Сборник решений задач по математике

Докажите, что задача упорядочения п чисел требует по порядку не менее п log п сравнений.
Указание. Число различных результатов работы программы равно, с одной стороны n! > (п/3)п, а с другой стороны — не больше 3т, где т — число выполненных сравнений (исходов сравнения три: >,=,<).
Задача точного нахождения минимального числа сравнений при больших п, поставленная польским математиком Г.Штейнгаузом, не решена до сих пор.
Из задачи 302 следует, что задачу построения триангуляции для данных п произвольных точек нельзя решить со сложностью, по порядку меньшей nlogn.
2.2. Быстрое вычисление различных мер
Отметим одну тонкость. В модели геометрических построений построение триангуляции для п точек указанного выше примера можно конечно выполнить за 0(п) операций, так как упорядочение п данных точек на прямой в этой модели делать не нужно: глаз сам видит, в каком порядке расположен точки.
Если же использовать вычислительную модель алгебраические решающие деревья, то нижние оценки п log п можно получить для многих задач так называемой вычислительной геометрии (см. об этом книгу [55]), в частности для задачи поиска одной пары ближайших соседей, задачи поиска всех пар ближайших соседей, задачи построения минимального дерева, стягивающего данные точки (таким деревом для данных п точек является связная система п — 1 отрезков с концами в данных точках, т.е. такая, что по этим отрезкам можно пройти из любой точки в любую другую).
Действительно, если п разных точек лежат на прямой, то решив задачу о минимальном дереве для них мы получим монотонное упорядочение этих точек, а это дает нижнюю оценку по порядку п log п. Если же п не обязательно разных точек лежат на прямой, то решив задачу о ближайшей паре, мы узнаем, есть ли среди данных точек совпадающие, или нет (совпадающие точки дают очевидно ближайшую пару). Задача же проверки данных п чисел на предмет равенства каких-то из них в модели алгебраических деревьев решений решается со сложностью не меньше по порядку п log п (см. [55]).
Существенно более сложно доказывается, что для задач о ближайших соседях, задачи о минимальном дереве, задачи о триангуляции решаются со сложностью 0(п log п) (см. [55]). Для этого используются, например, такие понятия как диаграмма Вороного4 и триангуляция Делоне5. Эти два понятия тесно связаны друг с другом (триангуляция Делоне является двойственным графом к диаграмме Вороного) и оба строятся со сложностью О (n logn). Исходя из триангуляции Делоне можно построить минимальное дерево даже со сложностью 0(п) (известно, что минимальное стягивающее дерево в произвольном графе с е ребрами, которым сопоставлены числа, можно найти со сложностью 0(еloge) и со сложностью, меньшей е найти нельзя). Исходя из диаграммы Вороного для данных п точек поиск ближайшего соседа О (logn) при использованном объеме памяти О(п), а построить выпуклую оболочку этих точек можно построить со сложностью 0(п), Более сложной оказывается упоминавшаяся выше задача построения триангуляции внутренности простого п—угольника (потому, что на триангуляцию наложено некоторое ограничение), но она все равно решается в [55] со сложностью 0(n logn).
Для темы нашей книги видимо более интересной является следующая задача.
Построить выпуклую оболочку п точек со сложностью 0(п logn).
Указание. Известны разные алгоритмы для этой задачи. Далее будет кратко изложен алгоритм Грехэма-Эндрю. Спроектируем перпендикулярно точки на произвольную прямую и выбрав крайние проекции, получим два перпендикуляра, являющиеся параллельными опорными прямыми для искомой выпуклой оболочки. Сложность этого построения равна 0(п). Пусть А,В — точки выпуклой оболочки, лежащие на этих прямых. Проведем через них прямую. Она разбивает наше множество (и его выпуклую оболочку) на два подмножества (выпуклыми оболочками которых являются указанные части искомой выпуклой оболочки). Достаточно построить их выпуклые оболочки по отдельности, и их очевидное объединение будет искомой выпуклой оболочкой данного множества. Рассмотрим любое из указанных подмножеств pi,… ,Рш) т < п. Они выделяется «бесплатно», если мы используем модель геометрических построений, или со сложностью 0(п) в вычислительной модели. Упорядочим этим т точек в порядке расположения их указанных проекций. В модели геометрических построений это тоже «бесплатно», а в вычислительной модели указанное упорядочение выполняется со сложностью O(nlogn) любым хорошим алгоритмом сортировки (см., например, [2]). Просматривая точки в указанном порядке, удаляем каждую точку pi, если она лежит с той же стороны от отрезка pt_i,pj+i, что и отрезок А, В (т.е. если точка pi нарушает выпуклость ломаной А = р\,.. .рі+1), а потом делаем такую же проверку для точек Рі+і,Рг-і,Рі-2 (потому что здесь могло возникнуть нарушение выпуклости, которого до удаления точки рг не было), и опять удаляем «плохую» точку и т.д. Так точки только удаляются, а выпуклая оболочка при этом не меняется, то этот алгоритм заканчивает работу не позднее, чем на т — 3-ем шаге. Сложность всего вычисления равна 0(п). Аналогично вычисляем выпуклую оболочку второго подмножества. В модели геометрических построений сложность всего алгоритма равна 0(п), но в вычислительной модели она равна 0(п log п) из-за необходимости сортировки.
(Шеймос) Для вычислительной модели показать, что сложность алгоритма построения выпуклой оболочки не может быть меньше по порядку п log п.
Указание. Пусть Хі,г = 1,п — произвольный набор различных чисел и рі = (хі,х?) — п точек на параболе у = х2. При построении выпуклой оболочки этих точек они упорядочиваются по величине абсциссы. Поэтому решается задача сортировки п чисел. А ее сложность по порядку не менее nlogn согласно задаче 302.

[свернуть]

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

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