Карацуба Анатолий Алексеевич: биография
В 1960 году на механико-математическом факультете МГУ начал работать семинар по математическим вопросам кибернетики под руководством А. Н. Колмогорова, где была сформулирована «гипотеза » и поставлен ряд задач об оценке сложности других подобных вычислений. Анатолий Карацуба, надеясь получить нижнюю оценку величины , нашёл новый метод умножения двух n-значных чисел, известный теперь как умножение Карацубы, с оценкой сложности
и тем самым опровергнув гипотезу , о чём сообщил Колмогорову после очередного заседания семинара. На следующем заседании семинара этот метод был рассказан самим Колмогоровым, и семинар прекратил свою работу. Первая статья с описанием умножения Карацубы была подготовлена самим Колмогоровым, где он представил два разных и несвязанных друг с другом результата двух своих учеников. Хотя в статье Колмогоров чётко отметил, что одна теорема (не связанная с быстрым умножением) принадлежит Ю. Офману, а другая теорема (с первым в истории быстрым умножением) — А. Карацубе, эта публикация двух авторов надолго сбила с толку читателей, которые полагали, что оба автора внесли вклад в создание метода быстрого умножения, и даже называли этот метод двумя именами. Метод Карацубы впоследствии был обобщён до парадигмы «разделяй и властвуй», другими важными примерами которой являются метод двоичного разбиения (), двоичный поиск, метод бисекции и др.
Впоследствии на основе этой идеи А. Карацубы были построено множество быстрых алгоритмов, самыми известными из которых являются его непосредственные обобщения, такие как метод умножения Шёнхаге-Штрассена, метод матричного умножения Штрассена и быстрое преобразование Фурье.
Алгоритм Анатолия Карацубы внедрён практически во все современные компьютеры, и не только в качестве software, но и как hardware.
Основные исследования
В своей статье «О математических работах профессора Карацубы», посвящённой 60-летнему юбилею А. А. Карацубы, его ученики Г. И. Архипов и В. Н. Чубариков так описывают особенности научных работ А. А. Карацубы:
Основные исследования А. А. Карацубы опубликованы более чем в 160 научных статьях и монографиях.
Тригонометрические суммы и тригонометрические интегралы
А. А. Карацуба построил новый -адический метод а теории тригонометрических сумм. Полученные им оценки так называемых -сумм вида
привели к новым границам нулей -рядов Дирихле по модулю, равному степени простого числа, к выводу асимптотической формулы для числа варинговского сравнения вида
решению проблемы распределения дробных долей многочлена с целыми коэффициентами по модулю . А. А. Карацуба первый реализует в -адической форме «принцип вложения» Эйлера-Виноградова и строит -адический аналог - чисел Виноградова при оценке числа решений сравнения варинговского типа.
Пусть
причём
где — простое число. А. А. Карацуба доказал, что в этом случае для всякого натурального числа существует такое, что для любого всякое натуральное число представимо в виде (1) при , а при существуют такие, что сравнение (1) неразрешимо.
Этот новый подход, найденный А. А. Карацубой, привёл к новому -адическому доказательству теоремы о среднем И. М. Виноградова, играющей центральную роль в методе тригонометрических сумм Виноградова.
Ещё одним элементом -адического метода А. А. Карацубы является переход от неполных систем уравнений к полным за счёт локального -адического изменения неизвестных.
Пусть — произвольное натуральное число, , и целое число определяется неравенствами . Рассмотрим систему уравнений
А. А. Карацуба доказал, что для числа решений этой системы уравнений при справедлива оценка
Для неполных систем уравнений, в которых переменные пробегают числа с малыми простыми делителями, А. А. Карацуба применил мультипликативный сдвиг переменных. Это привело к качественно новой оценке тригонометрических сумм и новой теореме о среднем для таких систем уравнений.
где — фиксированное число.
В данном случае показателем сходимости называется такое значение , что сходится при и расходится при , где сколь угодно мало. Было установлено, что интеграл сходится при и расходится при .
Тогда же была решена и аналогичная проблема для интеграла
где — целые числа, удовлетворяющие условиям
А. А. Карацубой и его учениками было установлено, что интеграл сходится, если и расходится, если .
с нулевым свободным коэффициентом, , — -мерный вектор, составленный из коэффициентов , то интеграл
сходится при , где — наибольшее из чисел
← предыдущая следующая →
Страницы: 1 2
Комментарии
Комментарии
знаменитый немецкий математик
французский математик
английский физик и математик
древнегреческий математик, философ, путешественник, создатель школы пифагорейцев
французский математик, признанный лидер математиков Франции во второй половине XIX века
датский математик, статистик и инженер, основатель научного направления по изучению трафика в телекоммуникационных системах и теории массового обслуживания
французский математик, работавший в области дифференциальной топологии и теории категорий
французский математик и логик