ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
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 г.