Карацуба Анатолій Олексійович

У Вікіпедії є статті про інших людей із прізвищем Карацуба.

Анатолій Олексійович Карацу́ба (31 січня 1937, Грозний — 28 вересня 2008, Москва) — радянський і російський математик. Творець першого швидкого методу в історії математики — методу множення великих чисел (множення Карацуби).

Карацуба Анатолій Олексійович
рос. Анатолий Алексеевич Карацуба
Народився	31 січня 1937(1937-01-31)^[1] Грозний, РРФСР, СРСР^[1]
Помер	28 вересня 2008(2008-09-28)^[1] (71 рік) Москва, Росія
Країна	Росія  СРСР
Діяльність	математик, викладач університету
Alma mater	^d МДУ^[2]
Галузь	математичний аналіз, теорія чисел, фізика, теорія алгоритмів і математика^[3]
Заклад	Математичний інститут імені Стєклова МДУ
Науковий ступінь	доктор фізико-математичних наук
Науковий керівник	^d
Відомі учні	^d
Аспіранти, докторанти	^d ^d ^d ^d^[2] ^d^[2] ^d^[2] ^d^[2] ^d^[2] ^d^[2] ^d^[2] ^d^[2] ^d^[2] ^d^[2] ^d^[2] ^d^[2]
Діти	^d
Нагороди
Карацуба Анатолій Олексійович у Вікісховищі

Навчання і робота

А. А. Карацуба — випускник середньої школи

Анатолій Карацуба навчався в 1944—1954 роках у середній чоловічій школі № 6 міста Грозного і закінчив її зі срібною медаллю. Вже в ранні роки він виявив виняткові здібності до математики, розв'язуючи в молодших класах завдання, які давали в математичному гуртку старшокласникам.

1959 року закінчив механіко-математичний факультет МДУ ім. Ломоносова. 1962 року він став кандидатом фізико-математичних наук з дисертацією «Раціональні тригонометричні суми спеціального вигляду та їх застосування» (науковий керівник — Н. М. Коробов), і почав працювати на факультеті в МДУ. 1966 року він захистив докторську дисертацію «Метод тригонометричних сум і теореми про середнє» і став науковим співробітником Математичного інституту АН СССР.

Від 1983 року був провідним фахівцем у галузі теорії чисел в СРСР і Росії, і завідувачем відділу теорії чисел в МІАН, професором кафедри теорії чисел МДУ від 1970 року і професором кафедри математичного аналізу МДУ (створена 1962 року) від 1980 року. Його дослідницькі інтереси включали тригонометричні суми і тригонометричні інтеграли, дзета-функцію Рімана, характери Діріхле, скінченні автомати, ефективні алгоритми.

Карацуба був науковим керівником 15 аспірантів, які отримали ступінь кандидата наук; семеро з них стали згодом докторами наук.

Премії і звання

• 1981: ^[ru]
• 1999: Заслужений діяч науки РФ
• 2001: ^[ru] РАН

Ранні праці з інформатики

Студентом МДУ ім. Ломоносова, А. О. Карацуба брав участь у роботі семінару А. М. Колмогорова і розв'язав дві поставлені Колмогоровим задачі, що дало імпульс розвитку теорії автоматів і поклало початок новому напрямку в математиці — теорії швидких алгоритмів.

Автомати

У статті Едварда Мура «Умоглядні експерименти на послідовних машинах» ${\displaystyle (n;m;p)}$-автомат (або машина) ${\displaystyle S}$ визначається як пристрій, що має ${\displaystyle n}$ станів, ${\displaystyle m}$ вхідних символів і ${\displaystyle p}$ вихідних символів. Доводиться дев'ять теорем про структуру ${\displaystyle S}$ та експерименти з ${\displaystyle S}$. Пізніше такі ${\displaystyle S}$-машини почали називати автоматами Мура. Наприкінці статті, у главі «Нові проблеми» Мур формулює задачу про поліпшення оцінок отриманих ним у теоремах 8 і 9:

Теорема 8 (Мур). Нехай задано довільну ${\displaystyle (n;m;p)}$-машину ${\displaystyle S}$, таку, що кожні два її стани відрізняються один від іншого, тоді існує експеримент довжини ${\displaystyle n(n-1)/2}$, який встановлює (знаходить) стан ${\displaystyle S}$ в кінці цього експерименту.

