ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2001, ТОМ 7, ВЫПУСК 2, СТР. 597-614

Сложность алгоритмов при построениях циркулем и линейкой

М. В. Алехнович
А. Я. Белов

Аннотация

Посмотреть как HTML    Посмотреть как рисунок    Посмотреть в формате LaTeX

Статья посвящена следующей задаче. Пусть на плоскости отмечены две точки $A$ и $B$ и задано натуральное число $n$. Наша цель -- построить на прямой, проходящей через эти точки, третью точку $C$ так, чтобы длина $AC$ была в $n$ раз больше длины $AB$, с помощью линейки и (или) циркуля (при этом прямая $AB$ считается проведённой). На каждом шаге мы можем либо проводить линейкой прямую через две отмеченные точки, либо окружность с центром в отмеченной точке радиуса, равного расстоянию между отмеченными точками. При пересечении проведённых прямых и окружностей возникают новые отмеченные точки. Обозначим через $Ц(n)$ минимальное число шагов, необходимое при решении задачи одним циркулем, а через $ЦЛ(n)$ -- необходимых при решении её циркулем и линейкой. Задача заключается в оценке асимптотического поведения функций $Ц(n)$ и $ЦЛ(n)$. Основной результат работы заключается в следующем: существуют такие константы $c$₁,c₂ > 0, что: а) $c$₁ ln n ≤ Ц(n) ≤ c₂ ln n, б) $c$₁ ln ln n ≤ ЦЛ(n) ≤ c₂ln n/ln ln n.

Наиболее интересный результат получается при нижней оценке функции $ЦЛ(n)$, где совершенно неожиданно возникают чисто алгебраические понятия, такие как высота числа и др.

Полнотекстовая версия статьи в формате PostScript (75 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k01/k012/k01216h.htm.
Изменения вносились 31 октября 2001 г.