RUS  ENG
Полная версия
ЖУРНАЛЫ // Фундаментальная и прикладная математика // Архив

Фундамент. и прикл. матем., 2001, том 7, выпуск 2, страницы 597–614 (Mi fpm561)

Математическое просвещение

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

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

Дом научно-технического творчества молодежи

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

Ключевые слова: сложность вычислений, высота числа, алгебраическая сложность.

УДК: 510.52+514.112

Поступила в редакцию: 01.12.1996



Реферативные базы данных:


© МИАН, 2024