1957 року Карацуба довів дві теореми, які повністю вирішили проблему Мура з поліпшення оцінки довжини експерименту в його Теоремі 8.

Теорема A (Карацуба). Якщо ${\displaystyle S}$ — ${\displaystyle (n;m;p)}$-машина така, що кожні два два її стани відрізняються один від дного, то існує експеримент довжини не більше, ніж ${\displaystyle (n-1)(n-2)/2+1}$, за допомогою якого можна встановити (знайти) стан ${\displaystyle S}$ в кінці експерименту.

Теорема B (Карацуба). Існує ${\displaystyle (n;m;p)}$-машина, кожні два стани якої взаєморізні, така, що довжина найкоротшого експерименту, що встановлює стан машини в кінці експерименту, дорівнює ${\displaystyle (n-1)(n-2)/2+1}$.

Швидкі алгоритми

 — галузь обчислювальної математики, яка вивчає алгоритми обчислення заданої функції з заданою точністю з застосуванням якомога меншої кількості бітових операцій. Вважається, що числа записано в двійковій системі числення, знаки якої 0 і 1 називають бітами. Одна бітова операція визначається як запис знаків 0, 1, плюс, мінус, дужка; додавання, віднімання і множення двох бітів. Перші постановки задач про бітову складність обчислення належать А. М. Колмогорову. Складність алгоритму множення ${\displaystyle n}$ визначається як кількість бітових операцій, достатня для обчислення добутку двох n-значних чисел за допомогою такого алгоритму.

Перемножуючи два n-значних числа звичайним шкільним способом «у стовпчик», ми маємо оцінку зверху ${\displaystyle M(n)=O(n^{2})}$. 1956 року А. М. Колмогоров висловив гіпотезу, що нижня оцінка ${\displaystyle M(n)}$ будь-якого методу множення є також величина порядку ${\displaystyle n^{2}}$, тобто не можна обчислити добуток двох n-значних чисел швидше, ніж за ${\displaystyle n^{2}}$ операцій (так звана «гіпотеза ${\displaystyle n^{2}}$»). На правдоподібність гіпотези ${\displaystyle n^{2}}$ вказував той факт, що за весь час існування математики до того моменту люди виконували множення зі складністю порядку ${\displaystyle O(n^{2})}$, і, якби був швидший метод множення, то його, імовірно, вже було б знайдено.

1960 року на механіко-математичному факультеті МДУ почав працювати під керівництвом А. М. Колмогорова семінар з математичних питань кібернетики, де було сформульовано «гіпотезу ${\displaystyle n^{2}}$» і поставлено кілька задач про оцінку складності інших подібних обчислень. Анатолій Карацуба, сподіваючись отримати нижню оцінку величини ${\displaystyle M(n)}$, знайшов новий метод множення двох n-значних чисел, відомий тепер як множення Карацуби, з оцінкою складності

${\displaystyle M(n)=O(n^{\log _{2}3})=O(n^{1,58496\ldots }),}$

Таким чином він спростував гіпотезу ${\displaystyle n^{2}}$, про що повідомив Колмогорову після чергового засідання семінару. На наступному засіданні семінару цей метод розказав сам Колмогоров, і семінар припинив свою роботу. Першу статтю з описом множення Карацуби підготував Колмогоров, подавши в ній два різних, не пов'язаних між собою результати двох своїх учнів.

