Анатолий Карацуба
Анатолий Алексеевич Карацуба (его имя часто пишется Анатолий ) ( русский : Анато́лий Алексе́евич Карацу́ба ; Грозный , Советский Союз , 31 января 1937 г. - Москва , Россия , 28 сентября 2008 г. [1] ) был русским математиком , работавшим в области аналитической теории чисел . , p -адические числа и ряды Дирихле .
Большую часть своей студенческой и профессиональной жизни был связан с механико-математическим факультетом МГУ , защитив докторскую диссертацию. там под названием «Метод тригонометрических сумм и теоремы о промежуточных значениях» в 1966 году. [2] Позже он занимал должность в Математическом институте им. В. А. Стеклова Академии наук . [2]
Алгоритм Карацубы является самым ранним из известных алгоритмов умножения « разделяй и властвуй » и существует как частный случай его прямого обобщения, алгоритма Тума-Кука . [3]
Основные научные труды Анатолия Карацубы опубликованы более чем в 160 научных статьях и монографиях. [4]
Будучи студентом МГУ имени Ломоносова, Карацуба посетил семинар Андрея Колмогорова и нашел решение двух задач, поставленных Колмогоровым. Это было необходимо для развития теории автоматов и положило начало новой ветви математики — теории быстрых алгоритмов.
В статье Эдварда Ф. Мура [ 5] автомат (или машина) определяется как устройство с состояниями, входными и выходными символами. Доказаны девять теорем о строении и опытах с ним. Позже такие машины получили название машин Мура . В конце статьи, в главе «Новые проблемы», Мур формулирует задачу улучшения оценок, полученных им в теоремах 8 и 9:
