RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Фундамент. и прикл. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

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

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

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

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

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

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

Полный текст: PDF файл (897 kB)

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

Тип публикации: Научно-популярный, образовательный материал
УДК: 510.52+514.112
Поступила в редакцию: 01.12.1996

Образец цитирования: М. В. Алехнович, А. Я. Белов, “Сложность алгоритмов при построениях циркулем и линейкой”, Фундамент. и прикл. матем., 7:2 (2001), 597–614

Цитирование в формате AMSBIB
\RBibitem{AleBel01}
\by М.~В.~Алехнович, А.~Я.~Белов
\paper Сложность алгоритмов при построениях циркулем и линейкой
\jour Фундамент. и прикл. матем.
\yr 2001
\vol 7
\issue 2
\pages 597--614
\mathnet{http://mi.mathnet.ru/fpm561}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1866477}
\zmath{https://zbmath.org/?q=an:1017.51018}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/fpm561
  • http://mi.mathnet.ru/rus/fpm/v7/i2/p597

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Фундаментальная и прикладная математика
    Просмотров:
    Эта страница:494
    Полный текст:120
    Первая стр.:1

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019