Хоча в статті Колмогоров чітко зазначив, що одна теорема (не пов'язана зі швидким множенням) належить Ю. Офману, а інша теорема (з першим в історії швидким множенням) належить А. Карацубі, однак, ця публікація двох авторів надовго збила з пантелику читачів, які вважали, що обидва автори відкрили метод швидкого множення разом, і навіть називали цей метод іменами обох дослідників. Метод Карацуби згодом узагальнено за допомогою парадигми «розділяй та володарюй», іншими важливими прикладами якої є ^[en], двійковий пошук, метод бісекції та інші.

Згодом на основі цієї ідеї А. Карацуби побудовано багато швидких алгоритмів, найвідомішими з яких є його безпосередні узагальнення, такі як метод множення Шьонгаґе — Штрассена, метод матричного множення Штрассена, метод швидкого перетворення Фур'є. Французький математик і філософ ^[en] назвав метод множення Карацуби «одним з найкорисніших результатів математики». Алгоритм Анатолія Карацуби впроваджено практично в усіх сучасних комп'ютерах не лише на програмному, а й на апаратному рівні^[].

Основні дослідження

У своїй статті «Про математичні роботи професора Карацуби», присвяченій 60-річному ювілею А. О. Карацуби, його учні Г. І. Архипов і ^[ru] так описують особливості наукових робіт А. О. Карацуби :

«При викладі праць чудових учених природно виділити якісь характерні і яскраві риси їхньої творчості. Такими визначальними рисами в науковій діяльності професора Карацуби є комбінаторна винахідливість, ґрунтовність і певна завершеність результатів.»

Основні дослідження А. О. Карацуби опубліковані більш ніж у 160 наукових статтях і монографіях.

Тригонометричні суми та тригонометричні інтеграли

p-адичний метод

А. О. Карацуба побудував новий ${\displaystyle p}$-адичний метод у теорії тригонометричних сум. Отримані ним оцінки привели до нових меж нулів ${\displaystyle L}$-рядів Діріхле за модулем, рівним степеню простого числа, до виведення асимптотичної формули для числа варінговського порівняння вигляду

${\displaystyle x_{1}^{n}+\dots +x_{t}^{n}\equiv N{\pmod {p^{k}}},\quad 1\leq x_{s}\leq P,\quad 1\leq s\leq n,\quad P<p^{k},}$

вирішення проблеми розподілу дробових часток многочлена з цілими коефіцієнтами за модулем ${\displaystyle p^{k}}$. А. О. Карацуба перший реалізує в ${\displaystyle p}$-адичній формі «принцип вкладення» Ейлера — Виноградова і будує ${\displaystyle p}$-адичний аналог ${\displaystyle u}$-чисел Виноградова при оцінці числа розв'язків порівняння варінговського типу.

Нехай

${\displaystyle x_{1}^{n}+\dots +x_{t}^{n}\equiv N{\pmod {Q}},\quad 1\leq x_{s}\leq P,\quad 1\leq s\leq t,\quad (1)}$

причому

${\displaystyle P^{r}\leq Q<P^{r+1},\quad 1\leq r\leq {\frac {1}{12}}{\sqrt {n}},\quad Q=p^{k},\quad k\geq 4(r+1)n,}$

де ${\displaystyle p}$ — просте число. А. О. Карацуба довів, що в цьому випадку для будь-якого натурального числа ${\displaystyle n\geq 144}$ існує ${\displaystyle p_{0}=p_{0}(n)}$ таке, що для будь-якого ${\displaystyle p_{0}>p_{0}(n)}$ будь-яке натуральне число ${\displaystyle N}$ подаване у вигляді (1) при ${\displaystyle t\geq 20r+1}$, а при ${\displaystyle t<r}$ існують ${\displaystyle N}$ такі, що порівняння (1) нерозв'язне.

Цей новий підхід, знайдений А. О. Карацубою, привів до нового ${\displaystyle p}$-адичного доведення теореми про середнє І. М. Виноградова, яка грає центральну роль у методі тригонометричних сум Виноградова.

Ще одним елементом ${\displaystyle p}$-адичного методу А. О. Карацуби є перехід від неповних систем рівнянь до повних за рахунок локальної ${\displaystyle p}$-адичної зміни невідомих.

Нехай ${\displaystyle r}$ — довільне натуральне число, ${\displaystyle 1\leq r\leq n}$, і ціле число ${\displaystyle t}$ визначається нерівностями ${\displaystyle m_{t}\leq r\leq m_{t+1}}$. Розглянемо систему рівнянь

${\displaystyle {\begin{cases}x_{1}^{m_{1}}+\dots +x_{k}^{m_{1}}=y_{1}^{m_{1}}+\dots +y_{k}^{m_{1}},\\\qquad \qquad \qquad \qquad \vdots \\x_{1}^{m_{s}}+\dots +x_{k}^{m_{s}}=y_{1}^{m_{s}}+\dots +y_{k}^{m_{s}},\\x_{1}^{n}+\dots +x_{k}^{n}=y_{1}^{n}+\dots +y_{k}^{n}.\end{cases}}}$

${\displaystyle 1\leq x_{1},\dots ,x_{k},y_{1},\dots ,y_{k}\leq P,\quad 1\leq m_{1}<m_{2}<\dots <m_{s}<m_{s+1}=n.}$

А. О. Карацуба довів, що для числа розв'язків ${\displaystyle I_{k}}$ цієї системи рівнянь при ${\displaystyle k\geq 6rn\log n}$ справедлива оцінка

${\displaystyle I_{k}\ll P^{2k-\delta },\quad \delta =m_{1}+\dots +m_{t}+(s-t+1)r.}$

Для неповних систем рівнянь, у яких змінні пробігають числа з малими простими дільниками, А. О. Карацуба застосував мультиплікативний зсув змінних. Це призвело до якісно нової оцінки тригонометричних сум і нової теореми про середнє для таких систем рівнянь.

Примітки

1. Deutsche Nationalbibliothek Record #1024789535 // Gemeinsame Normdatei — 2012—2016.
   d:Track:Q27302d:Track:Q36578
2. Математичний генеалогічний проєкт — 1997.
   d:Track:Q829984
3. Czech National Authority Database
   d:Track:Q13550863
4. С. А. Гриценко, Е. А. Карацуба, М. А. Королëв, И. С. Резвякова, Д. И. Толев, М. Е. Чанга. Научные достижения Анатолия Алексеевича Карацубы. Математика и информатика, 1. // К 75-летию со дня рождения Анатолия Алексеевича Карацубы. — Совр. пробл. матем. — 2012. — Т. 16. — С. 7–30.
5. Кнут Д. Искусство программирования для ЭВМ. — 1-е изд. — М. : Мир (издательство), 1977. — Т. 2. — С. 315.
6. Moore, E. F. (1956). Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, Princeton University Press, Princeton, N.J., (34): 129—153.
7. Карацуба А. А. Сложность вычислений // Тр. МИАН. — 1995. — Т. 211. — С. 186–202.
8. Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145, № 2.
9. Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen. — Elektronische Informationsverarbeitung und Kybernetik, 1975. — Bd. 11.
10. Дональд Кнут. Искусство программирования. — 3-е изд. — 2007. — Т. 2. Получисленные алгоритмы. — P. 832. — ..
11. Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. — 1971. — № 7. — P. 281—292.
12. Jean-Paul Delahaye. Mathematiques et philosophie : ( )[фр.] // Pour la Science. — 2000. — № 277. — P. 100—104.
13. Г. И. Архипов; В. Н. Чубариков. О математических работах профессора А. А. Карацубы // Труды МИАН. — 1997. — Т. 218. — С. 7—19.
14. Карацуба А. А. (1975). Основы аналитической теории чисел. М.: Наука.
15. Архипов Г. И., Карацуба А. А., Чубариков В. Н. (1987). Теория кратных тригонометрических сумм. М.: Наука.
16. Воронин С. М., Карацуба А. А. (1994). Дзета-функция Римана. М.: Физматлит.
17. Karatsuba A. A. (1995). Complex analysis in number theory. London, Tokyo: C.R.C.
18. Карацуба, А. А. (1961). Оценки тригонометрических сумм особого вида и их приложения. Докл. АН СССР (137:3): 513—514.
19. Карацуба, А. А. (1962). Проблема Варинга для сравнения по модулю, равному степени простого числа. Вестн. МГУ (1:4): 28—38.
20. Карацуба, А. А. (1965). Об оценке числа решений некоторых уравнений. Докл. АН СССР (165:1): 31—32.
21. Карацуба, А. А. (1965). Системы сравнений и уравнения Варинговского типа. Докл. АН СССР (1:4): 274—276.

Посилання

• Список наукових праць [ 28 лютого 2018 у Wayback Machine.] на сайті МІАНу
• Данні про наукові інтереса, освіту і професійну діяльність [ 4 березня 2016 у Wayback Machine.]
• , Анатолий Алексеевич Карацуба [ 20 серпня 2021 у Wayback Machine.]