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

Алехнович, М.В.; Канель-Белов, А.Я.; Сулейкин, А.О.

Авторы: Алехнович М.В., Канель-Белов А.Я., Сулейкин А.О.
Журнал: Математическое просвещение
Номер: 33
Год издания: 2024
Первая страница: 155
Последняя страница: 182
Аннотация: Статья посвящена решению задачи 32.9 (выпуск 32, с. 181). Пусть на плоскости отмечены две точки A и B и задано натуральное число n. Наша цель — построить на прямой, проходящей через эти точки, третью точку C так, чтобы длина отрезка AC была в n раз больше длины отрезка AB, с помощью линейки и (или) циркуля (при этом прямая AB считается проведённой). На каждом шаге мы можем либо проводить линейкой прямую через две отмеченные точки, либо строить окружность с центром в отмеченной точке радиусом, равным расстоянию между отмеченными точками. При пересечении проведённых прямых и окружностей возникают новые отмеченные точки. Обозначим через Ц(n) минимальное число шагов, необходимое при решении задачи одним циркулем, а через ЦЛ(n) — число шагов, необходимых при решении её циркулем и линейкой. Задача заключается в оценке асимптотического поведения функций Ц(n) и ЦЛ(n). Основной результат работы заключается в следующем. Существуют такие константы c1, c2 > 0, что: а) c1 ln n ¶ Ц(n) ¶ c2 ln n; б) c1 ln ln n ¶ ЦЛ(n) ¶ c2 ln n ln ln n . Наиболее интересный результат получается при нижней оценке функции ЦЛ(n), где совершенно неожиданно возникают чисто алгебраические понятия, такие как высота числа и др. Над статьёй совместно работали М. В. Алехнович и А. Я. Канель-Белов. Работа была завершена А. Я. Канель-Беловым и А. О. Сулейкиным.
Добавил в систему: Белов Алексей Яковлевич

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

ИСТИНА

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

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

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