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

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

Авторы: Алехнович М.В., Белов А.Я.
Журнал: Фундаментальная и прикладная математика
Том: 7
Номер: 2
Год издания: 2001
Издательство: Интуит
Местоположение издательства: М.
Первая страница: 597
Последняя страница: 614
Аннотация: There is a well-known theorem by Moor and Masceroni which asserts that each geometric construction which is possible using both a compass and a straightedge is possible using a compass only. However, the procedure of construction using a compass only can require unbounded number of steps and it is easy to see that in some cases the existence of the straightedge can economize the number of the steps essentially. \par The main purpose of the paper is to compare complexity of constructions using a compass only and using both a compass and a straightedge. Namely, the following problem is under consideration. Let $A$ and $B$ be two points on the plane and a natural number $n$ is given. The problem is to find the third point $C$ on the line containing $A$ and $B$ such that the length $AC$ is $n$ times larger than the length $AB$ using either only a compass or a compass and a straightedge. On each step it is possible either to construct a straight line contained two constructed points or a circle with a constructed point as a center and with a radius equal to the distance between two constructed points. \par In the case of constructions with only a compass all lines are assumed to be defined by couples of points. Denote the minimal number of steps necessary to solve the problem under consideration using only a compass by $C(n)$, and the minimal number of steps necessary to solve this problem using a compass and a straightedge by $CS(n)$. It can be proved within the limits of school program that $\frac{C(n)}{CS(n)}$ is unbounded, in particular this fraction goes to infinity if $n=2^{2^k}$ and $k\to \infty$. In the paper the asymptotic behavior of the functions $C(n)$ and $CS(n)$ as $n$ goes to the infinity is estimated. It is proved that there exist constants $c_1, c_2,c_3, c_4>0$ such that $c_1\ln n \le C(n)\le c_2 \ln n$ and $c_3 \ln \ln n \le CS(n) \le \frac{c_4 \ln n}{\ln\ln n}$. For the proof of a lower bound for $CS(n)$ a very interesting purely algebraic technique appears, namely, the notion of height of a number, and some matrix algebras are used, too.\par At the end of the paper a list of open problems concerning this subject is presented. For example: Is it true that $\frac{S(n)}{CS(n)}$ is unbounded, where $S(n)$ is the minimal number of steps necessary to solve the problem under consideration using only a straightedge? Is it true that the undeterministic algorithm is equivalent to the deterministic algorithm? By the undeterministic algorithm in the above setting the authors mean the algorithm in which it is possible to take arbitrary points at the plane as beginning for some constructions (not only constructed points).Reviewer: Alexander E.Guterman (Moskva)
Добавил в систему: Белов Алексей Яковлевич

	ИСТИНА	Войти в систему Регистрация
	Интеллектуальная Система Тематического Исследования НАукометрических данных
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

Интеллектуальная Система Тематического Исследования НАукометрических данных

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

Прикрепленные файлы