FPM 2001, ТОМ 7, ВЫПУСК 2, СТР. 597-614

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

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

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

Аннотация

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



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

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

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

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